Difference between compile-time and runtime float precision on 32-bit x86 without SSE can cause miscompilation leading to segfault

[beetrees]

The following program (based on the Rust version from here, which is based on @comex's example from a different issue; they gave an explanation of how they found it here)

#include <stdio.h>
#include <stddef.h>

void print_vals(float x, size_t i, int vals_i) {
	printf("x=%f i=%zu vals[i]=%i\n", x, i, vals_i);
}

void out_of_bounds(float x, size_t i) {
	printf("x=%f i=%zu vals[i]=out of bounds\n", x, i);
}

void evil(int vals[300]) {
	float x = 0.0;
	size_t i = 0;

	while (x != 90.0) {
		// At compile time, LLVM will brute-force the loop and discover that it
		// terminates after 90 iterations, with `i` always less than 300. This bounds
		// check therefore gets optimised out.
		if (i < 300) {
			print_vals(x, i, vals[i]);
		} else {
			out_of_bounds(x, i);
		}
		x += 1.0;
		// This addition is too small to have any effect on the value of `x` with
		// regular `float` precision, which is what LLVM uses at compile-time.
		// However, with the extra precision offered by x87 floating point registers,
		// the value of `x` will change slightly, meaning it will never hit exactly
		// 90.0 and therefore the loop will never terminate at runtime.
		x += 2.9802322387695312e-08;
		i += 2;
	}
}

int main() {
	int vals[300];
	for (int i = 0; i < 300; i++) {
		vals[i] = i;
	}
	evil(vals);
}

compiled with clang -O3 --target=i686-unknown-linux-gnu -mno-sse code.c will segfault at runtime. This is due to LLVM evaluating floats at standard float precision at compile-time, but outputting machine code that uses x87 extended precision at runtime. Specifically, llvm/lib/Analysis/ScalarEvolution.cpp will brute force the loop using compile-time semantics, causing the bounds check to be optimised out; however the extra precision of x87 extended precision floats will mean that the loop termination condition is never hit at runtime.

The LangRef appears to imply that the compile-time semantics are correct, so this is a bug in the x86 backend.

Related to #44218.

[efriedma-quic]

I suspect this isn't x87-specific; there's probably interactions with fast-math flags, math library calls, maybe some other stuff. The fundamental issue is that if we constant-fold an operation with a non-deterministic result, we need to actually replace the value in the IR, or else we might get a different result at runtime. So ScalarEvolution::computeExitCountExhaustively is unsound; it needs to be reimplemented as a fold in indvars. (Or we could forbid folding non-deterministic instructions in ScalarEvolution::computeExitCountExhaustively, but we lose some optimizations if we do that.)

See also https://reviews.llvm.org/D84792 , which is the same class of issue.

[Muon]

The fundamental issue is that if we constant-fold an operation with a non-deterministic result, we need to actually replace the value in the IR, or else we might get a different result at runtime.

Every operation in that testcase is deterministic.

[beetrees]

I think there's possibly two different bugs here:

Floating point accuracy

Which LLVM floating point operations guarantee deterministic results? As far as I'm aware there is a general presumption that add/sub/mul/div/rem/fma give perfect accurately rounded results, whereas other floating point operations might not. However, I was unable to find this codified anywhere in the LangRef. If this is true, then the LLVM IR optimisation is correct in the original example, and the x86 backend is responsible for the miscompilation.

Incorrect constant folding of non-deterministic operations

The original example can be adapted to use any operation which LLVM will constant-fold while brute-forcing a loop, but which differs between compile-time and runtime. rust-lang/rust#124364 is an example in Rust which uses the differences in the implementation of sin to cause a miscompilation leading to a segfault at runtime, but any non-deterministic const-foldable operation will do.

[Muon]

The people writing the optimizations assume correct rounding, so it's the case de facto, regardless of the LangRef's opinion. It's also necessary to actually provide what C and C++ require. I did open a bug about the documentation a while ago: #60942

[nikic]

I suspect this isn't x87-specific; there's probably interactions with fast-math flags, math library calls, maybe some other stuff. The fundamental issue is that if we constant-fold an operation with a non-deterministic result, we need to actually replace the value in the IR, or else we might get a different result at runtime. So ScalarEvolution::computeExitCountExhaustively is unsound; it needs to be reimplemented as a fold in indvars. (Or we could forbid folding non-deterministic instructions in ScalarEvolution::computeExitCountExhaustively, but we lose some optimizations if we do that.)

Is your suggestion for the IndVars optimization to replace the exit with a comparison of a canonical IV against the exhaustive exit count there?

[efriedma-quic]

Is your suggestion for the IndVars optimization to replace the exit with a comparison of a canonical IV against the exhaustive exit count there?

That's what I was thinking (similar to the existing LFTR), but considering it a bit more, I'm not sure how safe that actually is. If the IV isn't used for anything else, it's fine, but in most interesting cases the floating-point IV will have other uses. Even if we do LFTR, the computed trip count needs to be consistent with the actual floating-point numbers we're using. So we'd actually need to replace the floating-point computation in each iteration with the constant-folded result. That's theoretically possible (just store the values in a constant table), but the profitability becomes a bit questionable.

[nikic]

Is your suggestion for the IndVars optimization to replace the exit with a comparison of a canonical IV against the exhaustive exit count there?

That's what I was thinking (similar to the existing LFTR), but considering it a bit more, I'm not sure how safe that actually is. If the IV isn't used for anything else, it's fine, but in most interesting cases the floating-point IV will have other uses. Even if we do LFTR, the computed trip count needs to be consistent with the actual floating-point numbers we're using. So we'd actually need to replace the floating-point computation in each iteration with the constant-folded result. That's theoretically possible (just store the values in a constant table), but the profitability becomes a bit questionable.

Right. I think we need to approach this the other way around and have a flag for ConstantFolding to skip these. At least as far as SCEV is concerned, I don't think we actually care about FP exits conditions there (I think it's more about things like load-from-constant based exit conditions).

