Inhalt des Dokuments
Preprint 551-1997
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- Linear-Time register allocation for a fixed number of registers and no stack variables
- Authors
- Publication
- appeared SODA'98
- Classification
-
not available
- Keywords
-
not available
- Abstract
-
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.
- Source
- Download as [ps.gz]
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe