The table below represents a register-interference graph. Nodes 1-6 are precolored (with colors 1-6), and nodes A-H are ordinary (non-precolored). Every pair of precolored nodes interferes, and each ordinary node interferes with nodes where there is an x in the table.
|
A
|
1
x
|
2
x
|
3
x
|
4
x
|
5
x
|
6
x
|
A
|
B
|
C
|
D
|
E
|
F
|
G
|
H
|
|
B
|
x
|
|
x
|
x
|
x
|
x
|
|
|
|
|
|
|
|
|
|
C
|
|
|
x
|
x
|
x
|
x
|
|
|
|
x
|
x
|
x
|
x
|
x
|
|
D
|
x
|
|
x
|
x
|
x
|
|
|
|
x
|
|
x
|
x
|
x
|
x
|
|
E
|
x
|
|
x
|
|
x
|
x
|
|
|
x
|
x
|
|
x
|
x
|
x
|
|
F
|
x
|
|
x
|
x
|
|
x
|
|
|
x
|
x
|
x
|
|
x
|
x
|
|
G
|
|
|
|
|
|
|
|
|
x
|
x
|
x
|
x
|
|
|
|
H
|
x
|
|
|
x
|
x
|
x
|
|
|
x
|
x
|
x
|
x
|
|
|
The following pairs of nodes are related by MOVE instructions:
( A, 3) (H, 3) (G, 3) (B, 2) (C, 1) (D, 6) (E, 4) (F, 5)
Assume that register allocation must be done for an 8-register machine.
a. Ignoring the MOVE instructions, and without using the coalesce heuristic, color this graph using simplify and spill. Record the sequence (stack) of simplify and potential-spill decisions, show which potential spills become actual spills, and show the coloring that results.
b. Color this graph using coalescing. Record the sequence of simplify, coalesce, freeze, and spill decisions. Identify each coalesce as Briggs- or George-style. Show how many MOVE instructions remain.
*c. Another coalescing heuristic is biased coloring. Instead of using a conservative coalescing heuristic during simplification, run the simplify-spill part of the algorithm as in part (a), but in the select part of the algorithm,
i. When selecting a color for node X that is move-related to node Y , when a color for Y has already been selected, use the same color if possible (to eliminate the MOVE).
ii. When selecting a color for node X that is move-related to node Y , when a color for Y has not yet been selected, use a color that is not the same as the color of any of Y 's neighbors (to increase the chance of heuristic (i) working when Y is colored).
Conservative coalescing (in the simplify phase) has been found to be more effective than biased coloring, in general; but it might not be on this particular graph. Since the two coalescing algorithms are used in different phases, they can both be used in the same register allocator.
*d. Use both conservative coalescing and biased coloring in allocating registers. Show where biased coloring helps make the right decisions.