6 ms·
> A long-standing miscompilation in the Rust compiler was the incorrect removal of loops even if the compiler cannot tell whether it terminates (#28728). >This
by sebstefan 3y ago
> A long-standing miscompilation in the Rust compiler was the incorrect removal of loops even if the compiler cannot tell whether it terminates (#28728).
>This resulted in the Rust compiler apparently “proving” the unresolved Collatz conjecture by optimising this function to return true [1].
pub fn collatz(n: usize) -> bool {
match n {
1 => true,
n if n % 2 == 0 => collatz(n/2),
_ => collatz(3\*n + 1),
}
}
That's funny. Hey maybe it was just that good!
- j16sdiz 3y agoCollatz conjecture is tested to be true for n < 2^100000 - 1. That is, true for all value represent-able in usize.
- Squeeze2664 3y agoSounds like it was working as intended, then! Doing a great job at it, too.
- dllthomas 3y agoSounds, rather, like it was doing the right thing in that case but for the wrong reasons!
- Sharlin 3y agoOh yes, that's just LLVM's ConstantFoldCollatzConjecture pass, a basic optimization. > That is, true for all value represent-able in usize. A slight understatement!
- dllthomas 3y agoBut exactly the statement you need to fold it to a constant.
- not2b 3y agoBut if we pass in an odd value that is more than half of the maximum value represented in a usize, we get an overflow and a panic when we make a recursive call with n * 3 + 1, right? We shouldn't be optimizing those away.
- kevincox 3y agoIn the default release profile math wraps.
- progbits 3y agoBut does it converge using wrapping math for all usize values? There might be a cycle in theory.
- kevincox 3y agoThere can be a cycle but IIRC Rust inherits C/C++'s rule that infinite loops without side effects are undefined behaviour. So there are cycles (for example 0) but since there are no side effects and the only way to escape the loop is the `return true` the compiler only has to handle the `return true` path.
- progbits 3y agoOh sure that is fine, I just wonder if colatz is proven to converge for 32bit/64bit wrapping integer math.
- _ahxg 3y ago> The source of this bug is LLVM [2] which Rust relies on for optimisations and machine code generation. So basically rustc_codegen_gcc and cranelift can compile code that don't with LLVM and then introduce (or solve) new bugs?
- kibwen 3y agoNote that it's entirely feasible that GCC would do the same in this specific case. This wasn't necessarily a "bug" in LLVM per se, because this is the specified behavior in C and C++, and LLVM was simply implementing those semantics. The fix here was just to allow languages to opt-out of this behavior. Since GCC is also primarily a C/C++ backend, you'd have the same problem unless they offer a similar opt-out. But in general, yes, if this was unintended behavior of LLVM, then we would expect alternative backends to exhibit differing behavior.
- Arnavion 3y agoWhat you're talking about was a bug in LLVM. The paper says: >Infinite loops and recursions are Undefined Behaviour in C and C++, therefore the compiler can assume that a loop always terminates. ... which is wrong - only C++ requires loops to terminate. C allows non-terminating loops (with some specific requirements), and LLVM was already known to miscompile C in this same way until it was fixed in LLVM 12 with the `mustprogress` attribute. https://bugs.llvm.org/show_bug.cgi?id=965 https://bugs.llvm.org/show_bug.cgi?id=965 https://stackoverflow.com/questions/59925618/how-do-i-make-an-infinite-empty-loop-that-won-t-be-optimized-away https://stackoverflow.com/questions/59925618/how-do-i-make-a... Then this: >While LLVM does not require loops to terminate and should compile Rust loops correctly, its code contained assumptions that only hold for C/C++, thus miscompiling Rust code. ... is implied to be a different LLVM bug after the first one was already fixed, ie despite using `mustprogress` LLVM had additional miscompilations for Rust code because of "assumptions that only hold for C/C++". I can't tell which one in table 4.2 it is, though; none of them see to match.
- kibwen 3y agoAh, thank you, I was assuming that C++ inherited this from C.
- gpm 3y agoEh, 0 is an infinite loop in that function. It also doesn't implement the collatz conjecture. It implements the collatz-conjecture mod (usize::MAX + 1). I don't know about that modulus specifically, but there are m where the collatz conjecture mod m is false. https://www.researchgate.net/profile/Cganesa-Moorthy/publication/316141441_Collatz_Conjecture_for_Modulo_an_Integer/links/58f21cadaca27289c21671cf/Collatz-Conjecture-for-Modulo-an-Integer.pdf https://www.researchgate.net/profile/Cganesa-Moorthy/publica... Edit: (2^64 - 1) / 3 is an integer and also trivially infinitely loops (by going to 0).
- Georgelemental 3y ago> It implements the collatz-conjecture mod (usize::MAX + 1). Only if you have overflow checking disabled.
- gpm 3y agoOf course, if overflow checking isn't disabled returning true is wrong because of panicking instead of infinite loops.
- aidenn0 3y agoNote that in C++, all side-effect-free loops can be assumed to terminate, and thus eliminated.
- vacuity 3y agoAssume is a strong word. It's defined by the standard by way of undefined behavior.
- aidenn0 3y agoA C++ program with a non-terminating side-effect-free loop is malformed, so if we assume the program is not malformed, then we can assume side-effect-free loops terminate.
- tester756 3y agoWhich is crazy, because there's always side effect like temperature, fans speed/noise, etc.
- not2b 3y agoThat isn't what is meant by "side effect" here. A function with no side effects only modifies its local variables and returns a result. So, if we have int foo(int a, int b) { int c = bar(a); return b; } and we can see bar's body, and therefore we can determine that it has no side effects, we can optimize the call to bar away, because we can assume that it terminates and it doesn't affect the result. But if bar writes to global variables, that's a side effect. If we can't see the body of bar we have to assume that it might.