Mon Mar 13, 2006, 1-2pm, 4549 Boelter Hall.

Register allocation: What does Chaitin's proof really prove?

Fabrice Rastello
ENS Lyon, France

Register allocation is one of the most studied problem in compilation.
It is considered as an NP-complete problem since Chaitin, in 1981,
showed that assigning temporary variables to k machine registers
amounts to color with k colors the interference graph associated to
variables and that this graph can be arbitrary, thereby proving the
NP-completeness of the problem. However, this original proof does not
really show where the complexity comes from. Recently, the
re-discovery that interference graphs of SSA programs can be colored
in polynomial time raised the question: Can we exploit SSA to perform
register allocation in polynomial time, without contradicting
Chaitin's NP-completeness result? To address such a question, we
revisit Chaitin's proof to better identity the interactions between
spilling (load/store insertion), coalescing/splitting (moves between
registers), critical edges (a property of the control-flow graph), and
coloring (assignment to registers). In particular, we show that when
it is easy to decide if temporary variables can be assigned to k
registers or if some spilling is necessary. The real complexity of the
problem comes from critical edges, spilling, and coalescing, which
will be addressed in the next talks.

Host: Jens Palsberg