Hacker News Reader

> 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.

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.

> 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.

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?

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.

Okay and which optimization does this allow for? What's the difference in the emitted binary?

See https://blog.regehr.org/archives/140 for a longer discussion.

(And to make it closer to our situation, assume that the loop being executed was looking for something that actually has a counterexample that could be found after a long time; instead of Fermat's last theorem.)

What point is there in deleting side-effect free loops though? Literally the only use for those is to trap the control flow.

The only intentional use. However when writing generic code you often have code lines that after several levels of code inline reduce to that example.

So, generic code with a loop, which, depending on parameters, sometimes has side effects and sometimes doesn't, and in the case that it doesn't have side effects it is still not easy to recognize if the loop terminates?

I suppose that is possible, although I'm having a hard time coming up with any reasonable examples.

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.

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.

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.

Yep. Here's an example I found once: https://godbolt.org/z/XQBcR9

  pub fn mul1(mut a: i32, b:i32) -> i32 {
      let mut out = 0;
      while a != 0 {
          out += b;
          a-=1;
      }
      out
  }

  pub fn mul2(a: i32, b: i32) -> i32 {
      if a == 0 {
          0
      } else {
          b + mul2(a-1, b)
      }
  }

Both are optimized to imul. But that's not actually correct: neither of these should terminate for negative a!

Incidentally, this is actually a rust bug, caused by LLVM performing this optimization despite it being illegal in rust.

Interesting! In C/C++, optimizing to imul would be correct since if a was negative it would eventually underflow, and signed integer underflow is UB. Therefore ignoring that case is fine.

Presumably the same is true for LLVM IR, which would mean that it's Rust's responsibility to emit code that checks for that case since in Rust under/overflow is defined. Very interesting compiler bug! I noticed that they haven't fixed it for the latest version. Did you submit the bug report to Rust?

> Presumably the same is true for LLVM IR

I think it depends on the flags the multiplication operation is emitted with; namely, the nsw and nuw (no signed/unsigned wrap) would denote whether the optimization LLVM does is correct. If rust emits those flags then that would be a Rust bug; if Rust does not, then it might be an LLVM bug (I'm not sure what LLVM's semantics are for regular imul without flags).

I didn't: I assumed that[1] was sufficient. But (I assume, knowing little about C++) you're right that it's actually not an infinite loop, it's signed integer underflow. Given that, I'll file a bug.

[1] https://github.com/rust-lang/rust/issues/28728

I'm not entirely sure how that is an example I asked for. In this case, it seems like the compiler in both cases was able to see that the loop always terminates, either by hitting 0 directly, or by wrapping around and then hitting 0, or by simply assuming integer underflow to be UB.

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

The posted program is one instruction too!

    main:
        ud2

(ud2 is a permanently illegal instruction on x86)

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.

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.

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.

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.

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. 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.

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.

This is rubbish. The bug exists in LLVM regardless of whether Rust has its own fork, and you don't even need to use Rust to reproduce it.

Furthermore, using your system (ie. unmodified) LLVM with Rust is supported, and still exhibits this bug.

> This is rubbish.

Please mind your manners.

> The bug exists in LLVM regardless of whether Rust has its own fork, and you don't even need to use Rust to reproduce it.

It is not a bug in the broken sense since it was intended. There is simply no way to create a formally infinite loop in LLVM IR.

Clang in C mode (and rustc) are generating known broken LLVM IR for their semantics, Clang in C++ is fine. They could add something to the generated IR to make it formally finite in the IR instead of waiting years until LLVM IR adds something for that niche case.

> Furthermore, using your system (ie. unmodified) LLVM with Rust is supported, and still exhibits this bug.

That has nothing to do with what I said. The point is that if no frontend cares for such a feature, LLVM may not care about adding it.

If rustc was inside the LLVM project, like Clang and others are, then it would be a "bug" of LLVM and they would have an incentive for fixing it.

But given Clang does not care either in C mode, I don't have my hopes up.