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.
