Lazy Array Data-Flow Dependence Analysis
抄録
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)