compiler optimization - GCD test - to test dependency between loop statements -

i understand how gcd works on trivial example below:

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

we first transform following form: x[a*i + b] , x[c*i + d]

a=2, b=3, c=2, d=0 , gcd(a,c)=2 , (d-b) -3. since 2 not divide -3, no dependence possible.

but how can gcd test on doubly nested loop?

for example:

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

while subscripts can delinearized, gcd test simple apply directly. in example, subscript pair [1+2*i + 20*j] , [2+20*i + 2*j], we're looking integer solution equation

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

rearranging, get

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

compute gcd of coefficients, 2, -20, 20, , -2, , see if divides constant. in case, gcd 2. since 2 doesn't divide 1, there's no dependence.