Accession Number:

AD1006367

Title:

Eliminating Scope and Selection Restrictions in Compiler Optimization

Descriptive Note:

Technical Report

Corporate Author:

Princeton University Princeton United States

Personal Author(s):

Report Date:

2006-09-01

Pagination or Media Count:

109.0

Abstract:

To meet the challenges presented by the performance requirements of modern architectures, compilers have been augmented with a rich set of aggressive optimizing transformations. However, the overall compilation model within which these transformations operate has remained fundamentally unchanged. This model imposes restrictions on these transformations application, limiting their effectiveness. First, procedure-based compilation limits code transformations within a single procedures boundaries, which may not present an ideal optimization scope. Although aggressive inlining and interprocedural optimization can alleviate this problem, code growth and compile time considerations limit their applicability. Second, by applying a uniform optimization process on all codes, compilers cannot meet the particular optimization needs of each code segment. Although the optimization process is tailored by heuristics that attempt to a priori judge the effect of each transformation on final code quality, the unpredictability of modern optimization routines and the complexity of the target architectures severely limit the accuracy of such predictions. This thesis focuses on removing these restrictions through two novel compilation framework modifications, Procedure Boundary Elimination PBE and Optimization-Space ExplorationOSE.PBE forms compilation units independent of the original procedures. This is achieved by unifying the entire application into a whole-program control-flow graph, allowing the compiler to repartition this graph into free-form regions, making analysis and optimization routines able to operate on these generalized compilation units. Targeted code duplication techniques can then recover the performance benefits of inlining while limiting code growth.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE