There are a number of data dependence tests that have been proposed in the literature. In each test there is a different trade-off between accuracy and efficiency. The most widely used approximate data dependence tests are the Banerjee inequality and the GCD test; whereas the Omega test is a well-known exact data dependence test. In this paper we consider parallelization for microprocessors with a multimedia extension (the short SIMD execution model). For the short SIMD parallelism extraction it is essential that, if dependency exists, then the dependence distance is greater than or equal to the number of data processed in the SIMD register. This implies that some loops that could not be vectorized on traditional vector processors can still be parallelized for the short SIMD execution. In all of these tests the parallelization would be prohibited when actually there is no parallelism restriction relating to the short SIMD execution model.

In this paper we present a new, fast and accurate data dependence test (D-test) for array references with linear subscripts, which is used in a vectorizing compiler for microprocessors with a multimedia extension. Our method extends Banerjee test in such a way that the dependence analysis will be correct in many cases where dependence exists with the dependence distance that is greater than or equal to the number of data processed in the SIMD register. These special cases in which Banerjee test fails to prove the independece can than be attacked with D-test.