Traditional data dependence analysis solves an integer programming problem for every pair of array accesses in a loop of interest. This analysis becomes prohibitively expensive for very large loops, particularly in the interprocedural setting. One way to improve efficiency is to summarize the array accesses in a region of code; a data dependence analysis is then applied to a small number of summaries. The summaries also provide the representation used by the array data-flow analysis, described below.
There have been many different designs of summaries that trade off efficiency and precision [13,14,18,24]. We represent a summary of a set of array accesses by a list of systems of linear inequalities: the array indices are equated to affine expressions of outer loop indices and loop-invariant values, constrained further by inequalities derived from the loop bounds. The representation of data accesses as a set of systems allows us to trade off precision for efficiency where necessary. For example, union of two summaries combines two systems into one only if it is computationally inexpensive and no loss of information results. Further, representing multiple regions for an array is essential to capture the examples from Figure 2(c)-(d); representing the array summaries as convex hulls would not have the necessary precision.
We create a summary of an access outside an enclosing loop by projecting away the loop index variable, using a Fourier-Motzkin projection that has been enhanced for the integer domain. We similarly transform an access summary across a procedure call by equating array subscript variables in the formal parameter to the subscript variables in the actual parameter, further constrained by the declared types for both formal and actual. Projection eliminates the formal parameter subscripts and replaces them with the actual parameter subscripts. This strategy for transforming summaries across procedure boundaries provides a general mechanism for analyzing array reshapes, where the number or size of array dimensions are altered at a call. A similar approach to array reshapes has also recently been adopted by Creussilet .