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

[Preston Briggs]

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>