A Progressive Register Allocator for Irregular Architectures

 

In Proceedings of the International Symposium on Code Generation and Optimization (CGO'05)

David Ryan Koes and Seth Copen Goldstein

pages 269–280, Washington, DC

March, 2005

Abstract


download pdf


@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 = {March},
  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}
}

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