llvm dev - Apr 2016 - Is trapping allowed when an add with nsw flag overflows?

Hi,

In our backend, we currently emit add operations that trap on overflow 
if the IR operation has the nsw flag set.  Is this allowed?

According to the documentation about poison values, overflowing a nsw 
add is undefined behavior.  However I didn't find a formal definition of 
undefined behavior in LLVM.  Judging from previous discussions on the 
mailing list, there seems to be a vague line of what LLVM is allowed to 
do in case of undefined behavior.  Is trapping allowed?

-Manuel

> On Apr 15, 2016, at 10:28 AM, Manuel Jacob via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hi,
> 
> In our backend, we currently emit add operations that trap on overflow if
the IR operation has the nsw flag set.  Is this allowed?
Isn't it what something like UBSAN would do?

> According to the documentation about poison values, overflowing a nsw add
is undefined behavior.
I don't read it the same way: "Poison value behavior is defined in
terms of value dependence:  [....]  Poison values have the same behavior as
undef values, with the additional effect that any instruction that has a
dependence on a poison value has undefined behavior."
So merely overflowing a nsw operation is not UB, until you do a side effect
operation that depends on the poison value.

-- 
Mehdi



>  However I didn't find a formal definition of undefined behavior in
LLVM.  Judging from previous discussions on the mailing list, there seems to be
a vague line of what LLVM is allowed to do in case of undefined behavior.  Is
trapping allowed?
> 
> -Manuel
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

On Fri, Apr 15, 2016 at 10:28 AM, Manuel Jacob via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi,
>
> In our backend, we currently emit add operations that trap on overflow if
> the IR operation has the nsw flag set.  Is this allowed?
>
No.  Operations like `add nsw` can be hoisted around control dependencies
and unconditionally executed.

The only information that flag yields is that downstream users of the
instruction don't need to worry about the instruction producing a result
which results in wrapping when taking it's operands into account.

>
> According to the documentation about poison values, overflowing a nsw add
> is undefined behavior.  However I didn't find a formal definition of
> undefined behavior in LLVM.  Judging from previous discussions on the
> mailing list, there seems to be a vague line of what LLVM is allowed to do
> in case of undefined behavior.  Is trapping allowed?
>
> -Manuel
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160415/8e50c324/attachment.html>

No, trapping is not allowed, since an overflowing add nsw is defined to 
produce a poison value, which sort of explodes into undefined behavior 
if it reaches a side-effect.  This is to support speculative execution.

If you emit trapping adds for nsw, you'll see spurious traps every now 
and then.

There's a stronger form of undefined behavior, exhibited by things like 
divide by zero, that permits traps.

John



On 4/15/16 7:28 PM, Manuel Jacob via llvm-dev wrote:
> Hi,
>
> In our backend, we currently emit add operations that trap on overflow
> if the IR operation has the nsw flag set.  Is this allowed?
>
> According to the documentation about poison values, overflowing a nsw
> add is undefined behavior.  However I didn't find a formal definition
of
> undefined behavior in LLVM.  Judging from previous discussions on the
> mailing list, there seems to be a vague line of what LLVM is allowed to
> do in case of undefined behavior.  Is trapping allowed?
>
> -Manuel
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

[This mail could be an answer to the other responses as well, as they 
basically are the same.]

Ah, I think I understand now what poison is for.  Adds are defined to 
not have side-effects, so the dependence rule is needed so the optimizer 
is allowed to exploit undefined behavior.  Is this correct?

I forgot to mention in my original mail that our trapping arithmetic 
operations are fully speculable.  This means that the trap won't happen 
until the result is e.g. stored to memory.  A bit like poison values in 
hardware.

Something is still unclear to me: while, according to the examples in 
LangRef, a volatile store has undefined behavior when a poison value is 
stored, this seems to not be true in case of non-volatile stores.  Can 
someone clarify please?

On 2016-04-15 19:44, John Regehr via llvm-dev wrote:
> No, trapping is not allowed, since an overflowing add nsw is defined
> to produce a poison value, which sort of explodes into undefined
> behavior if it reaches a side-effect.  This is to support speculative
> execution.
> 
> If you emit trapping adds for nsw, you'll see spurious traps every now 
> and then.
> 
> There's a stronger form of undefined behavior, exhibited by things
> like divide by zero, that permits traps.
> 
> John
> 
> 
> 
> On 4/15/16 7:28 PM, Manuel Jacob via llvm-dev wrote:
>> Hi,
>> 
>> In our backend, we currently emit add operations that trap on overflow
>> if the IR operation has the nsw flag set.  Is this allowed?
>> 
>> According to the documentation about poison values, overflowing a nsw
>> add is undefined behavior.  However I didn't find a formal
definition
>> of
>> undefined behavior in LLVM.  Judging from previous discussions on the
>> mailing list, there seems to be a vague line of what LLVM is allowed 
>> to
>> do in case of undefined behavior.  Is trapping allowed?
>> 
>> -Manuel