HyFM: Function Merging for Free

Rodrigo C O Rocha, Pavlos Petoumenos, Zheng Wang, Murray Cole, Kim Hazelwood, Hugh Leather

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

140 Downloads (Pure)

Abstract

Function merging is an important optimization for reducing code size. The existing state-of-the-art relies on a well-known sequence alignment algorithm to identify duplicate code across whole functions. However, this algorithm is quadratic in time and space on the number of instructions. This leads to very high time overheads and prohibitive levels of memory usage even for medium-sized benchmarks. For larger programs, it becomes impractical. This is made worse by an overly eager merging approach. All selected pairs of functions will be merged. Only then will
this approach estimate the potential benefit from merging and decide whether to replace the original functions with the merged one. Given that most pairs are unprofitable, a significant amount of time is wasted producing merged functions that are simply thrown away. In this paper, we propose HyFM, a novel function merging technique that delivers similar levels of code size reduction for significantly lower time overhead and memory usage. Our alignment strategy works at the block level. Since basic blocks are usually much shorter than functions, even a quadratic
alignment is acceptable. However, we also propose a linear algorithm for aligning blocks at a much lower cost. We extend this strategy with a multi-tier profitability analysis that bails out early from unprofitable merging attempts. By aligning individual pairs of blocks, we are able to decide their
alignment’s profitability before actually generating code.
Experimental results on SPEC 2006 and 2017 show that
HyFM needs orders of magnitude less memory, using up
to 48 MB or 5.6 MB, depending on the variant used, while the state-of-the-art requires 32 GB in the worst case. HyFM
also runs over 4.5× faster, while still achieving comparable
code size reduction. Combined with the speedup of later
compilation stages due to the reduced number of functions,
HyFM contributes to a reduced end-to-end compilation time.
Original languageEnglish
Title of host publicationInternational Conference on Languages Compilers, Tools and Theory of Embedded Systems (LCTES 2021)
DOIs
Publication statusAccepted/In press - 9 Apr 2021
EventInternational Conference on Languages Compilers, Tools and Theory of Embedded Systems -
Duration: 20 Jun 202125 Jun 2021

Conference

ConferenceInternational Conference on Languages Compilers, Tools and Theory of Embedded Systems
Abbreviated titleLCTES 2021
Period20/06/2125/06/21

Fingerprint

Dive into the research topics of 'HyFM: Function Merging for Free'. Together they form a unique fingerprint.

Cite this