188宝金博页面版

Region Formation Analysis withDemand-driven Inlining for Region-based OptimizationTom Way, Ben Breech and Lori PollockDepartment ofComputer and Information SciencesUniversity ofDelaware, Newark, DE 19716way,breech,pollock @cis.udel.eduAbstractRegion-based compilation repartitions a program intomore desirable compilation units for optimization andscheduling, particularly beneficial for ILP architectures.With region-based compilation, the compiler can controlproblem size and complexity by controlling region size andcontents, expose interprocedural scheduling and optimiza-tion opportunities withoutinterproceduralanalysis orlargefunction bodies, and create compilation units for programanalysis that more accurately reflect the dynamic behav-ior of the program. This paper presents a region forma-tion algorithm that eliminates the high compile-time mem-ory costs due to an aggressive inlining prepass. Individualsubregions are inlined in a demand-driven way during in-terprocedural region formation. Our experimental resultson a subset ofthe SPEC benchmarks demonstrate a signifi-cant reduction in compile-time memory requirements withcomparable runtime performance.1. IntroductionFor abstraction, software maintenance ease, and a num-berofotherreasons, large applications are written in a mod-ular fashion. Compiler writers have addressed the prob-lem of modularity by developing techniques that rangefrom aggressive procedure inlining to procedure cloningto fast, flow and context insensitive interprocedural anal-ysis to more sophisticated flow and context sensitive in-terprocedural analysis. While evidence shows that espe-cially with many small functions, whole program analysiscan significantly improve the precision of program anal-ysis and increase opportunities for optimization, most ofthese methods suffer from poor scalability in either or bothcompilation-time memory and time requirements for largeprograms. All have been applied to the original programpartitioned by the programmer into functions created withabstraction and good program design in mind.A very different approach that has been developed forILP compilers is region-based compilation [14, 15, 19], inwhich the compiler repartitions the program into a new,more desirable, set of compilation units prior to programanalysis and optimization. Hank, Hwu, and Rau [15] showsolid experimental evidence of the potential impact of giv-ing the compiler control of the compilation unit size andcontents. The compilercan successfully repartitionthe codeinto compilation units that will enable more aggressive op-timizations to be performed. The use of profile informa-tion for region formation allows the compiler to create re-gions that more accurately reflect the dynamic behavior ofthe program. Hank, Hwu, and Rau [15] found that thesize of each of the resulting compilation units is typicallysmaller than functions, which has the effect of reducingthe impact of the quadratic algorithmic complexity of theapplied optimizing transformations. Aggressive optimiza-tions can be performed in the presence of large functionbodies. In particular, by creating new regions, the com-piler has more freedom to move code between proceduresthan approaches based on interprocedural analysis. Hank’simplementation [14] included classical optimizations likeglobal common subexpression elimination, dead code re-moval, and code motion, but particularly found register al-location and scheduling to be enhanced by this approach.Region-based compilation as proposed by Hank et al.and as implemented in the IMPACT [5] compiler is ac-complished by performing an aggressive inlining pass, fol-lowed by a partitioning phase that forms new regions basedon a heuristic, bundles regions to look like functions, andpasses these compiler-created functions to the unchangedoptimization phases. While this approach can achieve somedegree ofscalability during program analysis and optimiza-tion by allowing the compiler to control the size ofregions,the region formation phase itselfremains quite unscalable.The region formation phase works on a form of thewhole program which has been aggressively inlined, in or-der to be able to form regions that cross function bound-