Previous    Next

## EXERCISES

• 18.1

1. Calculate the dominators of each node of this Flowgraph:

2. Show the immediate-dominator tree.
3. Identify the set of nodes in each natural loop.
• 18.2 Calculate the immediate-dominator tree of each of the following graphs:
1. The graph of Image 2.8.

2. The graph of Exercise 2.3a.
3. The graph of Exercise 2.5a.
4. The graph of Image 3.27.
• *18.3 Let G be a control-flow graph, h be a node in G, A be the set of nodes in a loop with header h, and B be the set of nodes in a different loop with header h. Prove that the subgraph whose nodes are AB is also a loop.
• *18.4 The immediate-dominator theorem (page 380) is false for graphs that contain unreachable nodes.
1. Show a graph with nodes d, e, and n such that d dominates n, e dominates n, but neither d dominates e nor e dominates d.

2. Identify which step of the proof is invalid for graphs containing unreachable nodes.
3. In approximately three words, name an algorithm useful in finding unreachable nodes.
• *18.5 Show that in a connected flowgraph (one without unreachable nodes), a natural loop as defined on page 381 satisfies the definition of loop given on page 376.
• 18.6 For some purposes it is desirable that each loop-header node should have exactly two predecessors, one outside the loop and one inside. We can ensure that there is only one outside predecessor by inserting a preheader node, as described in . Explain how to insert a postbody node to ensure that the loop header has only one predecessor inside the loop.
• *18.7 Suppose any arithmetic overflow or divide-by-zero will raise an exception at run time. If we hoist tab out of a loop, and the loop might not have executed the statement at all, then the transformed program may raise the exception where the original program did not. Revise the criteria for loopinvariant hoistingto take account of this. Instead of writing something informal like "might not execute the statement", use the terminology of dataflow analysis and dominators.
• 18.8 On pages 385±385 the transformation of a while loop to a repeat loop is described. Show how a while loop may be characterized in the control-flow graph of basic blocks (using dominators) so that the optimizer can recognize it. The body of the loop may have explicit break statements that exit the loop.
• *18.9 For bounds-check elimination, we required (on page 392) that the loop-exit test dominate the bounds-check comparison. If it is the other way around, then (effectively) we have one extra array subscript at the end of the loop, so the criterion ak + i · bk ≤ 0 ∧ (nak) ≤ bj < (uaj) · bk

is "off by one." Rewrite this criterion for the case where the bounds-check comparison occurs before the loop-exit test.

• *18.10 Write down the rules for unrolling a loop, such that the induction-variable increments are agglomerated and the unrolled loop has only one loop-exit test per iteration, as was shown informally for Program 18.10.

 JaVa Previous    Next