direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 551-1997

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Linear-Time register allocation for a fixed number of registers and no stack variables
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(nc) algorithm exists with c independent on the number of registers.
Download as [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe