llvm dev - Mar 2018 - how to simplify FP ops with an undef operand?

For the first part of Sanjay’s question, I think the answer is, “Yes, we can
fold all of these to NaN in the general case.” For the second part, which the
nnan FMF is present, I’m not sure. The particulars of the semantics of nnan are
unclear to me.

But let me explore what Eli is saying. It sounds reasonable, but I have a
question about it.

Suppose we have the nnan FMF set, and we encounter this:

%y = fdiv float %x, undef

If I’ve understood Eli’s interpretation correctly, any of the following
transformations would be legal and safe:

%y = 0.0
%y = -1.0
%y = inf
%y = NaN

And so on, covering all possible concrete values, right? Now suppose I don’t
change it at all. Now I might have IR that looks like this.

%y = fdiv float %x, undef
%z = fmul float %q, %y

At this point, while working on %z, I could reconsider and say “If I had
transformed the fdiv into ‘%y = 0.0’ I could optimize this fmul away too.” So at
that point I can choose to do that, right? And in general I can “retroactively”
choose any concrete value that would be convenient for the next transformation.
You see where I’m going with this?

How is that different from just folding the fdiv into undef to begin with? Is it
because I can’t choose different values on different code paths?

-Andy


From: Friedman, Eli [mailto:efriedma at codeaurora.org]
Sent: Wednesday, February 28, 2018 3:07 PM
To: Sanjay Patel <spatel at rotateright.com>; Kaylor, Andrew
<andrew.kaylor at intel.com>
Cc: llvm-dev <llvm-dev at lists.llvm.org>; Nuno Lopes <nunoplopes at
sapo.pt>; Stephen Canon <scanon at apple.com>; David Majnemer
<david.majnemer at gmail.com>; John Regehr <regehr at cs.utah.edu>;
Sanjoy Das <sanjoy at playingwithpointers.com>; Matt Arsenault <arsenm2
at gmail.com>; Kreitzer, David L <david.l.kreitzer at intel.com>
Subject: Re: how to simplify FP ops with an undef operand?

I'm pretty sure that isn't what nnan is supposed to mean. If the result
of nnan math were undefined in the sense of "undef", programs using
nnan could have undefined behavior if the result is used in certain ways which
would not be undefined for any actual float value (e.g. converting the result to
a string), which seems like a surprising result.  And I don't think we gain
any useful optimization power from saying we can fold to undef instead of
something else.

So I think it's supposed to say "the result is not specified" or
something (so an nnan operation which would produce a nan can instead produce
any value that isn't undef/poison).

-Eli

On 2/28/2018 2:45 PM, Sanjay Patel wrote:
Ah, thanks for explaining. So given that any of these ops will return NaN with a
NaN operand, let's choose the undef operand value to be NaN. That means we
can fold all of these to a NaN constant in the general case.

But if we have 'nnan' FMF, then we can fold harder to undef?
nnan - Allow optimizations to assume the arguments and result are not NaN. Such
optimizations are required to retain defined behavior over NaNs, but the value
of the result is undefined.

On Wed, Feb 28, 2018 at 3:25 PM, Kaylor, Andrew <andrew.kaylor at
intel.com<mailto:andrew.kaylor at intel.com>> wrote:
What I’m saying is that if we have one operand that is not an undef value then
that operand might be NaN and if it is then the result must be NaN. So while it
may be true that we don’t have a NaN, it is not true that we definitely do not
have a NaN in the example. This is analogous to the example in the language
reference where it says “%A = or %X, undef” -> “%A = undef” is unsafe because
any bits that are set in %A must be set in the result. If any floating point
operand is NaN dynamically, then the result must be NaN.

I don’t believe it’s accurate to say that NaN is “morally equivalent” to undef.
There are some similarities, but the important difference is that NaN always has
well defined behavior with a specific correct result. There is, perhaps, a sense
in which it is analogous to a poison value, but for the purposes of reasoning
about the correctness of floating point operations I think it’s best to be
pedantic about treating it as the specific value that it is.

Finally, I was pretty sure you knew that fdiv by zero wasn’t undefined. I just
wanted to clarify that the “?” in your comment was indicating that the assertion
in the language reference was questionable as opposed to this point being in any
way actually uncertain.

From: Sanjay Patel [mailto:spatel at rotateright.com<mailto:spatel at
rotateright.com>]
Sent: Wednesday, February 28, 2018 1:05 PM
To: Kaylor, Andrew <andrew.kaylor at intel.com<mailto:andrew.kaylor at
intel.com>>
Cc: llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>; Nuno Lopes <nunoplopes at
sapo.pt<mailto:nunoplopes at sapo.pt>>; Stephen Canon <scanon at
apple.com<mailto:scanon at apple.com>>; David Majnemer
<david.majnemer at gmail.com<mailto:david.majnemer at gmail.com>>;
John Regehr <regehr at cs.utah.edu<mailto:regehr at cs.utah.edu>>;
Sanjoy Das <sanjoy at playingwithpointers.com<mailto:sanjoy at
playingwithpointers.com>>; Friedman, Eli <efriedma at
codeaurora.org<mailto:efriedma at codeaurora.org>>; Matt Arsenault
<arsenm2 at gmail.com<mailto:arsenm2 at gmail.com>>; Kreitzer, David
L <david.l.kreitzer at intel.com<mailto:david.l.kreitzer at
intel.com>>

Subject: Re: how to simplify FP ops with an undef operand?

Correct - NaN is not undef in IR. But we don't have a NaN in this example.
We have its moral equivalent in LLVM - an uninitialized value, undef.

So we're not introducing any extra uncertainty by propagating the undef. The
backend can choose whatever encoding of undef makes sense when lowering?
And yes, I don't know why FP-div-by-zero would ever be UB. I think that text
in the LangRef should be removed regardless of any other outcome here.

On Wed, Feb 28, 2018 at 1:18 PM, Kaylor, Andrew <andrew.kaylor at
intel.com<mailto:andrew.kaylor at intel.com>> wrote:
Why is NaN “just ‘undef’ in IR”? NaN is a specific value with well-defined
behavior. I would think that unless the no-NaNs flag is used we need to preserve
the behavior of NaNs.

From: Sanjay Patel [mailto:spatel at rotateright.com<mailto:spatel at
rotateright.com>]
Sent: Wednesday, February 28, 2018 12:08 PM
To: Kaylor, Andrew <andrew.kaylor at intel.com<mailto:andrew.kaylor at
intel.com>>
Cc: llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>; Nuno Lopes <nunoplopes at
sapo.pt<mailto:nunoplopes at sapo.pt>>; Stephen Canon <scanon at
apple.com<mailto:scanon at apple.com>>; David Majnemer
<david.majnemer at gmail.com<mailto:david.majnemer at gmail.com>>;
John Regehr <regehr at cs.utah.edu<mailto:regehr at cs.utah.edu>>;
Sanjoy Das <sanjoy at playingwithpointers.com<mailto:sanjoy at
playingwithpointers.com>>; Friedman, Eli <efriedma at
codeaurora.org<mailto:efriedma at codeaurora.org>>; Matt Arsenault
<arsenm2 at gmail.com<mailto:arsenm2 at gmail.com>>
Subject: Re: how to simplify FP ops with an undef operand?

Yes, if %x is a NaN, we should expect that NaN is propagated.

I'm still not sure what to do here. We can take comfort in knowing that
whatever we do is likely an improvement over the current situation though. :)
That's because the code in InstSimplify is inconsistent with the LangRef:
http://llvm.org/docs/LangRef.html#undefined-values (UB for fdiv by 0?)
...and both of those are inconsistent with undef handling in SDAG.
Let me propose an alternate interpretation:

