Linear-time register allocation for a fixed number of registers

Hans Bodlaender*, Jens Gustedt, Jan Arne Telle

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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 languageEnglish
Title of host publicationProceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1998
EditorsHoward J. Karloff
Place of PublicationPhiladelphia, PA, United States
PublisherSIAM
Pages574-583
Number of pages10
Publication statusPublished - 1 Dec 1998
EventProceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA, United Kingdom
Duration: 25 Jan 199827 Jan 1998

Conference

ConferenceProceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited Kingdom
CitySan Francisco, CA, USA
Period25/01/9827/01/98

Fingerprint

Dive into the research topics of 'Linear-time register allocation for a fixed number of registers'. Together they form a unique fingerprint.

Cite this