Optimal and Heuristic Global Code Motion for Minimal Spilling
Optimal and Heuristic Global Code Motion for Minimal Spilling
复制标题
最佳和启发式全局代码运动可最大限度地减少溢出
DOI：
10.1007/978-3-642-37051-9_2
复制
发表时间：
2013
影响因子：
5.1
通讯作者：
A. Krall
中科院分区：
文献类型：
--
作者：
Gergö Barany;A. Krall
寄存器分配和说明计划的相互作用是一个充分研究的问题：在基本块中安排说明的某些方法减少了实时范围的重叠，从而导致插入较低的溢出代码。但是，以前几乎没有关于将此问题扩展到全球代码运动的研究，即，块之间的指令运动。我们提出了一种将全局代码运动建模为优化问题的算法，目的是最大程度地减少实时范围之间的重叠，以最大程度地减少溢出代码。
我们的方法分析了该程序，以确定实时范围重叠，以确保所有可能的说明放置在基本块中以及块内所有指令的顺序。使用此信息，我们制定了一个优化问题，以确定代码动作和部分本地时间表，以最大程度地减少实时范围重叠的总成本。我们使用可行的整数线性编程和简单的贪婪启发式方法来评估此优化问题的解决方案。
我们得出的结论是，全球代码运动的唯一目标是避免溢出很少会导致性能提高，因为代码过于保守。另一方面，与启发式调度程序相比，纯粹的本地最佳指令计划可最小的溢出计划可有效提高性能。
The interaction of register allocation and instruction scheduling is a well-studied problem: Certain ways of arranging instructions within basic blocks reduce overlaps of live ranges, leading to the insertion of less costly spill code. However, there is little previous research on the extension of this problem to global code motion, i.e., the motion of instructions between blocks. We present an algorithm that models global code motion as an optimization problem with the goal of minimizing overlaps between live ranges in order to minimize spill code.
Our approach analyzes the program to identify the live range overlaps for all possible placements of instructions in basic blocks and all orderings of instructions within blocks. Using this information, we formulate an optimization problem to determine code motions and partial local schedules that minimize the overall cost of live range overlaps. We evaluate solutions of this optimization problem using integer linear programming, where feasible, and a simple greedy heuristic.
We conclude that global code motion with the sole goal of avoiding spills rarely leads to performance improvements because code is placed too conservatively. On the other hand, purely local optimal instruction scheduling for minimal spilling is effective at improving performance when compared to a heuristic scheduler for minimal register use.