[llvm-dev] Inferring nsw/nuw flags for increment/decrement based on relational comparisons
Philip Reames via llvm-dev
llvm-dev at lists.llvm.org
Wed Sep 28 07:50:54 PDT 2016
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
> 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
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?
More information about the llvm-dev