[LLVMdev] ScalarEvolution::createNodeForPHI

[Andrew Trick]

On Oct 3, 2013, at 10:14 AM, Michele Scandale <michele.scandale at gmail.com> wrote:

> On 10/03/2013 04:15 PM, Michele Scandale wrote:
>> On 10/03/2013 01:22 AM, Andrew Trick wrote:
>>> 
>>> I’m not sure how to make sense of an NUW flag coming from a sub.
>>> 
>>> NSW is just a misnomer for signed overflow. SCEV canonicalizes sub a,b to add a, (-b). Unfortunately, signed overflow is not the same thing for sub and add...
>>> 
>>> sub nsw %a, %b != add nsw %a, (-1 * %b)
>>> 
>>> sub nsw i32, -1, INT_MIN is true.
>>> 
>>> add nsw i32, -1, (-1 * INT_MIN) is false.
>>> 
>>> NSW flags just aren’t an effective way to tell SCEV about overflow. Ideally we could reason more generally about the loop’s undefined behavior. For example, I’d like to query the range of values that a variable can hold before the loop hits undefined behavior. I don’t know how to implement something like this yet. Ideas are welcome.
>>> 
>>> Reading this code again, even the addition case looks too aggressive to me.
>>> See:
>>> llvm.org/PR17452 - SCEV createNodeForPHI is too optimistic about NSW.
>>> 
>> 
>> If the behavior is different between 'add nsw' and 'sub nsw' then the SCEV
>> canonicalization of 'sub' leads to incorrect results.
>> 
>> In your example both result should be the same but the 'add' produces a poison
>> value. Is this what we really want?
> 
> Reflecting on this I think that the example is wrong: the point is that -1 *
> INT_MIN is not representable over 32bit. The overflow rule is the same for 'add'
> and 'sub', however it's not true that you can replace a 'sub %a, %b' with 'add
> %a, (-1 * %b)'. If the SCEVExpander can avoid these case it should be fine, but
> it may be useful to have also a direct support for 'sub’.

The difference between sub/add overflow is that the sub internally negates its operand using 2’s-complement in the same precision as the result. Overflow status reflects the final result relative to the operands, independent of whether the negation internally overflowed.

SCEV is also well-defined using 2’s-complement. Everything is representable. So it’s fine to canonicalize sub to negate->add if we drop NSW flags.

I know it’s crazy that this defeats the optimizer. If I knew how to preserve correctness without worrying about this I wouldn’t have mentioned it. 

>> The case of an expression with mixed operator ('add' with and without nsw) flag
>> would require an explicit representation of the two operator making more complex
>> reassociation, simplification and reordering of the expression operands.
>> 
>> Your proposed workaround of checking that the BEValue is an operation between
>> the PHINode Value and a loop invariant would be fine but it's still a workaround.
> 
> If it's legal to reassociate a mix of 'add' and 'add nsw' then the poison value
> propagation would make the NSW inference on the whole expression correct. On the
> contrary to ensure semantic correctness we should keep distinct operator and
> allow operator promotion in those cases where we are able to prove that the
> wraparound cannot happen. I think that this is currently not possible because
> SCEV are not uniquely mapped to a given IR Value...
> 
> What do you think about?

Now we’re switching back to the separate potential bug of mixing nsw and non-nsw. I don’t think this is important case to optimize, so I suggested a conservative approach.

In theory you could have:
add i, 2**31-2
add nsw i, 1

And iterate for a while before you see any poison values. I don’t think this happens in practice which is why I didn’t checkin an immediate fix.

-Andy

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131003/de05bf63/attachment.html>