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(nc) algorithm
exists with c independent on the number of registers.
