Semantics of NaN

IR & Optimizations
1

I’m trying to (re-)implement NaN in Alive2, including signaling/quiet NaNs, etc
Since I don’t know much about floats, I’ve a few questions about what’s the intended semantics.

  1. Do all arithmetic FP operations return a canonical NaN (i.e., a fixed bit pattern)? Or can they return different bit patterns on each execution?
  2. How instructions always return silent NaNs? Or is there a global flag to make them return signaling NaNs?
  3. Do the regular FP ops in LLVM signal with signaling NaNs? Do you need to use some specific intrinsic? Or does it depend on a global flag?
  4. Do FP operations canonicalize NaNs? For example, can fsub %x, 0 be replaced with %x? If NaN canonicalization happens, then the answer is no! Likewise for fmul %x, 1.0
  5. Are fabs and fneg special when handling denormals and NaNs? Do they only flip the sign bit and that’s it?
  6. If 5) is true, then fsub 0, %x if not equivalent to fneg %x?
  7. Does load canonicalizes NaNs? This is a long-standing question, so I would like to document it. If the answer is no, can we support x87 correctly? Does that matter? What about bitcast?
  8. Do phi & select canonicalize NaNs? In case they have fast-math flags, e.g. we only adjust the sign bit (for nsz)?
  9. Can the compiler assume any NaN bit pattern. E.g., can we replace fdiv 0.0, 0.0 with 2139095041 (or any NaN pattern)?

Note that the answers for these questions depend greatly on the ISAs we care about. I have even less idea about what the chips do for the cases above.

Original thread: 45152 – Instcombine incorrectly transforms store i64 -> store double
Related gcc x87 miscompilation: 58416 – Incorrect x87-based union copying code

Thank you!

1 Like
2

IEEE 754-2019 introduces the idea of a canonical NaN, but it does not require it. I don’t think we can rely on exact content of a NaN in LLVM, aside from quiet vs signaling, it does not make any guarantees about that (and neither do runtime libraries).

3

Going off of memory so there may be some inaccurate points here, but here’s my understanding:

Do all arithmetic FP operations return a canonical NaN (i.e., a fixed bit pattern)? Or can they return different bit patterns on each execution?

Minnum/maxnum may be a special case. If both inputs to minnum/maxnum are a nan, you can get the payload bits for either one.

How instructions always return silent NaNs? Or is there a global flag to make them return signaling NaNs?

Yes (the exception is for copysign, fneg and fabs which are bit ops). There is another exception, which is libm’s fmin and fmax will return a signaling nan (which are also what you currently get with llvm.minnum/maxnum)

Signaling nans are never returned in proper IEEE code and only appear from initializations. Any proper FP operation should raise exception and pass through the quieted nan. There are some non-IEEE exceptions that do apply. AMDGPU has an FP mode bit that breaks signaling nan handling (used by default for graphics), such that signaling nans aren’t quieted and end up getting passed through. Technically, we should have to insert some bit ops to quiet signaling nans but that would be really slow and nobody would ever implement. If we cared to try to handle signaling nans in non-strict FP code, I’d really like to have separate nnan flags for qnan and san.

Do the regular FP ops in LLVM signal with signaling NaNs? Do you need to use some specific intrinsic? Or does it depend on a global flag?

This isn’t really written. In practice LLVM pretends signaling nans don’t exist and break the handling everywhere. I view getting correct snan behavior here as somewhat hopeless, and if you expect correct snan handling you should probably just use the constrained FP intrinsics.

Do FP operations canonicalize NaNs? For example, can fsub %x, 0 be replaced with %x? If NaN canonicalization happens, then the answer is no! Likewise for fmul %x, 1.0

“For an operation with quiet NaN inputs, except as stated otherwise, if a floating-point result is to be delivered the result shall be a canonical quiet NaN”

This would change the payload bits, which according to the spec says preserves the literal meaning of the source even though it is value changing. I think this optimization should be OK; we could reconsider for constrained operations.

Are fabs and fneg special when handling denormals and NaNs? Do they only flip the sign bit and that’s it?

