On local register allocation

Martin Farach, Vincenzo Liberatore

    Research output: Contribution to conferencePaperpeer-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 thirty years in the theory and compiler communities. It was not known if LRA is NP-hard, but no subexponential time algorithm was known. Furthermore, the most popular heuristics in use in compilers can perform arbitrarily poorly in the worst case. In this paper, we present the following results: We show that the Local Register Allocation problem is NP-hard. We show that a variant of the furthest-first heuristic achieves a good approximation ratio. We give a 2-approximation algorithm for LRA. We report the experimental performance of a branch-and-bound algorithm and both approximation algorithms on standard benchmarks.

    Original languageEnglish (US)
    Pages564-572
    Number of pages9
    StatePublished - 1998
    EventProceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA
    Duration: Jan 25 1998Jan 27 1998

    Other

    OtherProceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms
    CitySan Francisco, CA, USA
    Period1/25/981/27/98

    ASJC Scopus subject areas

    • Software
    • General Mathematics

    Fingerprint

    Dive into the research topics of 'On local register allocation'. Together they form a unique fingerprint.

    Cite this