An Analysis of Graph Coloring Register Allocation

 

Carnegie Mellon University Technical Report No. CMU-CS-06-111

David Ryan Koes and Seth Copen Goldstein

page 10

March, 2006

Abstract


download pdf


@techreport{koes-tr06,
  author = {Koes, David Ryan and Goldstein, Seth Copen},
  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://www.cs.cmu.edu/~seth/papers/koes-tr06.pdf},
  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.},
  keywords = {Compilers:Register Allocation}
}

Related Papers

Compilers:Register Allocation
A Better Global Progressive Allocator
David Ryan Koes and Seth Copen Goldstein. In LCTES 06 Student Poster Session, 2006.
A global progressive register allocator
David Ryan Koes and Seth Copen Goldstein. In Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation (PLDI'06), pages 204–215, 2006.
An Analysis of Graph Coloring Register Allocation
David Ryan Koes and Seth Copen Goldstein. Carnegie Mellon University Technical Report No. CMU-CS-06-111, pages 10, March, 2006.
A Progressive Register Allocator for Irregular Architectures
David Ryan Koes and Seth Copen Goldstein. In Proceedings of the International Symposium on Code Generation and Optimization (CGO'05), pages 269–280, March, 2005.


Back to publications list