Exact side effects for interprocedural dependence analysis

Abstract

Exact side effects of array references in subroutines are essential for exact interprocedural dependence analysis. To summarize the side effects of multiple array references, a collective representation of all the array elements accessed is needed. So far all existing forms of collective summary of side effects of multiple array references are approximate. In this paper, we present a method to represent the exact side effects of multiple array references in the form of the projection of a single integer programming problem. Since the representation is collective, it dramatically reduces the number of pairs of dependences checking compared with other methods of exact interprocedural analysis. The representation of the exact side effects proposed in this paper can be used by the Omega test to support the exact interprocedural dependence analysis in parallelizing compilers.