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:

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

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

Oh, I think I am misinterpreting the non-affine AddRec:

{L,+,M,+,N}<%BB> is L+Mbb+N(bb+1)*bb/2

Sorry for the noise. 