Hacker News Reader

Comment by pingyong | Hacker News Reader

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?

View on HN

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.

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.

Reply on news.ycombinator.com