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