5 ms·

My "favourite" recent compiler bug comes from Rust. Compile the following code in Release mode: fn main() { (|| loop {})() } This defines an anonymous fun

My "favourite" recent compiler bug comes from Rust. Compile the following code in Release mode: fn main() { (|| loop {})() } This defines an anonymous function containing an infinite loop, and calls it. Any sane compiler would make this just loop forever, right? $ cargo run --release test Illegal instruction (core dumped) Yeah, that's right. In Rust, an ostensibly safe language, Clang's overeager optimizer chooses to emit an illegal instruction in lieu of an infinite loop. (Try it here: https://play.rust-lang.org/?version=stable&mode=release&edition=2018&gist=4233cbe4bf524b1154b2e7b560d58610 https://play.rust-lang.org/?version=stable&mode=release&edit...) This particular bug actually comes from C++. In C++, threads may be assumed to always make forward progress, i.e. side-effect-free infinite loops are UB. However, this is not true in C, and it's definitely not true in Rust, yet Clang makes this assumption anyway. It gets a lot worse; once Clang sees an infinite loop and decides it's UB, it gets to make all sorts of thoroughly invalid and silly "optimizations"; see this SO question for some examples: https://stackoverflow.com/questions/59925618/how-do-i-make-an-infinite-empty-loop-that-wont-be-optimized-away https://stackoverflow.com/questions/59925618/how-do-i-make-a...

lmm 7y ago
> This particular bug actually comes from C++. In C++, threads may be assumed to always make forward progress, i.e. side-effect-free infinite loops are UB. However, this is not true in C That's very much disputed. The C standard requires programs' behaviour to be as-if executed on the C abstract machine when they terminate. It's not at all clear whether the standard imposes any requirements on programs that would not terminate when executed on the C abstract machine.
- _kst_ 7y ago
  C11 does have a special case rule for infinite loops. Section 6.8.5 paragraph 6: "An iteration statement whose controlling expression is not a constant expression, that performs no input/output operations, does not access volatile objects, and performs no synchronization or atomic operations in its body, controlling expression, or (in the case of a for statement) its expression-3, may be assumed by the implementation to terminate." (I'm personally not happy that this is stated in terms of that the implementation may assume rather than what a program may do.) Note that this does not apply to infinite loops with constant conditions. For example, given `while (1) { /* ... */ }`, the above doesn't apply and the implementation may not assume the loop will terminate.
  - lmm 7y ago
    > Note that this does not apply to infinite loops with constant conditions. For example, given `while (1) { /* ... */ }`, the above doesn't apply and the implementation may not assume the loop will terminate. Where is that guaranteed? I can see that the above rule suggests that the implementation may not make that assumption, but it doesn't actually rule it out.
- pingyong 7y ago
  Is there even a case where the compiler can optimize a terminating loop better when it is allowed to assume that it will terminate at some point?
  - eru 7y ago
    Yes. The simplest example is when the loop has no other side-effects. But you could also have something like: while(true) { if(some condition) { do stuff; break; } } In this case, a compiler might be allowed to assume that 'some condition' happens to be true eventually.
    - pingyong 7y ago
      Okay and which optimization does this allow for? What's the difference in the emitted binary?
      - lmkg 7y ago
        If you propagate "some condition," that could allow dead-code elimination later on, especially if an if-statement uses "some condition" as a predicate later. This seems redundant in hand-written code, but keep in mind the if-statement may actually be from an inlined function. If "some condition" is actually testing a variable for equality, then you could do constant-folding.
        pingyong 7y ago
        My point is that if a loop - doesn't terminate, doesn't have side effects -> optimization doesn't matter - doesn't terminate, has side effects -> optimization isn't valid - does terminate, doesn't has side effects -> optimization would be valid, but why would such a loop exist? One example that was brought up was generic code, but I'm not entirely convinced yet.
        eru 7y ago
        Because of interaction with other undefined behaviour (in the body of your loop), you might think you are in a different case than what the compiler thinks. Also the definition of 'side effect' here is a weird one: reading and writing to variables is not considered a side effect, even though a different thread could change them while your loop is running.
unlinked_dll 7y ago
That's a shame because you could get an essentially one-instruction program loop: jmp loop CE shows this happens on opt-level=1 which is neat. Of the weird breakages this takes the case! https://godbolt.org/z/LyERew https://godbolt.org/z/LyERew
- nneonneo 7y ago
  The posted program is one instruction too! main: ud2 (ud2 is a permanently illegal instruction on x86)
  - CUViper 7y ago
    Even that `ud2` is only there because rustc sets the `TrapUnreachable` flag for LLVM. In older versions you would get nothing at all, so calling main would fall through to whatever was next in memory.
jfkebwjsbx 7y ago
Rust does not use Clang. You are thinking about LLVM. But the bug is actually on rustc side because they fork LLVM on purpose and use it as they wish. If the rustc folks merge their project into LLVM, then you could claim it is an LLVM bug, otherwise please do not.
- nneonneo 7y ago
  Ah, nomenclature fail on my part. You're right, it's LLVM. This is an LLVM bug - it affects C code too (when it should only apply to C++). If you compile this code: static void die() { while(1) ; } int main() { die(); } as a C program with optimizations, it will die with an illegal instruction too.
  - zzo38computer 7y ago
    Perhaps it should be allow to optimize it to: int main() { while(1) pause(); } But only if system call optimizations are enabled (otherwise it can't add the call to pause()), and only if you did not specifically disable the optimization for infinite loops, and only if you do not use the -Os option.
  - saagarjha 7y ago
    Correct, the bug is that LLVM (being mostly built around C++?) did not have a concept of infinite loops that could not be removed for quite a while. Here's the Rust bug about this, which also contains links to relevant discussion on the LLVM side, including some forward progress: https://github.com/rust-lang/rust/issues/28728 https://github.com/rust-lang/rust/issues/28728. I believe the current status is that machinery has been added that language frontends can use to mark loops as having side effects, which will indicate to LLVM that they should not be optimized out.
  - jfkebwjsbx 7y ago
    It is not a bug in the broken sense since it was intended. There is simply no way to create an infinite loop in LLVM IR. You could argue it is Clang generating bad LLVM IR for C mode, same as Rust. They could add something to the generated IR to make it formally finite.
einpoklum 7y ago
> This particular bug actually comes from C++. No, it does not. Don't gaslight please. The bug is either in Rust or in clang. The C++ language, and the language committee, are not responsible for this bug at all.

lmm 7y ago

> This particular bug actually comes from C++. In C++, threads may be assumed to always make forward progress, i.e. side-effect-free infinite loops are UB. However, this is not true in C That's very much disputed. The C standard requires programs' behaviour to be as-if executed on the C abstract machine when they terminate. It's not at all clear whether the standard imposes any requirements on programs that would not terminate when executed on the C abstract machine.

_kst_ 7y ago
C11 does have a special case rule for infinite loops. Section 6.8.5 paragraph 6: "An iteration statement whose controlling expression is not a constant expression, that performs no input/output operations, does not access volatile objects, and performs no synchronization or atomic operations in its body, controlling expression, or (in the case of a for statement) its expression-3, may be assumed by the implementation to terminate." (I'm personally not happy that this is stated in terms of that the implementation may assume rather than what a program may do.) Note that this does not apply to infinite loops with constant conditions. For example, given `while (1) { /* ... */ }`, the above doesn't apply and the implementation may not assume the loop will terminate.
- lmm 7y ago
  > Note that this does not apply to infinite loops with constant conditions. For example, given `while (1) { /* ... */ }`, the above doesn't apply and the implementation may not assume the loop will terminate. Where is that guaranteed? I can see that the above rule suggests that the implementation may not make that assumption, but it doesn't actually rule it out.
pingyong 7y ago
Is there even a case where the compiler can optimize a terminating loop better when it is allowed to assume that it will terminate at some point?
- eru 7y ago
  Yes. The simplest example is when the loop has no other side-effects. But you could also have something like: while(true) { if(some condition) { do stuff; break; } } In this case, a compiler might be allowed to assume that 'some condition' happens to be true eventually.
  - pingyong 7y ago
    Okay and which optimization does this allow for? What's the difference in the emitted binary?
    - lmkg 7y ago
      If you propagate "some condition," that could allow dead-code elimination later on, especially if an if-statement uses "some condition" as a predicate later. This seems redundant in hand-written code, but keep in mind the if-statement may actually be from an inlined function. If "some condition" is actually testing a variable for equality, then you could do constant-folding.
      - pingyong 7y ago
        My point is that if a loop - doesn't terminate, doesn't have side effects -> optimization doesn't matter - doesn't terminate, has side effects -> optimization isn't valid - does terminate, doesn't has side effects -> optimization would be valid, but why would such a loop exist? One example that was brought up was generic code, but I'm not entirely convinced yet.
        eru 7y ago
        Because of interaction with other undefined behaviour (in the body of your loop), you might think you are in a different case than what the compiler thinks. Also the definition of 'side effect' here is a weird one: reading and writing to variables is not considered a side effect, even though a different thread could change them while your loop is running.

unlinked_dll 7y ago

That's a shame because you could get an essentially one-instruction program loop: jmp loop CE shows this happens on opt-level=1 which is neat. Of the weird breakages this takes the case! https://godbolt.org/z/LyERew https://godbolt.org/z/LyERew

nneonneo 7y ago
The posted program is one instruction too! main: ud2 (ud2 is a permanently illegal instruction on x86)
- CUViper 7y ago
  Even that `ud2` is only there because rustc sets the `TrapUnreachable` flag for LLVM. In older versions you would get nothing at all, so calling main would fall through to whatever was next in memory.

jfkebwjsbx 7y ago

Rust does not use Clang. You are thinking about LLVM. But the bug is actually on rustc side because they fork LLVM on purpose and use it as they wish. If the rustc folks merge their project into LLVM, then you could claim it is an LLVM bug, otherwise please do not.

nneonneo 7y ago
Ah, nomenclature fail on my part. You're right, it's LLVM. This is an LLVM bug - it affects C code too (when it should only apply to C++). If you compile this code: static void die() { while(1) ; } int main() { die(); } as a C program with optimizations, it will die with an illegal instruction too.
- zzo38computer 7y ago
  Perhaps it should be allow to optimize it to: int main() { while(1) pause(); } But only if system call optimizations are enabled (otherwise it can't add the call to pause()), and only if you did not specifically disable the optimization for infinite loops, and only if you do not use the -Os option.
- saagarjha 7y ago
  Correct, the bug is that LLVM (being mostly built around C++?) did not have a concept of infinite loops that could not be removed for quite a while. Here's the Rust bug about this, which also contains links to relevant discussion on the LLVM side, including some forward progress: https://github.com/rust-lang/rust/issues/28728 https://github.com/rust-lang/rust/issues/28728. I believe the current status is that machinery has been added that language frontends can use to mark loops as having side effects, which will indicate to LLVM that they should not be optimized out.
- jfkebwjsbx 7y ago
  It is not a bug in the broken sense since it was intended. There is simply no way to create an infinite loop in LLVM IR. You could argue it is Clang generating bad LLVM IR for C mode, same as Rust. They could add something to the generated IR to make it formally finite.

einpoklum 7y ago

> This particular bug actually comes from C++. No, it does not. Don't gaslight please. The bug is either in Rust or in clang. The C++ language, and the language committee, are not responsible for this bug at all.