Must a `const fn` behave exactly the same at runtime as at compile-time?

[oli-obk]

TLDR: should we allow floating point types in const fn?

Basically the question is whether the following const fn

const fn foo(a: f32, b: f32) -> f32 {
    a / b
}

must yield the same results for the same arguments if it is invoked at runtime or compile-time:

const RES1: f32 = foo(1.0, 0.0);

fn main() {
  let res2: f32 = foo(1.0, 0.0);
  assert_eq!(RES1.to_bits(), res2.to_bits());
}

Depending on the platform's NaN behavior, the result will differ between runtime and compile-time execution of foo(1.0, 0.0). Compile-time execution is determined by the Rust port of apfloat (a soft-float implementation); runtime behavior depends on the actual NaN patterns used by the hardware which are not always fully determined by the IEEE specification.

Note that this is entirely independent of any optimizations; we are discussing here the relationship between code that the user explicitly requests to be executed at compile-time, and regular run-time code. Optimizations apply to all code equally and they treat fn and const fn the same, so the the questions of how floating-point operations can be optimized is an entirely separate from and off-topic for this issue.

cc @rust-lang/wg-const-eval

[RalfJung]

(Replying to an older version of the OP)

I think you are asking two different questions here and treat them as if they are the same. Let me explain. :)

More concretely, when we optimize the following code, are we allowed to const propagate the foo call?

Note that this is a different question from the issue title. The behavior at runtime could be non-deterministic according to the spec, so even if you see one particular runtime behavior and a different compile-time behavior, it would still be correct to do const-propagation. Floating-point operations likely are non-deterministic.

I feel rather strongly that const fn must behave in a way that is allowed to occur at runtime; that is just a different way of saying that CTFE must implement the Rust spec. It would be rather strange if that was not the case. From this alone it already follows that const propagation like you are asking is allowed. I cannot see any reasonable way (assuming a bug-free CTFE engine) in which this optimization is not allowed.

But then there is the separate question, do we want to allow non-deterministic operations in const fn? CTFE inherently has to make some choice to resolve the non-determinism(*), and that choice might be different from what codegen+LLVM happen to currently do, which could be surprising for programmers that do not expect such non-determinism to actually be observable (even though it could, in theory, be observable even without any CTFE being involved). I think this is really the question you are asking here, but it is unrelated to const propagation. Unlike "is this optimization correct", this question cannot be answered by proving a theorem; this is a judgment call we could make either way as part of language design.

(*) Actually that is not entirely true -- allocation base addresses are another example of non-determinism, and there CTFE uses a form of symbolic execution to basically track all possible non-deterministic choices at once, and halt evaluation for cases where that is not possible. This is required because the non-deterministic choice made for a certain allocation must be consistent for a given Rust program across const-time and run-time execution. For runtime code that choice is only made when the program actually starts (thanks to ASLR) and thus CTFE has to be done in a way that is compatible with every possible choice made later. We do not need such a heavy hammer for floating-point operations because their non-deterministic choice is much more local, confined to each individual operation.

[bugadani]

I wonder in what real-world use case would somebody want to do complex calculations with NaN-s in compile time. I also wonder if the answer is the same if a compile-time calculation results in a NaN - is it something somebody actually wants, or does it hide an error?

[est31]

If NaN is the only concern, then the const fn implementation could just error out every time a NaN is encountered/obtained from computation. I also worry about floating point implementations having minuscle differences even for well-defined floats, but can't come up with an example. I see miri gives an error when a dangling pointer is returned in a constant as well (requires nightly to trigger it), so it's doable.

[oli-obk]

So.. if we have a const F: f32 = A + B; and at runtime a let f: f32 = A + black_box(B);, then it is not necessary for F.to_bits() == f.to_bits(), but it must at least be possible for that to be equal for some execution of the runtime code (even if not observable in practice due to CPU bugs).

