The complexity of register allocation
The complexity of register allocation
复制标题
寄存器分配的复杂性
DOI：
10.1016/j.dam.2013.03.015
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Philipp Krause
中科院分区：
文献类型：
--
作者：
Philipp Krause
在编译器中，寄存器分配是针对典型目标（如代码大小、代码速度或能源效率）进行优化的最重要阶段之一。图论中的最优寄存器分配问题是在给定程序的冲突图中找到一个权值最大的r-可着色诱导子图的问题。参数r是寄存器的个数。大型程序类是结构化的，即它们的控制流图具有有界的树宽度(Thorup （1998)[17]， Gustedt等人（2002）[8]和Burgstaller等人（2004）[3]）。确定结构化程序的冲突图是否可色的决策问题已知是固定参数可处理的（Bodlaender et al.(1998)[1]）。结构化程序的最佳寄存器分配已知在XP中（Krause(2013)[13]）。我们通过证明r参数化的最优寄存器分配是W [SAT]-hard来补充这些结果。这甚至适用于只使用if/else和while作为控制结构的程序；这些程序形式是结构化程序的子类。
In compilers, register allocation is one of the most important stages with respect to optimization for typical goals, such as code size, code speed, or energy efficiency. Graph theoretically, optimal register allocation is the problem of finding a maximum weight r-colorable induced subgraph in the conflict graph of a given program. The parameter r is the number of registers. Large classes of programs are structured, ie their control-flow graphs have bounded tree-width (Thorup (1998)[17], Gustedt et al.(2002)[8] and Burgstaller et al.(2004)[3]). The decision problem of deciding if a conflict graph of a structured program is r-colorable is known to be fixed-parameter tractable (Bodlaender et al.(1998)[1]). Optimal register allocation for structured programs is known to be in XP (Krause (2013)[13]). We complement these results by showing that optimal register allocation parametrized by r is W [SAT]-hard. This even holds for programs using only if/else and while as control structures; these programs form are subclass of the structured programs.
登录
查看更多内容
固定数量寄存器的线性时间寄存器分配
DOI：
--
发表时间：
1998
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
H. Bodlaender;J. Gustedt;J. A. Telle
通讯作者：
J. A. Telle
DOI：
10.1137/0601025
发表时间：
1980-06
期刊：
SIAM J. Algebraic Discret. Methods
影响因子：
--
作者：
M. Garey;David S. Johnson;G. Miller;C. Papadimitriou
通讯作者：
M. Garey;David S. Johnson;G. Miller;C. Papadimitriou
论Ada程序的树宽
DOI：
--
发表时间：
2004
期刊：
International Conference on Reliable Software Technologies
影响因子：
--
作者：
Bernd Burgstaller;Johann Blieberger;Bernhard Scholz
通讯作者：
Bernhard Scholz
计算机语言
DOI：
--
发表时间：
1985
期刊：
Australian Computer Journal
影响因子：
--
作者：
C. L. Hamblin
通讯作者：
C. L. Hamblin
H. Hadwiger 和 K. Wagner 对最终地衣的分类
DOI：
--
发表时间：
1967
期刊：
影响因子：
--
作者：
R. Halin
通讯作者：
R. Halin