Array Data Dependence Testing with the Chains of Recurrences Algebra

This paper presents a new approach to dependence testing in the presence of nonlinear and non-closed array index expressions and pointer references. The chains of recurrences formalism and algebra is used to analyze the recurrence relations of induction variables, and for constructing recurrence forms of array index expressions and pointer references. We use these recurrence forms to determine if the array and pointer references are free of dependences in a loop nest. Our recurrence formulation enhances the accuracy of standard dependence algorithms such as the extreme value test and range test. Because the recurrence forms are easily converted to closed forms (when they exist), induction variable substitution and array recovery can be delayed until after the loop is analyzed