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

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

Hi Mehdi,

Mehdi Amini wrote:
 >
 >> On Sep 16, 2016, at 1:56 PM, Kevin Choi via llvm-dev
 >> <llvm-dev at lists.llvm.org <mailto: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.

It is always valid to return 2 as the trip count.  But SCEV today is
not always able to exploit nsw/nuw due to some systemic issues.

I can go into details about the systemic issues here if you want, but
given that I've already repeated this several times on the mailing
list, I'd rather put that into a blog post to have a link to share
easily. :)

-- Sanjoy

> On Sep 16, 2016, at 2:23 PM, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
> 
> Hi Mehdi,
> 
> Mehdi Amini wrote:
> >
> >> On Sep 16, 2016, at 1:56 PM, Kevin Choi via llvm-dev
> >> <llvm-dev at lists.llvm.org <mailto: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.
> 
> It is always valid to return 2 as the trip count.  But SCEV today is
> not always able to exploit nsw/nuw due to some systemic issues.
I understood that SCEV can’t deduce it.
The point was more “abstracting the current implementation limitation”, there is
no fundamental issue with this code.

— 
Mehdi