Gents,<br><br>I spent some time reading over Sanjoy's patch for LoopDependenceAnalysis. Unfortunately, an early version of these notes escaped; this is the complete review.<br><br>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.<br>
<br>My biggest problem is with the choice (not Sanjoy's, I think) of implementing <i>Loop</i>DependenceAnalysis as a <i>Loop</i>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: <a href="https://sites.google.com/site/parallelizationforllvm/" target="_blank">https://sites.google.com/site/parallelizationforllvm/</a><br>
<br>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:<br><ol><li>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</li>
<li>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).</li></ol>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.<div>
<br></div><div>Remember that a single pair can end up with several dependences.</div><div><br></div><div>Remember loop-independent dependences.</div><div><br></div><div>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.<br>
<br></div><div>More detailed comments follow below.</div><div><br></div><div>Preston</div><div><br></div><div><br></div><div>LoopDependenceAnalysis.h</div>
<div><ul><li>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?</li>
<li>findOrInsertDependencePair() - insert into what? Could use some comments explaining whats going on here</li><li>cache should perhaps not be based on pairs of <i>instructions</i>, but on pairs of <i>subscripts, </i>since the anlysis for A[i] and A[i+1] is exactly the same as the analysis for B[i] and B[i + 1]</li>
</ul></div><div><br></div><div>LoopDependenceAnalysis.cpp</div><div><ul><li>AnalyzePair</li><ul><li>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.</li>
<li>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.</li><li>Of course, this is the place to accumulate and merge direction vectors.</li>
</ul><li>isSIVPair</li><ul><li>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).</li>
</ul><li>analyzeSIV</li><ul><li>annoying to search for common loop again, since we had to find it to arrive here</li><li>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</li>
<li>the actual tests look ok</li>
</ul></ul></div><div>Result types for analyzePair and analyzeSubscript (and analyzeSIV, at al.) should probably be different.</div><div><br></div>