Lazy Array Data-Flow Dependence Analysis

Abstract

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 contribute significantly to this. In this paper we introduce data-flow dependence analysis algorithm which exactly computes value-based dependence relations for program fragments in which all subscripts, loop bounds 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. And our algorithm is efficient too, because it is lazy. When searching for write statements that supply values used by a given read statement, it starts with statements which are lexicographically close to the read statement in iteration space. Then if some of the read statement instances are not ``satisfied'' with these close writes, the algorithm broadens its search scope by looking into more distant writes. The search scope keeps broadening until all read instances are satisfied or no write candidates are left. We timed our algorithm on several benchmark programs and the timing results suggest that our algorithm is fast enough to be used in commercial compilers --- it usually takes 5 to 15 percent of f77 -O2 compilation time to analyze a program. Most programs in the 100-line range take less than 1 second to analyze on a SUN SparcStation IPX. (Also cross-referenced as UMIACS-TR-93-69)