thr3ads.net - llvm dev - [llvm-dev] SCEV cannot compute the trip count of Simple loop [Sep 2016]

If this information is useful, please help other people find it:
Share via:

Rai, Deepali via llvm-dev

2016-Sep-16 08:44 UTC

[llvm-dev] SCEV cannot compute the trip count of Simple loop

I have modified the example test case for UB error, still it didn’t unroll

void foo(int x) {
  int p, i = 1;
  int mat[9][9][9];
  for (p = (x+1) ; p < (x+3) ;p++)
    mat[x][p-1][i] = mat[x][p-1][i] + 5;
}

Regard,
Deepali

From: Kevin Choi [mailto:code.kchoi at gmail.com]
Sent: Friday, September 16, 2016 1:20 PM
To: Rai, Deepali
Cc: llvm-dev at lists.llvm.org
Subject: Re: [llvm-dev] SCEV cannot compute the trip count of Simple loop

void foo(int x) {
  int p, i = 1;
  int mat[6][6][6];
  for (p = x+3 ; p<= x+6 ;p++)
    mat[x][p][i] = mat[x][p][i] + 5;
}

When x=0, max(p)=6, which is outside of allocated 3d array, which is UB.

On Fri, Sep 16, 2016 at 12:31 AM, Rai, Deepali via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
Hi All,

I am trying to unroll the below loop, but couldn’t as SCEV returns TripCount as
0.

void foo(int x) {
  int p, i = 1;
  int mat[6][6][6];
  for (p = x+3 ; p<= x+6 ;p++)
    mat[x][p][i] = mat[x][p][i] + 5;
}

For a quick reference I have added the generated IR compiled with clang using
–O3.
Please let me know if this is an known issue in SCEV or I am missing something
here ?

; Function Attrs: nounwind readnone uwtable
define void @_Z3fooi(i32 %x) local_unnamed_addr #0 {
entry:
  %mat = alloca [6 x [6 x [6 x i32]]], align 16
  %0 = bitcast [6 x [6 x [6 x i32]]]* %mat to i8*
  call void @llvm.lifetime.start(i64 864, i8* %0) #2
  %add = add nsw i32 %x, 3
  %add1 = add nsw i32 %x, 6
  %idxprom3 = sext i32 %x to i64
  %1 = sext i32 %add to i64
  %2 = sext i32 %add1 to i64
  br label %for.body

for.body:                                         ; preds = %for.body, %entry
  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ %1, %entry ]
  %arrayidx5 = getelementptr inbounds [6 x [6 x [6 x i32]]], [6 x [6 x [6 x
i32]]]* %mat, i64 0, i64 %idxprom3, i64 %indvars.iv, i64 1
  %3 = load i32, i32* %arrayidx5, align 4, !tbaa !1
  %add6 = add nsw i32 %3, 5
  store i32 %add6, i32* %arrayidx5, align 4, !tbaa !1
  %indvars.iv.next = add nsw i64 %indvars.iv, 1
  %cmp = icmp slt i64 %indvars.iv, %2
  br i1 %cmp, label %for.body, label %for.end

for.end:                                          ; preds = %for.body
  call void @llvm.lifetime.end(i64 864, i8* nonnull %0) #2
  ret void
}

Thanks,
Deepali

_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160916/bce97898/attachment.html>

Philip Pfaffe via llvm-dev

2016-Sep-16 11:45 UTC

head link

[llvm-dev] SCEV cannot compute the trip count of Simple loop

There is no way to express the trip count in a closed expression.

E.g., if I call foo(MAX_INT - 2), the loop condition will evaluate to false
immediately.

Best,
Philip

