llvm dev - Jul 2014 - [LLVMdev] On semantics of add instruction - nsw,nuw flags

On Wed, Jul 23, 2014 at 4:06 PM, Rekha R <rekharamapai at nitc.ac.in>
wrote:
> Ok. Got it.
>
> If *add nsw* overflows, this results in undefined value.
> But then *add* on same arguments results in well-defined value.
>
> Hence treating first one as redundant based on the second is acceptable.
> But vice versa is not.
>
If they are in different code paths, sure. It's not an undefined value,
it's undefined *behaviour*. We can assume that the operation might crash,
so the rest of the block is unreachable.
What you're really saying to the compiler with the nsw flag is " that
the
operation is *guaranteed *to not overflow" (
http://llvm.org/releases/2.6/docs/ReleaseNotes.html)
And that the compiler can use this information in optimising the rest of
your code.

>
> I was wondering on the role played by flags in detecting redundancies. At
> first I thought one need to consider only operands and operators. Now I
> understand flags also play a role.
>
> Thanks,
>  Rekha
>
>
> On Wed, Jul 23, 2014 at 11:42 AM, Jeremy Lakeman <Jeremy.Lakeman at
gmail.com
> > wrote:
>
>> IMHO;
>> On undefined behaviour we can do whatever we want. If the "add
nsw"
>> overflows this would lead to undefined behaviour.
>> Therefore we can assume that "add", with the same arguments
will not
>> overflow.
>>
>>
>> On Wed, Jul 23, 2014 at 3:32 PM, Tim Northover <t.p.northover at
gmail.com>
>> wrote:
>>
>>> On 23 July 2014 06:25, Rekha R <rekharamapai at nitc.ac.in>
wrote:
>>> > Are the following instructions semantically same?
>>> >   %add2 = add nsw i32 %add, %add1
>>> >   %add3 = add        i32 %add, %add1
>>> >
>>> > Based on my understanding from the Language Reference Manual,
I think
>>> they
>>> > are different. But then why is the gvn pass detecting %add3 as
>>> redundant and deleting it?
>>>
>>> On their common domain, the two instructions coincide. But the
second
>>> one is defined for more pairs of input. That is, it's also
defined
>>> when the (signed) sum overflows.
>>>
>>> So it's correct to eliminate the first one as redundant, in
favour of
>>> the second, but not the reverse. This is what I see GVN doing too
from
>>> my simple tests, do you have a complete .ll file where the wrong
one
>>> is removed?
>>>
>>> Cheers.
>>>
>>> Tim.
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>
>>
>>
>
>
> --
> Rekha
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140723/77f0b227/attachment.html>

This lead to some doubts in me.

1. The Language Manual says:
*"nuw and nsw stand for “No Unsigned Wrap” and “No Signed Wrap”,
respectively. If the nuw and/or nsw keywords are present, the result value
of the add is a poison value if unsigned and/or signed overflow,
respectively, occurs.*"

Then why does the Release Note say
" *the operation is guaranteed to not overflow*".

2.
What are the redundancies in the following code snip. Assume they appear in
that order in a basic block.

  Case1; %add2 = add nsw i32 %add, %add1
             %add3 = add        i32 %add, %add1

  Case2: %add2 = add        i32 %add, %add1
             %add3 = add nsw i32 %add, %add1

Thanks,
Rekha


On Wed, Jul 23, 2014 at 12:16 PM, Jeremy Lakeman <Jeremy.Lakeman at
gmail.com>
wrote:
>
>
>
> On Wed, Jul 23, 2014 at 4:06 PM, Rekha R <rekharamapai at nitc.ac.in>
wrote:
>
>> Ok. Got it.
>>
>> If *add nsw* overflows, this results in undefined value.
>> But then *add* on same arguments results in well-defined value.
>>
>> Hence treating first one as redundant based on the second is
acceptable.
>> But vice versa is not.
>>
>
> If they are in different code paths, sure. It's not an undefined value,
> it's undefined *behaviour*. We can assume that the operation might
crash,
> so the rest of the block is unreachable.
> What you're really saying to the compiler with the nsw flag is "
that the
> operation is *guaranteed *to not overflow" (
> http://llvm.org/releases/2.6/docs/ReleaseNotes.html)
> And that the compiler can use this information in optimising the rest of
> your code.
>
>
>>
>> I was wondering on the role played by flags in detecting redundancies.
At
>> first I thought one need to consider only operands and operators. Now I
>> understand flags also play a role.
>>
>> Thanks,
>>  Rekha
>>
>>
>> On Wed, Jul 23, 2014 at 11:42 AM, Jeremy Lakeman <
>> Jeremy.Lakeman at gmail.com> wrote:
>>
>>> IMHO;
>>> On undefined behaviour we can do whatever we want. If the "add
nsw"
>>> overflows this would lead to undefined behaviour.
>>> Therefore we can assume that "add", with the same
arguments will not
>>> overflow.
>>>
>>>
>>> On Wed, Jul 23, 2014 at 3:32 PM, Tim Northover <t.p.northover at
gmail.com>
>>> wrote:
>>>
>>>> On 23 July 2014 06:25, Rekha R <rekharamapai at
nitc.ac.in> wrote:
>>>> > Are the following instructions semantically same?
>>>> >   %add2 = add nsw i32 %add, %add1
>>>> >   %add3 = add        i32 %add, %add1
>>>> >
>>>> > Based on my understanding from the Language Reference
Manual, I think
>>>> they
>>>> > are different. But then why is the gvn pass detecting
%add3 as
>>>> redundant and deleting it?
>>>>
>>>> On their common domain, the two instructions coincide. But the
second
>>>> one is defined for more pairs of input. That is, it's also
defined
>>>> when the (signed) sum overflows.
>>>>
>>>> So it's correct to eliminate the first one as redundant, in
favour of
>>>> the second, but not the reverse. This is what I see GVN doing
too from
>>>> my simple tests, do you have a complete .ll file where the
wrong one
>>>> is removed?
>>>>
>>>> Cheers.
>>>>
>>>> Tim.
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>>
>>>
>>>
>>
>>
>> --
>> Rekha
>>
>
>

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

