{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/113862"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/113862","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Optimizing whole programs for code size","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-04-06 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-04-06 without embargo terms","abstract_has_math":false,"creators":["Bartell, Sean"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Adve, Vikram S","Marinov, Darko","Misailovic, Sasa","Regehr, John"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-04-29T21:34:32Z","date_published":"2022-04-29T21:34:32Z","updated_at":"2026-07-22T22:24:53Z","subjects":["Computer science"],"languages":["en","eng"],"rights":["Copyright 2021 Sean Bartell"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/113862","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Adve, Vikram S","Marinov, Darko","Misailovic, Sasa","Regehr, John"]},{"key":"dc:creator","label":"Author","values":["Bartell, Sean"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-04-29T21:34:32Z","2021-12","2021-12-01"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"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":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2021 Sean Bartell"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/113862"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-04-06 without embargo terms","The student, Sean Bartell, accepted the attached license on 2021-12-01 at 13:15.","The student, Sean Bartell, submitted this Dissertation for approval on 2021-12-01 at 13:29.","This Dissertation was approved for publication on 2021-12-01 at 15:37.","DSpace SAF Submission Ingestion Package generated from Vireo submission #17272 on 2022-04-06 at 17:10:04","Made available in DSpace on 2022-04-29T21:34:32Z (GMT). No. of bitstreams: 4 BARTELL-DISSERTATION-2021.pdf: 1077538 bytes, checksum: 817d8bbb77473d0782a6e202758ce182 (MD5) smb-dissertation.tar.xz: 7746204 bytes, checksum: 629d574e163c138eb48746bedc339a27 (MD5) LICENSE.txt: 4209 bytes, checksum: f9899214e341d03e46251d563aa9694a (MD5) PROQUEST_LICENSE.txt: 4555 bytes, checksum: 50f703e8f8ac825d4fbd7561af4bdd86 (MD5) Previous issue date: 2021-12-01","Reducing code size has benefits at every scale. It can help fit embedded software into strictly limited storage space, reduce mobile app download time, and improve the cache usage of supercomputer software. There are many optimizations available that reduce code size, but research has often neglected this goal in favor of speed, and some recently developed compiler techniques have not yet been applied for size reduction. My work shows that newly practical compiler techniques can be used to develop novel code size optimizations. These optimizations complement each other, and other existing methods, in minimizing code size. I introduce two new optimizations, Guided Linking and Semantic Outlining, and also present a comparison framework for code size reduction methods that explains how and when my new optimizations work well with other, existing optimizations. Guided Linking builds on recent work that optimizes multiple programs and shared libraries together. It links an arbitrary set of programs and libraries into a single module. The module can then be optimized with arbitrary existing link-time optimizations, without changes to the optimization code, allowing them to work across program and library boundaries; for example, a library function can be inlined into a plugin module. I also demonstrate that deduplicating functions in the merged module can significantly reduce code size in some cases. Guided Linking ensures that all necessary dynamic linker behavior, such as plugin loading, still works correctly; it relies on developer-provided constraints to indicate which behavior must be preserved. Guided Linking can achieve a 13% to 57% size reduction in some scenarios, and can speed up the Python interpreter by 9%. Semantic Outlining relies on the use of automated theorem provers to check semantic equivalence of pieces of code, which has only recently become feasible to perform at scale. It extends outlining, an established technique for deduplicating structurally equivalent pieces of code, to work on code pieces that are semantically equivalent even if their structure is completely different. My comparison framework covers a large number of different code size reduction methods from the literature, in addition to my new methods. It describes several different aspects by which each method can be compared; in particular, there are multiple types of redundancy in program code that can be exploited to reduce code size, and methods that exploit different types of redundancy are likely to work well in combination with each other. This explains why Guided Linking and Semantic Outlining can be effective when used together, along with some kinds of existing optimizations."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Optimizing whole programs for code size"]}]}],"canonical_facts":{"dc:contributor":["Adve, Vikram S","Marinov, Darko","Misailovic, Sasa","Regehr, John"],"dc:creator":["Bartell, Sean"],"dc:date":["2022-04-29T21:34:32Z","2021-12","2021-12-01"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-04-06 without embargo terms","The student, Sean Bartell, accepted the attached license on 2021-12-01 at 13:15.","The student, Sean Bartell, submitted this Dissertation for approval on 2021-12-01 at 13:29.","This Dissertation was approved for publication on 2021-12-01 at 15:37.","DSpace SAF Submission Ingestion Package generated from Vireo submission #17272 on 2022-04-06 at 17:10:04","Made available in DSpace on 2022-04-29T21:34:32Z (GMT). No. of bitstreams: 4 BARTELL-DISSERTATION-2021.pdf: 1077538 bytes, checksum: 817d8bbb77473d0782a6e202758ce182 (MD5) smb-dissertation.tar.xz: 7746204 bytes, checksum: 629d574e163c138eb48746bedc339a27 (MD5) LICENSE.txt: 4209 bytes, checksum: f9899214e341d03e46251d563aa9694a (MD5) PROQUEST_LICENSE.txt: 4555 bytes, checksum: 50f703e8f8ac825d4fbd7561af4bdd86 (MD5) Previous issue date: 2021-12-01","Reducing code size has benefits at every scale. It can help fit embedded software into strictly limited storage space, reduce mobile app download time, and improve the cache usage of supercomputer software. There are many optimizations available that reduce code size, but research has often neglected this goal in favor of speed, and some recently developed compiler techniques have not yet been applied for size reduction. My work shows that newly practical compiler techniques can be used to develop novel code size optimizations. These optimizations complement each other, and other existing methods, in minimizing code size. I introduce two new optimizations, Guided Linking and Semantic Outlining, and also present a comparison framework for code size reduction methods that explains how and when my new optimizations work well with other, existing optimizations. Guided Linking builds on recent work that optimizes multiple programs and shared libraries together. It links an arbitrary set of programs and libraries into a single module. The module can then be optimized with arbitrary existing link-time optimizations, without changes to the optimization code, allowing them to work across program and library boundaries; for example, a library function can be inlined into a plugin module. I also demonstrate that deduplicating functions in the merged module can significantly reduce code size in some cases. Guided Linking ensures that all necessary dynamic linker behavior, such as plugin loading, still works correctly; it relies on developer-provided constraints to indicate which behavior must be preserved. Guided Linking can achieve a 13% to 57% size reduction in some scenarios, and can speed up the Python interpreter by 9%. Semantic Outlining relies on the use of automated theorem provers to check semantic equivalence of pieces of code, which has only recently become feasible to perform at scale. It extends outlining, an established technique for deduplicating structurally equivalent pieces of code, to work on code pieces that are semantically equivalent even if their structure is completely different. My comparison framework covers a large number of different code size reduction methods from the literature, in addition to my new methods. It describes several different aspects by which each method can be compared; in particular, there are multiple types of redundancy in program code that can be exploited to reduce code size, and methods that exploit different types of redundancy are likely to work well in combination with each other. This explains why Guided Linking and Semantic Outlining can be effective when used together, along with some kinds of existing optimizations."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/113862"],"dc:language":["en","eng"],"dc:rights":["Copyright 2021 Sean Bartell"],"dc:subject":["Computer science"],"dc:title":["Optimizing whole programs for code size"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:53Z"}