2016-09-16 10:44 GMT+02:00 Rai, Deepali via llvm-dev <
llvm-dev at lists.llvm.org>:
> I have modified the example test case for UB error, still it didn’t unroll
>
>
>
> void foo(int x) {
>
>   int p, i = 1;
>
>   int mat[9][9][9];
>
>   for (p = (x+1) ; p < (x+3) ;p++)
>
>     mat[x][p-1][i] = mat[x][p-1][i] + 5;
>
> }
>
>
>
> Regard,
>
> Deepali
>
>
>
> *From:* Kevin Choi [mailto:code.kchoi at gmail.com]
> *Sent:* Friday, September 16, 2016 1:20 PM
> *To:* Rai, Deepali
> *Cc:* llvm-dev at lists.llvm.org
> *Subject:* Re: [llvm-dev] SCEV cannot compute the trip count of Simple
> loop
>
>
>
> void foo(int x) {
>
>   int p, i = 1;
>
>   int mat[6][6][6];
>
>   for (p = x+3 ; p<= x+6 ;p++)
>
>     mat[x][p][i] = mat[x][p][i] + 5;
>
> }
>
>
>
> When x=0, max(p)=6, which is outside of allocated 3d array, which is UB.
>
>
>
> On Fri, Sep 16, 2016 at 12:31 AM, Rai, Deepali via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> Hi All,
>
>
>
> I am trying to unroll the below loop, but couldn’t as SCEV returns
> TripCount as 0.
>
>
>
> void foo(int x) {
>
>   int p, i = 1;
>
>   int mat[6][6][6];
>
>   for (p = x+3 ; p<= x+6 ;p++)
>
>     mat[x][p][i] = mat[x][p][i] + 5;
>
> }
>
>
>
> For a quick reference I have added the generated IR compiled with clang
> using –O3.
>
> Please let me know if this is an known issue in SCEV or I am missing
> something here ?
>
>
>
> ; Function Attrs: nounwind readnone uwtable
>
> define void @_Z3fooi(i32 %x) local_unnamed_addr #0 {
>
> entry:
>
>   %mat = alloca [6 x [6 x [6 x i32]]], align 16
>
>   %0 = bitcast [6 x [6 x [6 x i32]]]* %mat to i8*
>
>   call void @llvm.lifetime.start(i64 864, i8* %0) #2
>
>   %add = add nsw i32 %x, 3
>
>   %add1 = add nsw i32 %x, 6
>
>   %idxprom3 = sext i32 %x to i64
>
>   %1 = sext i32 %add to i64
>
>   %2 = sext i32 %add1 to i64
>
>   br label %for.body
>
>
>
> for.body:                                         ; preds = %for.body,
> %entry
>
>   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ %1, %entry ]
>
>   %arrayidx5 = getelementptr inbounds [6 x [6 x [6 x i32]]], [6 x [6 x [6
> x i32]]]* %mat, i64 0, i64 %idxprom3, i64 %indvars.iv, i64 1
>
>   %3 = load i32, i32* %arrayidx5, align 4, !tbaa !1
>
>   %add6 = add nsw i32 %3, 5
>
>   store i32 %add6, i32* %arrayidx5, align 4, !tbaa !1
>
>   %indvars.iv.next = add nsw i64 %indvars.iv, 1
>
>   %cmp = icmp slt i64 %indvars.iv, %2
>
>   br i1 %cmp, label %for.body, label %for.end
>
>
>
> for.end:                                          ; preds = %for.body
>
>   call void @llvm.lifetime.end(i64 864, i8* nonnull %0) #2
>
>   ret void
>
> }
>
>
>
> Thanks,
>
> Deepali
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160916/1562f49b/attachment.html>

Mehdi Amini via llvm-dev

2016-Sep-16 20:02 UTC

head link

[llvm-dev] SCEV cannot compute the trip count of Simple loop

> On Sep 16, 2016, at 4:45 AM, Philip Pfaffe via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> There is no way to express the trip count in a closed expression.
> 
> E.g., if I call foo(MAX_INT - 2), the loop condition will evaluate to false
immediately.
Are you implying that because of wrapping?
Signed integer wrapping is UB.

— 
Mehdi

