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 report the experimental performance of a branch-and-bound
algorithm and both approximation algorithms on standard benchmarks.
Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-33.ps.gz