These are non-canonicalizing bit operations. They only touch the sign bit and nothing else. copysign also belongs in this family.

If 5) is true, then fsub 0, %x if not equivalent to fneg %x?

Yes, this is why it was silly to treat the fsub special case as identical and why later the fneg instruction was introduced.

Does load canonicalizes NaNs? This is a long-standing question, so I would like to document it. If the answer is no, can we support x87 correctly? Does that matter? What about bitcast?

No, that would imply specialness of memory based on the type. If you wanted to have canonical load semantics, you could insert a canonicalize call around your IR load. A backend with load FP semantics could fold the canonicalize into the load.

Do phi & select canonicalize NaNs? In case they have fast-math flags, e.g. we only adjust the sign bit (for nsz)?

No, for the same reasons as above. It’s specific FP operations that canonicalize

Can the compiler assume any NaN bit pattern. E.g., can we replace fdiv 0.0, 0.0 with 2139095041 (or any NaN pattern)?

I’d hope that any quiet bit pattern would be valid, and we would prefer to fold to a canonical quiet nan with no extra payload bits set. The problem is quiet vs. signaling wasn’t originally specified. Old mips had a different scheme than everyone else, but this is specified in the 2008 standard.

A few other points to consider:

  • Denormal flushing is not something recognized by the IEEE standard, so there’s a room for interpretation on what denormal-fp-mode really implies. I was viewing it as informative of what the FP mode is expected to be for the current function, but doesn’t mandate producing a flushed result. If you wanted to observe canonical bits, you could have inserted a canonicalize call. That’s all well and good for the denormal output flushing, but the denormal input handling is the scary one. For instance you now have to guard against potentially denormal inputs to avoid divide by 0.

  • Getting correct snan and denormal flushing behavior behavior for all the existing non-strict optimizations would be a pretty huge amount of work, and would involve introduce quite a lot of new canonicalizes if we were to fully model this. We’d probably want to promote canonicalize to a first class instruction if someone seriously wanted to pursue this and work hard to eliminate them.

  • The minnum/maxnum intrinsics were incorrectly named. They really have libm fmin/fmax semantics and will return a signaling nan. We should really rename these, and have the proper quieting semantics in another intrinsic pair

1 Like
4
  1. Do all arithmetic FP operations return a canonical NaN (i.e., a fixed bit pattern)? Or can they return different bit patterns on each execution?

Neither is a correct answer. The basic rule of thumb for operations (note this includes math library functions) in IEEE 754 is the flow is as follows:

  • If an input is a sNaN, signal the invalid exception and quiet the NaN.
  • If an input is a NaN and the output is a NaN, the result is a qNaN with the same payload as one of the inputs (which one is unspecified, and varies between different hardware implementations).
  • If no input is a NaN and the output is a NaN (e.g., 0.0/0.0), a qNaN is returned. I’m not seeing any definition of what the payload can be in IEEE 754, but my understanding is that the intent is that an implementation that stores the address of instruction as the payload in this case is meant to be conforming.

In other words, absent a few special-case operations, it’s guaranteed that the output of an operation is a qNaN, and a “custom” NaN payload is guaranteed to propagate through operations in a matter akin to pointer provenance. There is a concept of “canonical NaN”, but I believe this is parlance for cases like x87’s pseudo-NaN values, and for the basic bfloat, half, float, double, and fp128 types, every NaN is canonical.

  1. How instructions always return silent NaNs? Or is there a global flag to make them return signaling NaNs?

With a few exceptions (principally the operations that explicitly only manipulate the sign bit, or that allow users to construct custom NaNs like C’s setpayload), the result of every arithmetic operation is guaranteed to not be an sNaN.

  1. Do the regular FP ops in LLVM signal with signaling NaNs? Do you need to use some specific intrinsic? Or does it depend on a global flag?

C explicitly allows implementations the freedom to treat all sNaNs as if they were qNaNs, and C2x adds an FE_SNANS_ALWAYS_SIGNAL flag to detect if they take this freedom or not. I believe it is reasonable to assume that anything not using strictfp and constrained intrinsics is operating in an sNaN-is-qNaN mode (in other words, the C2x flag should only be set if -ffp-model=strict or similar is on the command line).

  1. Do FP operations canonicalize NaNs? For example, can fsub %x, 0 be replaced with %x? If NaN canonicalization happens, then the answer is no! Likewise for fmul %x, 1.0

