THE BANERJEE-WOLFE AND GCD TESTS ON EXACT DATA DEPENDENCE INFORMATION

The GCD test and the Banerjee-Wolfe test are the two tests traditional ly used to determine statement data dependence, subject to direction v ectors, in automatic vectorization/parallelization of loops. In an ear lier study, a sufficient condition for the accuracy of the Banerjee-Wo lfe test was stated and proved. In that work, we only considered the c ase of general data dependence, i.e., the case of data dependence with out direction vector information. In this paper, we extend the previou s result to the case of data dependence subject to an arbitrary direct ion vector. We also state and prove a sufficient condition for the acc uracy of a combination of the GCD and Banerjee-Wolfe tests. Furthermor e, we show that the sufficient conditions, for the accuracy of the Ban erjee-Wolfe test and the accuracy of a combination of the GCD and Bane rjee-Wolfe tests are necessary conditions as well. Finally, we demonst rate how these results can be used in actual practice to obtain exact data dependence information. (C) 1996 Academic Press, Inc.