1. The meaning of snan as written in IEEE754-2008 is: "Signaling NaNs
afford representations for uninitialized variables..."
2. That matches our intent with 'undef' here in IR as written in the
LangRef: "unspecified bit-pattern".
3. The current fdiv transform is actually correct (any SNaN UB/trapping
commentary is irrelevant because we assume exceptions are off by default).

The undef operand represents an uninitialized variable, and the result of any FP
op with that uninitialized variable is well-defined: it's another NaN which
is just 'undef' in IR.





On Wed, Feb 28, 2018 at 11:43 AM, Kaylor, Andrew <andrew.kaylor at
intel.com<mailto:andrew.kaylor at intel.com>> wrote:
I’m not sure the transformation happening with fdiv is correct. If we have “%y =
fdiv float %x, undef” and %x is a NaN then the result will be NaN for any value
of the undef, right? So if I understand the undef rules correctly (never a
certainty) then we can’t safely replace the expression with undef. We could, I
think, replace it with “%y = %x” though. I think the same is true for fadd,
fsub, fmul, and frem.

-Andy


%y = fadd float %x, undef

Can we simplify this?

Currently in IR, we do nothing for fadd/fsub/fmul. For fdiv/frem, we propagate
undef. The code comment for fdiv/frem says:
"the undef could be a snan"

If that's correct, then shouldn't it be the same for fadd/fsub/fmul? But
this can't be correct because we support targets that don't raise
exceptions...and even targets that raise exceptions do not trap by default on
snan?






--

Employee of Qualcomm Innovation Center, Inc.

Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180228/f5fc7cbe/attachment.html>

Yes, exactly; the difference is that every use has to use the same 
value, like freeze from the freeze/poison proposal.

-Eli

