A formal study of data dependence analysis for parallelizing compilers
Kleanthis Psarris · 1991
The question of whether a loop may be parallelized/vectorized depends upon the resolution of array aliases to determine statement data dependence. The most widely used approximate subscript analysis tests are the GCD test and the Banerjee test. The Banerjee test is commonly considered to be the more accurate of the two tests. From its derivation, however, there is no simple explanation why and how accurate it is. We state and prove a set of necessary and sufficient conditions for the Banerjee test's accuracy. We explain its perceived accuracy in actual practice by proving that under circumstances which occur extremely frequently in actual code, the Banerjee test is, in fact, not approximate but perfectly accurate. We also prove a set of necessary and sufficient conditions for the accuracy of a combination of the GCD and the Banerjee test.