On the perfect accuracy of an approximate subscript analysis test
David Klappholz, Kleanthis Psarris, Xiangyun Kong · ACM SIGARCH Computer Architecture News · 1990
The Banerjee test is commonly considered to be the more accurate of the two major approximate data dependence tests used in automatic vectorization/parallelization of loops, the other being the GCD test. From its derivation, however, there is no simple explanation of why the Banerjee test should be nearly as accurate as it is given credit for. We present a set of sufficient conditions for the Banerjee test's accuracy, and 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.