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.2.
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
Exercise 8.4.2
Figure 8.11 is code to count the number of primes from 2 to n, using the sieve method on a suitably large array a. That is, a[i] is TRUE at the end only if there is no prime Vi or less that evenly divides i. We initialize all a[i] to TRUE and then set a\j] to FALSE if we find a divisor of j.
a) Translate the program into three-address statements of the type we have been using in this section. Assume integers require 4 bytes.
b) Construct the flow graph for your code from (a).
c) Identify the loops in your flow graph from (b).
Figure 8.11