> 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),
}
}
But 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.
There 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.
Note 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.
What 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.
>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.
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.
A 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.
That 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.
Going by that rule, optimizing compilers just shouldn't exist. Optimizations will (or at least are supposed to) decrease computation, which will affect CPU temperatures.
Nikita Popov is thanked in the forward for work fixing LLVM bugs.
Before he pivoted to LLVM work, Nikita was one of the key individual contributors to the official PHP project in the last decade. He's an incredible force for good.
I don't think you can dismiss criticism of programming languages as "PL tribalism". The idea that all programming languages are equally great and "best tool for the job" excuses all flaws is clearly ridiculous.
PHP is not a very good language. Yes, even modern PHP.
The approach described in this section (just insert a bunch of calls to a dump_var() function which dumps its results into the graph) is really interesting to me. A problem I've had with fuzzing is getting some high-bandwidth error data other than "the program crashed". You can eg instrument pointer reads and writes, but sometimes reordering or deleting them is a legitimate optimization.
It's really cool to see Rust developers pioneer these revolutionary new methods nobody thought of before. </CunninghamsLaw> (But seriously, if someone has a name for this technique, I'm interested.)
As I understand it, the value of this thesis is the design of the fuzzer, which produces sufficiently 'complex' code to exercise uncommon code paths in the compiler, while retaining desirable properties such as reducibility.
45 comments
[ 1.0 ms ] story [ 14.4 ms ] thread>This resulted in the Rust compiler apparently “proving” the unresolved Collatz conjecture by optimising this function to return true [1].
That's funny. Hey maybe it was just that good!> That is, true for all value represent-able in usize.
A slight understatement!
There might be a cycle in theory.
So basically rustc_codegen_gcc and cranelift can compile code that don't with LLVM and then introduce (or solve) new bugs?
But in general, yes, if this was unintended behavior of LLVM, then we would expect alternative backends to exhibit differing behavior.
>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://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.
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/publica...
Edit: (2^64 - 1) / 3 is an integer and also trivially infinitely loops (by going to 0).
Only if you have overflow checking disabled.
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.
We got hurt by that in side-channel attacks.
[1] https://xkcd.com/1172/
Before he pivoted to LLVM work, Nikita was one of the key individual contributors to the official PHP project in the last decade. He's an incredible force for good.
In fact, if you check his Twitter, he retweeted the latest release of PHP version, 5 days ago: https://twitter.com/nikita_ppv
PHP is not a very good language. Yes, even modern PHP.
Moderation is active and monitors this kind of behavior. For example: https://news.ycombinator.com/item?id=38410031
Literally the first two lines about comment etiquete:
> Be kind. Don't be snarky. Converse curiously; don't cross-examine. Edit out swipes.
> Comments should get more thoughtful and substantive, not less, as a topic gets more divisive.
https://news.ycombinator.com/newsguidelines.html
Besides, bashing languages rarely lead to constructive conversations. That's exactly why guidelines and moderators discourage it.
[1] https://research.ralfj.de/ [2] https://news.ycombinator.com/user?id=ralfj
The approach described in this section (just insert a bunch of calls to a dump_var() function which dumps its results into the graph) is really interesting to me. A problem I've had with fuzzing is getting some high-bandwidth error data other than "the program crashed". You can eg instrument pointer reads and writes, but sometimes reordering or deleting them is a legitimate optimization.
It's really cool to see Rust developers pioneer these revolutionary new methods nobody thought of before. </CunninghamsLaw> (But seriously, if someone has a name for this technique, I'm interested.)