Constructing Efficient Extensible Compilers With Incremental Analysis
Carroll, Steven Marc
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/80829
Description
Title
Constructing Efficient Extensible Compilers With Incremental Analysis
Author(s)
Carroll, Steven Marc
Issue Date
2003
Doctoral Committee Chair(s)
Polychronopoulos, Constantine D.
Department of Study
Electrical Engineering
Discipline
Electrical Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
Abstract
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
