A New Approach to Optimal Function Inlining for Code Size Minimization via E-graphs

Minimizing code size is a central problem in compiler optimization, especially in the context of embedded systems and mobile applications. One of the classical optimizations that has recently been adopted to reduce the output code size is function inlining, i.e. repeatedly replacing a function call site by the body of the called function. At first glance, the fact that inlining can help reduce code size is counter-intuitive. However, it enables two types of subsequent optimizations which can affect the code size significantly: (i) the intra-procedural optimizations performed within each function, which make use of the additional context provided by inlining, and (ii) the elimination of dead functions. Many existing heuristics, such as those used by LLVM, focus on a local size analysis based on a few call sites. Thus, they miss the global opportunities to remove dead functions. On the other hand, the current state-of-the-art approach of auto-tuning by Theodoridis et al. [ASPLOS 2022] focuses on global code size but inspects each call site independently in order to avoid a combinatorial explosion. However, inlining decisions are not independent in practice. It is possible that two inlining choices each increase code size on their own, but applying both of them together reduces the size.

In this work, we show that the problem of optimal inlining for code size minimization is NP-hard. We then present a completely different approach to this problem. Our algorithm is based on equality graphs (e-graphs), which are a standard tool in automated theorem proving and have recently been adopted by the compiler optimization community as a key ingredient in equality saturation. We show that optimal function inlining can be reduced to e-graph extraction. Although e-graph extraction is also NP-hard, there are efficient solvers that can handle sparse instances of this problem [OOPSLA 2024]. We build upon these solvers and add further inlining-specific heuristics to design an algorithm for code size reduction.

Finally, we present experimental results on the standard SPEC benchmarks. Compared with LLVM, our approach reduces the code size to 95.34%. This is competitive with the state-of-the-art auto-tuning method of [ASPLOS 2022], which achieves 95.24%. In terms of running time, our approach is 20x faster than auto-tuning. More importantly, due to the two methods having orthogonal strengths, applying both of them leads to a further significant improvement, reducing the code size to 93.94% of LLVM's output.