Practical dependence analysis in a SIMD vectorizing compiler

In this paper we present a new, fast and accurate exact data dependence test method with linear cost for array references with linear subscripts, which solves the two-dimensional dependence equation by the use of the Bresenham incremental line algorithm which has been primarily used in computer graphics. The presented method uses only integer calculations and is implemented in our SIMD vectorizing compiler.