[LLVMdev] On semantics of add instruction - nsw,nuw flags

[Rekha R]

Hi,

I am trying to understand the semantics of Instructions in llvm.

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?

Your views are appreciated.

Rekha

--
Rekha

[Tim Northover]

On 23 July 2014 06:25, Rekha R <rekhar...@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
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[Jeremy Lakeman]

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.

[Rekha R]

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.

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

--
Rekha

[Jeremy Lakeman]

On Wed, Jul 23, 2014 at 4:06 PM, Rekha R <rekhar...@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.

[Rekha R]

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

--
Rekha

[Jeremy Lakeman]

Just found this old essay on the original rationale;

http://lists.cs.uiuc.edu/pipermail/llvmdev/2011-November/045730.html

[Tim Northover]

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

[Tobias Grosser]

On 23/07/2014 09:46, Tim Northover wrote:
>> 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.

Tim,

if both instructions are right after each other such that we know that
either none of them or both will be executed, is there a way to leave
the nsw flag taking advantage of the knowledge that any pair of values
that cause nsw in the instruction that originally had now nsw flag is
already known to break the nsw assumption of the other instruction
and causes consequently undefined behaviour?

The langref description is a little surprising, as it seems the
undefined behaviour only is invoked is the resulting poison value is
actually used:

"Poison Values have the same behavior as undef values, with the
additional affect that any instruction which has a dependence on a
poison value has undefined behavior."

Cheers,
Tobias

[Rekha R]

Hi Tim,

If:

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.

then

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.

why can't we retain add nsw and remove add (in the example Cases)? Because there is a guarantee overflow wouldn't occur.

Thanks,

--
Rekha

[Dan Gohman]

On Wed, Jul 23, 2014 at 1:54 AM, Tobias Grosser <tob...@grosser.es> wrote:

On 23/07/2014 09:46, Tim Northover wrote:

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.

Tim,

if both instructions are right after each other such that we know that either none of them or both will be executed, is there a way to leave the nsw flag taking advantage of the knowledge that any pair of values
that cause nsw in the instruction that originally had now nsw flag is already known to break the nsw assumption of the other instruction
and causes consequently undefined behaviour?

No; the motivation for poison values (formerly named trap values, if anyone is reading the rationale linked to earlier in the thread) is to defer undefined behavior until execution can no longer be speculative. The location where a poison value is produced isn't significant. What's important is the location of the use of a poison value (and how it's used).

 

The langref description is a little surprising, as it seems the undefined behaviour only is invoked is the resulting poison value is
actually used:

"Poison Values have the same behavior as undef values, with the additional affect that any instruction which has a dependence on a poison value has undefined behavior."

Correct. nsw isn't a guarantee that overflow won't occur. It is (intended to be) a guarantee that if overflow does occur, the program will avoid using the result for anything important (roughly speaking).

Dan

[Tobias Grosser]

Thanks, for bringing this back to my mind.

[Andrew Trick]

You can’t do this because the add’s have a different set of uses. This is valid IR modulo any typos I make:

%safeidx = add nsw i32 %a, %b
%idx = add i32 %a, %b
%cmp = cmp <some condition that guarantees no overflow>
br i1 %cmp, label %maynotoverflow, label %mayoverflow

maynotoverflow:
%p = getelementptr inbounds i32* %o, i32 %idx
load i32* %p

mayoverflow:
sext i32 %idx to i64
—

That’s why we need the concept of a “poison” value.

-Andy

>
> Thanks,
> --
> Rekha