The non-constrained operations are assumed to be in default rounding mode and ignoring exceptions, and NaN payloads are guaranteed to propagate, so replacing fsub %x, 0 with %x should be legal if the floating-point type is not x87_fp80 or ppc_fp128 (which have non-canonical NaNs). Actually, if you’re in a denormals-are-zero function, then it also changes the value, since a denormal is effectively noncanonical in that scenario.

  1. Are fabs and fneg special when handling denormals and NaNs? Do they only flip the sign bit and that’s it?

Yes. These operations are documented as flipping only the sign bit. They don’t even signal an exception if the input is sNaN, and they will return an sNaN output if the input is sNaN. They even preserve noncanonical encodings.

  1. If 5) is true, then fsub 0, %x if not equivalent to fneg %x?

That is why an fneg instruction was effectively added.

  1. Does load canonicalizes NaNs? This is a long-standing question, so I would like to document it. If the answer is no, can we support x87 correctly? Does that matter? What about bitcast?
  2. Do phi & select canonicalize NaNs? In case they have fast-math flags, e.g. we only adjust the sign bit (for nsz)?

Canonicalization should ideally happen only at the user’s explicit request, although I believe almost every floating-point arithmetic operation implicitly canonicalizes its inputs. (Note that canonicalization’s effects are to turn sNaN into qNaN, denormals into zero [in DAZ mode], and… something for the x87_fp80 types and ppc_fp128 that I doubt too many people actually care about).

I’m not sure if DAZ mode means that fcmp x, y is equivalent to fcmp (canonicalize x), (canonicalize y) (it appears to be true on x86 from the manual), but if that is the case, then you can handle noncanonical loads on x87 by only loading it as a float if you know all of the uses implicitly canonicalize, and using integer operations for those uses that don’t canonicalize (which include fneg and fabs). The only case I don’t know how to make noncanonical easily is ret float %x… maybe you could do it if you used FXSAVE/FXRSTOR? (NB: this is not a performance-oriented lowering.)

  1. Can the compiler assume any NaN bit pattern. E.g., can we replace fdiv 0.0, 0.0 with 2139095041 (or any NaN pattern)?

Now you’re getting into what LLVM’s NaN semantics should be as opposed to IEEE 754. :slight_smile:

Semantically, any operation that generates a NaN (i.e., none of its inputs were a NaN) should be viewed as producing an unspecified qNaN. Pragmatically, it should be the preferred qNaN (which, as @arsenm noted, is different for older MIPS processors). If the inputs are NaNs, then it is safe to replace fdiv %x, %y with canonicalize %x or canonicalize %y (if both are NaN, it’s unspecified which one it returns, so the optimizer could pick either one). I don’t think it is wise to eliminate user-added canonicalize operations, but I suspect in practice, we do a bad job of preserving the implicit canonicalize steps of existing FP operations.

1 Like
5

It would also be interesting to know whether just copying floats around guarantees to preserve NaN bits or not. I.e., can only float arithmetic change NaNs, or can this even happen “silently”? I sure hope only operations can affect NaN values but at least on some architectures, that does not currently seem to be guaranteed on 32bit x86. Would be good to get an official statement whether this is a bug/deficiency of that particular backend, or part of the LLVM semantics.

Furthermore, from trouble we are having in Rust it seems like LLVM also treats the sign of NaNs as unstable under optimizations. Is that deliberate?

(For the curious, here is a collection of float-related trouble in Rust, some of it involves LLVM and some does not.)

1 Like
6

I think that’s the intent.

