On Local Register Allocation

Martin Farach-Colton, Vincenzo Liberatore

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


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
Issue number1
StatePublished - Oct 2000

All Science Journal Classification (ASJC) codes

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


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

Cite this