<div class="gmail_extra">Perhaps this is really a question related to Clang or the IR.</div><div class="gmail_extra">When I try a slightly different source file, I indeed get a multi-index GEP.</div><div class="gmail_extra">
Here are two test cases:</div><div class="gmail_extra"><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b>int zap2(long int n, long int A[][n]) {</b></font></div>
</div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> long int sum = 0;</b></font></div></div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> for (long int i = 0; i < n; i++)</b></font></div>
</div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> for (long int j = i; j < n; j++)</b></font></div></div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> sum += A[i][j];</b></font></div>
</div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> return sum;</b></font></div></div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b>}</b></font></div>
</div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b><br></b></font></div></div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b><br>
</b></font></div></div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b>int zip2(long int n, long int A[][90]) {</b></font></div></div><div class="gmail_extra"><div class="gmail_extra">
<font face="'courier new', monospace"><b> long int sum = 0;</b></font></div></div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> for (long int i = 0; i < n; i++)</b></font></div>
</div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> for (long int j = i; j < n; j++)</b></font></div></div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> sum += A[i][j];</b></font></div>
</div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> return sum;</b></font></div></div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b>}</b></font></div>
</div></blockquote><div class="gmail_extra"><div><br></div></div><div class="gmail_extra">Here's what I see for the first case:</div><div class="gmail_extra"><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px">
<div class="gmail_extra"><div class="gmail_extra"><b><font face="'courier new', monospace"> %cmp4 = icmp sgt i64 %n, 0</font></b></div></div><div class="gmail_extra"><div class="gmail_extra"><b><font face="'courier new', monospace"> br i1 %cmp4, label %for.cond1.preheader, label %for.end7</font></b></div>
</div><div class="gmail_extra"><div class="gmail_extra"><b><font face="'courier new', monospace"> %i.06 = phi i64 [ %inc6, %for.inc5 ], [ 0, %entry ]</font></b></div></div><div class="gmail_extra"><div class="gmail_extra">
<b><font face="'courier new', monospace"> %sum.05 = phi i64 [ %sum.1.lcssa, %for.inc5 ], [ 0, %entry ]</font></b></div></div><div class="gmail_extra"><div class="gmail_extra"><b><font face="'courier new', monospace"> %cmp21 = icmp slt i64 %i.06, %n</font></b></div>
</div><div class="gmail_extra"><div class="gmail_extra"><b><font face="'courier new', monospace"> br i1 %cmp21, label %for.body3, label %for.inc5</font></b></div></div><div class="gmail_extra"><div class="gmail_extra">
<b><font face="'courier new', monospace"> %j.03 = phi i64 [ %inc, %for.body3 ], [ %i.06, %for.cond1.preheader ]</font></b></div></div><div class="gmail_extra"><div class="gmail_extra"><b><font face="'courier new', monospace"> %sum.12 = phi i64 [ %add, %for.body3 ], [ %sum.05, %for.cond1.preheader ]</font></b></div>
</div><div class="gmail_extra"><div class="gmail_extra"><b><font face="'courier new', monospace"> %0 = mul nsw i64 %i.06, %n</font></b></div></div><div class="gmail_extra"><div class="gmail_extra"><b><font face="'courier new', monospace"> %arrayidx.sum = add i64 %0, %j.03</font></b></div>
</div><div class="gmail_extra"><div class="gmail_extra"><b><font face="'courier new', monospace"> %arrayidx4 = getelementptr inbounds i64* %A, i64 %arrayidx.sum</font></b></div></div><div class="gmail_extra"><div class="gmail_extra">
<b><font face="'courier new', monospace"> %1 = load i64* %arrayidx4, align 8</font></b></div></div><div class="gmail_extra"><div><b><font face="'courier new', monospace"> ...</font></b></div></div></blockquote>
<div class="gmail_extra"><div><br></div></div><div class="gmail_extra">And here's what I see for the second case:</div><div class="gmail_extra"><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div class="gmail_extra">
<div class="gmail_extra"><font face="'courier new', monospace"><b> %cmp4 = icmp sgt i64 %n, 0</b></font></div></div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> br i1 %cmp4, label %for.cond1.preheader, label %for.end7</b></font></div>
</div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> %i.06 = phi i64 [ %inc6, %for.inc5 ], [ 0, %entry ]</b></font></div></div><div class="gmail_extra"><div class="gmail_extra">
<font face="'courier new', monospace"><b> %sum.05 = phi i64 [ %sum.1.lcssa, %for.inc5 ], [ 0, %entry ]</b></font></div></div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> %cmp21 = icmp slt i64 %i.06, %n</b></font></div>
</div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> br i1 %cmp21, label %for.body3, label %for.inc5</b></font></div></div><div class="gmail_extra"><div class="gmail_extra">
<font face="'courier new', monospace"><b> %j.03 = phi i64 [ %inc, %for.body3 ], [ %i.06, %for.cond1.preheader ]</b></font></div></div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> %sum.12 = phi i64 [ %add, %for.body3 ], [ %sum.05, %for.cond1.preheader ]</b></font></div>
</div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> %arrayidx4 = getelementptr inbounds [90 x i64]* %A, i64 %i.06, i64 %j.03</b></font></div></div><div class="gmail_extra">
<div class="gmail_extra"><font face="'courier new', monospace"><b> %0 = load i64* %arrayidx4, align 8</b></font></div></div><div class="gmail_extra"><div><font face="'courier new', monospace"><b> ...</b></font></div>
</div></blockquote><div class="gmail_extra"><br></div><div class="gmail_extra">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.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">Too bad for the dependence analyzer; we'll have to jump through more hoops to recover the subscripts.</div><div class="gmail_extra"><br></div><div class="gmail_extra">
Preston</div><div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Mon, Apr 23, 2012 at 4:01 PM, Preston Briggs <span dir="ltr"><<a href="mailto:preston.briggs@gmail.com" target="_blank">preston.briggs@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="gmail_extra">Hi,</div><div class="gmail_extra"><br></div><div class="gmail_extra">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.</div>
<div class="gmail_extra"><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> // Collect GEP operand pairs (FIXME: use GetGEPOperands from BasicAA), adding</b></font></div>
</div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> // trailing zeroes to the smaller GEP, if needed.</b></font></div></div><div class="gmail_extra"><div class="gmail_extra">
<font face="'courier new', monospace"><b> GEPOpdsTy destOpds, srcOpds;</b></font></div></div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> for(GEPOperator::const_op_iterator destIdx = destGEP->idx_begin(),</b></font></div>
</div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> destEnd = destGEP->idx_end(),</b></font></div></div><div class="gmail_extra">
<div class="gmail_extra"><font face="'courier new', monospace"><b> srcIdx = srcGEP->idx_begin(),</b></font></div></div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> srcEnd = srcGEP->idx_end();</b></font></div>
</div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> destIdx != destEnd && srcIdx != srcEnd;</b></font></div></div><div class="gmail_extra"><div class="gmail_extra">
<font face="'courier new', monospace"><b> destIdx += (destIdx != destEnd), srcIdx += (srcIdx != srcEnd)) {</b></font></div></div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> const SCEV* destSCEV = (destIdx != destEnd) ? SE->getSCEV(*destIdx) :</b></font></div>
</div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> GetZeroSCEV(SE);</b></font></div></div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> destOpds.push_back(destSCEV);</b></font></div>
</div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> const SCEV* srcSCEV = (srcIdx != srcEnd) ? SE->getSCEV(*srcIdx) :</b></font></div></div><div class="gmail_extra">
<div class="gmail_extra"><font face="'courier new', monospace"><b> GetZeroSCEV(SE);</b></font></div></div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> srcOpds.push_back(srcSCEV);</b></font></div>
</div><div class="gmail_extra"><div class="gmail_extra"><font face="'courier new', monospace"><b> }</b></font></div></div></blockquote><div class="gmail_extra"><div><br></div><div>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:</div>
<div><br></div></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div class="gmail_extra"><div><div><b><font face="'courier new', monospace">i</font></b><font face="'courier new', monospace"><b>nt zap2(long int n, long int A[][n]) {</b></font></div>
</div></div><div class="gmail_extra"><div><div><font face="'courier new', monospace"><b> long int sum = 0;</b></font></div></div></div><div class="gmail_extra"><div><div><font face="'courier new', monospace"><b> for (long int i = 0; i < n; i++)</b></font></div>
</div></div><div class="gmail_extra"><div><div><font face="'courier new', monospace"><b> for (long int j = i; j < n; j++)</b></font></div></div></div><div class="gmail_extra"><div><div><font face="'courier new', monospace"><b> sum += A[i][j];</b></font></div>
</div></div><div class="gmail_extra"><div><div><font face="'courier new', monospace"><b> return sum;</b></font></div></div></div><div class="gmail_extra"><div><div><font face="'courier new', monospace"><b>}</b></font></div>
</div></div></blockquote><div class="gmail_extra"><div><br></div><div>Any ideas about what I'm doing wrong? Could it be that I'm not running certain important passes? Here's my current list:</div><div><br></div>
</div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div class="gmail_extra"><div><b><font face="'courier new', monospace">-basicaa -mem2reg -simplifycfg -loop-simplify -loop-rotate -simplifycfg -instcombine</font></b></div>
</div></blockquote><div class="gmail_extra"><div><br></div><div>Thanks,</div><div>Preston</div><div><br></div><div><br></div><div><br></div><div><br></div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra">
<br><div class="gmail_quote">On Thu, Apr 12, 2012 at 5:14 AM, Sanjoy Das <span dir="ltr"><<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi,<br>
<br>
Here is a preliminary (monolithic) version you can comment on. This<br>
is still buggy, however, and I'll be testing for and fixing bugs over<br>
the next few days. I've used your version of the strong siv test.<br>
<br>
Thanks!<br>
<div><div>--<br>
Sanjoy Das.<br>
<a href="http://playingwithpointers.com" target="_blank">http://playingwithpointers.com</a><br>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>