Gents,
I spent some time reading over Sanjoy's patch for LoopDependenceAnalysis.
Unfortunately, an early version of these notes escaped; this is the
complete review.
First off, I agree with his choice to implement the SIV
tests. For scientific Fortran, the SIV (and the simpler ZIV) tests cover
about 85% of the cases in practice. For C and C++, I expect the percentage
will be much higher. Someday we might like to see the general SIV test and
handling of MIV subscripts, but we can get a long ways without them. It was
my intention to implement exactly these tests, but Sanjoy is way ahead of
me.
My biggest problem is with the choice (not Sanjoy's, I think)
of implementing *Loop*DependenceAnalysis as a *Loop*Pass. Dependence
analysis needn't be restricted to loop nests. I'd like to
see DependenceAnalysis for an entire function, so we can do things like
loop fusion, scheduling, etc. In particular, we should be able to test for
dependence between references in disjoint loops. Here's an (incomplete)
description of what I'm thinking:
https://sites.google.com/site/parallelizationforllvm/
In the large, I think we want to build a dependence graph for an
entire function, with edges for dependences, annotated with
direction/distance info. I imagine the code divided into 2 big chunks:
1. the dependence graph builder, that walks around the code looking
for interesting pairs of references, calling the dependence tester,
and assembling the results into a dependence graph
2. the dependence tester, that takes a pair of references and tests them
for dependence, computing direction/distance vectors when possible (very
close to what Sanjoy has built).
In the meantime, I agree with Sanjoy's idea that a great next step would be
to compute direction vectors (distance vectors when possible, strong SIV).
I'd reorganize things a bit, maybe, so we return NULL for proven
independence and a pointer for a dependence description otherwise,
including a direction/distance vector with an entry for all common loops
(or potentially common loops, in case of loop fusion). Entries in the
vector should include <, =, > (and combos like <=) and distances, but also
entries for Scalar and Unknown.
Remember that a single pair can end up with several dependences.
Remember loop-independent dependences.
Might make provision finding input dependences. They're expensive
(typically lots of them), but very useful to guide restructuring to improve
use of cache and registers.
More detailed comments follow below.
Preston
LoopDependenceAnalysis.h
- comment about isAffine() seems wrong. Consider A[2*i + 3*j + 10],
where i and j are both induction variables in the loop nest. Isn't that
affine?
- findOrInsertDependencePair() - insert into what? Could use some
comments explaining whats going on here
- cache should perhaps not be based on pairs of *instructions*, but on
pairs of *subscripts, *since the anlysis for A[i] and A[i+1] is exactly
the same as the analysis for B[i] and B[i + 1]
LoopDependenceAnalysis.cpp
- AnalyzePair
- should check for mod-ref info with calls, so we can take advantage
of any available interprocedural analysis. For example, if we have a load
from A[i] and a call, you immediately give up and call it
Unknown.. That's
pessimistic; we should make sure that A is modified by the call.
- when analyzing subscript pairs, if a result is Unknown, you give
up. That's pessimistic; you should look at remaining subscript pairs too.
If one proves Independent, then there's no dependence.
- Of course, this is the place to accumulate and merge direction
vectors.
- isSIVPair
- only works with single loop nest. We'd prefer that it also work
with disjoint loops too, so we can do loop fusion. See Wolfe's
"Optimizing
Supercompilers for Supercomputers", page 18 and chapter 5.
Instead of a set
of Loop *, accumulate a set of loop levels (ints).
- analyzeSIV
- annoying to search for common loop again, since we had to find it
to arrive here
- want to be able to analyze references in disjoint loops as if
already fused; will need to adapt SIV tests, since loop bounds aren't
always available
- the actual tests look ok
Result types for analyzePair and analyzeSubscript (and analyzeSIV, at al.)
should probably be different.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120319/962521c8/attachment.html>