[JonChesterfield]

It's np hard. You can solve it perfectly for a given instance using a constraint solver and adequate patience.

Unfortunately instruction selection is also NP, and so is instruction scheduling, and all three are inter-related. An optimal solution for one tends to be suboptimal for the other two.

Ideally one would feed all three problems into a constraint solver together. Thus far this is considered computationally infeasible, though I don't think that belief would bear up to scrutiny with a supercomputer.

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

[LoganDark]

> though I don't think that belief would bear up to scrutiny with a supercomputer.

It's certainly computationally infeasible for home users, that's for sure.