llvm dev - Sep 2016 - Inferring nsw/nuw flags for increment/decrement based on relational comparisons

On 2016-09-27 02:28, Philip Reames wrote:
> On 09/20/2016 12:05 PM, Matti Niemenmaa via llvm-dev wrote:
>> I posted some questions related to implementing inference of nsw/nuw
>> flags based on known icmp results to Bug 30428 (
>> https://llvm.org/bugs/show_bug.cgi?id=30428 ) and it was recommended
>> that I engage a wider audience by coming here. The minimal context is
>> the following, please see the bug report for more detail:
>>
>> > 1. If (X s< Y), then both X + 1 and Y - 1 are nsw.
>> > 2. If (X u< Y), then both X + 1 and Y - 1 are nuw.
> If this is the only case you want to support, this sounds like a fairly
> straight forward extension to the LazyValueInfo analysis.  In
> particular, take a look at getValueFromICmpCondition.  I'd be happy to
> help review a patch here once you've got something working.
>
> The basic idea would be that (X s<Y ) implies X s< INT_MAX since Y
must
> be INT_MAX or smaller and X is less than that.  We can tell this without
> needing to know anything about Y.
Looks like a good idea, but I'm not sure how LazyValueInfo's interface 
would support this case. Did you mean synthesizing the INT_MAX constant 
and then checking specifically for "X s< INT_MAX" using 
LazyValueInfo::getPredicateAt? At a glance that seems like it would 
work, but it feels like an odd way of doing it.

Initially I was looking at LVI::getConstantRange but its "at the end of 
the specified block" interface seems too restrictive. The block 
containing the comparison may end in a conditional br and so surely LVI 
can't prove anything there. And the block containing the 
increment/decrement instruction may contain some later information that 
LVI can prove at the end of the block, but is not true at the instruction?

CorrelatedValuePropagation and JumpThreading appear to be the only 
transformation passes making use of LVI at the moment, and that's 
probably something we don't want to change. This kind of nsw/nuw flag 
inference doesn't really fit in either, but CVP is definitely the closer 
match and it should be possible to shoehorn it in there.
> Fair warning, we're actively working through issues related to nsw/nuw
> inference causing overall regressions.  I think we've got the key one
> identified and a patch is under review, but I suspect you'll stumble
> across the same thing.
Interesting, so adding nsw/nuw flags is pessimizing the generated code? 
Can you provide any links?

On 09/27/2016 09:55 AM, Matti Niemenmaa wrote:
> On 2016-09-27 02:28, Philip Reames wrote:
>> On 09/20/2016 12:05 PM, Matti Niemenmaa via llvm-dev wrote:
>>> I posted some questions related to implementing inference of
nsw/nuw
>>> flags based on known icmp results to Bug 30428 (
>>> https://llvm.org/bugs/show_bug.cgi?id=30428 ) and it was
recommended
>>> that I engage a wider audience by coming here. The minimal context
is
>>> the following, please see the bug report for more detail:
>>>
>>> > 1. If (X s< Y), then both X + 1 and Y - 1 are nsw.
>>> > 2. If (X u< Y), then both X + 1 and Y - 1 are nuw.
>> If this is the only case you want to support, this sounds like a fairly
>> straight forward extension to the LazyValueInfo analysis.  In
>> particular, take a look at getValueFromICmpCondition.  I'd be happy
to
>> help review a patch here once you've got something working.
>>
>> The basic idea would be that (X s<Y ) implies X s< INT_MAX since
Y must
>> be INT_MAX or smaller and X is less than that.  We can tell this
without
>> needing to know anything about Y.
>
> Looks like a good idea, but I'm not sure how LazyValueInfo's
interface
> would support this case. Did you mean synthesizing the INT_MAX 
> constant and then checking specifically for "X s< INT_MAX"
using
> LazyValueInfo::getPredicateAt? At a glance that seems like it would 
> work, but it feels like an odd way of doing it.
>
> Initially I was looking at LVI::getConstantRange but its "at the end 
> of the specified block" interface seems too restrictive. The block 
> containing the comparison may end in a conditional br and so surely 
> LVI can't prove anything there. And the block containing the 
> increment/decrement instruction may contain some later information 
> that LVI can prove at the end of the block, but is not true at the 
> instruction?
>
> CorrelatedValuePropagation and JumpThreading appear to be the only 
> transformation passes making use of LVI at the moment, and that's 
> probably something we don't want to change. This kind of nsw/nuw flag 
> inference doesn't really fit in either, but CVP is definitely the 
> closer match and it should be possible to shoehorn it in there.
Will respond to this later once I have a bit more time to put thoughts 
together.
>
>> Fair warning, we're actively working through issues related to
nsw/nuw
>> inference causing overall regressions.  I think we've got the key
one
>> identified and a patch is under review, but I suspect you'll
stumble
>> across the same thing.
>
> Interesting, so adding nsw/nuw flags is pessimizing the generated 
> code? Can you provide any links?
https://reviews.llvm.org/D24280 is the active review.  It's been 
accepted and should go in shortly.

On 09/27/2016 09:55 AM, Matti Niemenmaa wrote:
> On 2016-09-27 02:28, Philip Reames wrote:
>> On 09/20/2016 12:05 PM, Matti Niemenmaa via llvm-dev wrote:
>>> I posted some questions related to implementing inference of
nsw/nuw
>>> flags based on known icmp results to Bug 30428 (
>>> https://llvm.org/bugs/show_bug.cgi?id=30428 ) and it was
recommended
>>> that I engage a wider audience by coming here. The minimal context
is
>>> the following, please see the bug report for more detail:
>>>
>>> > 1. If (X s< Y), then both X + 1 and Y - 1 are nsw.
>>> > 2. If (X u< Y), then both X + 1 and Y - 1 are nuw.
>> If this is the only case you want to support, this sounds like a fairly
>> straight forward extension to the LazyValueInfo analysis.  In
>> particular, take a look at getValueFromICmpCondition.  I'd be happy
to
>> help review a patch here once you've got something working.
>>
>> The basic idea would be that (X s<Y ) implies X s< INT_MAX since
Y must
>> be INT_MAX or smaller and X is less than that.  We can tell this
without
>> needing to know anything about Y.
>
> Looks like a good idea, but I'm not sure how LazyValueInfo's
interface
> would support this case. Did you mean synthesizing the INT_MAX 
> constant and then checking specifically for "X s< INT_MAX"
using
> LazyValueInfo::getPredicateAt? At a glance that seems like it would 
> work, but it feels like an odd way of doing it.
>
> Initially I was looking at LVI::getConstantRange but its "at the end 
> of the specified block" interface seems too restrictive. The block 
> containing the comparison may end in a conditional br and so surely 
> LVI can't prove anything there. And the block containing the 
> increment/decrement instruction may contain some later information 
> that LVI can prove at the end of the block, but is not true at the 
> instruction?
>
> CorrelatedValuePropagation and JumpThreading appear to be the only 
> transformation passes making use of LVI at the moment, and that's 
> probably something we don't want to change. This kind of nsw/nuw flag 
> inference doesn't really fit in either, but CVP is definitely the 
> closer match and it should be possible to shoehorn it in there.
CVP actually already supports this case in ToT; it's just hidden behind 
an option while we address the regression previously mentioned.  See 
-cvp-dont-process-adds and the relevant guarded code.

Your point about the end of block bit can be split into two pieces:
1) Asking a question about an add guarded by a condition in a *previous* 
block.  This case LVI handles elegantly.  It's pretty much it's reason 
for existence.
2) An add which is guarded by an assume or guard in the *same* block 
does look concerning.  From a quick glance at the (off by default) 
functionality, it looks like there might be a bug here?  (Artur, please 
write a test case to check and submit it.)

>
>> Fair warning, we're actively working through issues related to
nsw/nuw
>> inference causing overall regressions.  I think we've got the key
one
>> identified and a patch is under review, but I suspect you'll
stumble
>> across the same thing.
>
> Interesting, so adding nsw/nuw flags is pessimizing the generated 
> code? Can you provide any links?

On 2016-09-28 17:50, Philip Reames wrote:
> On 09/27/2016 09:55 AM, Matti Niemenmaa wrote:
>> On 2016-09-27 02:28, Philip Reames wrote:
>>> On 09/20/2016 12:05 PM, Matti Niemenmaa via llvm-dev wrote:
>>>> I posted some questions related to implementing inference of
nsw/nuw
>>>> flags based on known icmp results to Bug 30428 (
>>>> https://llvm.org/bugs/show_bug.cgi?id=30428 ) and it was
recommended
>>>> that I engage a wider audience by coming here. The minimal
context is
>>>> the following, please see the bug report for more detail:
>>>>
>>>> > 1. If (X s< Y), then both X + 1 and Y - 1 are nsw.
>>>> > 2. If (X u< Y), then both X + 1 and Y - 1 are nuw.
>>> If this is the only case you want to support, this sounds like a
fairly
>>> straight forward extension to the LazyValueInfo analysis.  In
>>> particular, take a look at getValueFromICmpCondition.  I'd be
happy to
>>> help review a patch here once you've got something working.
>>>
>>> The basic idea would be that (X s<Y ) implies X s< INT_MAX
since Y must
>>> be INT_MAX or smaller and X is less than that.  We can tell this
without
>>> needing to know anything about Y.
>>
>> Looks like a good idea, but I'm not sure how LazyValueInfo's
interface
>> would support this case. Did you mean synthesizing the INT_MAX
>> constant and then checking specifically for "X s< INT_MAX"
using
>> LazyValueInfo::getPredicateAt? At a glance that seems like it would
>> work, but it feels like an odd way of doing it.
>>
>> Initially I was looking at LVI::getConstantRange but its "at the
end
>> of the specified block" interface seems too restrictive. The block
>> containing the comparison may end in a conditional br and so surely
>> LVI can't prove anything there. And the block containing the
>> increment/decrement instruction may contain some later information
>> that LVI can prove at the end of the block, but is not true at the
>> instruction?
>>
>> CorrelatedValuePropagation and JumpThreading appear to be the only
>> transformation passes making use of LVI at the moment, and that's
>> probably something we don't want to change. This kind of nsw/nuw
flag
>> inference doesn't really fit in either, but CVP is definitely the
>> closer match and it should be possible to shoehorn it in there.
> CVP actually already supports this case in ToT; it's just hidden behind
> an option while we address the regression previously mentioned.  See
> -cvp-dont-process-adds and the relevant guarded code.
Well then, seems like I'm a few months late. :-) I tried out passing 
-cvp-dont-process-adds=false and the optimization I initially described 
is performed exactly as I would expect it to be. I'll close Bug 30428.

The only missing thing is handling subtractions; this aspect of CVP is 
now restricted to additions. This makes a difference only for the nuw 
case, and only if a canonicalization change is made first: X - 1 is 
currently canonicalized to X + -1, which are equivalent in terms of nsw, 
but only the former could be correctly marked as nuw based on a 
previously true X u> Y (or Y u< X). (This also came up in my slightly 
related patch at D24700: https://reviews.llvm.org/D24700 )
> Your point about the end of block bit can be split into two pieces:
> 1) Asking a question about an add guarded by a condition in a *previous*
> block.  This case LVI handles elegantly.  It's pretty much it's
reason
> for existence.
> 2) An add which is guarded by an assume or guard in the *same* block
> does look concerning.  From a quick glance at the (off by default)
> functionality, it looks like there might be a bug here?  (Artur, please
> write a test case to check and submit it.)
It seems like this was noticed already at the original bug report at 
https://llvm.org/bugs/show_bug.cgi?id=28620 — 'Hopefully "fixing"
this
will just require adjusting the documentation a bit.' Please do test it 
though.

On 28 Sep 2016, at 17:50, Philip Reames <listmail at
philipreames.com<mailto:listmail at philipreames.com>> wrote:



On 09/27/2016 09:55 AM, Matti Niemenmaa wrote:
On 2016-09-27 02:28, Philip Reames wrote:
On 09/20/2016 12:05 PM, Matti Niemenmaa via llvm-dev wrote:
I posted some questions related to implementing inference of nsw/nuw
flags based on known icmp results to Bug 30428 (
https://llvm.org/bugs/show_bug.cgi?id=30428 ) and it was recommended
that I engage a wider audience by coming here. The minimal context is
the following, please see the bug report for more detail:
> 1. If (X s< Y), then both X + 1 and Y - 1 are nsw.
> 2. If (X u< Y), then both X + 1 and Y - 1 are nuw.
If this is the only case you want to support, this sounds like a fairly
straight forward extension to the LazyValueInfo analysis.  In
particular, take a look at getValueFromICmpCondition.  I'd be happy to
help review a patch here once you've got something working.

The basic idea would be that (X s<Y ) implies X s< INT_MAX since Y must
be INT_MAX or smaller and X is less than that.  We can tell this without
needing to know anything about Y.

Looks like a good idea, but I'm not sure how LazyValueInfo's interface
would support this case. Did you mean synthesizing the INT_MAX constant and then
checking specifically for "X s< INT_MAX" using
LazyValueInfo::getPredicateAt? At a glance that seems like it would work, but it
feels like an odd way of doing it.

Initially I was looking at LVI::getConstantRange but its "at the end of the
specified block" interface seems too restrictive. The block containing the
comparison may end in a conditional br and so surely LVI can't prove
anything there. And the block containing the increment/decrement instruction may
contain some later information that LVI can prove at the end of the block, but
is not true at the instruction?

CorrelatedValuePropagation and JumpThreading appear to be the only
transformation passes making use of LVI at the moment, and that's probably
something we don't want to change. This kind of nsw/nuw flag inference
doesn't really fit in either, but CVP is definitely the closer match and it
should be possible to shoehorn it in there.
CVP actually already supports this case in ToT; it's just hidden behind an
option while we address the regression previously mentioned.  See
-cvp-dont-process-adds and the relevant guarded code.

Your point about the end of block bit can be split into two pieces:
1) Asking a question about an add guarded by a condition in a *previous* block. 
This case LVI handles elegantly.  It's pretty much it's reason for
existence.
2) An add which is guarded by an assume or guard in the *same* block does look
concerning.  From a quick glance at the (off by default) functionality, it looks
like there might be a bug here?  (Artur, please write a test case to check and
submit it.)
CVP doesn’t look at instructions which operands are in the same basic block at
the instruction. The motivation is not to spend time for cases which can be
handled without expensive LVI machinery.

This test checks that LVI uses information from guard intrinsics:
https://github.com/llvm-mirror/llvm/blob/master/test/Transforms/CorrelatedValuePropagation/guards.ll

Artur



Fair warning, we're actively working through issues related to nsw/nuw
inference causing overall regressions.  I think we've got the key one
identified and a patch is under review, but I suspect you'll stumble
across the same thing.

Interesting, so adding nsw/nuw flags is pessimizing the generated code? Can you
provide any links?

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160929/4207e487/attachment-0001.html>