2 ms·
The K-graph coloring problem for register allocation is NP-complete, but in SSA form is actually linear. The tougher problem isn't the coloring but rather where
by verall 9y ago
The K-graph coloring problem for register allocation is NP-complete, but in SSA form is actually linear. The tougher problem isn't the coloring but rather where to optimally place spills and fills around loops and calls.
https://llvm.org/devmtg/2011-11/Olesen_RegisterAllocation.pdf https://llvm.org/devmtg/2011-11/Olesen_RegisterAllocation.pd...
- andrewflnr 9y agoYeah, the number of "registers" needed isn't really NP-complete the way that the number of colors in a graph is. It's just the maximum number of live values, which, while not exactly trivial, is not that hard to figure out.