A global progressive register allocator

 

In Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation (PLDI'06)

David Ryan Koes and Seth Copen Goldstein

pages 204–215, New York, NY

2006

Abstract


download pdf


@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}
}

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