On 2/28/2018 3:29 PM, Kaylor, Andrew wrote:
>
> For the first part of Sanjay’s question, I think the answer is, “Yes, 
> we can fold all of these to NaN in the general case.” For the second 
> part, which the nnan FMF is present, I’m not sure. The particulars of 
> the semantics of nnan are unclear to me.
>
> But let me explore what Eli is saying. It sounds reasonable, but I 
> have a question about it.
>
> Suppose we have the nnan FMF set, and we encounter this:
>
> %y = fdiv float %x, undef
>
> If I’ve understood Eli’s interpretation correctly, any of the 
> following transformations would be legal and safe:
>
> %y = 0.0
>
> %y = -1.0
>
> %y = inf
>
> %y = NaN
>
> And so on, covering all possible concrete values, right? Now suppose I 
> don’t change it at all. Now I might have IR that looks like this.
>
> %y = fdiv float %x, undef
>
> %z = fmul float %q, %y
>
> At this point, while working on %z, I could reconsider and say “If I 
> had transformed the fdiv into ‘%y = 0.0’ I could optimize this fmul 
> away too.” So at that point I can choose to do that, right? And in 
> general I can “retroactively” choose any concrete value that would be 
> convenient for the next transformation. You see where I’m going with this?
>
> How is that different from just folding the fdiv into undef to begin 
> with? Is it because I can’t choose different values on different code 
> paths?
>
> -Andy
>
> *From:*Friedman, Eli [mailto:efriedma at codeaurora.org]
> *Sent:* Wednesday, February 28, 2018 3:07 PM
> *To:* Sanjay Patel <spatel at rotateright.com>; Kaylor, Andrew 
> <andrew.kaylor at intel.com>
> *Cc:* llvm-dev <llvm-dev at lists.llvm.org>; Nuno Lopes 
> <nunoplopes at sapo.pt>; Stephen Canon <scanon at apple.com>;
David Majnemer
> <david.majnemer at gmail.com>; John Regehr <regehr at
cs.utah.edu>; Sanjoy
> Das <sanjoy at playingwithpointers.com>; Matt Arsenault 
> <arsenm2 at gmail.com>; Kreitzer, David L <david.l.kreitzer at
intel.com>
> *Subject:* Re: how to simplify FP ops with an undef operand?
>
> I'm pretty sure that isn't what nnan is supposed to mean. If the 
> result of nnan math were undefined in the sense of "undef",
programs
> using nnan could have undefined behavior if the result is used in 
> certain ways which would not be undefined for any actual float value 
> (e.g. converting the result to a string), which seems like a 
> surprising result.  And I don't think we gain any useful optimization 
> power from saying we can fold to undef instead of something else.
>
> So I think it's supposed to say "the result is not specified"
or
> something (so an nnan operation which would produce a nan can instead 
> produce any value that isn't undef/poison).
>
> -Eli
>
> On 2/28/2018 2:45 PM, Sanjay Patel wrote:
>
>     Ah, thanks for explaining. So given that any of these ops will
>     return NaN with a NaN operand, let's choose the undef operand
>     value to be NaN. That means we can fold all of these to a NaN
>     constant in the general case.
>
>     But if we have 'nnan' FMF, then we can fold harder to undef?
>     nnan - Allow optimizations to assume the arguments and result are
>     not NaN. Such optimizations are required to retain defined
>     behavior over NaNs, but the value of the result is undefined.
>
>     On Wed, Feb 28, 2018 at 3:25 PM, Kaylor, Andrew
>     <andrew.kaylor at intel.com <mailto:andrew.kaylor at
intel.com>> wrote:
>
>         What I’m saying is that if we have one operand that is not an
>         undef value then that operand might be NaN and if it is then
>         the result must be NaN. So while it may be true that we don’t
>         have a NaN, it is not true that we definitely do not have a
>         NaN in the example. This is analogous to the example in the
>         language reference where it says “%A = or %X, undef” -> “%A >
undef” is unsafe because any bits that are set in %A must be
>         set in the result. If any floating point operand is NaN
>         dynamically, then the result must be NaN.
>
>         I don’t believe it’s accurate to say that NaN is “morally
>         equivalent” to undef. There are some similarities, but the
>         important difference is that NaN always has well defined
>         behavior with a specific correct result. There is, perhaps, a
>         sense in which it is analogous to a poison value, but for the
>         purposes of reasoning about the correctness of floating point
>         operations I think it’s best to be pedantic about treating it
>         as the specific value that it is.
>
>         Finally, I was pretty sure you knew that fdiv by zero wasn’t
>         undefined. I just wanted to clarify that the “?” in your
>         comment was indicating that the assertion in the language
>         reference was questionable as opposed to this point being in
>         any way actually uncertain.
>
>         *From:*Sanjay Patel [mailto:spatel at rotateright.com
>         <mailto:spatel at rotateright.com>]
>         *Sent:* Wednesday, February 28, 2018 1:05 PM
>         *To:* Kaylor, Andrew <andrew.kaylor at intel.com
>         <mailto:andrew.kaylor at intel.com>>
>         *Cc:* llvm-dev <llvm-dev at lists.llvm.org
>         <mailto:llvm-dev at lists.llvm.org>>; Nuno Lopes
>         <nunoplopes at sapo.pt <mailto:nunoplopes at sapo.pt>>;
Stephen
>         Canon <scanon at apple.com <mailto:scanon at
apple.com>>; David
>         Majnemer <david.majnemer at gmail.com
>         <mailto:david.majnemer at gmail.com>>; John Regehr
>         <regehr at cs.utah.edu <mailto:regehr at cs.utah.edu>>;
Sanjoy Das
>         <sanjoy at playingwithpointers.com
>         <mailto:sanjoy at playingwithpointers.com>>; Friedman, Eli
>         <efriedma at codeaurora.org <mailto:efriedma at
codeaurora.org>>;
>         Matt Arsenault <arsenm2 at gmail.com <mailto:arsenm2 at
gmail.com>>;
>         Kreitzer, David L <david.l.kreitzer at intel.com
>         <mailto:david.l.kreitzer at intel.com>>
>
>
>         *Subject:* Re: how to simplify FP ops with an undef operand?
>
>         Correct - NaN is not undef in IR. But we don't have a NaN in
>         this example. We have its moral equivalent in LLVM - an
>         uninitialized value, undef.
>
>         So we're not introducing any extra uncertainty by propagating
>         the undef. The backend can choose whatever encoding of undef
>         makes sense when lowering?
>
>         And yes, I don't know why FP-div-by-zero would ever be UB. I
>         think that text in the LangRef should be removed regardless of
>         any other outcome here.
>
>         On Wed, Feb 28, 2018 at 1:18 PM, Kaylor, Andrew
>         <andrew.kaylor at intel.com <mailto:andrew.kaylor at
intel.com>> wrote:
>
>             Why is NaN “just ‘undef’ in IR”? NaN is a specific value
>             with well-defined behavior. I would think that unless the
>             no-NaNs flag is used we need to preserve the behavior of NaNs.
>
>             *From:*Sanjay Patel [mailto:spatel at rotateright.com
>             <mailto:spatel at rotateright.com>]
>             *Sent:* Wednesday, February 28, 2018 12:08 PM
>             *To:* Kaylor, Andrew <andrew.kaylor at intel.com
>             <mailto:andrew.kaylor at intel.com>>
>             *Cc:* llvm-dev <llvm-dev at lists.llvm.org
>             <mailto:llvm-dev at lists.llvm.org>>; Nuno Lopes
>             <nunoplopes at sapo.pt <mailto:nunoplopes at
sapo.pt>>; Stephen
>             Canon <scanon at apple.com <mailto:scanon at
apple.com>>; David
>             Majnemer <david.majnemer at gmail.com
>             <mailto:david.majnemer at gmail.com>>; John Regehr
>             <regehr at cs.utah.edu <mailto:regehr at
cs.utah.edu>>; Sanjoy
>             Das <sanjoy at playingwithpointers.com
>             <mailto:sanjoy at playingwithpointers.com>>; Friedman,
Eli
>             <efriedma at codeaurora.org
>             <mailto:efriedma at codeaurora.org>>; Matt Arsenault
>             <arsenm2 at gmail.com <mailto:arsenm2 at
gmail.com>>
>             *Subject:* Re: how to simplify FP ops with an undef operand?
>
>             Yes, if %x is a NaN, we should expect that NaN is propagated.
>
>             I'm still not sure what to do here. We can take comfort in
>             knowing that whatever we do is likely an improvement over
>             the current situation though. :)
>
>             That's because the code in InstSimplify is inconsistent
>             with the LangRef:
>             http://llvm.org/docs/LangRef.html#undefined-values (UB for
>             fdiv by 0?)
>
>             ...and both of those are inconsistent with undef handling
>             in SDAG.
>
>             Let me propose an alternate interpretation:
>
>             1. The meaning of snan as written in IEEE754-2008 is:
>             "Signaling NaNs afford representations for uninitialized
>             variables..."
>             2. That matches our intent with 'undef' here in IR as
>             written in the LangRef: "unspecified bit-pattern".
>             3. The current fdiv transform is actually correct (any
>             SNaN UB/trapping commentary is irrelevant because we
>             assume exceptions are off by default).
>
>             The undef operand represents an uninitialized variable,
>             and the result of any FP op with that uninitialized
>             variable is well-defined: it's another NaN which is just
>             'undef' in IR.
>
>             On Wed, Feb 28, 2018 at 11:43 AM, Kaylor, Andrew
>             <andrew.kaylor at intel.com <mailto:andrew.kaylor at
intel.com>>
>             wrote:
>
>                 I’m not sure the transformation happening with fdiv is
>                 correct. If we have “%y = fdiv float %x, undef” and %x
>                 is a NaN then the result will be NaN for any value of
>                 the undef, right? So if I understand the undef rules
>                 correctly (never a certainty) then we can’t safely
>                 replace the expression with undef. We could, I think,
>                 replace it with “%y = %x” though. I think the same is
>                 true for fadd, fsub, fmul, and frem.
>
>                 -Andy
>
>                 %y = fadd float %x, undef
>
>                 Can we simplify this?
>
>                 Currently in IR, we do nothing for fadd/fsub/fmul. For
>                 fdiv/frem, we propagate undef. The code comment for
>                 fdiv/frem says:
>                 "the undef could be a snan"
>
>                 If that's correct, then shouldn't it be the same
for
>                 fadd/fsub/fmul? But this can't be correct because we
>                 support targets that don't raise exceptions...and even
>                 targets that raise exceptions do not trap by default
>                 on snan?
>
> -- 
> Employee of Qualcomm Innovation Center, Inc.
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project

