Register allocation in general is np-complete[1][2]. Having polynomial-time coloring algorithm for SSA doesn't make the allocation optimal -- you still need to

Register allocation in general is np-complete[1][2]. Having polynomial-time coloring algorithm for SSA doesn't make the allocation optimal -- you still need to "lower" the SSA to proper machine code. [1] http://www.cs.cmu.edu/afs/cs/academic/class/15745-s07/www/papers/pereira-fossacs06.pdf http://www.cs.cmu.edu/afs/cs/academic/class/15745-s07/www/pa... [2] http://pharm.ece.wisc.edu/wddd/2006/papers/wddd_05.pdf http://pharm.ece.wisc.edu/wddd/2006/papers/wddd_05.pdf