|
|
|
A Framework for Unrestricted Whole-Program Optimization [abstract]
Procedures are the basic units of compilation in conventional
optimization frameworks. This limits code transformations to within a
single procedure's boundaries, which may not present an ideal scope
for optimization. Although aggressive inlining and certain
interprocedural optimization routines can alleviate this problem,
these can be applied only sparingly, the former because it causes
excessive code growth, and the latter because their compile-time
requirements scale poorly with program size.
Motivated by this fact, this paper introduces Procedure Boundary
Elimination (PBE), the first compilation framework that allows
unrestricted whole-program optimization. PBE begins by unifying an
entire application's code into an optimizable program-wide
control-flow graph, called the whole-program intermediate
representation (WIR). By employing an expanded version of
region formation, the compiler can then divide the WIR into
more manageable compilation units, chosen according to optimization
needs. By employing targeted code specialization routines,
PBE can recover the specialization benefits of inlining while keeping
code growth in check. Of course, PBE's central challenge is that
subsequent optimization and analysis routines must be able to operate
on arbitrary WIR subgraphs, without regard to the original procedure
boundaries. This paper introduces the analysis techniques that make
this possible, by extending and generalizing interprocedural analysis
algorithms, and by introducing a novel region encapsulation scheme.
|
