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.