> 
> Best,
> Philip
> 
> 2016-09-16 10:44 GMT+02:00 Rai, Deepali via llvm-dev <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>>:
> I have modified the example test case for UB error, still it didn’t unroll
> 
>  
> 
> void foo(int x) {
> 
>   int p, i = 1;
> 
>   int mat[9][9][9];
> 
>   for (p = (x+1) ; p < (x+3) ;p++)
> 
>     mat[x][p-1][i] = mat[x][p-1][i] + 5;
> 
> }
> 
>  
> 
> Regard,
> 
> Deepali
> 
>  
> 
> From: Kevin Choi [mailto:code.kchoi at gmail.com <mailto:code.kchoi at
gmail.com>]
> Sent: Friday, September 16, 2016 1:20 PM
> To: Rai, Deepali
> Cc: llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> Subject: Re: [llvm-dev] SCEV cannot compute the trip count of Simple loop
> 
>  
> 
> void foo(int x) {
> 
>   int p, i = 1;
> 
>   int mat[6][6][6];
> 
>   for (p = x+3 ; p<= x+6 ;p++)
> 
>     mat[x][p][i] = mat[x][p][i] + 5;
> 
> }
> 
>  
> 
> When x=0, max(p)=6, which is outside of allocated 3d array, which is UB.
> 
>  
> 
> On Fri, Sep 16, 2016 at 12:31 AM, Rai, Deepali via llvm-dev <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
> 
> Hi All,
> 
>  
> 
> I am trying to unroll the below loop, but couldn’t as SCEV returns
TripCount as 0.
> 
>  
> 
> void foo(int x) {
> 
>   int p, i = 1;
> 
>   int mat[6][6][6];
> 
>   for (p = x+3 ; p<= x+6 ;p++)
> 
>     mat[x][p][i] = mat[x][p][i] + 5;
> 
> }
> 
>  
> 
> For a quick reference I have added the generated IR compiled with clang
using –O3.
> 
> Please let me know if this is an known issue in SCEV or I am missing
something here ?
> 
>  
> 
> ; Function Attrs: nounwind readnone uwtable
> 
> define void @_Z3fooi(i32 %x) local_unnamed_addr #0 {
> 
> entry:
> 
>   %mat = alloca [6 x [6 x [6 x i32]]], align 16
> 
>   %0 = bitcast [6 x [6 x [6 x i32]]]* %mat to i8*
> 
>   call void @llvm.lifetime.start(i64 864, i8* %0) #2
> 
>   %add = add nsw i32 %x, 3
> 
>   %add1 = add nsw i32 %x, 6
> 
>   %idxprom3 = sext i32 %x to i64
> 
>   %1 = sext i32 %add to i64
> 
>   %2 = sext i32 %add1 to i64
> 
>   br label %for.body
> 
>  
> 
> for.body:                                         ; preds = %for.body,
%entry
> 
>   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ %1, %entry ]
> 
>   %arrayidx5 = getelementptr inbounds [6 x [6 x [6 x i32]]], [6 x [6 x [6 x
i32]]]* %mat, i64 0, i64 %idxprom3, i64 %indvars.iv, i64 1
> 
>   %3 = load i32, i32* %arrayidx5, align 4, !tbaa !1
> 
>   %add6 = add nsw i32 %3, 5
> 
>   store i32 %add6, i32* %arrayidx5, align 4, !tbaa !1
> 
>   %indvars.iv.next = add nsw i64 %indvars.iv, 1
> 
>   %cmp = icmp slt i64 %indvars.iv, %2
> 
>   br i1 %cmp, label %for.body, label %for.end
> 
>  
> 
> for.end:                                          ; preds = %for.body
> 
>   call void @llvm.lifetime.end(i64 864, i8* nonnull %0) #2
> 
>   ret void
> 
> }
> 
>  
> 
> Thanks,
> 
> Deepali
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
>  
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160916/5a40c9ec/attachment.html>

Sanjoy Das via llvm-dev

2016-Sep-16 20:27 UTC

head link

[llvm-dev] SCEV cannot compute the trip count of Simple loop

Hi Deepali,

SCEV reports the backedge taken count as "((-1 * (sext i32 (3 + %x) to
i64))<nsw> + ((sext i32 (3 + %x) to i64) smax (sext i32 (6 + %x) to
i64)))", so symbolically it does have an answer.

Ideally SCEV should be able to exploit <nsw> on (3 + %x) and (6 + %x)
to fold the expression above to "3", but due to some systemic issues
SCEV can't exploit <nsw> as aggressively as we should.

Without exploiting <nsw> the trip count is 2^32, which does not fit in
an 32 bit unsigned integer.  This is why getSmallConstantTripCount
returns 0.

Does this answer your question?

-- Sanjoy

llvm dev - Sep 2016 - SCEV cannot compute the trip count of Simple loop

[llvm-dev] SCEV cannot compute the trip count of Simple loop

[llvm-dev] SCEV cannot compute the trip count of Simple loop

[llvm-dev] SCEV cannot compute the trip count of Simple loop

[llvm-dev] SCEV cannot compute the trip count of Simple loop