llvm dev - Sep 2016 - 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

> int mat[9][9][9];
> for (p = (x+1) ; p < (x+3) ;p++)
>    mat[x][p-1][i] = mat[x][p-1][i] + 5;
> }
The trip count of 2 should be valid for x in [0,6]. If SCEV doesn't catch
it with, say GVN and appropriate matching conditions, it could be improved.
CMIIW, I don't think LLVM goes out of the way to opportunistically version
the loop by inserting if check(s) and then unroll it.

-Kevin

On Fri, Sep 16, 2016 at 1:27 PM, Sanjoy Das via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> 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 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/3faf26b4/attachment.html>

> On Sep 16, 2016, at 1:56 PM, Kevin Choi via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> > int mat[9][9][9];
> > for (p = (x+1) ; p < (x+3) ;p++)
> >    mat[x][p-1][i] = mat[x][p-1][i] + 5;
> > }
> The trip count of 2 should be valid for x in [0,6].
It is not clear to me why the trip count of 2 isn’t *always* valid.
> If SCEV doesn't catch it with, say GVN and appropriate matching
conditions, it could be improved.
> CMIIW, I don't think LLVM goes out of the way to opportunistically
version the loop by inserting if check(s) and then unroll it.
We shouldn’t need any runtime check to derive the trip count here.

— 
Mehdi

> 
> -Kevin
> 
> On Fri, Sep 16, 2016 at 1:27 PM, Sanjoy Das via llvm-dev <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
> 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 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/32411017/attachment.html>

Thanks Sanjoy for the clarification. Can you please share the link to blog for
systemic issues in SCEV that you were mentioning.

Thanks,
Deepali

-----Original Message-----
From: Sanjoy Das [mailto:sanjoy at playingwithpointers.com] 
Sent: Saturday, September 17, 2016 1:58 AM
To: Philip Pfaffe
Cc: Rai, Deepali; llvm-dev at lists.llvm.org
Subject: Re: [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

Hi Deepali,

Rai, Deepali wrote:

 > Thanks Sanjoy for the clarification. Can you please share the link
 > to blog for systemic issues in SCEV that you were mentioning.

I didn't write a blog post, but I found a previous instance of me
answering the same question on the mailing list:
http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160613/366023.html

Thanks,
-- Sanjoy