### Vincenzo Liberatore

### Rutgers Universit

### On Local Register Allocation

In this talk, 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.
We present the following original 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.

(Joint work with M. Farach)