Tue Mar 14, 2006, 4-5pm, 4549 Boelter Hall.

Complexity results for register allocation with spilling.

Fabrice Rastello
ENS Lyon, France

This talk deals with the optimization problem of minimum spilling
"everywhere" related to register allocation: many heuristics for
register allocation use the interference graph and try to color it.
Spill (everywhere) a variable roughly corresponds to remove the
corresponding node from the graph. This formulation is exact if
instructions can directly access memory (like Pentium).
If on the other hand, an evicted variable has to be loaded in a register
previously to each use, spilling a variable everywhere does not
correspond to remove its full live range, but its live range with holes
on it.

We will first address the node deletion problem without holes. It is
proved to be NP-complete from Chaitin et al's reduction; however, it can
be formulated as an IL program using the incidence matrix of live-ranges
on computation points. The incidence matrix is totally unimodular for
interval hypergraphs and the problem gets polynomial on basic-blocs.
This property holds also for the more general class of path graphs which
are particular chordal graphs; but chordal graphs are the interference
graphs of variables under SSA... So the hope was to find such a
polynomial result for the weighted node deletion problem under SSA.
Unfortunately, this is not the case and we will show that even the
problem of lowering the register pressure by one is NP-complete. 

Still, as already stressed, the node deletion problem without holes is
polynomial on basic blocs. Besides, there exists several known
polynomial results for the load/store minimization problem
(non-everywhere spilling) depending on whether loads or stores have non
zero cost or not. So we will then address the minimum spilling
everywhere problem with holes on basic blocs. We will show different
complexity results depending on the value of k (the number of
registers), MAXLIVE, t (the number of simultaneously used variables)...

Host: Jens Palsberg