[llvm-dev] AddRec.getStepRecurrence

[Alexandre Isoard via llvm-dev]

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

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

Sorry for the noise. :-)

On Mon, Dec 18, 2017 at 4:26 PM, Alexandre Isoard <
alexandre.isoard at gmail.com> wrote:

> 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*
>



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