I didn't realize it was that old. Also surprised that intraprocedural techniques havent had as much adoption. There's potential there for improvement in real-world compilers. Just gotta integrate it with Clang or GCC which Im pretty sure academics already have in prototypes. Then make it fast.
Chaitin published his stuff in the early 80s. Presumably the implementation is a bit older. But the idea of doing register allocation via graph coloring goes back to the late 60s and the idea of using graph coloring to minimize storage requirements generally goes back to around '63.
The interprocedural problem is mostly engineering - how to manage libraries, make files, etc., in a way that programmer will use it.
So I'll add graph coloring to the list of great things that happened in the 1960's that still kick arse today. Burroughs architecture, graph coloring, Dijkstra's methods... quite a few.
I did one of my undergrad junior independent projects on this around 1997-8, implementing and benchmarking a graph-coloring register allocator in lcc. The main goal was to beat the more ad-hoc/heuristic-driven register allocation algorithms implemented in common compilers, thereby gaining better-optimized code from a more generalized and well-known cs problem. iirc a straightforward implementation like the one in the paper here gave comparable but somewhat worse results than the ad-hoc algorithms for a number of important cases in our benchmark suite. I wonder if my advisor ever went further with it...
Cool stuff. The heuristics have been tuned over many years. Hard to beat good ones. So, if it was mostly comparable, then you were doing decent at it. Would be nice to see someone sit down to try to understand why each of those cases did better, extract the lessons, and plug them back into intraprocedural optimizer.
We did a lot of this in our compilers class. A lot of fun.
We spent lots of time talking about parsing in my compiler class :-/
Unfortunately, a lot of compiler classes are like that! Fortunately, the availability of gcc / clang / path64 means that it doesn't have to be that way.
Doesn't libfirm utilize this?
libfirm (http://pp.ipd.kit.edu/firm/) uses SSA-based register allocation (http://d-nb.info/986273813/34), which allows a decoupled spilling phase. Moreover, the register assignment becomes polynomial, while register coalescing remains NP-complete.