2 ms·
> Is it an NP complete problem our own heuristics are currently better at estimating? Some of the important problems are NP-complete (like register allocation)
by haberman 15y ago
> Is it an NP complete problem our own heuristics are currently better at estimating?
Some of the important problems are NP-complete (like register allocation). Another problem is that compilers aren't that good at telling fast-paths from slow-paths (and keeping everything in registers for the fast paths). For more info see this message from the author of LuaJIT: http://article.gmane.org/gmane.comp.lang.lua.general/75426 http://article.gmane.org/gmane.comp.lang.lua.general/75426
- BrandonM 15y agoThanks for the link. That email was informative enough that I thought it deserved its own submission: http://news.ycombinator.com/item?id=2588696 http://news.ycombinator.com/item?id=2588696
- kragen 15y agoThere's a new formulation of register allocation that's computationally tractable: http://compilers.cs.ucla.edu/fernando/projects/puzzles/experiments/ http://compilers.cs.ucla.edu/fernando/projects/puzzles/exper...