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 ` K`th 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.

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.

Mon Oct 2 11:00:22 PDT 1995