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

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 --------------
A non-text attachment was scrubbed...
Name: patch.diff
Type: application/octet-stream
Size: 40632 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120412/261b2eb9/attachment.obj>

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>

Hi Sanjoy,

Here's a slightly fixed & improved version of the weak-crossing SIV
test:
https://sites.google.com/site/parallelizationforllvm/weak-crossing-siv-test

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/20120413/873af082/attachment.html>

Hi Sanjoy,

Here's a version of Banerjee and Wolfe's Exact SIV test:
https://sites.google.com/site/parallelizationforllvm/weak-siv-test
It assumes you've already filtered out the easy cases handled by ZIV,
strong SIV, etc.

I'm not confident about my uses of APInt. If you have any comments, I'd
love to hear them.

Thanks,
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/20120418/d907bc6a/attachment.html>

On Wed, 18 Apr 2012 18:16:47 -0700
Preston Briggs <preston.briggs at gmail.com> wrote:
> Hi Sanjoy,
> 
> Here's a version of Banerjee and Wolfe's Exact SIV test:
> https://sites.google.com/site/parallelizationforllvm/weak-siv-test
> It assumes you've already filtered out the easy cases handled by ZIV,
> strong SIV, etc.
> 
> I'm not confident about my uses of APInt. If you have any comments,
> I'd love to hear them.
Are you worried about properly setting the bit lengths, or about loss
of generality by restricting to constants? I've not thought about this
too deeply, but are there cases where some or all of the relevant
inputs are not constants, but yet we can still determine whether the
expressions involving them satisfy the required inequalities? One of
the nice things about SCEV is its ability, to some extent, to handle
and simplify "algebraic" expressions, and if appropriate, I think we
should use that ability.

Thanks again,
Hal
> 
> Thanks,
> 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
> >


-- 
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory

Hi,

When I write various test cases and explore how they're handled by the code
in LoopDependenceAnalysis::analysePair, I'm surprised. This loop collects
pairs of subscripts from the source and destination refs.

*  // Collect GEP operand pairs (FIXME: use GetGEPOperands from BasicAA),
adding*
*  // trailing zeroes to the smaller GEP, if needed.*
*  GEPOpdsTy destOpds, srcOpds;*
*  for(GEPOperator::const_op_iterator destIdx = destGEP->idx_begin(),*
*                                     destEnd = destGEP->idx_end(),*
*                                     srcIdx = srcGEP->idx_begin(),*
*                                     srcEnd = srcGEP->idx_end();*
*      destIdx != destEnd && srcIdx != srcEnd;*
*      destIdx += (destIdx != destEnd), srcIdx += (srcIdx != srcEnd)) {*
*    const SCEV* destSCEV = (destIdx != destEnd) ? SE->getSCEV(*destIdx) :*
*      GetZeroSCEV(SE);*
*    destOpds.push_back(destSCEV);*
*    const SCEV* srcSCEV = (srcIdx != srcEnd) ? SE->getSCEV(*srcIdx) :*
*      GetZeroSCEV(SE);*
*    srcOpds.push_back(srcSCEV);*
*  }*


But in my various test cases, I never see the loop iterate more than once.
That is, there always seems to be exactly 1 index.  Here's a typical test
case:

*i**nt zap2(long int n, long int A[][n]) {*
*  long int sum = 0;*
*  for (long int i = 0; i < n; i++)*
*    for (long int j = i; j < n; j++)*
*      sum += A[i][j];*
*  return sum;*
*}*


Any ideas about what I'm doing wrong? Could it be that I'm not running
certain important passes?  Here's my current list:

*-basicaa -mem2reg -simplifycfg -loop-simplify -loop-rotate -simplifycfg
-instcombine*


Thanks,
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/20120423/cb4a1044/attachment.html>

Perhaps this is really a question related to Clang or the IR.
When I try a slightly different source file, I indeed get a multi-index GEP.
Here are two test cases:

*int zap2(long int n, long int A[][n]) {*
*  long int sum = 0;*
*  for (long int i = 0; i < n; i++)*
*    for (long int j = i; j < n; j++)*
*      sum += A[i][j];*
*  return sum;*
*}*
*
*
*
*
*int zip2(long int n, long int A[][90]) {*
*  long int sum = 0;*
*  for (long int i = 0; i < n; i++)*
*    for (long int j = i; j < n; j++)*
*      sum += A[i][j];*
*  return sum;*
*}*


Here's what I see for the first case:

