Classical dependence analysis techniques: sufficiently accurate in practice

Data dependence analysis is the foundation of any parallelizing compiler. The GCD (greatest common divisor) test and the Banerjee-Wolfe test (U. Banerjee 1988, M. Wolfe 1989) are the two tests traditionally used to determine statement data dependence in automatic vectorization/parallelization of loops. These tests are approximate in the sense that they are necessary but not sufficient conditions for data dependence. In an earlier work (Proc. 6th ACM Int. Conf. Supercomputing, Washington, DC, USA, July 1992), we extended the Banerjee-Wolfe test and a combination of the GCD and Banerjee-Wolfe tests with a set of conditions to derive exact data dependence information. In this paper, we perform an empirical study on the Perfect benchmarks to demonstrate the effectiveness and practical importance of our conditions. We show that the Banerjee-Wolfe test extended with our conditions becomes an exact test for data dependence in actual practice