next up previous
Next: Representation: Symbolic Maps Up: Scalar Data-Flow Analysis Previous: Scalar Data-Flow Analysis

Support for Array Analysis: Interprocedural Symbolic Analysis


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.

Saman Amarasinghe
Mon Oct 2 11:00:22 PDT 1995