I discovered a graph-coloring register allocator that optimally allocates registers for structured programs in polynomial time. It can handle register aliasing. The assignment of registers is optimal with respect to spill and rematerialization costs, register preferences and coalescing. The register allocator is not restricted to programs in SSA form or chordal interference graphs. It requires the input program to be structured, which is automatically true for many programming languages and for others, such as C, is equivalent to a bound on the number of goto labels per function. The number of registers is assumed to be fixed. Non-structured programs can be handled at the cost of either a loss of optimality or an increase in runtime.
I implemented a prototype, which is already the default register allocator in the Z80, Z180, Rabbit 2000/3000, Rabbit 3000A, LR35902 (Gameboy CPU), HC08 and S08 backends of sdcc, a cross-compiler for embedded systems.
Significant improvements in runtime over my approach are unlikely, since I found proof that optimal register allocation for structured programs is W[SAT]-hard, even for programs of tree-width 2.