# 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

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