✦ LIBER ✦

On Local Register Allocation

✍ Scribed by Farach-Colton, Martin (author);Liberatore, Vincenzo (author)

Book ID: 102573636
Publisher: Academic Press
Year: 2000
Tongue: English
Weight: 188 KB
Volume: 37
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.2000.1095

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

On Local Register Allocation

✍ Farach-Colton, Martin (author);Liberatore, Vincenzo (author) 📂 Article 📅 2000 🏛 Academic Press 🌐 English ⚖ 188 KB

On the Minimization of Loads/Stores in L

On the Minimization of Loads/Stores in Local Register Allocation

✍ Wei-Chung Hsu; Fischer, C.N.; Goodman, J.R. 📂 Article 📅 1989 🏛 IEEE 🌐 English ⚖ 970 KB

✍ Gregory J. Chaitin; Marc A. Auslander; Ashok K. Chandra; John Cocke; Martin E. H 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 827 KB

Linear scan register allocation

✍ Poletto, Massimiliano; Sarkar, Vivek 📂 Article 📅 1999 🏛 Association for Computing Machinery 🌐 English ⚖ 225 KB

✍ Atsushi Ohori 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 318 KB

✍ Sampath Kannan; Todd Proebsting 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 124 KB

In this article we look at the register allocation problem. In the literature this problem is frequently reduced to the general graph coloring problem and the solutions to the problem are obtained from graph coloring heuristics. Hence, no algorithm with a good performance guarantee is known. Here we