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