llvm dev - Mar 2012 - [LLVMdev] SIV tests in LoopDependence Analysis, Sanjoy's patch

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>

Hi Hal, Preston!

Sorry for the delay!  Got busy with some offline work.

I've worked on my previous code to calculate direction and distance
vectors whenever possible (strong SIV, basically).  I think the
current code is much clearer and would like your opinions on it.

I have attached the patch and also pushed to the github repo I
mentioned [1].

Thanks!

[1] https://github.com/sanjoy/llvm/tree/lda
-- 
Sanjoy Das.
http://playingwithpointers.com
-------------- next part --------------
A non-text attachment was scrubbed...
Name: lda.diff
Type: text/x-patch
Size: 35188 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120326/ab45b7ba/attachment.bin>

Hi Sanjoy,

Thanks for the update.

Reading through LoopDependenceAnalysis.h

   - I'd sure like to see some design documentation (this is true for most
   of the LLVM code I've seen). Tell us what the plan is, only then talk
about
   the implementation
   - I hate the names Subscript and Subscripts. Implies each entry
   corresponds to a subscript, but that's not true. Each entry corresponds
to
   a level in the loop nest. There may be several subscript pairs summarized
   in a single level entry. I'd suggest Level, or LoopLevel, or some such,
   more closely related to the literature. Indicating that entries are related
   to the loop nest, versus suggesting that they somehow correspond to
   subscripts (which are associated with memory references).

Your definition for Subscript has a Kind that's either Independent,
Dependent, or Unknown. This seems all wrong. If some level is independent,
then no dependence exists at all (not just at this level). Otherwise, there
will absolutely be a direction (3 bits) and perhaps a distance. I'd also
like to see a bit for Scalar, and perhaps a few more (see
here<https://sites.google.com/site/parallelizationforllvm/representing-dependences>).
Unknown isn't special; it just mean there's a dependence and any
direction
is possible. We indicate Unknown by setting all 3 bits in the direction
vector (same for Scalar). In this way, we can test for the validity of many
xforms by simply examining the direction vectors; don't need to look at
other flags.

The definition for Dependence should probably be a class with a number of
methods.
You currently have a field for Result.  Don't think it's useful.
On the other hand, I'd include Kind, one of Flow, Antri, Output, and Input.
You absolutely need a flag indicating the possibility of a loop-independent
dependence.
You need your vector of levels.
I think I'd include pointers to the source and destination here.
I'd have methods for things like:

   - bool confused(), returns true if all levels are <=>
   - bool consistent(), returns true is all levels are Scalar or have a
   distance
   - unsigned loopCarried(), return the level of the left-most non-equal
   direction

The methods could be implemented by a computation or by looking at a flag
that's computed once.

I'd very much like to see the dependence representation and tests separated
from the collection of dependences associated with a loop nest. People
working on loop nests will need to be able to access the associated
dependences in various ways (e.g., give me all the dependences carried by a
certain level) that you can't yet predict. Make 'em define their own
structures. You should focus on the tests.

I'd encourage more discussion (indeed, any discussion) of all this before
hacking up more code. Read the stuff I've written
here<https://sites.google.com/site/parallelizationforllvm/>and
comment, or I'll get you access and you can write directly That's not
to say what you've written is a waste; I think it's quite wonderful.
You've
implemented most of the tough parts and I'm confident it will all prove
useful in the final solution.

I'll review the actual implementation in LoopDependenceAnalysis.cpp in
another note.

Thanks,
Preston



On Sun, Mar 25, 2012 at 9:49 PM, Sanjoy Das
<sanjoy at playingwithpointers.com>wrote:
> Hi Hal, Preston!
>
> Sorry for the delay!  Got busy with some offline work.
>
> I've worked on my previous code to calculate direction and distance
> vectors whenever possible (strong SIV, basically).  I think the
> current code is much clearer and would like your opinions on it.
>
> I have attached the patch and also pushed to the github repo I
> mentioned [1].
>
> Thanks!
>
> [1] https://github.com/sanjoy/llvm/tree/lda
> --
> Sanjoy Das.
> http://playingwithpointers.com
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120327/3aef292e/attachment.html>

Hi Sanjoy,

In LoopDependenceAnalysis::AnalyzePair, what's going to happen if we have
something like this

for (i = 0; i < n; i++)
  for (j = 0; j < n; j++)
    A[i][j]++;


versus

for (i = 0; i < n; i++)
  for (j = 0; j < n; j++)
    A[j][i]++;


That is, will the ordering of the Subscripts in Subscript be different?
I don't think they should be. The ordering should correspond to the loops.
That is, results related to the i loop should appear first, then results
related to the j loop.

And what's going to happen here?


for (i = 0; i < n; i++)
    A[i+1][i+2] = A[i][i];


where there's 2 subscripts, but only one loop level?
We should analyze each pair of subscripts separately
and merge (intersect) results applying to the same loop level.
In this case, we should notice that there's no possible dependence.

And here?

for (i = 0; i < n; i++)
  for (j = 0; j < n; j++)
    A[i] = A[i] + B[i][j];


where A subscripts don't mention the j loop at all?
I would say there are 3 dependences:

   1. a loop-independent anti dependence with direction vector [0 S|<]
   2. a loop-carried flow dependence with direction vector [0 S|0]
   3. a loop-carried output dependence with direction vector [0 S|0]

You don't seem to have any scheme for handling these cases.
We should come up with something.

Preston


On Sun, Mar 25, 2012 at 9:49 PM, Sanjoy Das
<sanjoy at playingwithpointers.com>wrote:
> Hi Hal, Preston!
>
> Sorry for the delay!  Got busy with some offline work.
>
> I've worked on my previous code to calculate direction and distance
> vectors whenever possible (strong SIV, basically).  I think the
> current code is much clearer and would like your opinions on it.
>
> I have attached the patch and also pushed to the github repo I
> mentioned [1].
>
> Thanks!
>
> [1] https://github.com/sanjoy/llvm/tree/lda
> --
> Sanjoy Das.
> http://playingwithpointers.com
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120327/0b26178a/attachment.html>

Hi Sanjoy & Hal,

Looking at LoopDependenceAnalysis::analyzeZIV ...
I don't understand much about SCEV, but the code seems inadequate.
Consider these three examples:

int a = ...; // we can't be sure of the relationship between a and b
int b = ...; // perhaps they are parameters, or the result of I/O

for (int i = 0; i < n; i++) {
  v[a][i] = ...;
  v[a + 1][i] = ...;
}

for (int i = 0; i < n; i++) {
  v[a][i] = ...;
  v[a][i] = ...;
}

for (int i = 0; i < n; i++) {
  v[a][i] = ...;
  v[b][i] = ...;
}


In the first loop, we can be confident that the two stores are to different
locations and there is no dependence.

In the second loop, we can be sure that the two references are to the same
location and that there's a consistent loop-independent output dependence
between the two stores.

In the third loop, we can't be sure what's going on and must therefore
assume an inconsistent loop-independent output dependence.

The ZIVanalysis code doesn't do the right thing.  I believe, but am not
certain, that it will get the 1st two loops right, but will return
Independent for the 3rd case. Better code might look something like:

SCEV *delta = a - b
if (delta is zero) {
  consistant &= true
  return Dependent
}
else if (delta is a known constant)
  return Independent
}
else { // delta is some symbolic term
  consistent = false
  return Dependent
}


