I talked with Chris Lattner a few years ago about register allocation and he had an interesting perspective. In his view (from what I remember; my recollection could be somewhat incorrect) most of the classical academic research on it is solving the wrong problem. Most formulations of register allocation are graph coloring algorithms designed to answer the question "is this function colorable using K registers without spilling?" The algorithms for handling the case when you <i>do</i> spill usually don't have as much thought put into them. But this is emphasizing the wrong aspect of the problem in practice; for almost any interesting function on the commonly used architectures (x86/ARM), the answer to the theoretical question is trivially "no" (because there are relatively few registers), and the most important practical problem is how to spill effectively (including deciding whether to spill versus split versus rematerialize, etc.) As I understand it, that's the idea behind LLVM's (relatively) new greedy allocator [1]: the graph-coloring part of the problem is simple, and the focus is on spilling and splitting, problems that the classical academic literature has tended to put less emphasis on.<p>[1]: <a href="http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html" rel="nofollow">http://blog.llvm.org/2011/09/greedy-register-allocation-in-l...</a>