I don't know what to recommend. Piddling around with Google Scholar I find lots of promising-looking survey articles about polynomial-time optimal register allocation and chordal interference graphs and the like, but I don't know which ones to recommend. Pereira's dissertation in 02008 https://homepages.dcc.ufmg.br/~fernando/publications/papers/... was what I remember as the big breakthrough I was describing above:
> Even though this is an old problem,
compilers still use heuristics to solve register allocation, or use exact algorithms
that have exponential complexity. We present an optimal, polynomial time, register assignment algorithm.
But that may not be entirely fair; for example, Hack and Goos presented a linear-time algorithm for SSA depending on special properties of SSA interference graphs in 02005 in http://web.cs.ucla.edu/~palsberg/course/cs232/papers/HackGoo..., and Pereira also presented such an algorithm in the same year.
But that was 17 years ago. What's happened in those 17 years? I've heard that polynomial-time optimal register allocation algorithms have gone into common use, but I don't know which ones!
> Even though this is an old problem, compilers still use heuristics to solve register allocation, or use exact algorithms that have exponential complexity. We present an optimal, polynomial time, register assignment algorithm.
Pereira and Palsberg presented a shorter version at PLDI that year; the paper is at https://llvm.org/pubs/2008-06-PLDI-PuzzleSolving.html.
But that may not be entirely fair; for example, Hack and Goos presented a linear-time algorithm for SSA depending on special properties of SSA interference graphs in 02005 in http://web.cs.ucla.edu/~palsberg/course/cs232/papers/HackGoo..., and Pereira also presented such an algorithm in the same year.
But that was 17 years ago. What's happened in those 17 years? I've heard that polynomial-time optimal register allocation algorithms have gone into common use, but I don't know which ones!
If you find good references, please let me know!