Previous    Next

## EXERCISES

• 17.1 Show the dataflow equations for reaching expressions(page 358). Be specific about what happens in the case of quadruples such as t ← tb or t ← M[t], where the defined temporary also appears on the right-hand side. The elements of the gen and kill sets will be definition IDs, as in reaching definitions.

Hint: If the definition on page 358 is not clear enough to formulate a precise definition, be guided by the role that reaching expressions must play in common-subexpression elimination (page 359).

• 17.2 Write down the control-flow graph of basic blocks (not just statements) for Program 17.3, and show the genand killsets (for reaching definitions) of each block.
• *17.3 Show how to combine the genand killeffects of two adjacent statements in the same basic block for each of:
1. Available expressions.

2. Liveness analysis.
• **17.4 Modify the algorithm for computing available expressions to simultaneously compute reaching expressions. To make the algorithm more efficient, you may take advantage of the fact that if an expression is not available at statement s, then we do not need to know if it reaches s or not (for purposes of common-subexpression elimination). Hint: For each available expression a + b that is propagated through statement s, also propagate a set representing all the statements that define a + b and reach s.
• 17.5 Consider the calculation of reaching definitionson the following program:
```x := 1;
y := 1;
if z <> 0
then x := 2
else y := 2;
w := x+y
```

• a. Draw a control-flow graph for this program.

• b. Show the sorted array that results from running Algorithm 17.5 on the program.
• c. Calculate reaching definitions, showing the result of each iteration in tabular format as on page 356. How many iterations are required?
• *d. Prove that when reaching definitions is computed by iteration on an acyclic graph, taking the nodes in the order given by Algorithm 17.5, only one iteration is necessary (the second iteration merely verifies that nothing has changed). Hint: Prove, and make use of, the lemma that each node is visited after all of its predecessors.
• e. Suppose we order the nodes according to the order they are first visited by depth-first search. Calculate reaching definitions using that order, showing the results in tabular format; how many iterations are required?
• *17.6 Write down a work-list algorithm for liveness analysis, in a form similar to that of Algorithm 17.6.

 JaVa Previous    Next