Previous Next |
11.1 The following program has been compiled for a machine with three registers r_{1}, r_{2}, r_{3}; r_{1} and r_{2} are (caller-save) argument registers and r_{3} 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.
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.
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).
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.
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?
Show that this kind of coalescing cannot create any new potential spills.
Hint: Use the graph of Exercise 11.3, with K = 4.
JaVa | Previous Next |