Chapter 10 Exercises

1. Perform a strength reduction on:

  (a) A := 8 * I
  (b) A := I2

2. Assuming quadruple intermediate representation, write an algorithm to perform

(a) Constant folding as in Example 4

(b) Constant folding in Example 5

3. What changes need to be made to perform constant folding if the intermediate representation is an abstract syntax tree?

4. What other optimizations might be included in a general constant folding test?

5. Why is the statement X := Y + Z in Example 7 not loop-inariant?

6. Eliminate variable i in Example 12 by replacing the FOR loop with a WHILE loop, making all the appropriate changes.

7. Name some other strength reductions.

8. Can the following loops be fused?

LOOP I := 1 to 100
  A(I) := 0
ENDLOOP
LOOP I := 1 to 100
  A(I) = A(I) + Y
ENDLOOP

9. Write an algorithm to find and implement each of the following optimizations. Presume control flow analysis and data flow analysis have been performed and that there are procedures to call to find loop invariants and induction variables.

(a) Loop unrolling

(b) Loop fusion

(c) Unswitching

10. For the program in Section 9.4.

(a) Find the dominators.

(b) Perform a data flow analysis.

(c) Show that the two loops described are natural loops.

(d) Explain what information is needed (from (b) and (c)) in order to perform each of the optimizations discussed in Section 9.4.

or

(e) For each of the optimizations discussed, write an algorithm outline (using dominators, reaching definitions, live variable analysis, etc.) to find the optimization.

11. Following the outline in Section 9.4, create the basic blocks and the control flow graph, perform data flow analysis and optimize the following algorithm which performs an exchange sort:

LOOP FOR I := 1 TO N - 1
  Min := Listi
  Place := i
  LOOP FOR J := i + 1 to N
    IF Listj < Min THEN
      Place := J
      Min := Listj
    ENDIF
  ENDLOOP J
  Temp := Listi
  Listi := Listplace
  Listplace := Temp
ENDLOOP

12. Name other program invariances as discussed in Section 9.5.1

13. Using data flow analysis, show how a compiler might discover that a matrix is a diagonal matrix.

14. Create table entries for the following using the models in Section 9.5.6:

(a) algebraic simplifications such as multiplying by one and adding zero

(b) loop collapsing

(c) conditional pruning

(d) conditional reordering

(e) goto chasing

(f) elimination of array temporaries

(g) hoisting of loop-invariants

(h) induction-variable elimination

(i) replacement of loop conditional with a count up to 0

(j) movement of While test to loop end

(k) strip mining

(l) loop unrolling