Constructing Efficient Extensible Compilers With Incremental Analysis

124 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2003.Much of the research in compiler design and optimization has traditionally focused on the effectiveness and efficiency of code optimization. However, the subject of efficiency of the entire compilation process itself (as opposed to the complexity of individual analysis or optimization algorithms) remains a highly complex and less investigated topic. In this dissertation, we present a global approach to extensible and efficient compiler design, which aims at also improving the effectiveness and efficiency of analysis and optimization capabilities. Extensibility in complex compiler systems goes well beyond modularity of design and it needs to be considered from the early stages of the design, especially the design of the Intermediate Representation (IR). One of the primary barriers to compiler pass extensibility and modularity is interference between passes caused by transformations that invalidate existing analysis information. In this dissertation we also present a callback system, which is provided to automatically track changes to the compiler's internal representation (IR), allowing full pass reordering and an easy-to-use interface for developing lazy update incremental analysis passes. We present a new algorithm for incremental interprocedural data flow analysis and several parallelization analyses and demonstrate the benefits of our design framework and our prototype compiler system. It is shown that compilation time for multiple data flow analysis algorithms can be cut in half by incrementally updating data flow analysis. Parallelization analyses demonstrate similar speedups. Unlike previous work, our quantitative performance analysis is based on well-known benchmarks, not random graphs. For smaller optimizations, order of magnitude improvements have been demonstrated. Our approach also simplifies design and implementation and hides many of the intricacies of a compiler's internal structures from the developer.U of I OnlyRestricted to the U of I community idenfinitely during batch ingest of legacy ETD