1. See Appel, Chapter 11, 11.2a. An interference graph is given on nodes 1-6 and A-H on page 266. Using ONLY nodes C-H, hand simulate the optimistic register allocation algorithm (without coalescing) first for 6 registers (i.e., 6 colors) and then for 4 registers (i.e., 4 colors). Make sure to mark nodes as "potential spill" or "actual spill" as you stack and pop them. Report if you can color the graph with 4 and/or 6 registers without spilling any live ranges.

Use this file for questions 2 and 3.

2. Using control flow graph 1, calculate the sets of reaching definitions at each basic block entry. The notation [k,n] means the definition of k in basic block number n. Using control flow graph 2, calculate the live uses of variables at each basic block exit. For this problem, the notation [k,m] means the use (before definition) of k in basic block number m.

Note: if the instructions are k=2; x=k; then there are no live uses of k in this basic block because k is defined before it is used. On the other hand, if the instructions are x=k; k=2; then the use of k is live in this basic block because k will have whatever value it has on entry to this basic block.

3. If our control flow graph contains a loop, then we must iterate the data-flow equations to solve them. In each iteration, we traverse every node and check that the righthandside of its data-flow equation calculates the same set as is the current solution at that node. If not, store the set calculated by the righthandside into the lefthandside. Iteration continues until there is no change in the solution.

Using this approach, solve reaching definitions and live uses of variables on control flow graph 3.

Prepared by Barbara Ryder at 4:40pm on April 27, 1999.