-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180228/6f77a3dd/attachment-0001.html>

On Feb 28, 2018, at 3:29 PM, Kaylor, Andrew via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> For the first part of Sanjay’s question, I think the answer is, “Yes, we
can fold all of these to NaN in the general case.”
Agreed.  Those IR instructions are undefined on SNAN, and that undef could take
on an SNAN value.  Folding these instructions to undef seems reasonable, and it
is arguable that you could even fold it to an ‘unreachable'.

-Chris

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

On 2/28/2018 5:46 PM, Chris Lattner wrote:
> On Feb 28, 2018, at 3:29 PM, Kaylor, Andrew via llvm-dev 
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>> wrote:
>> For the first part of Sanjay’s question, I think the answer is, “Yes, 
>> we can fold all of these to NaN in the general case.”
>
> Agreed.  Those IR instructions are undefined on SNAN, and that undef 
> could take on an SNAN value.  Folding these instructions to undef 
> seems reasonable, and it is arguable that you could even fold it to an 
> ‘unreachable'.
fdiv snan, snan is undefined?  As opposed to producing a qnan, as 
specified by IEEE-754?

-Eli

-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project

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

We can do "add %x, undef" => "undef" because for any
value of %x, we can
always find a value that when added to %x produces any value in the domain 
of integers.

