> The best assignment is NP-hard to find, so all practical allocators use heuristics.
That said if you do the register allocation while the program is still in SSA form, it becomes polynomial (interference graph is a chordal graph).
That said if you do the register allocation while the program is still in SSA form, it becomes polynomial (interference graph is a chordal graph).
I got the impression that expensive register allocation is not an option. A 1% improvement in register allocation that results in a 0.1% local performance improvement and a 0.002% program performance improvement may be considered not to justify 1000x local compile time, but for frequently run stable-ish software the compile time and compiler development/maintenence time might be justified.
(I am not a programmer, but I do like thinking and learning about such things.)