Automatic parallelization of real FORTRAN programs does not live up to users expectations yet, and dependence analysis algorithms which either produce too many false dependences or are too slow to contribute significantly to this. In this paper we introduce dataflow dependence analysis algorithm which exactly computes value-based dependence relations for program fragments in which all subscripts, loop bound and IF conditions are affine. Our algorithm also computes good affine approximations of dependence relations for non-affine program fragments. Actually, we do not know about any other algorithm which can compute better approximations.

Exact and efficient data dependence testing is a key to success of loop-parallelizing compiler for computationally intensive programs. A number of algorithms has been created to test array references contained in parameter loops for dependence but most of them are unable to answer the following question correctly: Are references C(i1 + 10j1) and C(i2 + 5), 0 ≤ i1, i2 ≤ 4, 0 ≤ j1,j2 ≤ 9 independent? The technique introduced in this paper recognizes that i1, i2 and j1, j2 make different order contributions to the subscript index, and breaks dependence equation i1 + 10j1 = i2 + 10j2 + 5 into two equations i1 = i2 and 10j1 = 10j2 which then can be solved independently. Since resulting equations contain less variables it is less expensive to solve them. We call this technique delinearization because it is reverse of the linearization much discussed in the literature.