Hello,
I am doubting our implementation of getStepRecurrence on non-affine SCEVAddRec.
The following code:
int func(int n) {
int sum = 0;
for (int i = 0; i < n; ++i)
sum += i;
return sum;
}
Gives:
define i32 @func(i32 %n) {
entry:
br label %header
header: ; preds = %body, %entry
%sum = phi i32 [ 0, %entry ], [ %sum.next, %body ] ; {0,+,0,+,1}<%header>
%i = phi i32 [ 0, %entry ], [ %i.next, %body ] ; {0,+,1}<%header>
%cond = icmp slt i32 %i, %n
br i1 %cond, label %body, label %exit
body: ; preds = %header
%sum.next = add nsw i32 %sum, %i ; {0,+,1,+,1}<%header>
%i.next = add nsw i32 %i, 1 ; {1,+,1}<%header>
br label %header
exit: ; preds = %header
ret i32 %sum
}
This looks correct to me, and I deduce that:
{L,+,M,+,N}<%BB> means L+Mbb+Nbb*bb (where bb is the number of times the back-edge is taken)
But then, the getStepRecurrence would gives:
{M,+,N}<%BB> which means M+N*bb (where bb is the number of times the back-edge is taken)
But that does not correspond to anything sensible. It is neither:
- the increment from the previous iteration to this one, ({M-N,+,2*N}<%BB>) [see footnote 1]
- nor the increment from this iteration to the next one. ({N+M,+,2*N}<%BB>) [see footnote 2]
Am I interpreting things the wrong way?
Footnotes:
1: L+Mbb+Nbbbb - (L+M(bb-1)+N*(bb-1)(bb-1)) = M-N+2bbN
2: L+M(bb+1)+N*(bb+1)(bb+1) - (L+Mbb+Nbbbb) = M+N+2bbN