By the way, when I assert all these things about dependence analysis, I'm
not always correct. If you disagree, please let me know and we'll discuss
it.

Thanks,
Preston
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120328/a4bc2d0d/attachment.html>

Hi Sanjoy,

Reading through LoopDependenceAnalysis::analyseWeakZeroSIV(), it appears
you give up some information. Sometimes it's possible to prove that certain
directions aren't possible.

Consider this example

   for (i = 0; i < N; i++) {
1)   t = A[0];
2)   A[i] = t;
   }


There's a loop-carried flow dependence from (2) to (1) with distance vector
[<=|0] and a loop-independent anti dependence from (1) to (2) with distance
vector [=|<]. We should be able to find these using the Weak-Zero SIV test.

If the distance (difference of the two constant parts) is 0, as it is in
this case, the direction vector is either <= (if the bCoefficent is 0) or (if
the aCoefficient is 0).

What's cool about this case is that we can peel the first iteration and
remove the loop-carried dependence.

Here's similar case that happens a lot:


   for (i = 0; i < N; i++) {
1)   t = A[N - 1];
2)   A[i] = t;
   }


This time there's a loop-carried anti dependence from (1) to (2), with
distance vector [<=|<]. Again, we should be able to find this with the
Weak-Zero SIV test.

If the distance equals iterationCount - 1, as it does in this case, the
direction vector is either <= (if the aCoefficient is 0) or = (if the
bCoefficient is 0).

Again, we can do useful things here by peeling off the last iteration.

Make sense?

Thanks,
Preston




On Sun, Mar 25, 2012 at 9:49 PM, Sanjoy Das <sanjoy at
playingwithpointers.com>
wrote:
> Hi Hal, Preston!
>
> Sorry for the delay!  Got busy with some offline work.
>
> I've worked on my previous code to calculate direction and distance
> vectors whenever possible (strong SIV, basically).  I think the
> current code is much clearer and would like your opinions on it.
>
> I have attached the patch and also pushed to the github repo I
> mentioned [1].
>
> Thanks!
>
> [1] https://github.com/sanjoy/llvm/tree/lda
> --
> Sanjoy Das.
> http://playingwithpointers.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120404/2667e4d9/attachment.html>

Hi Sanjoy,

Reading through LoopDependenceAnalysis::analyseStrongSIV(), I noticed one
problem and one confusion.

My confusion related to your naming of the two instructions as A and B.
It's consistent all through LoopDependenceAnalysis. I'd prefer something
like source and destination, so I can keep track of which is which. It
didn't matter so much when you were simply proving or disproving
dependence, but when you compute direction, it's suddenly crucial.

The problem is the computation of direction from distance. The code says:

if (distance->isZero())
  S->Direction = Subscript::EQ;
else if (isGT)
  S->Direction = Subscript::GT;
else
  S->Direction = Subscript::LT;


While it looks sensible, it's incorrect. Correct is


if (distance->isZero())
  S->Direction = Subscript::EQ;
else if (isGT)
  S->Direction = Subscript::LT; // !!
else
  S->Direction = Subscript::GT; // !!


The Delta test paper (Section 1.3) and the 1st printing of Allen & Kennedy
(Definition 2.10) are similarly incorrect.
See http://www.elsevierdirect.com/companion.jsp?ISBN=9781558602861
particularly the replacement for page 46.

I'm also confused about the math, but I'll keep working on it.

Thanks,
Preston



On Sun, Mar 25, 2012 at 9:49 PM, Sanjoy Das <sanjoy at
playingwithpointers.com>
wrote:
> Hi Hal, Preston!
>
> Sorry for the delay!  Got busy with some offline work.
>
> I've worked on my previous code to calculate direction and distance
> vectors whenever possible (strong SIV, basically).  I think the
> current code is much clearer and would like your opinions on it.
>
> I have attached the patch and also pushed to the github repo I
> mentioned [1].
>
> Thanks!
>
> [1] https://github.com/sanjoy/llvm/tree/lda
> --
> Sanjoy Das.
> http://playingwithpointers.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120405/2d6e8e30/attachment.html>