This is not the case with floats since with some inputs, e.g., NaNs, we are 
not able to produce some values in the domain (e.g., there's no value of %x 
that makes "fadd NaN, %x" return 42.0).

In summary, since there's no NaN constant in the IR, all we can do is to 
canonicalize to some instruction that yields NaN (and treat that as a NaN 
constant throughout the pipeline, I guess).

Nuno

P.S.: With poison you can always fold operations with a poison input to 
poison (e.g., "fadd %x, poison" => poison).


-----Original Message----- 
From: Kaylor, Andrew
Sent: Wednesday, February 28, 2018 11:29 PM
Subject: RE: how to simplify FP ops with an undef operand?



For the first part of Sanjay’s question, I think the answer is, “Yes, we can 
fold all of these to NaN in the general case.” For the second part, which 
the nnan FMF is present, I’m not sure. The particulars of the semantics of 
nnan are unclear to me.



But let me explore what Eli is saying. It sounds reasonable, but I have a 
question about it.



Suppose we have the nnan FMF set, and we encounter this:



%y = fdiv float %x, undef



If I’ve understood Eli’s interpretation correctly, any of the following 
transformations would be legal and safe:



%y = 0.0

%y = -1.0

%y = inf

%y = NaN



And so on, covering all possible concrete values, right? Now suppose I don’t 
change it at all. Now I might have IR that looks like this.



%y = fdiv float %x, undef

%z = fmul float %q, %y



At this point, while working on %z, I could reconsider and say “If I had 
transformed the fdiv into ‘%y = 0.0’ I could optimize this fmul away too.” 
So at that point I can choose to do that, right? And in general I can 
“retroactively” choose any concrete value that would be convenient for the 
next transformation. You see where I’m going with this?



How is that different from just folding the fdiv into undef to begin with? 
Is it because I can’t choose different values on different code paths?



-Andy







From: Friedman, Eli [mailto:efriedma at codeaurora.org]
Sent: Wednesday, February 28, 2018 3:07 PM
To: Sanjay Patel <spatel at rotateright.com>; Kaylor, Andrew 
<andrew.kaylor at intel.com>
Cc: llvm-dev <llvm-dev at lists.llvm.org>; Nuno Lopes <nunoplopes at
sapo.pt>;
Stephen Canon <scanon at apple.com>; David Majnemer <david.majnemer at
gmail.com>;
John Regehr <regehr at cs.utah.edu>; Sanjoy Das 
<sanjoy at playingwithpointers.com>; Matt Arsenault <arsenm2 at
gmail.com>;
Kreitzer, David L <david.l.kreitzer at intel.com>
Subject: Re: how to simplify FP ops with an undef operand?







I'm pretty sure that isn't what nnan is supposed to mean. If the result
of
nnan math were undefined in the sense of "undef", programs using nnan
could
have undefined behavior if the result is used in certain ways which would 
not be undefined for any actual float value (e.g. converting the result to a 
string), which seems like a surprising result.  And I don't think we gain 
any useful optimization power from saying we can fold to undef instead of 
something else.

