On Local Register Allocation

Martin Farach-Colton, Vincenzo Liberatore

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

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 languageEnglish (US)
Pages (from-to)37-65
Number of pages29
JournalJournal of Algorithms
Volume37
Issue number1
DOIs
StatePublished - Oct 2000

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'On Local Register Allocation'. Together they form a unique fingerprint.

Cite this