TABLE OF CONTENTS This section develops an algorithm for performing scalar replacement based on the simple principles developed earlier. The first step in the process involves pruning the dependence graph of extraneous dependences, so that each dependence can be used as a precise measure of gain in memory reuse. Later sections then extend the principles to handle more general dependences.
In this section we will present an algorithm for pruning the dependence graph so that each dependence edge represents a possible elimination of a load or a store. The problem is illustrated by the following code:
DO I = 1, NS<sub1 </sub>A(I+1) = A(I-1) + B(I-1)S<sub2 </sub>A(I) = A(I) + B(I) + B(I+1) ENDDO
The dependence patterns for A and B in this example are interesting. The assignment to A(I+1) in statement S 1 reaches the use of A(I) in statement S 2 but not the use of A(I 1) in statement S 1 because it is killed by the assignment in statement S 2. The location used in S 2 at the reference to B(I+1) is reused in S 2 an iteration later and again in S 1 on a third iteration.
The dependences before and after pruning are shown in Figure 8.2. The edges remaining after pruning are shown as solid lines. The dashed edges would be produced by dependence testing the normal way, but would...
