GCD test

GCD Test

This is test used in compiler theroy to test the dependency between loop statements,if two statements are indexing to same array using same index variable,then this test can be conducted to test wheather there is any dependency between the statement.The test is carried out as followed. Loop code in general:

for (int i=0;i<n;i++) {

s1   a[x*i+k] = b[i]; 
s2   c[i] = a[y*i+m];                

}

if gcd(x,y) divides (m-k) then it can be said that there may be some dependency in the loop statement s1 and s2

for example:Code in C

for(int i=0;i<100;i++) {

s1 a[2*i]=b[i];
s2 c[i]=a[4*i+1];

}

gcd of(2,4) is 2 and dividend is 1.As 2 can not divide 1 properly(leaving remainder zero),there is no dependency between s1 and s2 and varoous other loop transformation methods can be applied.

source of information is book on Advanced compiler design and implementation by Steven S Muchnick