GCD test - to test dependency between loop statements

I understand how the GCD works on a trivial example as below:

for(i=1; i<=100; i++)
{
        X[2*i+3] = X[2*i] + 50;
}

we first transform it into the following form: X[a*i + b] and X[c*i + d]

a=2, b=3, c=2, d=0 and GCD(a,c)=2 and (d-b) is -3. Since 2 does not divide -3, no dependence is possible.

But how can we do this GCD test on a doubly nested loop?

F开发者_StackOverflow社区or example:

for (i=0; i<10; i++){
   for (j=0; j<10; j++){
       A[1+2*i + 20*j] = A[2+20*i + 2*j);
    }
}

While the subscripts can be delinearized, the GCD test is simple to apply directly. In your example, the subscript pair is [1+2*i + 20*j] and [2+20*i + 2*j], so we're looking for an integer solution to the equation

1 + 2*i + 20*j = 2 + 20*i' + 2*j'

Rearranging, we get

2*i - 20*i' + 20*j - 2*j = 1

Compute the GCD of all the coefficients, 2, -20, 20, and -2, and see if it divides the constant. In this case, the GCD is 2. Since 2 doesn't divide 1, there's no dependence.

The "easy" way to apply GCD in the nested loop case is to apply it only in cases where the arrays themselves are multidemsional; i.e., the original source code uses multiple subscripts rather than already linearized expressions. Of course if you can "back transform" these linearized subscripts then you'll have the equivalent.

Once you've cast the problem as a multidemsional problem then you may simply apply the GCD test "dimension by dimension". If any dimension shows no dependence then you can stop and declare there is no dependence for the entire multidemsional subscripting sequence.

The key of course is that casting as a multidimensional indexing problem gives you the nice property that there's a one-to-one mapping between individual index values and the corresponding index expression tuples. Without this the problem is harder.

This is the approach I took in the ASC Fortran vectorizing compiler back in the 70's and it worked pretty well, particularly used in conjunction with directional subscript analysis for the non disjoint case. The GCD test by itself is really not sufficient, but it does give you a relatively inexpensive way of making an early decision in your analysis in those cases where you then can avoid the more expensive dependence analysis.