Edinburgh Research Explorer

Function Merging by Sequence Alignment

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related Edinburgh Organisations

Open Access permissions

Open

Documents

Original languageEnglish
Title of host publicationProceedings of the 2019 International Symposium on Code Generation and Optimization
Place of PublicationWashington DC, USA
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages15
StateAccepted/In press - 29 Oct 2018
Event2019 International Symposium on Code Generation and Optimization - Marriott Marquis Washington DC Hotel, Washington, United States
Duration: 16 Feb 201920 Feb 2019
http://cgo.org/cgo2019/

Conference

Conference2019 International Symposium on Code Generation and Optimization
Abbreviated titleCGO 2019
CountryUnited States
CityWashington
Period16/02/1920/02/19
Internet address

Abstract

Resource-constrained devices for embedded systems are becoming increasingly important. In such systems, memory is highly restrictive, making code size in most cases even more important than performance. Compared to more traditional platforms, memory is a larger part of the cost and code occupies much of it. Despite that, compilers make little effort to reduce code size. One key technique attempts to merge the bodies of similar functions. However, production compilers only apply this optimization to identical functions, while research compilers improve on that by merging the few functions with identical control-flow graphs and signatures. Overall, existing solutions are insufficient and we end up having to either increase cost by adding more memory or remove functionality from programs.
We introduce a novel technique that can merge arbitrary functions through sequence alignment, a bioinformatics algorithm for identifying regions of similarity between sequences. We combine this technique with an intelligent exploration mechanism to direct the search towards the most promising function pairs. Our approach is more than 2.4x better than the state-of-the-art, reducing code size by up to 25%, with an overall average of 6%, while introducing an average compilation-time overhead of only 15%. When aided by profiling information, this optimization can be deployed without any significant impact on the performance of the generated code.

    Research areas

  • Compilers, Software engineering, Function merging, Compiler optimization, Code size

Event

2019 International Symposium on Code Generation and Optimization

16/02/1920/02/19

Washington, United States

Event: Conference

Download statistics

No data available

ID: 77871596