*  %cmp4 = icmp sgt i64 %n, 0*
*  br i1 %cmp4, label %for.cond1.preheader, label %for.end7*
*  %i.06 = phi i64 [ %inc6, %for.inc5 ], [ 0, %entry ]*
*  %sum.05 = phi i64 [ %sum.1.lcssa, %for.inc5 ], [ 0, %entry ]*
*  %cmp21 = icmp slt i64 %i.06, %n*
*  br i1 %cmp21, label %for.body3, label %for.inc5*
*  %j.03 = phi i64 [ %inc, %for.body3 ], [ %i.06, %for.cond1.preheader ]*
*  %sum.12 = phi i64 [ %add, %for.body3 ], [ %sum.05, %for.cond1.preheader ]
*
*  %0 = mul nsw i64 %i.06, %n*
*  %arrayidx.sum = add i64 %0, %j.03*
*  %arrayidx4 = getelementptr inbounds i64* %A, i64 %arrayidx.sum*
*  %1 = load i64* %arrayidx4, align 8*
*  ...*


And here's what I see for the second case:

*  %cmp4 = icmp sgt i64 %n, 0*
*  br i1 %cmp4, label %for.cond1.preheader, label %for.end7*
*  %i.06 = phi i64 [ %inc6, %for.inc5 ], [ 0, %entry ]*
*  %sum.05 = phi i64 [ %sum.1.lcssa, %for.inc5 ], [ 0, %entry ]*
*  %cmp21 = icmp slt i64 %i.06, %n*
*  br i1 %cmp21, label %for.body3, label %for.inc5*
*  %j.03 = phi i64 [ %inc, %for.body3 ], [ %i.06, %for.cond1.preheader ]*
*  %sum.12 = phi i64 [ %add, %for.body3 ], [ %sum.05, %for.cond1.preheader ]
*
*  %arrayidx4 = getelementptr inbounds [90 x i64]* %A, i64 %i.06, i64 %j.03*
*  %0 = load i64* %arrayidx4, align 8*
*  ...*


Why can't the first case (which is what scientific programmers will want to
write) be more like the second (which is sadly limited)? My guess is that
GEP can't represent it.

Too bad for the dependence analyzer; we'll have to jump through more hoops
to recover the subscripts.

Preston






On Mon, Apr 23, 2012 at 4:01 PM, Preston Briggs <preston.briggs at
gmail.com>wrote:
> Hi,
>
> When I write various test cases and explore how they're handled by the
> code in LoopDependenceAnalysis::analysePair, I'm surprised. This loop
> collects pairs of subscripts from the source and destination refs.
>
> *  // Collect GEP operand pairs (FIXME: use GetGEPOperands from BasicAA),
> adding*
> *  // trailing zeroes to the smaller GEP, if needed.*
> *  GEPOpdsTy destOpds, srcOpds;*
> *  for(GEPOperator::const_op_iterator destIdx = destGEP->idx_begin(),*
> *                                     destEnd = destGEP->idx_end(),*
> *                                     srcIdx = srcGEP->idx_begin(),*
> *                                     srcEnd = srcGEP->idx_end();*
> *      destIdx != destEnd && srcIdx != srcEnd;*
> *      destIdx += (destIdx != destEnd), srcIdx += (srcIdx != srcEnd)) {*
> *    const SCEV* destSCEV = (destIdx != destEnd) ? SE->getSCEV(*destIdx)
:
> *
> *      GetZeroSCEV(SE);*
> *    destOpds.push_back(destSCEV);*
> *    const SCEV* srcSCEV = (srcIdx != srcEnd) ? SE->getSCEV(*srcIdx) :*
> *      GetZeroSCEV(SE);*
> *    srcOpds.push_back(srcSCEV);*
> *  }*
>
>
> But in my various test cases, I never see the loop iterate more than once.
> That is, there always seems to be exactly 1 index.  Here's a typical
test
> case:
>
> *i**nt zap2(long int n, long int A[][n]) {*
> *  long int sum = 0;*
> *  for (long int i = 0; i < n; i++)*
> *    for (long int j = i; j < n; j++)*
> *      sum += A[i][j];*
> *  return sum;*
> *}*
>
>
> Any ideas about what I'm doing wrong? Could it be that I'm not
running
> certain important passes?  Here's my current list:
>
> *-basicaa -mem2reg -simplifycfg -loop-simplify -loop-rotate -simplifycfg
> -instcombine*
>
>
> Thanks,
> 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/20120423/29f39d9d/attachment.html>