<div dir="ltr">Oh, I think I am misinterpreting the non-affine AddRec:<div><br></div><div><span style="font-size:12.8px">{L,+,M,+,N}<%BB> is L+M*bb+N*(bb+1)*bb/2</span><br></div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px">Sorry for the noise. :-)</span></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Dec 18, 2017 at 4:26 PM, Alexandre Isoard <span dir="ltr"><<a href="mailto:alexandre.isoard@gmail.com" target="_blank">alexandre.isoard@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 dir="ltr">Hello,<div><br></div><div>I am doubting our implementation of getStepRecurrence on non-affine SCEVAddRec.</div><div><br></div><div>The following code:</div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">int func(int n) {</font></div><div><font face="monospace, monospace"> int sum = 0;</font></div><div><font face="monospace, monospace"> for (int i = 0; i < n; ++i)</font></div><div><font face="monospace, monospace"> sum += i;</font></div><div><font face="monospace, monospace"> return sum;</font></div><div><font face="monospace, monospace">}</font></div><div><br></div><div>Gives:</div><div><br></div><div><div><font face="monospace, monospace">define i32 @func(i32 %n) {</font></div><div><font face="monospace, monospace">entry:</font></div><div><font face="monospace, monospace"> br label %header</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">header: ; preds = %body, %entry</font></div><div><font face="monospace, monospace"> %sum = phi i32 [ 0, %entry ], [ %sum.next, %body ] ; {0,+,0,+,1}<%header></font></div><div><font face="monospace, monospace"> %i = phi i32 [ 0, %entry ], [ %i.next, %body ] ; {0,+,1}<nuw><nsw><%header></font></div><div><font face="monospace, monospace"> %cond = icmp slt i32 %i, %n</font></div><div><font face="monospace, monospace"> br i1 %cond, label %body, label %exit</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">body: ; preds = %header</font></div><div><font face="monospace, monospace"> %sum.next = add nsw i32 %sum, %i ; {0,+,1,+,1}<%header></font></div><div><font face="monospace, monospace"> %i.next = add nsw i32 %i, 1 ; {1,+,1}<nuw><%header></font></div><div><font face="monospace, monospace"> br label %header</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">exit: ; preds = %header</font></div><div><font face="monospace, monospace"> ret i32 %sum</font></div><div><font face="monospace, monospace">}</font></div><div><br></div><div>This looks correct to me, and I deduce that:</div><div><br></div><div>{L,+,M,+,N}<%BB> means L+M*bb+N*bb*bb (where bb is the number of times the back-edge is taken)</div><div><br></div><div>But then, the getStepRecurrence would gives:</div><div><br></div><div>{M,+,N}<%BB> which means M+N*bb (where bb is the number of times the back-edge is taken)</div><div><br></div><div>But that does not correspond to anything sensible. It is neither:</div><div>- the increment from the previous iteration to this one, ({M-N,+,2*N}<%BB>) [see footnote 1]</div><div>- nor the increment from this iteration to the next one. ({N+M,+,2*N}<%BB>) [see footnote 2]</div><div><br></div><div>Am I interpreting things the wrong way?</div><div><br></div><div>Footnotes:</div><div>1: L+M*bb+N*bb*bb - (L+M*(bb-1)+N*(bb-1)*(bb-1)) = M-N+2*bb*N</div><div>2: L+M*(bb+1)+N*(bb+1)*(bb+1) - (L+M*bb+N*bb*bb) = M+N+2*bb*N</div><span class="HOEnZb"><font color="#888888"><div><br></div>-- <br><div class="m_-3609498246005211005gmail_signature"><div dir="ltr"><b>Alexandre Isoard</b><br></div></div>
</font></span></div></div>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><b>Alexandre Isoard</b><br></div></div>
</div>