Abstract
We show that for any fixed number of registers there is a linear-time algorithm which given a structured (≡goto-free) program finds, if possible, an allocation of variables to registers without using intermediate storage. Our algorithm allows for rescheduling, i.e. that straight-line 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(nc) 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.
Original language | English |
---|---|
Title of host publication | Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1998 |
Editors | Howard J. Karloff |
Place of Publication | Philadelphia, PA, United States |
Publisher | SIAM |
Pages | 574-583 |
Number of pages | 10 |
Publication status | Published - 1 Dec 1998 |
Event | Proceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA, United Kingdom Duration: 25 Jan 1998 → 27 Jan 1998 |
Conference
Conference | Proceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms |
---|---|
Country/Territory | United Kingdom |
City | San Francisco, CA, USA |
Period | 25/01/98 → 27/01/98 |