Optimal register allocation for SSA-form programs in polynomial time

This paper gives a constructive proof that the register allocation problem for a uniform register set is solvable in polynomial time for SSA-form programs.