There are very few academic papers that just consider the coloring problem of register allocation. One of the reasons for tis is that there is essentially no pr

There are very few academic papers that just consider the coloring problem of register allocation. One of the reasons for tis is that there is essentially no progress to be made on the instances of graph coloring that arise in register allocation. As far as I know, all graph coloring register allocators use the greedy coloring algorithm given by Chaitin, which was actually first published by Kempe in the 19th century. There are better graph coloring algorithms, but the interference graphs that arise from real programs are sufficiently uninteresting that they don't matter. And if you're using an SSA IR in your backend, things get even simpler: the greedy algorithm is optimal, and you can perfectly color the interference graph without even constructing it. Most of the work on register allocation (both in academia and production compilers) happens on the aspects of the problem that are not reflected in the graph coloring formulation: 1) Copy elimination. You can approximate this problem by adding affinity weights to edges of the interference graph and asking for a coloring that minimizes the cost of unfulfilled affinities. This doesn't actually represent the problem as it exists on a real computer, because you can sometimes get rid of copies by other means than just choosing a lucky assignment, e.g. you can restructure the program to move a copy outside of a hot loop. This is especially relevant given the use of SSA form in modern compilers, because if you do nothing then you will end up inserting copies all over the place to implement phis. 2) Spill code insertion. If you perform a coloring of the interference graph and find that you don't have enough physical registers, then you have to restructure the program to spill registers to the stack and reload them. The particulars of which variables to spill and where to insert the stores and loads are very important for code quality. This includes things like rematerialization that let you insert other instruction sequences instead of loads to recreate the spilled value. 3) Live range splitting. In a sense, the idea that live range splitting is a distinct problem from the other problems of register allocation is relevant more to the implementation of register allocators than register allocation as an abstract optimization problem. If your allocator operates on a per-variable basis, then it often makes sense to split a variable into two separate variables and insert a copy merging the two live ranges. For example, a variable might be used frequently in one control-flow region and not used at all down another, and you want the register allocator to be able to make distinct decisions about those two regions. This problem is worsened by compiler optimizations, because compilers can often realize that multiple variables in a function have the same value and optimize them to use a common definition. The area where academic register allocation research has the largest gap from actual practice is probably the consideration of architectural constraints on registers like instructions with fixed registers, pairs of adjacent registers, etc. and register files that have overlapping registers. You can always insert copies around an instruction to satisfy almost any constraint, but that doesn't work out so well. :) Most of the academic work I have seen on this problem is either overly simplified and doesn't handle all of the constraints that befall a production compiler, or it is considerably expensive to implement. This gets worse when you write a portable compiler; while the constraints of any single architecture may be manageable, it's harder when you have to handle the union of the constraints imposed by all architectures that you want to support. The aliasing between the various ARM floating-point register files was a strong motivator in the design of LLVM's greedy allocator. The LLVM 'greedy' allocator is probably poorly named. It started out as a simple greedy register allocator, and over time it gained mechanisms like register eviction that make it a non-greedy algorithm. You don't have to squint too hard at it before it looks like a variation of priority allocation: http://dl.acm.org/citation.cfm?id=88621 http://dl.acm.org/citation.cfm?id=88621 The allocator described in that paper uses an interference graph for liveness and interference checks and a different method of choosing the priorities, but if you abstract away those details it's pretty similar.