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

@Sanjoy, what's the issue with <nsw>? Moreover, why can't SCEV
detect that
x is loop invariant and just take the diff/incr?

On Fri, Sep 16, 2016 at 2:50 PM, Kevin Choi <code.kchoi at gmail.com>
wrote:
> Assuming compiler assumes program is free of UB, I suppose trip count of 2
> is always valid. I misplaced valid to trip count when it should've been
> "program is valid only for x in [0.6]".
>
> On Fri, Sep 16, 2016 at 2:29 PM, Mehdi Amini <mehdi.amini at
apple.com>
> wrote:
>
>>
>> > 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
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160916/c9da951b/attachment-0001.html>

Hi Kevin,

Kevin Choi wrote:
 > @Sanjoy, what's the issue with <nsw>?

I'll write up something in a central location and share it.

 > Moreover, why can't SCEV detect
 > that x is loop invariant and just take the diff/incr?

Detecting the loop invariance of x is not the problem.  SCEV currently
stumbles on proving that "x + 1" and "x + 3" don't
overflow.

If "x + 1" and "x + 3" cannot be proven to overflow then the
loop no
longer has a constant trip count of "2".  For instance if
"x" is
INT_MAX-1 then the loop will run 0 times.

-- Sanjoy

On Fri, Sep 16, 2016 at 4:05 PM, Sanjoy Das <sanjoy at
playingwithpointers.com>
wrote:
> Hi Kevin,
>
>
> If "x + 1" and "x + 3" cannot be proven to overflow
then the loop no
> longer has a constant trip count of "2".
If we apply "Assuming compiler assumes program is free of UB", can
above
requirement be relaxed?

-Kevin

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