Nonlinear and symbolic data dependence testing

One of the most crucial qualities of an optimizing compiler is its ability to detect when different data references access the same storage location. Such references are said to be data-dependent and they impose constraints o n the amount of program modifications the compiler can apply for improving the program's performance. For parallelizing compilers, the most important program constructs to investigate are loops and the array references they c ontain. In previous work. we have found a serious limitation of current dat a dependence tests to be that they cannot handle loop bounds or array subsc ripts that are symbolic, nonlinear expressions. 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 sy mbolic analyses and constraint propagation techniques were developed to pro ve such inequalities. The Range Test has been implemented in Polaris, a par allelizing compiler developed at the University of Illinois. We will presen t measurements of the Range Test's performance and compare it with state-of -the-art tests.