A Framework for Unrestricted Whole-Program Optimization

In current compilers, the vast majority of optimization routines operates within procedure boundaries. Since individual procedures do not usually present the ideal scope to optimization, significant performance enhancement opportunities are left unrealized. Although aggressive inlining and interprocedural analysis can alleviate this problem, these can be applied only sparingly, so as to avoid excessive code growth and compile-time dilation. Furthermore, the compiler’s ability to exploit optimization opportunities across procedures is constrained by the need to maintain the program’s procedure-based structure.

In order to eliminate these restrictions, this talk proposes a novel compilation framework called Procedure Boundary Elimination (PBE). By generalizing interprocedural analysis algorithms and utilizing appropriate intermediate representations, PBE enables all optimization and analysis routines to operate freely across procedure boundaries. This enables the compiler to reorganize the program into arbitrarily shaped interprocedural compilation units, according to its compile-time and optimization needs. By using the proper encapsulation techniques, PBE allows each unit thus selected to be analyzed and optimized in isolation, thereby eliminating the scalability problems of traditional interprocedural optimization. Finally, the PBE framework leverages both existing and novel targeted code duplication techniques, so as to achieve the specialization benefits of inlining while avoiding unnecessary code growth. Overall, PBE achieves a superset of the benefits of inlining and traditional interprocedural optimization, while limiting their associated costs.