While extensive research efforts have been expended on developing compiler and run-time optimization techniques for programs executing on various types of architectures, little attention has been paid to the scalability and the effectiveness of these techniques when applied to large programs (i.e., on the order of hundreds of procedures). Although many optimization techniques have been shown to be effective for improving run-time performance, the benchmarks typically used in experimental studies have included only small to moderately sized programs. This interest in code improving transformations has also found its way into industry as the majority of compilers produced today employ some type of optimizing transformations. However, with the increasing complexity of applications and the use of modular design, programs are increasing in size and rely heavily on the use of procedures. Indications from industry are that for large application programs, many of today's optimization techniques are too costly to apply or are not effective.
The goal of this project is to develop and experimentally verify a scalable approach to compiler optimizations. In particular, our approach to scalability is to employ techniques that limit the scope of optimizations. That is, instead of simultaneously considering the optimization opportunities across the whole program, as current techniques do, we will use program paths as the scope of the optimization application. Path selection will be based on execution profiles and resource demand profiles, as the most effective optimizations are those that are applied on frequently executed paths as long as the resources needed are available. We will use the demand driven algorithms that we have developed in our approach to analyze program paths and apply optimizations. Using a demand driven approach not only enables us to analyze only what is necessary in order to apply an optimization but also enables us to develop techniques in which the time and space overhead can be controlled and limited.
The focus of the University of Delaware group has been on scalable procedure restructuring for ambitious optimization. Region-based compilation repartitions a program into more desirable compilation units for optimization and ILP scheduling. With region-based compilation, the compiler can control problem size and complexity by controlling region size and contents, and expose interprocedural scheduling and optimization opportunities without interprocedural analysis or large function bodies. Our work has explored a more scalable way to perform region-based compilation, with demand-driven inlining integrated with region formation, experimentally investigating various heuristics for demand-driven inlining performed during region formation, path-spectra-based cloning during region formation, and partial inlining techniques.
Faculty: Dr. Lori Pollock
Graduated Ph.D. Student: Tom Way
Past Graduate Students: Ben Breech, Wei Du
Past Undergraduates: Matt Bridges, Ves Stoyanov
Collaborators: Rajiv Gupta, Mary Lou Soffa, David Whalley
National Science Foundation Experimental Software System grant