Linear-time register allocation for a fixed number of registers
Hans L. Bodlaender, Jens Gustedt, Jan Arne Telle · 1998
We show that for any fixed number of registers there is a linear-time algorithm which given a structured (j goto-free) 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 also 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 c ) 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.