1 comments
> The best assignment is NP-hard to find, so all practical allocators use heuristics.<p>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).<p><a href="https://compilers.cs.uni-saarland.de/projects/ssara/" rel="nofollow">https://compilers.cs.uni-saarland.de/projects/ssara/</a>
Not quite, SSA form makes only the colouring pass polynomial time, optimal choice of spilling and coalescing is still NP-complete. cf. <a href="https://hal-lara.archives-ouvertes.fr/hal-02102286v1/document" rel="nofollow">https://hal-lara.archives-ouvertes.fr/hal-02102286v1/documen...</a>