[PhilipRoman]

>You can solve it perfectly for a given instance using a constraint solver and adequate patience.

Is this really true for cases where there is no choice but to spill registers? How would a graph coloring solver understand to spill outer loop variables instead of inner loop ones? I've never written a "proper" register allocator so I'm curious.

[mzl]

The article links to the Unison project, which does optimal spilling and register allocation using constraint programming solvers.

The core idea is that memory for spilling is treated as an additional set of register-like locations, with costs for using.