On Local Register Allocation

Martin Farach-Colton, Vincenzo Liberatore

    Research output: Contribution to journalArticlepeer-review


    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

    ASJC Scopus subject areas

    • 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