next up previous
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

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 up previous
Next: Region-Based Analysis Up: Analysis of Array Previous: Representation: Summaries



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