The range test: a dependence test for symbolic, non-linear expressions

Abstract

Most current data dependence tests cannot handle loop bounds or array subscripts that are symbolic, nonlinear expressions (e.g. A (n*i+j), where 0 ≤ j ≤ n). In this paper, we describe a dependence test, called the range test, that can handle such expressions. Briefly, the range test proves independence by determining whether certain symbolic inequalities hold for a permutation of the loop nest. Powerful symbolic analyses and constraint propagation techniques were developed to prove such inequalities. The range test has been implemented in Polaris, a parallelizing compiler being developed at the University of Illinois.