F3M: Fast Focused Function Merging

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

Abstract

From IoT devices to datacenters, code size is important, motivating ongoing research in binary reduction. A key technique is the merging of similar functions to reduce code redundancy. Success, however, depends on accurately identifying functions that can be profitably merged. Attempting to merge all function pairs is prohibitively expensive. Current approaches, therefore, employ summaries to estimate similarity. However these summaries often give little information about how well two programs will merge. To make things worse, they rely on exhaustive search across all summaries; impractical for realworld programs. In this work, we propose a new technique for matching similar functions. We use a hash-based approach that better captures code similarity and, at the same time, significantly reduces the search space by focusing on the most promising candidates. Experimental results show that our similarity metric has a better correlation with merging profitability. This improves the average code size reduction by 6 percentage points, while it reduces the overhead of function merging by 1.8x on average and by as much as 597x for large applications. Faster merging and reduced code size to compile at later stages mean that our approach introduces little to no compile time overhead, while in many cases it makes compilation faster by up to 30%.
Original languageEnglish
Title of host publication2022 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)
EditorsJae W. Lee, Sebastian Hack, Tatiana Shpeisman
PublisherIEEE
Pages242-253
Number of pages12
ISBN (Electronic)978-1-6654-0584-3
ISBN (Print)978-1-6654-0585-0
DOIs
Publication statusPublished - 29 Mar 2022
Event2022 International Symposium on Code Generation and Optimization - Virtual Conference
Duration: 2 Apr 20226 Apr 2022
https://conf.researchr.org/home/cgo-2022

Conference

Conference2022 International Symposium on Code Generation and Optimization
Abbreviated titleCGO 2022
Period2/04/226/04/22
Internet address

Keywords

  • Code-Size Reduction
  • Function Merging
  • LLVM
  • Compiler Optimization

Fingerprint

Dive into the research topics of 'F3M: Fast Focused Function Merging'. Together they form a unique fingerprint.

Cite this