I also worry about floating point implementations having minuscle differences even for well-defined floats, but can't come up with an example.

I always thought that even non-NaN floating point math can differ (in miniscule ways) between hardware even if it's the same target triple.

the const fn implementation could just error out every time a NaN is encountered/obtained from computation

That's one way, but it may be expensive. We specifically do not validate in const eval like we do in miri, because that validation is expensive. Doing it for floats may be cheaper, but if we also have to look at floats in large structs or arrays it can get expensive very quickly again. We could of course just check during each operation, which is much more direct and should only impact float ops. I think that if nondeterministic operations include non-NaN numbers, then that doesn't help us a lot though.

I think that we can just make a judgement call on how we make such nondetermism deterministic (by choosing one possibility), even if that choice changes between target platforms, compiler versions, optimization levels or other compiler flags.

The main question is then, how to make that choice I guess. Just put it on the const eval roadmap that I should really really finish and have T-lang sign it off?

[RalfJung]

So.. if we have a const F: f32 = A + B; and at runtime a let f: f32 = A + black_box(B);, then it is not necessary for F.to_bits() == f.to_bits(), but it must at least be possible for that to be equal for some execution of the runtime code (even if not observable in practice due to CPU bugs).

No CPU bugs involved. If the spec says that non-deterministically, A or B can happen, then it is completely okay for runtime execution to always do A. Or to do A on Tuesdays and B every other day of the week. Or to do A only in crates whose name starts with a vowel. Or whatever. And CTFE can make its own choice of A or B completely independently on that.

So in your case, both f.to_bits() and F.to_bits() must be results that are allowed by the spec, but since the spec might allow multiple results, the two do not have to be the same. And that's really all we can say; there is no requirement that running the program many times must eventually produce all possible results or so. (This distinguishes non-determinism from randomness.)

I always thought that even non-NaN floating point math can differ (in miniscule ways) between hardware even if it's the same target triple.

AFAIK IEEE fully specifies what happens for primitive FP operations (except for NaN bits). Basically the operation has to return the best possible approximation to the result of the computation if it were carried out on actual rational numbers. (Transcendental functions are a different game.) The remaining differences here really are down to CPU bugs -- 32bit x86 is notorious here, and I hear some architectures handle subnormals (values very close to 0) incorrectly.

See rust-lang/unsafe-code-guidelines#237 for some more open questions about "what even are our floating-point semantics".

That's one way, but it may be expensive. We specifically do not validate in const eval like we do in miri, because that validation is expensive. Doing it for floats may be cheaper, but if we also have to look at floats in large structs or arrays it can get expensive very quickly again. We could of course just check during each operation, which is much more direct and should only impact float ops.

If the latest analysis in #73328 is correct, then only floating-point operations are non-deterministic, but copying around FP values is deterministic. I do not think it would be expensive to check at each floating point addition etc whether the result is deterministic (basically, if the result is non-NaN, but we can easily add further conditions), and raise an error if it is not. This has nothing to do with checking the validity invariant.

I think that if nondeterministic operations include non-NaN numbers, then that doesn't help us a lot though.

Why that? I think it would work just as well. Unless of course all operations are non-deterministic, then this would be equivalent to ruling out FP entirely.

[oli-obk]

Why that? I think it would work just as well. Unless of course all operations are non-deterministic, then this would be equivalent to ruling out FP entirely.

What I mean is if we error whenever any operation returns a NaN, but still have other nondeterministic ops, then we haven't gained anything and should either keep ruling out FP ops or just allowing NaN and not checking anything.

If the latest analysis in #73328 is correct, then only floating-point operations are non-deterministic, but copying around FP values is deterministic.

Oooh, neat. That is an improvement to the info I had when we created min_const_fn

[RalfJung]

What I mean is if we error whenever any operation returns a NaN, but still have other nondeterministic ops, then we haven't gained anything and should either keep ruling out FP ops or just allowing NaN and not checking anything.

