Java Reference
In-Depth Information
proc() {
a = 100;
b=0;
for (i=0;i<10;i++)
b=b+i*i;
print(a, b);
c = 100;
print(a*c);
}
Figure 13.14: A Simple Procedure with Candidates for Procedure-level
Register Allocation.
b
c
a
i
Figure 13.15: Interference Graph for procedure of Figure 13.14
beginning) is part of
m
's range. In other words,
l
and
m
cannot share the same
register if at the point
l
is first computed or loaded,
m
is also in use.
To represent all of the interferences in a subprogram (there normally are
many), an
interference graph
is built. Nodes of the graph are the live ranges of
the subprogram. An arc exists between live ranges
l
and
m
if
l
interferes with
m
or
m
interferes with
l
(the arc is undirected). Consider the simple procedure
shown in Figure 13.14. It has four register candidates, a, b, c,andi. The live
ranges for a, b,andi all interfere with each other; c's live range interferes only
with a's. This interference information is concisely shown in the interference
graph of Figure 13.15.
With an interference graph, the problem of allocating registers reduces to
a well-known problem, that of
coloring
the nodes of a graph. In the
graph
coloring problem
, we must determine whether
n
colors su
ce to color a
graph, given the rule that no two nodes connected by an arc may share the
same color. This exactly models register allocation, where
n
is the number of
registers we have available and each color represents a di
ff
erent register.
