Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Linear-Time register allocation for a fixed number of registers and no stack variables
Author(s): Bodlaender, Hans
Gustedt, Jens
Telle, Jan Arne
Type: Research Paper
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.
Subject(s): registers
linear-time register
linear-time algorithm
Issue Date: 1997
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 1997, 551
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 15.5 MB
DownloadShow Preview
Format: Postscript | Size: 337.21 kB

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.