Register Allocation
Next: Printed Circuit Board
Up: Sample Applications
Previous: Frequency Assignment
One very active application for
graph coloring is register allocation. The register allocation
problem is to assign variables to a limited number of hardware
registers during program execution. Variables in registers can be
accessed much quicker than those not in registers. Typically, however,
there are far more variables than registers so it is necessary to
assign multiple variables to registers. Variables conflict with each
other if one is used both before and after the other within a short period
of time (for instance, within a subroutine). The goal is to assign variables
that do not conflict so as to minimize the use of non-register memory.
A simple approach to this is to create a graph where the nodes
represent variables and an edge represents conflict between its nodes.
A coloring is then a conflict-free assignment. If the number of
colors used is less than the number of registers then a conflict-free
register assignment is possible. Some papers that outline and expand
on this method include Chaitin [24], Chaitin et. al
[25], Chow and Hennessy [28][27], and
Briggs, Cooper, Kennedy, and Torczon [19].
Michael A. Trick
Thu Oct 27 21:43:48 EDT 1994