[llvm-dev] Inferring nsw/nuw flags for increment/decrement based on relational comparisons

[Matti Niemenmaa via llvm-dev]

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.