{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/80829"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/80829","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Constructing Efficient Extensible Compilers With Incremental Analysis","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Carroll, Steven Marc"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical Engineering","degree_department":null,"school":null,"contributors":["Polychronopoulos, Constantine D."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-09-25T20:08:22Z","date_published":"2015-09-25T20:08:22Z","updated_at":"2026-07-22T22:26:15Z","subjects":["Computer Science"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(MiAaPQ)AAI3101811"],"render_values":[{"text":"(MiAaPQ)AAI3101811","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/80829","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Polychronopoulos, Constantine D."]},{"key":"dc:creator","label":"Author","values":["Carroll, Steven Marc"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-09-25T20:08:22Z","10000-01-01","2003"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/80829","(MiAaPQ)AAI3101811"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2015-09-25T20:08:22Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 3101811.pdf: 6356374 bytes, checksum: 71840404a37760d831d2055c8433e668 (MD5) Previous issue date: 2003","Embargo set by: Seth Robbins for item 82111 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","124 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2003."]},{"key":"dc:title","label":"Title","values":["Constructing Efficient Extensible Compilers With Incremental Analysis"]}]}],"canonical_facts":{"dc:contributor":["Polychronopoulos, Constantine D."],"dc:creator":["Carroll, Steven Marc"],"dc:date":["2015-09-25T20:08:22Z","10000-01-01","2003"],"dc:description":["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.","Made available in DSpace on 2015-09-25T20:08:22Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 3101811.pdf: 6356374 bytes, checksum: 71840404a37760d831d2055c8433e668 (MD5) Previous issue date: 2003","Embargo set by: Seth Robbins for item 82111 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","124 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2003."],"dc:identifier":["http://hdl.handle.net/2142/80829","(MiAaPQ)AAI3101811"],"dc:language":["eng"],"dc:subject":["Computer Science"],"dc:title":["Constructing Efficient Extensible Compilers With Incremental Analysis"],"dc:type":["text"],"thesis:degree_discipline":["Electrical Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:15Z"}