A Generalized Algorithm for Graph-Coloring Register Allocation
Graph-coloring register allocation is an elegant and extremely
popular optimization for modern machines.
But as currently formulated, it does not handle
two characteristics commonly found in commercial architectures.
First, a single register name may appear in multiple register
classes, where a class is a set of register names that are
interchangeable in a particular role.
Second, multiple register names may be aliases for
a single hardware register.
We present a generalization of graph-coloring register allocation
that handles these problematic characteristics while
preserving the elegance and practicality of traditional
graph coloring.
Our generalization adapts easily to a new target machine,
requiring only the sets of names in the register classes and
a map of the register aliases.
It also drops easily into a well-known
graph-coloring allocator, is efficient at compile time, and
produces high-quality code.
Full paper
The paper is available as
US Letter PostScript (942K),
US Letter PDF (296K), and
US Letter TeX DVI (120K,
without graphs).