Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14433
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
URI: https://depositonce.tu-berlin.de/handle/11303/15660
http://dx.doi.org/10.14279/depositonce-14433
License: http://rightsstatements.org/vocab/InC/1.0/
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
allocation
rescheduling
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:
Report-551-1997.pdf
Format: Adobe PDF | Size: 15.5 MB
DownloadShow Preview
Thumbnail
Report-551-1997.ps
Format: Postscript | Size: 337.21 kB
Download

Item Export Bar

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