(github issues link to that report: Instcombine incorrectly transforms store i64 -> store double · Issue #44497 · llvm/llvm-project · GitHub)

The semantics of float/double on x87 is basically hopeless…we can’t even be value-preserving across a spill to memory, never-mind NAN-preserving. The registers always store an 80-bit precision float, and all operations (e.g. add) are 80-bit operations. The only way to round down to float/double precision is store/load. So if you have a function that claims to be

define float @f(float %0, float %1) {
  %3 = fadd float %0, %1
  ret float %3
}

…on x86-32 with SSE2 disabled, that’s a big lie. The ABI calls for the float parameters to be passed in memory, so those are actually 32-bit floats. But they get converted to x86_fp80 upon load, the add is really fadd x86_fp80 under the hood – and then the return is in a register, so that’s actually x86_fp80 as well. Yet, if you put a store/load before the return (either in IR – as it was before optimization passes, or even as a register spill!), it’ll change the return value.

This is why GCC has (default off) flags like -ffloat-store and -fexcess-precision=standard. Clang never implemented support for those flags, I expect because Clang defaults to using SSE2 on x86-32, which avoids any of these problems. At this point, I don’t think anyone cares about getting floating-point math actually correct in this mode…

7

If we can rely on this being basically an x86-32 backend bug (caused by hardware limitations) that will not affect other bugs, that’s probably the best we can hope for at this point.

AFAIK some problems remain? I don’t understand the details but Rust is observing problems even with SSE2 enabled, and it seems to be because the x87 stack is still used for return values? (The Rust i686 target does have SSE2 enabled, similar to Clang.)

8

Yes, you’re correct. The standard C ABI requires using the x87 stack for return values.

Because we always use the SSE2 FPU for float/double types inside a function, we have eliminated the problems with excess precision, which is 99% of the problems people run into. But, for the return value, we must move the value from an xmm register to the 80-bit x87 fpu stack. That is considered a format conversion by the X87 FPU (from float/double → x86_fp80), which means it can raise fp exceptions and does NaN canonicalization.

I think there’s nothing that can reasonably be done, without using an incompatible ABI, which isn’t going to happen (by default) for C. But since rust doesn’t promise ABI stability between versions, using a different ABI does seem like an entirely reasonable option for non-FFI rust.

1 Like
9

The main problem that remains is x87 stack is used in the C ABI for returning float/double/long double on x86-32. I don’t know of an easy way to load a sNaN into the x87 stack–you might be able to leverage FXSAVE/FXRSTOR to fill the stack with sNaN values, but that is a very roundabout way to achieve something to avoid a problem very few people care about. (Does LLVM have a calling convention on x86-32 that allows define float @foo() to return in SSE registers rather than x87? IMHO, it should, even if it’s not default cdecl ABI).

10

Furthermore, from trouble we are having in Rust it seems like LLVM also treats the sign of NaNs as unstable under optimizations. Is that deliberate?

Yes. The sign bit of a nan is defined to be meaningless.

11

Wow, thank you all for the discussion so far. Super helpful!

Let me just confirm one thing:

%a = fdiv float 0.0, 0.0
%b = fdiv float 0.0, 0.0
%ac = bitcast float %a to i32
%bc = bitcast float %b to i32
%cmp = icmp eq i32 %a, %bc

Is %cmp always true?
If so, what if we compare different instructions that produce NaN? Do we always get the same NaN bit pattern?

12

Regarding NaN canonicalization: generally when IEEE754-2019 refers to canonicalization, it’s referring to an operation that only matters for decimal floating point. For binary{16,32,64}, all bit-patterns (including NaNs) are considered to be in the canonical encoding, so canonicalization of NaN is a no-op. That said, I do believe various FPU flags tend to do things like flush denormals to zero at this step, and plausibly muck with NaN somewhat (although doing so is non-compilaint, of course).

More generally, I agree with @RalfJung that it’d be great if we had cleaner semantics here. As mentioned, NaN sign-bits and payloads are observable in Rust, which means that optimizations that change their value are… unfortunate. I’ve suspected that an effective bandaid here would just be to have llvm::APFloat generate the correct default NaN for the given target in cases where it is deterministic (it tends to behave appropriately after that), but when I looked into it, doing so seemed tricky due to where APFloat was located in the module structure (I am not terribly familiar with LLVM though, so I may have been mistaken).

That said, given that this discussion is mostly about specifying the existing semantics (which seem to consider these things unobservable), so I’d understand if this is an inappropriate thread to bring this up.

But since rust doesn’t promise ABI stability between versions, using a different ABI does seem like an entirely reasonable option for non-FFI rust.

Yeah, a custom ABI for extern "Rust" should work for us for all our tier1 targets. This has actually been noted before, and is probably what we’ll have to do. It’s pretty unfortunate for sure, but yeah, I can’t see what other option there would be.

13

Is %cmp always true?

I don’t think IEEE 754 guarantees that %cmp is always true. In practice, I think every hardware implementation has a “preferred NaN” that is generated in all cases where the NaN payload is not propagated, but I don’t have sufficient knowledge of the diversity of hardware implementations to be able to confidently assert that as fact.

1 Like
14

Meaningless, but still consistent, I assume? That is, if I write Rust code like

let f = 0f64 / 0f64;
return f.is_sign_negative() == f.is_sign_negative();

that will definitely return true?
This is subtle because if LLVM for some reason duplicates the division, and then constant-folds one but not the other, results might end up inconsistent. That would be an LLVM bug. Right?

In practice, LLVM optimizations can make equivalent code not return true here – we have observed this in practice.

Nuno’s example is basically what you get when you ‘inline’ the division into the two uses of f in my example. It hence follows that LLVM may never ‘inline’ floating point operations in that sense, where an operation was originally performed once, but the transformed code performs in multiple times.

Formally speaking, I think we must consider floating point operations as non-deterministic if they produce a NaN – they basically non-deterministically pick a sign bit and payload. This is a valid choice but only if all parts of LLVM are aware that there is possible non-determinism in floating point operations, which I am not sure is the case.

That would help for most pure Rust programs, but not for Rust code interacting with C code via FFI, or for Rust code that uses extern "C" (even between two Rust functions). So we’d still have to document this as a caveat in our target support page: floating point semantics on this target are inherently busted.

15

Meaningless, but still consistent, I assume?

No. I don’t think LLVM semantics should target bit identical nan values. Doing so would be an undue burden

16

The potential of returning false in icmp eq i32 %a %a would be a much bigger burden, I am sure.

I am not asking for consistency between multiple divisions. I can see how that would be a problem given diverse hardware behavior. (That’s why wasm also went with nondeterminism here, though I hear they might change that. But strictly speaking right now when compiling to wasm it is not possible to guarantee that 0/0 always produces the same bit pattern.) I am asking for consistency when looking multiple times at the result of a single division.

17

If %a is potentially undef, that comparison can evaluate to false. That’s what undefined behavior does.

18

It would be a huge problem if %a were undef there – that seems far worse.

19

Okay, true, I should have qualified.

I am assuming that fdiv float 0.0, 0.0 does not produce an undef.

20

So, let’s ignore x86-32 for the moment…

Elsewhere, the result should depend on whether the CPU, and LLVM optimizations, always produces the same NaN value for a given operation. I think in practice all CPUs have deterministic results, based upon the input NaN bit-patterns and/or that architecture’s preferred NaN value.

But LLVM IR’s behavior is certainly not deterministic, since we don’t attempt to match the CPU’s sign/payload during constant folding.

But that’s just one issue – it gets worse. We also certainly haven’t guaranteed to use a consistent operand ordering for the otherwise-commutative operations like add/mul. Which NaN do you get from fadd NaN{payload1}, NaN{payload2}? Do you payload1, payload2, or the preferred NaN? LLVM constant folder returns the first NaN. CPUs typically return the first NaN operand, though sometimes the preferred NaN. But, when it comes to instruction selection…the order of “first” vs “second” operand is just not a consideration. We might generate the instruction in either order, whichever is more convenient/optimal.

Now, it might be a nice enhancement to teach LLVM’s constant folding how to generate the appropriate (architecture-specific) preferred NaN on the operations it folds. The goal here being that if the user’s code hasn’t introduced any custom NaN payloads, all of the NaNs, both from the CPU and from LLVM, should consist of the same (architecture-specific) bit-pattern. But that doesn’t solve the problem when there are custom NaN payloads, and I also don’t know if it’s reasonable to semantically require that.

1 Like