Linear-time register allocation for a fixed number of registers
Linear-time register allocation for a fixed number of registers
复制标题
固定数量寄存器的线性时间寄存器分配
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
J. A. Telle
中科院分区：
文献类型：
--
作者：
H. Bodlaender;J. Gustedt;J. A. Telle
我们表明，对于任何j&d数量的寄存器有一个线性时间算法，给定一个结构化的（= goto-fiee）程序发现，如果可能的话，分配变量的寄存器，而不使用中间存储。我们的算法允许重新安排，即直线序列的语句可以重新排序，以实现更好的寄存器分配，只要不违反程序的数据依赖关系。如果我们允许不同类型的寄存器，例如整数和浮点数，我们只能给出一个多项式时间算法。事实上，我们表明，这个问题，然后变得很难W-层次结构，这是一个强有力的迹象表明，没有O（n '）算法存在，它与c独立的寄存器的数量。然而，如果我们不允许重新调度，那么这种非均匀寄存器的情况也可以在线性时间内解决。
We show that for any j&d number of registers there is a linear-time algorithm which given a structured (= goto-fiee) program finds, if possible, an allocation of variables to registers without using intermediate storage. Our algorithm allows for rescheduling, i.e. that straightline sequences of statements may be reordered to achieve a better register allocation as long as the data dependencies of the program are not violated. If we al80 allow for registers of different types, e.g. for integers and floats, we can give only a polynomial time algorithm. In fact we show that the problem then becomes hard for the W-hierarchy which is a strong indication that no O(n’) algorithm exists for it with c independent on the number of registers. However, if we do not allow for rescheduling then this non-uniform register case is also solved in linear time.