Effective function merging in the SSA form
Effective function merging in the SSA form
复制标题
SSA形式的有效功能合并
DOI：
10.1145/3385412.3386030
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Rocha R
中科院分区：
文献类型：
--
作者：
Rocha R
函数合并是减少代码大小的重要优化。该技术通过将函数合并到单个函数中来消除函数之间的冗余代码。虽然最初仅限于相同或极其相似的函数，但最新的方法可以识别任意函数对中的所有合并机会。然而，这种方法有一个严重的局限性，使其无法充分发挥其潜力。由于它无法处理 phi 节点，因此最先进的技术会在应用其核心算法之前应用寄存器降级来消除它们。虽然表面上是一个较小的解决方法，但这会产生三重负面影响：通过人为地延长要对齐的指令序列，它阻碍了可合并指令的识别；它阻碍了大量功能的合并以盈利；它增加了编译时间和内存使用方面的编译开销。我们提出了 SalSSA，这是一种完全支持 SSA 形式的新颖方法，消除了寄存器降级的任何需要。通过这样做，我们显着增加了有利可图的合并功能的数量。我们在 LLVM 中实现 SalSSA 并将其应用到 SPEC 2006 和 2017 套件中。实验结果表明，我们的方法使编译代码的最终大小平均减少 7.9% 到 9.7%。与最先进的技术相比，这意味着代码大小减少了大约 2 倍。此外，由于对齐了较短的指令序列并减少了浪费的合并操作的数量，我们的新方法的平均编译时间开销仅为 5%，比最先进的技术低 3 倍，同时内存使用量也减少了 2 倍以上。
Function merging is an important optimization for reducing code size. This technique eliminates redundant code across functions by merging them into a single function. While initially limited to identical or trivially similar functions, the most recent approach can identify all merging opportunities in arbitrary pairs of functions. However, this approach has a serious limitation which prevents it from reaching its full potential. Because it cannot handle phi-nodes, the state-of-the-art applies register demotion to eliminate them before applying its core algorithm. While a superficially minor workaround, this has a three-fold negative effect: by artificially lengthening the instruction sequences to be aligned, it hinders the identification of mergeable instruction; it prevents a vast number of functions from being profitably merged; it increases compilation overheads, both in terms of compile-time and memory usage.We present SalSSA, a novel approach that fully supports the SSA form, removing any need for register demotion. By doing so, we notably increase the number of profitably merged functions. We implement SalSSA in LLVM and apply it to the SPEC 2006 and 2017 suites. Experimental results show that our approach delivers on average, 7.9% to 9.7% reduction on the final size of the compiled code. This translates to around 2x more code size reduction over the state-of-the-art. Moreover, as a result of aligning shorter sequences of instructions and reducing the number of wasteful merge operations, our new approach incurs an average compile-time overhead of only 5%, 3x less than the state-of-the-art, while also reducing memory usage by over 2x.
登录
查看更多内容
寄存器分配后SSA消除
DOI：
--
发表时间：
2009
期刊：
International Conference on Compiler Construction
影响因子：
--
作者：
Fernando Magno Quintão Pereira;J. Palsberg
通讯作者：
J. Palsberg
“以 SSA 形式进行有效功能合并”的工件
DOI：
--
发表时间：
2020
期刊：
影响因子：
--
作者：
Rodrigo C. O. Rocha;Pavlos Petoumenos;Z. Wang;M. Cole;Hugh Leather
通讯作者：
Hugh Leather
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
代码压缩*
DOI：
--
发表时间：
2006
期刊：
影响因子：
--
作者：
Fang Yu
通讯作者：
Fang Yu
超节点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