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