A possible way to go about this would be to extend IIQ AllowUndef to AllowNonDeterministic and then also pass that to ConstantFolding as well.

(As already mentioned above, it doesn't fix the specific issue with x87 here, but rather analogous issues with FP libcalls on not-fundamentally-broken targets.)

[RalfJung]

I suspect this isn't x87-specific; there's probably interactions with fast-math flags, math library calls, maybe some other stuff. The fundamental issue is that if we constant-fold an operation with a non-deterministic result, we need to actually replace the value in the IR, or else we might get a different result at runtime.

Yeah I agree, determinism is the sticky point here. Note that even basic float operations are not deterministic as per #66579 -- if they produce a NaN, some aspects of that NaN are picked non-deterministically.

Every operation in that testcase is deterministic.

I think that is exactly the question. One could specify float operations as being basically non-deterministic and producing a result with arbitrary precision. In that case the x86 backend would be right and the optimizer would be wrong to assume determinism.

However that would be a pretty bad spec IMO; the Rust frontend for sure would like to be able to generate code that exactly has IEEE semantics, and I suspect other frontends have similar requirements. In that case basic float operations are deterministic unless they produce a NaN, and it is the (non-SSE) x86 backend that is wrong. Transcendental functions however are still non-deterministic; that's what happens with the sin issue.

[beetrees]

Miscompilations can also occur when the bit-pattern of NaNs differs at compile-time and runtime. Here is an example in Rust that uses the differing signs of NaNs between compile-time and runtime to cause a miscompilation.

[RalfJung]

Nice example! So this does not just affect libcalls then, it affects all float operations as they can all produce NaNs (and LLVMs const-fold does not guarantee that the NaN bit pattern matches what the target would produce).

[nikic]

Simplified IR test case (https://llvm.godbolt.org/z/KW5s4oTPa):

; RUN: opt -S -passes=indvars < %s
define i64 @test() {
entry:
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  %fv = phi double [ 1.000000e+00, %entry ], [ %fv.next, %loop ]
  call void @use(double %fv)
  %fv.next = call double @llvm.sin.f64(double %fv)
  %iv.next = add i64 %iv, 1
  %fcmp = fcmp une double %fv, 0x3FC6BA15EE8460B0
  br i1 %fcmp, label %loop, label %exit

exit:
  ret i64 %iv
}

declare void @use(double %i)
declare double @llvm.sin.f64(double)

The replacement with ret i64 90 shouldn't occur.