>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.