Experimental evaluation of various register‐pressure‐reduction heuristics
Experimental evaluation of various register‐pressure‐reduction heuristics
复制标题
各种寄存器压力降低启发式的实验评估
DOI：
10.1002/spe.2297
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Hasan Al
中科院分区：
文献类型：
--
作者：
Ghassan Shobaki;Laith Sakka;Najm Eldeen Abu Rmaileh;Hasan Al
最小化溢出代码的数量仍然是代码生成和优化的一个开放式问题。分配前指令计划对溢出代码的数量的影响。但是，这些启发式技术的性能尚未相对于实际大规模计划的最优性研究涉及计算每个启发式性能和最佳性能之间差距的实验下限。与其他启发式方法相比，基本优先级方案和实验评估了该技术的性能，包括在LLVM Open -Open -ourserce编译器中实现的启发式方法。代码和执行时间。尽管它会产生更多的泄漏，但提议的启发式效果更好 - 订购机器。与最佳量相比，溢出代码要多。这个实验结果量化了直觉的信念，即在所有情况下都不太可能找到启发式的启发式，因此可以使用组合方法来讨论更严格的解决方案。涉及开发这种严格的解决方案。
Minimizing the amount of spill code is still an open problem in code generation and optimization. The amount of spill code depends on both the register allocation algorithm and the pre‐allocation instruction scheduling algorithm that controls the register pressure. In this paper, we focus on the impact of pre‐allocation instruction scheduling on the amount of spill code. Many heuristic techniques have been proposed to do instruction scheduling with the objective of minimizing register pressure and consequently the amount of spill code. However, the performance of these heuristic techniques has not been studied relative to optimality on real large‐scale programs. In this paper, we present an experimental study that evaluates the performance of several pre‐allocation scheduling heuristics. The evaluation involves computing an experimental lower bound on the size of gap between each heuristic's performance and optimal performance. We also propose a simple heuristic technique based on a specific permutation of two basic priority schemes and experimentally evaluate the performance of this technique compared with other heuristics, including the heuristics implemented in the LLVM open‐source Compiler. The evaluation is carried out by running SPEC CPU2006 on real x86‐64 hardware and measuring both the amount of spill code and the execution time. The results of our study show that the proposed heuristic technique gives better overall performance than LLVM's best heuristic on x86‐64, although it produces slightly more spilling. The proposed heuristic has better overall performance, because it achieves a better balance between register pressure and instruction‐level parallelism (ILP). This result shows the importance of ILP in pre‐allocation scheduling even on out‐of‐order machines. Furthermore, the results of the study show that there is a large gap between the performance of any of the studied heuristics and optimal performance; even the best heuristic in the study produces significantly more spill code than the optimal amount. This experimental result quantifies the intuitive belief that it is unlikely to find a heuristic that works well in all cases, thus showing the need for more rigorous solutions using combinatorial approaches. The paper discusses the challenges and complexities that are involved in developing such rigorous solutions. Copyright © 2014 John Wiley & Sons, Ltd.