For the flow graph of Fig. 9.10 (see the exercises for Section 9.1): i. Compute the dominator relation. ii. Find the immediate dominator of each node. 1 0 D . E. Knuth, "An empirical study of FORTRAN...

For the flow graph of Fig. 9.10 (see the exercises for Section 9.1):

i. Compute the dominator relation.

ii. Find the immediate dominator of each node. 1 0


D . E. Knuth, "An empirical study of FORTRAN programs," Software — Practice and Experience 1:2 (1971), pp. 105-133.


Hi. Construct the dominator tree.

iv. Find one depth-first ordering for the flow graph.


v. Indicate the advancing, retreating, cross, and tree edges for your answer to iv.

vi. Is the flow graph reducible?

vii. Compute the depth of the flow graph.


viii. Find the natural loops of the flow graph.

Fig. 9.10