"Here, real world cases likely will have only a fairly limited number of registers and only a limited (but potentially very long) length of code to optimize acr

"Here, real world cases likely will have only a fairly limited number of registers and only a limited (but potentially very long) length of code to optimize across. " You can do a good job with polynomial time heuristics (chaitin's heuristic) for coloring, however, you are wrong about the code. It is often very weird. At the same time, most of the performance issue is not coloring, or trying not to spill at all. The problem is deciding where to split live ranges (which introduces copies), where to merge existing live ranges (which removes copies at a cost of more interferences), where to spill, where to remat, are quite hard.