# how to simplify FP ops with an undef operand?

%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?

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

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.

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.

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.

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.

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.

It’d be great if we can get all of this properly documented in the LangRef - we often seem to be relying on comments next to the individual combines to guide us in many of these cases.

If we’re going to be using isKnownNeverNaN to support this - the SelectionDAG version needs a bit of improvement for better vector handling etc. to match the ValueTracking version.

Fair warning, the following is a tangent from the actual topic under discussion... It's only vaguely connected to the example at hand and is mostly a reaction to a collection of comments in various previous floating point discussion threads.

The reasoning here worries me. The semantics of LLVM IR is specified independently of what any particular target does. Referring to target behavior to decide on appropriate semantics for a particular optimization seems inherently problematic. We should instead use LLVM IR's stated semantics to decide legality. We should only use target semantics to help shape proposals to change the IR semantics.

To be specific, something along the lines of the following seems entirely reasonable: "LLVM IR allows us to perform the following optimization here, but doing that would radically complicate the lowering on target X which doesn't support Y. Should we change the IR specification to Z?" On the other hand, reasoning like "Target X doesn't do Y, so this optimization can't be legal" are problematic.

If the code is more specific than the LangRef, we should propose a clarification to the LangRef. The specification for floating point semantics is admittedly a weakness in the current version. Rather than working around it, we should fix that.

End vaguely related rant, thanks for reading!

Philip

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

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

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

-Eli

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

fdiv snan, snan is undefined? As opposed to producing a qnan, as specified by IEEE-754?

You’re talking about IEEE, I’m talking about LLVM IR. LLVM IR is undefined on SNaNs. It looks like LangRef isn’t clear about this, the only mention of SNaNs is in this statement:

"fdiv is not (currently) defined on SNaN’s.”

However, fdiv/fmul/etc are pervasively treated as not having side effects. The intention, and the only sensible definition for them, is that they are undefined on SNaNs.

-Chris

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

So you don’t think sNaNs can just be treated as if they were qNaNs? I understand why we would want to ignore the signaling part of things, but the rules for operating on NaNs are pretty clear and reasonable to implement. The signaling aspect can, I think, be safely ignored when we are in the mode of assuming the default FP environment.

As for the distinction between IEEE and LLVM IR, I would think we would want to define LLVM IR in such a way that it is possible to create and IEEE-compliant compiler. I know we’re not there yet, but we’re working toward it.

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?

Wait, back up, what? The invalid flag raised by operations on sNaN is no different from any other flag in fenv. There’s nothing sensible about saying that every operation that raises underflow/overflow/inexact is undefined, why are operations on sNaN any different?

– Steve

Ok, my bad, you can use the binary value directly. There are several NaN values, but I guess we could canonicalize on one of them.

Nuno