On Local Register Allocation

Martin Farach-Colton; Vincenzo Liberatore

doi:10.1006/jagm.2000.1095

On Local Register Allocation

Martin Farach-Colton, Vincenzo Liberatore

Research output: Contribution to journal › Article › peer-review

Abstract

In this paper, we consider the problem of local register allocation (LRA): given a sequence of instructions (basic block) and a number of general purpose registers, find the schedule of variables in registers that minimizes the total traffic between CPU and the memory system. Local register allocation has been studied for more than 30 years in the theory and compiler communities. In this paper, we give a 2-approximation algorithm for LRA. We also show that a variant of the known further-first heuristic achieves a good approximation ratio.

Original language	English (US)
Pages (from-to)	37-65
Number of pages	29
Journal	Journal of Algorithms
Volume	37
Issue number	1
DOIs	https://doi.org/10.1006/jagm.2000.1095
State	Published - Oct 2000

ASJC Scopus subject areas

Control and Optimization
Computational Mathematics
Computational Theory and Mathematics

Access to Document

10.1006/jagm.2000.1095

Cite this

@article{e65f6abf139a4a33a441830cbb022cd1,

title = "On Local Register Allocation",

abstract = "In this paper, we consider the problem of local register allocation (LRA): given a sequence of instructions (basic block) and a number of general purpose registers, find the schedule of variables in registers that minimizes the total traffic between CPU and the memory system. Local register allocation has been studied for more than 30 years in the theory and compiler communities. In this paper, we give a 2-approximation algorithm for LRA. We also show that a variant of the known further-first heuristic achieves a good approximation ratio.",

author = "Martin Farach-Colton and Vincenzo Liberatore",

year = "2000",

month = oct,

doi = "10.1006/jagm.2000.1095",

language = "English (US)",

volume = "37",

pages = "37--65",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - On Local Register Allocation

AU - Farach-Colton, Martin

AU - Liberatore, Vincenzo

PY - 2000/10

Y1 - 2000/10

N2 - In this paper, we consider the problem of local register allocation (LRA): given a sequence of instructions (basic block) and a number of general purpose registers, find the schedule of variables in registers that minimizes the total traffic between CPU and the memory system. Local register allocation has been studied for more than 30 years in the theory and compiler communities. In this paper, we give a 2-approximation algorithm for LRA. We also show that a variant of the known further-first heuristic achieves a good approximation ratio.

AB - In this paper, we consider the problem of local register allocation (LRA): given a sequence of instructions (basic block) and a number of general purpose registers, find the schedule of variables in registers that minimizes the total traffic between CPU and the memory system. Local register allocation has been studied for more than 30 years in the theory and compiler communities. In this paper, we give a 2-approximation algorithm for LRA. We also show that a variant of the known further-first heuristic achieves a good approximation ratio.

UR - http://www.scopus.com/inward/record.url?scp=0346739888&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0346739888&partnerID=8YFLogxK

U2 - 10.1006/jagm.2000.1095

DO - 10.1006/jagm.2000.1095

M3 - Article

AN - SCOPUS:0346739888

SN - 0196-6774

VL - 37

SP - 37

EP - 65

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 1

ER -

On Local Register Allocation

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this