Next: Region-Based Analysis Up: Analysis of Array Previous: Representation: Summaries

## Array Reshapes

Interprocedural array analysis must provide precise results in the presence of array reshapes at procedure boundaries, as when a slice of an array is passed into a procedure, and as in linearization, when a multi-dimensional array in one procedure is treated as a linear array in another. In the following example, FOO passes BAR the Kth column of the array X. This 10000-element vector from FOO, is manipulated as a array in BAR.

```      SUBROUTINE FOO                         SUBROUTINE BAR(Y)
INTEGER X(10000, 10)                   INTEGER Y(100, 100)
....                                      DO 9 I= 1,100
CALL BAR(X(1, K))                             DO 9 J= 1,50
Y(I,J) = ...
9   CONTINUE
```

Mapping an array summary from callee to caller is not a simple rename operation. We perform this mapping by deriving inequalities for the indices of the actual parameter in terms of the indices of the formal parameter and use the projection operation to eliminate the formal parameter's indices.

We formalize the mapping of summary S for an n-dimensional formal array parameter F, where is passed at the call site and actual A is an m-dimensional array, using the mapping function:

Where

• are variables representing the indices of accesses to array F.
• are variables representing the indices of accesses to array A.
• is the set of bounds for the array F given by its type declaration. (Note that the exact bounds of the outermost dimension are not required.)
• is the set of bounds for the array A given by its type declaration.
• describes the conditions under which an access in the procedure and an access in the callee refer to the same location. This occurs when the memory offset of is equal to the memory offset of minus the memory offset of . This relationship between memory offsets is represented as an equality relation; other known facts about variables used in the equality may be included in the system.
For the FOO, BAR example the mapping function is calculated using:

Thus when when using the mapping function on the summary of the array Y at the start of subroutine BAR:

This approach handles precisely cases where complex numbers in one procedure are treated as real numbers in another by modeling a complex number as an array with two elements. Some reshapes are not handled precisely. If array dimensions are unknown, for example, there is no linear relationship between the indices of the actual and formal parameters, and unless the unknown dimensions are identical, we must approximate.

Next: Region-Based Analysis Up: Analysis of Array Previous: Representation: Summaries

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