An Analysis of Graph Coloring Register Allocation

@inproceedings{koes-lctes06,
  author = {Koes, David Ryan and Goldstein, Seth Copen},
  title = {A Better Global Progressive Allocator},
  publisher = {Academia Press},
  url = {http://www.cs.cmu.edu/~seth/papers/koes-lctes06.pdf},
  booktitle = {LCTES 06 Student Poster Session},
  year = {2006},
  abstract = {We present an improvement to the simultaneous heuristic
     allocator component of the global progressive register allocator
     described in our previous work \cite{koes-pldi2006}. Our improved
     allocator decomposes the control flow graph into linear traces
     which are allocated in the same manner as a single basic block.
     We investigate two methods for handling the control flow within
     the traces both of which produce better quality allocations than
     the simultaneous heuristic allocator.},
  keywords = {Compilers:Register Allocation},
}

@inproceedings{koes-pldi2006,
  author = {Koes, David Ryan and Goldstein, Seth Copen},
  title = {A global progressive register allocator},
  booktitle = {Proceedings of the 2006 ACM SIGPLAN conference on
     Programming language design and implementation (PLDI'06)},
  year = {2006},
  isbn = {1-59593-320-4},
  pages = {204--215},
  doi = {http://doi.acm.org/10.1145/1133981.1134006},
  publisher = {ACM Press},
  address = {New York, NY},
  abstract = {This paper describes a {\em global progressive register
     allocator}, a register allocator that uses an expressive model of
     the register allocation problem to quickly find a good allocation
     and then progressively find better allocations until a provably
     optimal solution is found or a preset time limit is reached. The
     key contributions of this paper are an expressive model of global
     register allocation based on multi-commodity network flows that
     explicitly represents spill code optimization, register
     preferences, copy insertion, and constant rematerialization; two
     fast, but effective, heuristic allocators based on this model;
     and a more elaborate progressive allocator that uses Lagrangian
     relaxation to compute the optimality of its allocations. Our
     progressive allocator demonstrates code size improvements as
     large as 16.75\% compared to a traditional graph allocator. On
     average, we observe an initial improvement of 3.47\%, which
     increases progressively to 6.84\% as more time is permitted for
     compilation.},
  keywords = {Compilers:Register Allocation},
  url = {http://www.cs.cmu.edu/~seth/papers/koes-pldi2006.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 = {Mar},
  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},
}

@inproceedings{koes-cgo05,
  author = {Koes, David Ryan and Goldstein, Seth Copen},
  title = {A Progressive Register Allocator for Irregular
     Architectures},
  booktitle = {Proceedings of the International Symposium on Code
     Generation and Optimization {(CGO'05)}},
  month = {Mar},
  year = {2005},
  isbn = {0-7695-2298-X},
  pages = {269--280},
  doi = {http://dx.doi.org/10.1109/CGO.2005.4},
  publisher = {IEEE Computer Society},
  address = {Washington, DC},
  abstract = {Register allocation is one of the most important
     optimizations a compiler performs. Conventional graph-coloring
     based register allocators are fast and do well on regular,
     RISC-like, architectures, but perform poorly on irregular,
     CISC-like, architectures with few registers and non-orthogonal
     instruction sets. At the other extreme, optimal register
     allocators based on integer linear programming are capable of
     fully modeling and exploiting the peculiarities of irregular
     architectures but do not scale well. We introduce the idea of a
     \textit{progressive allocator} which finds an initial allocation
     of quality comparable to a conventional allocator, but as more
     time is allowed for computation the quality of the allocation
     approaches optimal. This paper presents a progressive register
     allocator which uses a multi-commodity network flow model to
     elegantly represent the intricacies of irregular architectures.
     We evaluate our allocator substituted for {\tt gcc}'s local
     register allocation pass.},
  keywords = {Compilers:Register Allocation},
  url = {http://www.cs.cmu.edu/~seth/papers/koes-cgo05.pdf},
}