[LLVMdev] SIV tests in LoopDependence Analysis, Sanjoy's patch

[Preston Briggs]

Hi Sanjoy,

Thanks for the update.

I reworked the code for analyseWeakZeroSIV, fixing bugs and exploiting the
two special cases mentioned in the paper.
It's here:
https://sites.google.com/site/parallelizationforllvm/weak-zero-siv-test

I'll rework analyseWeakCrossingSIV soon. I'll send you a note when it's
ready.

The current code for analyseZIV is wrong, in that it sets

*       level->direction = Level::ALL;*
*      level->distance = diffSCEV;*
*      level->scalar = true;*

Doesn't make sense, since ZIV tests have no induction variable and
therefore no associated loop level.
Suggests some work on analyseSubscript (where it's assumed that the ZIV
test relates to a loop)
and analysePair, which makes the same assumption.

In analysePair, there's some code that finds the innermost loop containing
the source value and the innermost loop containing the destination value.
Then it decides that if neither contains the other, then no dependence
exists. That's not correct. Consider this example:

*for (i = 0; i < n; i++) {*
*  for (j = 0; j < m; j++)*
*    A[j][i] = ...*
*  for (k = 0; k < m; k++)*
*    A[k][i] = ...*
*}*


Wolfe writes:

*Data dependence distances and directions between the two bodies are
computed only for the common loops, those that surround both bodies.*


So, we'll expect to find a loop-independent output dependence from the 1st
store to the 2nd store, with direction vector [= | <]. And, since the outer
loop carries no dependence, we could safely run it in parallel. Even
better, we could fuse the two inner loops, then collapse the resulting
inner loop with the outer loop and run the whole thing in parallel :-)

Embellishing the example slightly

*
for (i = 0; i < n; i++) {*
*  for (j = 0; j < m; j++)*
*    A[j][i][0] = ...*
*  for (j = 0; j < m; j++)*
*    for (k = 0; k < n; k++)*
*      A[j][i][k] = ...*
*}*


we again find a loop-independent output dependence from the 1st store to
the 2nd store, with direction vector [= | <]. The extra loop nesting
doesn't change anything.

Here's a final variation:

*
for (i = 0; i < n; i++) {*
*  for (j = 0; j < m; j++)*
*    A[j][i][0] = ...*
*  for (j = 0; j < m; j++)*
*    for (k = 0; k < n; k++)*
*      A[j][i + 1][k] = ...*
*}*


This time there's a loop-carried output dependence from the 2nd store back
to the 1st store, with distance vector [1 | 0]. We found this by running
the Strong SIV test on the middle subscript and ignoring the other two,
since they don't refer to a common loop.

Finally, there's still no mention of loop-independent dependences. They're
important!  When the dependence test is invoked, we need to pass in a flag
indicating if a loop-independent dependence is possible; that is, if
control can flow from the source to the destination without traversing a
back edge. At the end of the dependence test, if dependence has not been
disproved and the flag is set, we need to examine the direction vector. If
all levels include the = direction, then we mark the dependence as loop
independent.

Preston




On Thu, Apr 12, 2012 at 5:14 AM, Sanjoy Das
<sanjoy at playingwithpointers.com>wrote:

> Hi,
>
> Here is a preliminary (monolithic) version you can comment on.  This
> is still buggy, however, and I'll be testing for and fixing bugs over
> the next few days.  I've used your version of the strong siv test.
>
> Thanks!
> --
> Sanjoy Das.
> http://playingwithpointers.com
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120412/2a62acc6/attachment.html>