Sure, we'd have to capture every possible form of non-determinism. Also everything I say on this topic should be checked by an FP expert, which I am not.^^

Oooh, neat. That is an improvement to the info I had when we created min_const_fn

Yes, new info came up since then. Basically I think we should just copy whatever WebAssembly does -- it has an exhaustive and precise spec, and I am sure they involved enough FP experts to make sure the spec is also realistically implementable. Also this means if LLVM does soemthing else we can complain that they are incompatible with WebAssembly, which gives our complaint more weight. ;)

[ecstatic-morse]

Transcendental functions (e.g. trigonometry and non-integral exponentiation), can give different results between platforms. I don't think we can take a "hard-line" approach, since then functions like f32::tan that will take advantage of hardware support if it exists can never be const fn; Users would have to opt-in to a software emulated version (either in std or in the ecosystem). I view CTFE as just another platform on which floating point is supported. Users don't (or at least shouldn't) expect cross-platform consistency at runtime, why is CTFE any different?

Even trying to promise that the result given by CTFE is consistent between compiler versions would be foolish, since it would lock us into a particular software emulation strategy that may become outdated. I think we should guarantee that CTFE engine for a given compiler at a given optimization level is deterministic between runs and nothing more. I think we might already have this for NaN payloads, although it would be nice to have an actual set of rules for how they get handled instead of "whatever LLVM does".

[workingjubilee]

If NaN is the only concern, then the const fn implementation could just error out every time a NaN is encountered/obtained from computation. I also worry about floating point implementations having minuscle differences even for well-defined floats, but can't come up with an example.
-@est31

An example of what you may be thinking about is, for instance, ARMv7 Neon (the SIMD vector unit) flushing subnormal float values to zero. A floating-point operation in a register that flushes subnormal values to zero would potentially cause an alteration of the value even when the mantissa is not supposed to change (e.g. f32x4::abs). This is no longer a concern on ARMv8 Neon (usually "aarch64"), which will not do that if you don't ask it to, as far as I'm aware (and I am reasonably sure I would have found out by now).

Part of the reason that x86_64 is well-behaved while x86 is not is that, as @thomcc told me, on x86_64 the XMM registers (introduced as SIMD registers) are fully compliant and compilers exhibit a preference for them even for "scalar" floating point ops. That may sound like a niche oddity but I have been finding in my reading and experiments that "The floating point registers and SIMD registers are actually the same" is actually a fairly common hardware implementation approach... correct FP math is expensive in transistors to implement, so I suppose one saves some surface area on the die by not doing so twice.

In fact, this got me curious enough to feed some code into Godbolt...

pub fn f32_add(a: f32, b: f32) -> f32 {
    a + b
}

pub fn f32_abs(a: f32) -> f32 {
    a.abs()
}

; Compiled with rustc -C opt-level=3 -Cdebuginfo=0 -Ccodegen-units=1 --target armv7-unknown-linux-gnueabihf
example::f32_add:
        vadd.f32        s0, s0, s1
        bx      lr

example::f32_abs:
        vabs.f32        s0, s0
        bx      lr

Yes, those are vector instructions. I had developed a slightly more thorough platform comparison for x86 and Arm targets at the link (nothing particularly exciting, mind) but I excerpted that because it does seem that at least on some ARMv7 triples there is a similar default to using the (potentially buggy, as mentioned) vector unit for floating point math... a sound choice elsewhere, an implementation concern here.

There's more extensive documentation on all the nuances of Arm's various FP implementations spread across Arm's website but I found a relatively succinct explanation of some of the details on Debian's wiki in relation to their own support choices: https://wiki.debian.org/ArmHardFloatPort#Background_information

[tavianator]

This GCC bug is possibly related to this discussion: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93681. LLVM may have similar issues, I'm not sure.

The moral is that it's important that compile-time float evaluation can't lead the optimizer to make assumptions that may be contradicted at runtime.