CS Compiler Seminar: Vimarsh Sathia , "Understanding and exploiting optimal function inlining" and Benjamin Darnall, "egg: Fast and extensible equality saturation"

Event Type

Seminar/Symposium

Sponsor

Computer Science

Location

2124 Siebel Center

Virtual

Date

Feb 6, 2023   4:30 pm  

Views

88

Originating Calendar

Computer Science Speakers Calendar

We look forward to seeing you in person on Monday, February 6, at 4:03pm. Join in person at 2124 Siebel Center for Computer Science, 201 N. Goodwin Ave and also online via zoom, https://illinois.zoom.us/j/83675834345?pwd=T1l6aXdzK3lOdnNmVUtjZjFzdHZsdz09

Vimarsh Sathia:

Abstract: Inlining is a core transformation in optimizing compilers. It replaces a function call (call site) with the body of the called function (callee). It helps reduce function call overhead and binary size, and more importantly, enables other optimizations. The problem of inlining has been extensively studied, but it is far from being solved; predicting which inlining decisions are beneficial is nontrivial due to interactions with the rest of the compiler pipeline. Previous work has mainly focused on designing heuristics for better inlining decisions and has not investigated optimal inlining, i.e., exhaustively finding the optimal inlining decisions. Optimal inlining is necessary for identifying and exploiting missed opportunities and evaluating the state of the art. This paper fills this gap through an extensive empirical analysis of optimal inlining using the SPEC2017 benchmark suite. Our novel formulation drastically reduces the inlining search space size (from 2³⁴⁹ down to 2²⁵) and allows us to exhaustively evaluate all inlining choices on 1,135 SPEC2017 files. We show a significant gap between the state-of-the-art strategy in LLVM and optimal inlining when optimizing for binary size, an important, deterministic metric independent of workload (in contrast to performance, another important metric). Inspired by our analysis, we introduce a simple, effective autotuning strategy for inlining that outperforms the state of the art by 7% on average (and up to 28%) on SPEC2017, 15% on the source code of LLVM itself, and 10% on the source code of SQLite. This work highlights the importance of exploring optimal inlining by providing new, actionable insight and an effective autotuning strategy that is of practical utility.

Bio: Vimarsh is a first year PhD student at the UIUC. His research interests lie at the intersection of compilers, parallel programming and machine learning. Prior to this, Vimarsh received his Bachelors degree from IIT Madras, and had worked as a software engineer at Microsoft.

 Benjamin Darnall:

Abstract: An e-graph efficiently represents a congruence relation over many expressions. Although they were originally developed in the late 1970s for use in automated theorem provers, a more recent technique known as equality saturation repurposes e-graphs to implement state-of-the-art, rewrite-driven compiler optimizations and program synthesizers. However, e-graphs remain unspecialized for this newer use case. Equality saturation workloads exhibit distinct characteristics and often require ad-hoc e-graph extensions to incorporate transformations beyond purely syntactic rewrites.

This work contributes two techniques that make e-graphs fast and extensible, specializing them to equality saturation. A new amortized invariant restoration technique called rebuilding takes advantage of equality saturation's distinct workload, providing asymptotic speedups over current techniques in practice. A general mechanism called e-class analyses integrates domain-specific  analyses into the e-graph, reducing the need for ad hoc manipulation. 

We implemented these techniques in a new open-source library called egg. Our case studies on three previously published applications of equality saturation highlight how egg's performance and flexibility enable state-of-the-art results across diverse domains.

Bio: Ben is a first-year PhD student at UIUC. His research interests lie in programming languages and compilers, and his research is in applying program synthesis to DSL design.