Just found this old essay on the original rationale;
http://lists.cs.uiuc.edu/pipermail/llvmdev/2011-November/045730.html



On Wed, Jul 23, 2014 at 4:16 PM, Jeremy Lakeman <Jeremy.Lakeman at
gmail.com>
wrote:
>
>
>
> On Wed, Jul 23, 2014 at 4:06 PM, Rekha R <rekharamapai at nitc.ac.in>
wrote:
>
>> Ok. Got it.
>>
>> If *add nsw* overflows, this results in undefined value.
>> But then *add* on same arguments results in well-defined value.
>>
>> Hence treating first one as redundant based on the second is
acceptable.
>> But vice versa is not.
>>
>
> If they are in different code paths, sure. It's not an undefined value,
> it's undefined *behaviour*. We can assume that the operation might
crash,
> so the rest of the block is unreachable.
> What you're really saying to the compiler with the nsw flag is "
that the
> operation is *guaranteed *to not overflow" (
> http://llvm.org/releases/2.6/docs/ReleaseNotes.html)
> And that the compiler can use this information in optimising the rest of
> your code.
>
>
>>
>> I was wondering on the role played by flags in detecting redundancies.
At
>> first I thought one need to consider only operands and operators. Now I
>> understand flags also play a role.
>>
>> Thanks,
>>  Rekha
>>
>>
>> On Wed, Jul 23, 2014 at 11:42 AM, Jeremy Lakeman <
>> Jeremy.Lakeman at gmail.com> wrote:
>>
>>> IMHO;
>>> On undefined behaviour we can do whatever we want. If the "add
nsw"
>>> overflows this would lead to undefined behaviour.
>>> Therefore we can assume that "add", with the same
arguments will not
>>> overflow.
>>>
>>>
>>> On Wed, Jul 23, 2014 at 3:32 PM, Tim Northover <t.p.northover at
gmail.com>
>>> wrote:
>>>
>>>> On 23 July 2014 06:25, Rekha R <rekharamapai at
nitc.ac.in> wrote:
>>>> > Are the following instructions semantically same?
>>>> >   %add2 = add nsw i32 %add, %add1
>>>> >   %add3 = add        i32 %add, %add1
>>>> >
>>>> > Based on my understanding from the Language Reference
Manual, I think
>>>> they
>>>> > are different. But then why is the gvn pass detecting
%add3 as
>>>> redundant and deleting it?
>>>>
>>>> On their common domain, the two instructions coincide. But the
second
>>>> one is defined for more pairs of input. That is, it's also
defined
>>>> when the (signed) sum overflows.
>>>>
>>>> So it's correct to eliminate the first one as redundant, in
favour of
>>>> the second, but not the reverse. This is what I see GVN doing
too from
>>>> my simple tests, do you have a complete .ll file where the
wrong one
>>>> is removed?
>>>>
>>>> Cheers.
>>>>
>>>> Tim.
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>>
>>>
>>>
>>
>>
>> --
>> Rekha
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140723/89e59047/attachment.html>

> Then why does the Release Note say
> " the operation is guaranteed to not overflow".
It means that the person who wrote the IR has guaranteed that there's
no overflow (by some means) so LLVM can assume it during optimisation.

This guarantee might come from doing explicit checks before executing
the add/sub; or perhaps from performing the operation after a sext so
that the type is guaranteed to be big enough; or (as in C) by trusting
the programmer to make sure that doesn't happen.
> What are the redundancies in the following code snip. Assume they appear in
> that order in a basic block.
>
>   Case1; %add2 = add nsw i32 %add, %add1
>              %add3 = add        i32 %add, %add1
>
>   Case2: %add2 = add        i32 %add, %add1
>              %add3 = add nsw i32 %add, %add1
In both cases the add with nsw can be removed in favour of the one
without. Order is completely irrelevant for normal LLVM arithmetic
instructions.

Cheers.

Tim.