Linear-Time register allocation for a fixed number of registers and no stack variables

Hans Bodlaender, Jens Gustedt, and Jan Arne Telle

appeared SODA'98

not available

not available

We show that for any fixed} number of registers there is a linear-time algorithm which given a structured (equiv goto}-free) program finds, if possible, an allocation of variables to registers without using intermediate storage. Our algorithm takes rescheduling} into account, {sl i.e.} that straight-line sequences of statements may be reordered to achieve a better register allocation as long as the data flow of the program is not affected. par If we allow registers of different types, e.g.} for integers and floats, we can give only a polynomial time algorithm. In fact we show that if we allow for registers of at least two different types and also for rescheduling then the problem immediately becomes hard for the W-hierarchy which is a strong indication that no O(n^c) algorithm exists with c independent on the number of registers.

Download as [ps.gz]