# 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

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