So I think it's supposed to say "the result is not specified" or
something
(so an nnan operation which would produce a nan can instead produce any 
value that isn't undef/poison).

-Eli

On 2/28/2018 2:45 PM, Sanjay Patel wrote:



Ah, thanks for explaining. So given that any of these ops will return NaN 
with a NaN operand, let's choose the undef operand value to be NaN. That 
means we can fold all of these to a NaN constant in the general case.

But if we have 'nnan' FMF, then we can fold harder to undef?
nnan - Allow optimizations to assume the arguments and result are not NaN. 
Such optimizations are required to retain defined behavior over NaNs, but 
the value of the result is undefined.







On Wed, Feb 28, 2018 at 3:25 PM, Kaylor, Andrew <andrew.kaylor at
intel.com>
wrote:



What I’m saying is that if we have one operand that is not an undef value 
then that operand might be NaN and if it is then the result must be NaN. So 
while it may be true that we don’t have a NaN, it is not true that we 
definitely do not have a NaN in the example. This is analogous to the 
example in the language reference where it says “%A = or %X, undef” -> “%A = 
undef” is unsafe because any bits that are set in %A must be set in the 
result. If any floating point operand is NaN dynamically, then the result 
must be NaN.



I don’t believe it’s accurate to say that NaN is “morally equivalent” to 
undef. There are some similarities, but the important difference is that NaN 
always has well defined behavior with a specific correct result. There is, 
perhaps, a sense in which it is analogous to a poison value, but for the 
purposes of reasoning about the correctness of floating point operations I 
think it’s best to be pedantic about treating it as the specific value that 
it is.



Finally, I was pretty sure you knew that fdiv by zero wasn’t undefined. I 
just wanted to clarify that the “?” in your comment was indicating that the 
assertion in the language reference was questionable as opposed to this 
point being in any way actually uncertain.



From: Sanjay Patel [mailto:spatel at rotateright.com]
Sent: Wednesday, February 28, 2018 1:05 PM
To: Kaylor, Andrew <andrew.kaylor at intel.com>
Cc: llvm-dev <llvm-dev at lists.llvm.org>; Nuno Lopes <nunoplopes at
sapo.pt>;
Stephen Canon <scanon at apple.com>; David Majnemer <david.majnemer at
gmail.com>;
John Regehr <regehr at cs.utah.edu>; Sanjoy Das 
<sanjoy at playingwithpointers.com>; Friedman, Eli <efriedma at
codeaurora.org>;
Matt Arsenault <arsenm2 at gmail.com>; Kreitzer, David L 
<david.l.kreitzer at intel.com>




Subject: Re: how to simplify FP ops with an undef operand?







Correct - NaN is not undef in IR. But we don't have a NaN in this example. 
We have its moral equivalent in LLVM - an uninitialized value, undef.

So we're not introducing any extra uncertainty by propagating the undef. The
backend can choose whatever encoding of undef makes sense when lowering?



And yes, I don't know why FP-div-by-zero would ever be UB. I think that text
in the LangRef should be removed regardless of any other outcome here.







On Wed, Feb 28, 2018 at 1:18 PM, Kaylor, Andrew <andrew.kaylor at
intel.com>
wrote:



Why is NaN “just ‘undef’ in IR”? NaN is a specific value with well-defined 
behavior. I would think that unless the no-NaNs flag is used we need to 
preserve the behavior of NaNs.



From: Sanjay Patel [mailto:spatel at rotateright.com]
Sent: Wednesday, February 28, 2018 12:08 PM
To: Kaylor, Andrew <andrew.kaylor at intel.com>
Cc: llvm-dev <llvm-dev at lists.llvm.org>; Nuno Lopes <nunoplopes at
sapo.pt>;
Stephen Canon <scanon at apple.com>; David Majnemer <david.majnemer at
gmail.com>;
John Regehr <regehr at cs.utah.edu>; Sanjoy Das 
<sanjoy at playingwithpointers.com>; Friedman, Eli <efriedma at
codeaurora.org>;
Matt Arsenault <arsenm2 at gmail.com>
Subject: Re: how to simplify FP ops with an undef operand?







Yes, if %x is a NaN, we should expect that NaN is propagated.

I'm still not sure what to do here. We can take comfort in knowing that 
whatever we do is likely an improvement over the current situation though. 
:)



That's because the code in InstSimplify is inconsistent with the LangRef:
http://llvm.org/docs/LangRef.html#undefined-values (UB for fdiv by 0?)



...and both of those are inconsistent with undef handling in SDAG.



Let me propose an alternate interpretation:

1. The meaning of snan as written in IEEE754-2008 is: "Signaling NaNs
afford
representations for uninitialized variables..."
2. That matches our intent with 'undef' here in IR as written in the 
LangRef: "unspecified bit-pattern".
3. The current fdiv transform is actually correct (any SNaN UB/trapping 
commentary is irrelevant because we assume exceptions are off by default).

The undef operand represents an uninitialized variable, and the result of 
any FP op with that uninitialized variable is well-defined: it's another NaN
which is just 'undef' in IR.























On Wed, Feb 28, 2018 at 11:43 AM, Kaylor, Andrew <andrew.kaylor at
intel.com>
wrote:



I’m not sure the transformation happening with fdiv is correct. If we have 
“%y = fdiv float %x, undef” and %x is a NaN then the result will be NaN for 
any value of the undef, right? So if I understand the undef rules correctly 
(never a certainty) then we can’t safely replace the expression with undef. 
We could, I think, replace it with “%y = %x” though. I think the same is 
true for fadd, fsub, fmul, and frem.



-Andy







%y = fadd float %x, undef







Can we simplify this?

Currently in IR, we do nothing for fadd/fsub/fmul. For fdiv/frem, we 
propagate undef. The code comment for fdiv/frem says:
"the undef could be a snan"







If that's correct, then shouldn't it be the same for fadd/fsub/fmul? But
this can't be correct because we support targets that don't raise 
exceptions...and even targets that raise exceptions do not trap by default 
on snan?



-- Employee of Qualcomm Innovation Center, Inc.Qualcomm Innovation Center, 
Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative 
Project

On Thu, Mar 1, 2018 at 2:08 AM, Nuno Lopes <nunoplopes at sapo.pt> wrote:
> We can do "add %x, undef" => "undef" because for any
value of %x, we can
> always find a value that when added to %x produces any value in the domain
> of integers.
>
> This is not the case with floats since with some inputs, e.g., NaNs, we
> are not able to produce some values in the domain (e.g., there's no
value
> of %x that makes "fadd NaN, %x" return 42.0).
>
> In summary, since there's no NaN constant in the IR

