[llvm-dev] AddRec.getStepRecurrence

[Alexandre Isoard via llvm-dev]

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}<nuw><nsw><%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}<nuw><%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+M*bb+N*bb*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+M*bb+N*bb*bb - (L+M*(bb-1)+N*(bb-1)*(bb-1)) = M-N+2*bb*N
2: L+M*(bb+1)+N*(bb+1)*(bb+1) - (L+M*bb+N*bb*bb) = M+N+2*bb*N

-- 
*Alexandre Isoard*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20171218/02344fe9/attachment-0001.html>