A Framework for Unrestricted Whole-Program Optimization [abstract] (ACM DL, PDF)
Spyridon Triantafyllis, Matthew J. Bridges, Easwaran Raman, Guilherme Ottoni, and David I. August
Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), June 2006.
Procedures have long been the basic units of compilation in
conventional optimization frameworks. However, procedures are
typically formed to serve software engineering rather than
optimization goals, arbitrarily constraining code transformations.
Techniques, such as aggressive inlining and interprocedural
optimization, have been developed to alleviate this problem, but, due
to code growth and compile time issues, these can be applied only
sparingly.
This paper introduces the Procedure Boundary Elimination (PBE)
compilation framework, which allows unrestricted whole-program
optimization. PBE allows all intra-procedural optimizations and
analyses to operate on arbitrary subgraphs of the program, regardless
of the original procedure boundaries and without resorting to
inlining. In order to control compilation time, PBE also introduces
novel extensions of region formation and encapsulation.
PBE enables targeted code specialization, which recovers the
specialization benefits of inlining while keeping code growth in
check. This paper shows that PBE attains better performance than
inlining with half the code growth.