Go to the first, previous, next, last section, table of contents.

Finding Direction Vectors

for i = 1 to N
   for j = i to N
      A[i] = A[j]

For the two accesses of the above loop nest, the following LIC script will find the set of direction vectors. The systems `iterr' and `iterw' represents the read and write iteration space and the system `access' is the relationship between the read and the write access. The entire system is given by intersecting the above three systems (`full'). For each possible direction vector, a system representing that vector is created. If that vector is valid, the system will have a solution (`intsol()' is 1).

iterr = [ 1 <= ir <= N 
          ir <= jr <= N ]

iterw = [ 1 <= iw <= N 
          iw <= jw <= N ]

access = [ iw  = jr ]

full = { iterr, iterw, access }

// [= =]
#level3 = { full 
           [ ir = iw
             jr = jw ] }
intsol(level3)

// [= +]
#level2a = { full 
           [ ir = iw
             jr > jw ] }
intsol(level2a)

// [= +]
#level2b = { full 
           [ ir = iw
             jr < jw ] }
intsol(level2b)

// [+ *]
#level1a = { full 
           [ ir > iw ] }
intsol(level1a)

// [+ *]
#level1b = { full 
           [ ir < iw ] }
intsol(level1b)

end

The printout of the example session:

csh> lic -c
Rapid Prototyping System for Code Generation
> < example2
iterr = [ 1 <= ir <= N
          ir <= jr <= N ]
N-jr >= 0
jr-ir >= 0
N-ir >= 0
-1+ir >= 0

iterw = [ 1 <= iw <= N
          iw <= jw <= N ]
N-jw >= 0
jw-iw >= 0
N-iw >= 0
-1+iw >= 0

access = [ iw  = jr ]
iw-jr >= 0
-iw+jr >= 0

full = { iterr, iterw, access }
N-jr >= 0
jr-ir >= 0
N-ir >= 0
-1+ir >= 0
N-jw >= 0
jw-iw >= 0
N-iw >= 0
-1+iw >= 0
-jr+iw >= 0
jr-iw >= 0

// [= =]
#level3 = { full
           [ ir = iw
             jr = jw ] }
intsol(level3)
1

// [= +]
#level2a = { full
           [ ir = iw
             jr > jw ] }
intsol(level2a)
0

// [= +]
#level2b = { full
           [ ir = iw
             jr < jw ] }
intsol(level2b)
1

// [+ *]
#level1a = { full
           [ ir > iw ] }
intsol(level1a)
0

// [+ *]
#level1b = { full
           [ ir < iw ] }
intsol(level1b)
1

end
 > quit
done(0)

csh>

Thus the set of direction vectors consist of [+ *], [= +] and [= =].

Go to the first, previous, next, last section, table of contents.