Comment by leonidasrup
3 days ago
No compiler does optimal register allocation, because optimal register allocation is an NP-complete problem.
Chaitin et al.: "Register allocation via coloring".
3 days ago
No compiler does optimal register allocation, because optimal register allocation is an NP-complete problem.
Chaitin et al.: "Register allocation via coloring".
Yes? And stochastic methods are one way to approximate optimal NP solutions. In the context of register allocation, you'd be most likely to see that when modeling actual runtime optimality rather than minimizing spill or whatever. Mainstream compilers don't do that, but mainstream compilers don't incorporate many SOTA techniques.