198:516  Homework 4, Spring 2006

1. Using the graph on slide #27 in the SSA lecture notes, please answer the
following questions:

a. On what node(s) is node 12 control dependent?

b. On what node(s) is node 4 control dependent?

c. What are the natural loops in this control flowgraph?

d. Is there a single edge we could remove to make node 4 postdominate node 2?
Explain briefly.

2. Fill in the table for iterated dominance frontier on slide #27 in the SSA 
lecture notes.

3. Given the following graph:

(1,2), (2,3), (2,7), (3,4), (3,6), (4,5), (5,3), (6,2)

which represents a nested loop, assume there are definitions of
variable X at nodes 1, 3, and 5. 

a. Show the dominator tree for this graph and its corresponding DJ graph

b. Calculate the iterated dominance frontier corresponding to the X
variable definition nodes, using the DJ graph approach discussed in
the SSA lecture.