To precisely represent the array accesses in a loop (using an analysis such as the one to be described in Section 5) requires that array indices be rephrased in terms which are valid throughout the loop. Using traditional program analyses, a set of analyses of integer variable values is needed: constant propagation, induction and loop-invariant variable detection, and common subexpression recognition.
Our system provides the effect of such analyses through a single symbolic analysis, which is performed interprocedurally. For example, to parallelize the following loop:
K = J + 1
DO 10 I=1,N
A(J) = A(K)
J = J + 2
K = K + 2
10 CONTINUE
the array index
expressions in terms of loop-varying variables ( J and K)
are mapped into expressions in terms of normalized (base 0)
loop indices and loop invariants. In this particular loop, a new
loop-invariant variable 
is introduced to refer to the
value of J on entry to the loop and a base-0
iteration count variable i is introduced, local to the loop body.
J is found to have a value 
and
K a value 
.
Substituting these values into the array indices allows comparison of
the portions of array A read and written by the loop.
The symbolic analysis determines for each variable appearing in an array access a symbolic value: an arbitrary expression describing its value in terms of constants, loop-invariant variables, and normalized loop indices, if possible.
Array dependence analysis typically only handles affine array indices precisely; nevertheless, the symbolic values resulting from the symbolic analysis may be non-affine. In some cases our system is currently unable to make use of this non-affine information. In one common case of non-affine array indices---those resulting from a higher-order induction variable---we extract additional information which can be provided in an affine form, as discussed below.