Repeat Exercise 9.7.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. Fig. 9.3 Fig. 8.9 Exercise 9.7.1 For...

Repeat Exercise 9.7.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.

Fig. 9.3

Fig. 8.9

Exercise 9.7.1

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

i. Find all the possible regions. You may, however, omit from the list the regions consisting of a single node and no edges.

ii. Give the set of nested regions constructed by Algorithm 9.52.


Hi. Give a T\-T2 reduction of the flow graph as described in the box on "Where 'Reducible' Comes From" in Section 9.7.2.

Fig. 9.10

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