@TechReport{,
  author = 	 {David Koes and Seth Copen Goldstein},
  title = 	 {An Analysis of Graph Coloring Register Allocation},
  institution =  {Carnegie Mellon University},
  year = 	 {2006},
  number = 	 {CMU-CS-06-111},
  pages =        {10},
  month = 	 {March},
  url =          {http://reports-archive.adm.cs.cmu.edu/anon/2006/abstracts/06-111.html},
 abstract = {Graph coloring is the de facto standard technique for register
allocation within a compiler.  In this paper we examine the importance
 of the quality of the coloring algorithm
and various extensions of the basic graph coloring technique
by replacing the coloring phase of the GNU compiler's
register allocator with an optimal coloring algorithm.  We then
extend this optimal algorithm to incorporate various extensions
such as coalescing and preferential register assignment.
We find that using an optimal coloring algorithm has surprisingly little
benefit and empirically demonstrate the benefit of the various extensions.

}
}