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

[Philip Reames via llvm-dev]

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?