3.1 Introduction

Dependence testing is the method used to determine whether dependences exist between two subscripted references to the same array in a loop nest. Calculating data dependence for arrays is complex because arrays contain many different locations. This chapter provides detailed descriptions of methods for high-precision dependence testing. For the purposes of this explication, control flow (other than the loops themselves) is ignored.

Recall from Chapter 2 that dependence testing in almost full generality can be illustrated by the problem of determining whether a dependence exists from statement S ₁ to statement S ₂ in the following model loop nest:

    DO i<sub1</sub> = L<sub1</sub>, U<sub1</sub>       DO i<sub2</sub> = L<sub2</sub>, U<sub2</sub>          ...          DO i<subn</sub> = L<subn</sub>, U<subn</sub>S<sub1</sub>              A(f<sub1</sub>(i<sub1</sub>,...,i<subn</sub>),...,f<subm</sub>(i<sub1</sub>,...,i<subn</sub>)) = ...S<sub2</sub>              ... = A(g<sub1</sub>(i<sub1</sub>,...,i<subn</sub>),...,g<subm</sub>(i<sub1</sub>,...,i<subn</sub>))           ENDDO          ...       ENDDO    ENDDO

Let a and b be iteration vectors within the iteration space of the loop nest described above. Thus, a and b are vectors of length n, the kth entry of which is an integer value between the lower and upper bounds of the kth loop in the nest.