Wolfe tests to be perfectly accurate. In Section 5, we show how the results of Section 4 explain the accuracy of the Banerjee-Wolfe test in actual practice. In Section 6, we show that the sufficient conditions, for the accuracy of the Banerjee-Wolfe test and the accuracy of a combination of the GCD and the Banerjee-Wolfe tests, are necessary conditions as well. Finally, in Section 7, we conclude by showing how the previous results can be used in actual practice to obtain exact data dependence information.
2. DATA DEPENDENCE
Consider two statements, S 1 and S 2 (see Fig. 1), containing potentially conflicting references to p-dimensional array A. We assume that the subscript expressions are linear functions of the loop iteration variables, i.e.,
where each of v,0 , v,1 , v,2 , ..., v,r , v,rϩ1 , ..., v,s is an integer;
• for 1 Յ v Յ p, g v (I 1 , I 2 , ..., I r , I sϩ1 , ..., I t ) is a function of the form
where each of
Each iteration of a nest of loops is identified by an iteration vector whose elements are the values of the iteration variables for that iteration. A statement embedded in a nest of loops may be executed once for each iteration of the nest. Each potential execution of a statement is termed an instance of the statement. An instance of a statement is represented by the statement together with an iteration vector. For example, the instance of statement S 1 during iteration i ϭ (i 1 , i 2 , ..., i r , i rϩ1 , ..., i s ) is denoted S 1 (i) or S 1 (i 1 , i 2 , ..., i r , i rϩ1 , ..., i s ); the instance of statement S 2 during iteration j ϭ ( j 1 , j 2 , ..., j r , j sϩ1 , ..., j t ) is denoted S 2 (j) or S 2 ( j 1 , j 2 , ..., j r , j sϩ1 , ..., j t ).