Repeat Exercise 9.6.1 on the following flow graphs: a) Fig. 9.3. b) Fig. 8.9. c) Your flow graph from Exercise XXXXXXXXXXd) Your flow graph from Exercise 8.4.1. Exercise 9.6.1 For the flow graph of...

Repeat Exercise 9.6.1 on the following flow graphs: a) Fig. 9.3. b) Fig. 8.9. c) Your flow graph from Exercise 8.4.1. d) Your flow graph from Exercise 8.4.1.

Exercise 9.6.1

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

Fig. 9.3

Fig. 8.9

Exercise 8.4.1

Figure 8.10 is a simple matrix-multiplication program.


a) Translate the program into three-address statements of the type we have been using in this section. Assume the matrix entries are numbers that require 8 bytes, and that matrices are stored in row-major order.


b) Construct the flow graph for your code from (a).

c) Identify the loops in your flow graph from (b).

Figure 8.10