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.
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 language | English |
|---|---|
| Title of host publication | International Conference on Languages Compilers, Tools and Theory of Embedded Systems (LCTES 2021) |
| DOIs | |
| Publication status | Accepted/In press - 9 Apr 2021 |
| Event | International Conference on Languages Compilers, Tools and Theory of Embedded Systems - Duration: 20 Jun 2021 → 25 Jun 2021 |
Conference
| Conference | International Conference on Languages Compilers, Tools and Theory of Embedded Systems |
|---|---|
| Abbreviated title | LCTES 2021 |
| Period | 20/06/21 → 25/06/21 |