
19.1 Write an algorithm, using depthfirst search, to number the nodes of a tree in depthfirst order and to annotate each node with the number of its highestnumbered descendent. Show how these annotations can be used − once your preprocessing algorithm has been run on a dominator tree − to answer a query of the form "does node i dominate node j?" in constant time.
 Use Algorithm 19.9 to calculate the dominators of the Flowgraph of Exercise 18.1, showing the semidominators and spanning forest at various stages.
 For each of the graphs of Image 18.1 and Image 18.2, calculate the immediate dominator tree (using either Algorithm 19.9 or the algorithm in ), and for each node n calculate DF_{local}[n], DF_{up}[n], and DF.
 *19.4 Prove that, for any node v, Algorithm 19.9+19.10b always initializes best[v] ← v (in the Link function) before calling AncestorWithLowestSemi(v).
 Calculate the dominance frontier of each node in each of these graphs:

The graph of Image 2.8.
 The graph of Exercise 2.3a.
 The graph of Exercise 2.5a.
 The graph of Image 3.27.
 **19.6 Prove that
as follows:

Show that DF_{local}[n]⊆ DF[n];
 Show that for each child Z of n, DFup[Z]⊆ DF[n];
 If there is a node Y in DF[n], then therefore there is an edge U → Y such that n dominates U but does not strictly dominate Y. Show that if Y = n, then Y∉ DF_{local}[n], andif Y ≠ n, then Y∉ DF_{up}[Z] for some child Z of N.
 Combine these lemmas into a proof of the theorem.
 Convert this program to SSA form:
Show your work after each stage:

Add a start node containing initializations of all variables.
 Draw the dominator tree.
 Calculate dominance frontiers.
 Insert φfunctions.
 Add subscripts to variables.
 Use Algorithm 19.17 to build the interference graph.
 Convert back from SSA form by inserting move instructions in place of φfunctions.
 This C (or Java) program illustrates an important difference between defuse chains and SSA form:
int f(int i, int j) {
int x,y;
switch(i) {
case 0: x=3;
case 1: x=1;
case 2: x=4;
case 3: x=1;
case 4: x=5;
default: x=9;
}
switch(j) {
case 0: y=x+2;
case 1: y=x+7;
case 2: y=x+1;
case 3: y=x+8;
case 4: y=x+2;
default: y=x+8;
return y;
}

Draw the controlFlow graph of this program.
 Draw the usedef and defuse data structures of the program: For each definition site, draw a linkedlist data structure pointing to each use site, and vice versa.
 Starting from the CFG of part (a), convert the program to SSA form. Draw data structures representing the uses, defs, and φfunctions, as described at the beginning of .
 Count the total number of datastructure nodes in the usedef data, and the total number in the SSA data structure. Compare.
 Approximate the total sizes of the usedef data structures, and the SSA data structures, if there were N cases in each switch instead of 6.
 *19.9 Suppose the graph of Exercise 2.3a is the controlFlow graph of a program, and in block 1 there is an assigment to a variable v.

Convert the graph to SSA form (insert φfunctions for v).
 Show that for any N, there is a "ladder" CFG with O(N) blocks, O(N) edges, and O(N) assignment statements (all in the first block!), such that the number of φfunctions in the SSA form is N^{2}.
 Write a program whose CFG looks like this.
 Show that a program containing deeply nested repeatuntil loops can have the same N^{2} blowup of φfunctions.
 *19.10 Algorithm 19.7 uses a stack for each variable, to remember the current active definition of the variable. This is equivalent to using environments to process nested scopes, as explained for typechecking.

Rewrite Algorithm 19.7, calling upon the imperative environments of package Symbol (whose interface is given in Program 5.5) instead of using explicit stacks.
 Rewrite Algorithm 19.7, using the functionalstyle symbol tables whose Table class is described on page 110.
 Show that optimization on an SSA program can cause two SSA variables a_{1} and a_{2}, derived from the same variable a in the original program, to have overlapping live ranges as described on page 428. Hint: Convert this program to SSA, and then do exactly one constantpropagation optimization.
while c<0 do (b := a; a := M[x]; c := a+b);
return a;
 *19.12 Let V_{c} and E_{c} be the nodes and edges of the CFG, and V_{i} and E_{i} be the nodes and edges of the interference graph produced by Algorithm 19.17. Let N = V_{c} + E_{c} + V_{i} + E_{i}.

Show that the run time of Algorithm 19.17 on the following (weird) program is asymptotically proportional to N^{1}.^{5}:
v_{1} ← 0
v_{2} ← 0
⋮
v_{m} ← 0
goto L_{1}
L_{1} : goto L_{2}
L_{2} : goto L_{3}
⋮
L_{m}^{2} :
w_{1} ← v_{1}
w_{2} ← v_{2}
⋮
w_{m} ← v_{m}
 Show that if every block defines at least one variable, and has no more than c statements and no more than c outedges (for some constant c), then the time complexity of Algorithm 19.17 is O(N). Hint: Whenever LiveOutAtBlock is called, there will be at most c calls to LiveOutAtStatement, and at least one will add an edge to the interference graph.