4 ms·
> Also register allocation is an NP problem (graph coloring). No, this strongly depends on the form of the program. SSA form permits polynomial solution of reg
by dom0 9y ago
> Also register allocation is an NP problem (graph coloring).
No, this strongly depends on the form of the program. SSA form permits polynomial solution of register allocation. (SSA is the most widely used form in compilers; LLVM, GCC and even MSVC use it, and many more.)
- andrewflnr 9y agoMy understanding is that the number of colors is just the maximum number of live values at any point, which is easy to determine, so the theoretically NP-complete part of graph-coloring is solved before you even start trying to pick registers. After that, it gets tricky to even define optimality, because you have to trade off the likely runtime costs of different sets of moves (which in my mind includes which variables to spill to the stack when). If there's a formal framework that decisively handles that stuff, someone please let me know. OTOH, GP only actually said "NP problem", of which P is a subset, so they're not wrong. :)