The range test: a dependence test for symbolic, non-linear expressions
William Blume, Rudolf Eigenmann · 1994
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. 1 Introduction To allow sequential programs to run efficiently on parallel machines, parallelizing compilers were developed to transform these programs into parallel ones [3]. These compilers must be able to identify the important loops that can be run in parallel if they are to achieve decent speedups. Powerful dependence tests are needed to effectively exploit the inhere...