Isn't "float 0x7FF8000000000000" a NaN constant?


> , all we can do is to canonicalize to some instruction that yields NaN
> (and treat that as a NaN constant throughout the pipeline, I guess).
>
> Nuno
>
> P.S.: With poison you can always fold operations with a poison input to
> poison (e.g., "fadd %x, poison" => poison).
>
>
> -----Original Message----- From: Kaylor, Andrew
> Sent: Wednesday, February 28, 2018 11:29 PM
> Subject: RE: how to simplify FP ops with an undef operand?
>
>
>
>
> For the first part of Sanjay’s question, I think the answer is, “Yes, we
> can fold all of these to NaN in the general case.” For the second part,
> which the nnan FMF is present, I’m not sure. The particulars of the
> semantics of nnan are unclear to me.
>
>
>
> But let me explore what Eli is saying. It sounds reasonable, but I have a
> question about it.
>
>
>
> Suppose we have the nnan FMF set, and we encounter this:
>
>
>
> %y = fdiv float %x, undef
>
>
>
> If I’ve understood Eli’s interpretation correctly, any of the following
> transformations would be legal and safe:
>
>
>
> %y = 0.0
>
> %y = -1.0
>
> %y = inf
>
> %y = NaN
>
>
>
> And so on, covering all possible concrete values, right? Now suppose I
> don’t change it at all. Now I might have IR that looks like this.
>
>
>
> %y = fdiv float %x, undef
>
> %z = fmul float %q, %y
>
>
>
> At this point, while working on %z, I could reconsider and say “If I had
> transformed the fdiv into ‘%y = 0.0’ I could optimize this fmul away too.”
> So at that point I can choose to do that, right? And in general I can
> “retroactively” choose any concrete value that would be convenient for the
> next transformation. You see where I’m going with this?
>
>
>
> How is that different from just folding the fdiv into undef to begin with?
> Is it because I can’t choose different values on different code paths?
>
>
>
> -Andy
>
>
>
>
>
>
>
> From: Friedman, Eli [mailto:efriedma at codeaurora.org]
> Sent: Wednesday, February 28, 2018 3:07 PM
> To: Sanjay Patel <spatel at rotateright.com>; Kaylor, Andrew <
> andrew.kaylor at intel.com>
> Cc: llvm-dev <llvm-dev at lists.llvm.org>; Nuno Lopes <nunoplopes
at sapo.pt>;
> Stephen Canon <scanon at apple.com>; David Majnemer
<david.majnemer at gmail.com>;
> John Regehr <regehr at cs.utah.edu>; Sanjoy Das <
> sanjoy at playingwithpointers.com>; Matt Arsenault <arsenm2 at
gmail.com>;
> Kreitzer, David L <david.l.kreitzer at intel.com>
> Subject: Re: how to simplify FP ops with an undef operand?
>
>
>
>
>
>
>
> I'm pretty sure that isn't what nnan is supposed to mean. If the
result of
> nnan math were undefined in the sense of "undef", programs using
nnan could
> have undefined behavior if the result is used in certain ways which would
> not be undefined for any actual float value (e.g. converting the result to
> a string), which seems like a surprising result.  And I don't think we
gain
> any useful optimization power from saying we can fold to undef instead of
> something else.
>
> So I think it's supposed to say "the result is not specified"
or something
> (so an nnan operation which would produce a nan can instead produce any
> value that isn't undef/poison).
>
> -Eli
>
> On 2/28/2018 2:45 PM, Sanjay Patel wrote:
>
>
>
> Ah, thanks for explaining. So given that any of these ops will return NaN
> with a NaN operand, let's choose the undef operand value to be NaN.
That
> means we can fold all of these to a NaN constant in the general case.
>
> But if we have 'nnan' FMF, then we can fold harder to undef?
> nnan - Allow optimizations to assume the arguments and result are not NaN.
> Such optimizations are required to retain defined behavior over NaNs, but
> the value of the result is undefined.
>
>
>
>
>
>
>
> On Wed, Feb 28, 2018 at 3:25 PM, Kaylor, Andrew <andrew.kaylor at
intel.com>
> wrote:
>
>
>
> What I’m saying is that if we have one operand that is not an undef value
> then that operand might be NaN and if it is then the result must be NaN. So
> while it may be true that we don’t have a NaN, it is not true that we
> definitely do not have a NaN in the example. This is analogous to the
> example in the language reference where it says “%A = or %X, undef” ->
“%A
> = undef” is unsafe because any bits that are set in %A must be set in the
> result. If any floating point operand is NaN dynamically, then the result
> must be NaN.
>
>
>
> I don’t believe it’s accurate to say that NaN is “morally equivalent” to
> undef. There are some similarities, but the important difference is that
> NaN always has well defined behavior with a specific correct result. There
> is, perhaps, a sense in which it is analogous to a poison value, but for
> the purposes of reasoning about the correctness of floating point
> operations I think it’s best to be pedantic about treating it as the
> specific value that it is.
>
>
>
> Finally, I was pretty sure you knew that fdiv by zero wasn’t undefined. I
> just wanted to clarify that the “?” in your comment was indicating that the
> assertion in the language reference was questionable as opposed to this
> point being in any way actually uncertain.
>
>
>
> From: Sanjay Patel [mailto:spatel at rotateright.com]
> Sent: Wednesday, February 28, 2018 1:05 PM
> To: Kaylor, Andrew <andrew.kaylor at intel.com>
> Cc: llvm-dev <llvm-dev at lists.llvm.org>; Nuno Lopes <nunoplopes
at sapo.pt>;
> Stephen Canon <scanon at apple.com>; David Majnemer
<david.majnemer at gmail.com>;
> John Regehr <regehr at cs.utah.edu>; Sanjoy Das <
> sanjoy at playingwithpointers.com>; Friedman, Eli <efriedma at
codeaurora.org>;
> Matt Arsenault <arsenm2 at gmail.com>; Kreitzer, David L <
> david.l.kreitzer at intel.com>
>
>
>
>
> Subject: Re: how to simplify FP ops with an undef operand?
>
>
>
>
>
>
>
> Correct - NaN is not undef in IR. But we don't have a NaN in this
example.
> We have its moral equivalent in LLVM - an uninitialized value, undef.
>
> So we're not introducing any extra uncertainty by propagating the
undef.
> The backend can choose whatever encoding of undef makes sense when
lowering?
>
>
>
> And yes, I don't know why FP-div-by-zero would ever be UB. I think that
> text in the LangRef should be removed regardless of any other outcome here.
>
>
>
>
>
>
>
> On Wed, Feb 28, 2018 at 1:18 PM, Kaylor, Andrew <andrew.kaylor at
intel.com>
> wrote:
>
>
>
> Why is NaN “just ‘undef’ in IR”? NaN is a specific value with well-defined
> behavior. I would think that unless the no-NaNs flag is used we need to
> preserve the behavior of NaNs.
>
>
>
> From: Sanjay Patel [mailto:spatel at rotateright.com]
> Sent: Wednesday, February 28, 2018 12:08 PM
> To: Kaylor, Andrew <andrew.kaylor at intel.com>
> Cc: llvm-dev <llvm-dev at lists.llvm.org>; Nuno Lopes <nunoplopes
at sapo.pt>;
> Stephen Canon <scanon at apple.com>; David Majnemer
<david.majnemer at gmail.com>;
> John Regehr <regehr at cs.utah.edu>; Sanjoy Das <
> sanjoy at playingwithpointers.com>; Friedman, Eli <efriedma at
codeaurora.org>;
> Matt Arsenault <arsenm2 at gmail.com>
> Subject: Re: how to simplify FP ops with an undef operand?
>
>
>
>
>
>
>
> Yes, if %x is a NaN, we should expect that NaN is propagated.
>
> I'm still not sure what to do here. We can take comfort in knowing that
> whatever we do is likely an improvement over the current situation though.
> :)
>
>
>
> That's because the code in InstSimplify is inconsistent with the
LangRef:
> http://llvm.org/docs/LangRef.html#undefined-values (UB for fdiv by 0?)
>
>
>
> ...and both of those are inconsistent with undef handling in SDAG.
>
>
>
> Let me propose an alternate interpretation:
>
> 1. The meaning of snan as written in IEEE754-2008 is: "Signaling NaNs
> afford representations for uninitialized variables..."
> 2. That matches our intent with 'undef' here in IR as written in
the
> LangRef: "unspecified bit-pattern".
> 3. The current fdiv transform is actually correct (any SNaN UB/trapping
> commentary is irrelevant because we assume exceptions are off by default).
>
> The undef operand represents an uninitialized variable, and the result of
> any FP op with that uninitialized variable is well-defined: it's
another
> NaN which is just 'undef' in IR.
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> On Wed, Feb 28, 2018 at 11:43 AM, Kaylor, Andrew <andrew.kaylor at
intel.com>
> wrote:
>
>
>
> I’m not sure the transformation happening with fdiv is correct. If we have
> “%y = fdiv float %x, undef” and %x is a NaN then the result will be NaN for
> any value of the undef, right? So if I understand the undef rules correctly
> (never a certainty) then we can’t safely replace the expression with undef.
> We could, I think, replace it with “%y = %x” though. I think the same is
> true for fadd, fsub, fmul, and frem.
>
>
>
> -Andy
>
>
>
>
>
>
>
> %y = fadd float %x, undef
>
>
>
>
>
>
>
> Can we simplify this?
>
> Currently in IR, we do nothing for fadd/fsub/fmul. For fdiv/frem, we
> propagate undef. The code comment for fdiv/frem says:
> "the undef could be a snan"
>
>
>
>
>
>
>
> If that's correct, then shouldn't it be the same for
fadd/fsub/fmul? But
> this can't be correct because we support targets that don't raise
> exceptions...and even targets that raise exceptions do not trap by default
> on snan?
>
>
>
> -- Employee of Qualcomm Innovation Center, Inc.Qualcomm Innovation Center,
> Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative
> Project
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180301/e6e04e48/attachment.html>