<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><div><br></div>-- <br><div class="gmail_signature"><div dir="ltr"><b>Alexandre Isoard</b><br></div></div>
</div></div>