libfirm (http://pp.ipd.kit.edu/firm/) uses SSA-based register allocation (http://d-nb.info/986273813/34), which allows a decoupled spilling phase. Moreover, the register assignment becomes polynomial, while register coalescing remains NP-complete.