Previous    Next

## EXERCISES

• 11.1 The following program has been compiled for a machine with three registers r1, r2, r3; r1 and r2 are (caller-save) argument registers and r3 is a callee-save register. Construct the interference graph and show the steps of the register allocation process in detail, as on pages 229−232. When you coalesce two nodes, say whether you are using the Briggs or George criterion. Hint: When two nodes are connected by an interference edge andamove edge, you may delete the move edge; this is called constrain and is accomplished by the first else if clause of procedure Coalesce.

• 11.2 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 × in the table.

The following pairs of nodes are related by MOVE instructions:

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 selectpart of the algorithm,
1. 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).

2. 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.
• 11.3 Conservative coalescing is so called because it will not introduce any (potential) spills. But can it avoid spills? Consider this graph, where the solid edges represent interferences and the dashed edge represents a MOVE:
1. 4-color the graph without coalescing. Show the select-stack, indicating the order in which you removed nodes. Is there a potential spill? Is there an actual spill?

2. 4-color the graph with conservative coalescing. Did you use the Briggs or George criterion? Is there a potential spill? Is there an actual spill?
• 11.4 It has been proposed that the conservative coalescing heuristic could be simplified. In testing whether MOVE(a, b) can be coalesced, instead of asking whether the combined node ab is adjacent to < K nodes of significant degree, we could simply test whether ab is adjacent to < K nodes of any degree. The theory is that if ab is adjacent to many low-degree nodes, they will be removed by simplification anyway.
1. Show that this kind of coalescing cannot create any new potential spills.

2. Demonstrate the algorithm on this graph (with K = 3):
3. *Show that this test is less effective than standard conservative coalescing.

Hint: Use the graph of Exercise 11.3, with K = 4.

 JaVa Previous    Next
Comments