Go to the first, previous, next, last section, table of contents.
dimension A(100, 100)
do i = 1, 100
do j = 1, 25
call foo(A(10, i))
A(j, i) =
enddo
enddo
subroutine foo(B)
dimension B(50)
do k = 30, 50
= B(k)
enddo
The access `B(k)' and the access `A(p, q)' may be dependent, but without knowing the relationship between the accesses it is difficult to find this fact. In this script the relationship between two accesses is found. Then the existence of a dependence between two references is checked.
// base = A(10, i)
#callA = [ 100*i + 10 = base ]
// acc = A(j, i)
#accessA = [ 100 * i + j = acc ]
#dimA = [ 1 <= j <= 100
1 <= i <= 100 ]
// acc = B(k) + base
#accessB = [ acc = k + base ]
#dimB = [ 1 <= k <= 50 ]
#full = {callA, accessA, dimA, accessB, dimB}
#full = full.order(i j k base acc)
#full = full.project(acc)
#full = full.project(base)
// relationship
full.simplify()
#iterA = [ 1 <= i <= 100
1 <= j <= 25 ]
#iterB = [ 30 <= k <= 50 ]
#full = {iterA, callA, accessA, dimA, iterB, accessB, dimB}
// is dependent
full.realsol()
end
The printout of the example session:
csh> lic -c
Rapid Prototyping System for Code Generation
> < example7
// base = A(10, i)
#callA = [ 100*i + 10 = base ]
// acc = A(j, i)
#accessA = [ 100 * i + j = acc ]
#dimA = [ 1 <= j <= 100
1 <= i <= 100 ]
// acc = B(k) + base
#accessB = [ acc = k + base ]
#dimB = [ 1 <= k <= 50 ]
#full = {callA, accessA, dimA, accessB, dimB}
#full = full.order(i j k base acc)
#full = full.project(acc)
#full = full.project(base)
// relationship
full.simplify()
-1+i >= 0
100-i >= 0
60-j >= 0
-11+j >= 0
10-j+k >= 0
-10+j-k >= 0
#iterA = [ 1 <= i <= 100
1 <= j <= 25 ]
#iterB = [ 30 <= k <= 50 ]
#full = {iterA, callA, accessA, dimA, iterB, accessB, dimB}
// is dependent
full.realsol()
0
end
> quit
done(0)
csh>
From the simplified system we find that `A(k+25, i)' is the same as `B(k)'. Thus `A(k+25, i)' can be used instead of `B(k)' in checking the dependence between two accesses.
After formulating the dependence question by incorporating the loop bounds we find that the two accesses are independent.
Go to the first, previous, next, last section, table of contents.