HyFM: function merging for free
HyFM: function merging for free
复制标题
HyFM：免费功能合并
DOI：
10.1145/3461648.3463852
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Rocha R
中科院分区：
文献类型：
--
作者：
Rocha R
函数合并是减少代码大小的重要优化。它将多个函数合并为一个函数，消除了其中的重复代码。现有的最先进技术依赖于众所周知的序列比对算法来识别整个函数中的重复代码。然而，该算法在时间和空间上是指令数量的二次方。即使对于中等规模的基准测试，这也会导致非常高的时间开销和令人望而却步的内存使用量。对于较大的程序，它变得不切实际。过度急切的合并方法会使情况变得更糟。所有选定的函数对将被合并。只有这样，这种方法才会评估合并的潜在好处，并决定是否用合并后的功能替换原始功能。鉴于大多数配对都是无利可图的，因此会浪费大量时间来生成被简单丢弃的合并函数。在本文中，我们提出了 HyFM，这是一种新颖的函数合并技术，可以提供类似水平的代码大小减少，从而显着降低时间开销和内存使用量。与最先进的技术不同，我们的对齐策略在块级别起作用。由于基本块通常比函数短得多，因此即使是二次对齐也是可以接受的。然而，我们还提出了一种线性算法，以更低的成本对齐相同大小的块。我们通过多层盈利能力分析扩展了这一策略，尽早摆脱无利可图的合并尝试。通过对齐各个块对，我们能够在实际生成代码之前分别确定其对齐的盈利能力。 SPEC 2006 和 2017 的实验结果表明，HyFM 需要的内存少了几个数量级，根据所使用的变体，最多使用 48 MB 或 5.6 MB，而最先进的在最坏情况下需要 32 GB。 HyFM 的运行速度也快了 4.5×× 以上，同时仍然实现了相当的代码大小减少。结合由于函数数量减少而导致的后续编译阶段的加速，HyFM 有助于缩短端到端编译时间。
Function merging is an important optimization for reducing code size. It merges multiple functions into a single one, eliminating duplicate code among them. 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. Unlike the state-of-the-art, 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 of the same size 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 separately and 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.
登录
查看更多内容
DOI：
10.5555/3314872.3314892
发表时间：
2019-02
期刊：
2019 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)
影响因子：
--
作者：
Rodrigo C. O. Rocha;Pavlos Petoumenos;Zheng Wang;M. Cole;Hugh Leather
通讯作者：
Rodrigo C. O. Rocha;Pavlos Petoumenos;Zheng Wang;M. Cole;Hugh Leather
ThinLTO：可扩展和增量 LTO
DOI：
--
发表时间：
2017
期刊：
IEEE/ACM International Symposium on Code Generation and Optimization
影响因子：
--
作者：
Teresa L. Johnson;M. Amini;D. Li
通讯作者：
D. Li
超节点SLP：包含运算符及其逆元素的代码序列的优化矢量化
DOI：
--
发表时间：
2019
期刊：
IEEE/ACM International Symposium on Code Generation and Optimization
影响因子：
--
作者：
Vasileios Porpodas;Rodrigo C. O. Rocha;E. Brevnov;L. F. Góes;T. Mattson
通讯作者：
T. Mattson
GCC 中的代码分解
DOI：
--
发表时间：
2004
期刊：
影响因子：
--
作者：
Gábor Lóki;Ákos Kiss;J. Jász;Árpád Beszédes
通讯作者：
Árpád Beszédes
前瞻 SLP：存在交换运算时的自动矢量化
DOI：
--
发表时间：
2018
期刊：
IEEE/ACM International Symposium on Code Generation and Optimization
影响因子：
--
作者：
Vasileios Porpodas;Rodrigo C. O. Rocha;L. F. Góes
通讯作者：
L. F. Góes