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 on 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 contain. In previous work, we have found a serious limitation of current data dependence tests to be that they cannot handle loop bounds or array subscripts 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 symbolic analyses and constraint propagation techniques were developed to prove such inequalities. The range test has been implemented in Polaris, a parallelizing compiler developed at the University of Illinois. We present measurements of the range test's performance and compare it with state-of-the-art tests.

We have identified symbolic analysis techniques that will improve the effectiveness of parallelizing Fortran compilers, with emphasis upon data dependence analysts. We have done this by comparing the automatically and manually parallelized versions of the Perfect Benchmarks®. The techniques include: symbolic data dependence tests for nonlinear expressions, constraint propagation, array summary information, and run time tests.

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/spl les/j/spl les/n). 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.>

The speedups of the Perfect Benchmarks codes that result from automatic parallelization are reported. The performance gains caused by individual restructuring techniques have also been measured. Specific reasons for the successes and failures of the transformations are discussed, and potential improvements that result in measurably better program performance are analyzed. The most important findings are that available restructurers often cause insignificant performance gains in real programs and that only few restructuring techniques contribute to this gain. However, it can be shown that there is potential for advancing compiler technology so that many of the most important loops in these programs can be parallelized.>