LLVM loop optimization can make safe programs crash

[RalfJung]

The following snippet crashes when compiled in release mode on current stable, beta and nightly:

enum Null {}

fn foo() -> Null { loop { } }

fn create_null() -> Null {
    let n = foo();

    let mut i = 0;
    while i < 100 { i += 1; }
    return n;
}

fn use_null(n: Null) -> ! {
    match n { }
}


fn main() {
    use_null(create_null());
}

https://play.rust-lang.org/?gist=1f99432e4f2dccdf7d7e&version=stable

This is based on the following example of LLVM removing a loop that I was made aware of: https://github.com/simnalamburt/snippets/blob/master/rust/src/bin/infinite.rs.
What seems to happen is that since C allows LLVM to remove endless loops that have no side-effect, we end up executing a match that has to arms.

[ranma42]

The LLVM IR of the optimised code is

; Function Attrs: noreturn nounwind readnone uwtable
define internal void @_ZN4main20h5ec738167109b800UaaE() unnamed_addr #0 {
entry-block:
  unreachable
}

This kind of optimisation breaks the main assumption that should normally hold on uninhabited types: it should be impossible to have a value of that type.
rust-lang/rfcs#1216 proposes to explicitly handle such types in Rust. It might be effective in ensuring that LLVM never has to handle them and in injecting the appropriate code to ensure divergence when needed (IIUIC this could be achieved with appropriate attributes or intrinsic calls).
This topic has also been recently discussed in the LLVM mailing list: http://lists.llvm.org/pipermail/llvm-dev/2015-July/088095.html

[alexcrichton]

triage: I-nominated

Seems bad! If LLVM doesn't have a way to say "yes, this loop really is infinite" though then we may just have to sit-and-wait for the upstream discussion to settle.

[ranma42]

A way to prevent infinite loops from being optimised away is to add unsafe {asm!("" :::: "volatile")} inside of them. This is similar to the llvm.noop.sideeffect intrinsic that has been proposed in the LLVM mailing list, but it might prevent some optimisations.
In order to avoid the performance loss and to still guarantee that diverging functions/loops are not optimised away, I believe that it should be sufficient to insert an empty non-optimisable loop (i.e. loop { unsafe { asm!("" :::: "volatile") } }) if uninhabited values are in scope.
If LLVM optimises the code which should diverge to the point that it does not diverge anymore, such loops will ensure that the control flow is still unable to proceed.
In "lucky" case in which LLVM is unable to optimise the diverging code, such loop will be removed by DCE.

[geofft]

Is this related to #18785? That one's about infinite recursion to be UB, but it sounds like the fundamental cause might be similar: LLVM doesn't consider not halting to be a side effect, so if a function has no side effects other than not halting, it's happy to optimize it away.

[arielb1]

@geofft

It's the same issue.

[RalfJung]

Yes, looks like it's the same. Further down that issue, they show how to get undef, from which I assume it's not hard to make a (seemingly safe) program crash.

[simnalamburt]

👍

[ranma42]

Crash, or, possibly even worse heartbleed https://play.rust-lang.org/?gist=15a325a795244192bdce&version=stable

[nikomatsakis]

So I've been wondering how long until somebody reports this. :) In my opinion, the best solution would of course be if we could tell LLVM not to be so aggressive about potentially infinite loops. Otherwise, the only thing I think we can do is to do a conservative analysis in Rust itself that determines whether:

1. the loop will terminate OR
2. the loop will have side-effects (I/O operations etc, I forget precisely how this is defined in C)

Either of this should be enough to avoid undefined behavior.

[nikomatsakis]

triage: P-medium

We'd like to see what LLVM will do before we invest a lot of effort on our side, and this seems relatively unlikely to cause problems in practice (though I have personally hit this while developing the compiler as well). There are no backwards incomatibility issues to be concerned about.

[dotdash]

Quoting from the LLVM mailing list discussion:

 The implementation may assume that any thread will eventually do one of the following:
   - terminate
   - make a call to a library I/O function
   - access or modify a volatile object, or
   - perform a synchronization operation or an atomic operation

 [Note: This is intended to allow compiler transformations such as removal of empty loops, even
  when termination cannot be proven. — end note ]

[ranma42]

@dotdash The excerpt you are quoting comes from the C++ specification; it is basically the answer to "how it [having side effects] is defined in C" (also confirmed by the standard committee: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1528.htm ).

Regarding what is the expected behaviour of the LLVM IR there is some confusion. https://llvm.org/bugs/show_bug.cgi?id=24078 shows that there seems to be no accurate & explicit specification of the semantics of infinite loops in LLVM IR. It aligns with the semantics of C++, most likely for historical reasons and for convenience (I only managed to track down https://groups.google.com/forum/#!topic/llvm-dev/j2vlIECKkdE which apparently refers to a time when infinite loops were not optimised away, some time before the C/C++ specs were updated to allow it).

From the thread it is clear that there is the desire to optimise C++ code as effectively as possible (i.e. also taking into account the opportunity to remove infinite loops), but in the same thread several developers (including some that actively contribute to LLVM) have shown interest in the ability to preserve infinite loops, as they are needed for other languages.

[dotdash]

@ranma42 I'm aware of that, I just quoted that for reference, because one possibility to work-around this would be to detect such loops in rust and add one of the above to it to stop LLVM from performing this optimization.

[bstrie]

Is this a soundness issue? If so, we should tag it as such.

[bluss]

Yes, following @ranma42's example, this way shows how it readily defeats array bounds checks. playground link

[arielb1]

@bluss

The policy is that wrong-code issues that are also soundness issues (i.e. most of them) should be tagged I-wrong.

[zackw]

@gnzlbg

loop { if false { break; } } is an infinite loop that contains a break expression, yet we need to insert @llvm.sideeffect to prevent llvm from removing it.

Hm, yes, that's troublesome. But we don't have to be perfect, just conservatively correct. A loop like

while spinlock.load(Ordering::SeqCst) != 0 {}

(from the std::sync::atomic documentation) would easily be seen not to need a @llvm.sideeffect, since the controlling condition is not constant (and an atomic load operation had better count as a side-effect for LLVM purposes, or we have bigger problems). The kind of finite loop that might be emitted by a program generator,

loop {
    if /* runtime-variable condition */ { break }
    /* more stuff */
}

should also not be troublesome. In fact, is there any case that the "no break expressions in the body of the loop" rule gets wrong besides

loop {
    if /* provably false at compile time */ { break }
}

?

[RalfJung]

I thought that this issue is about fixing the implementation of Rust for infinite loops such that the behavior of the generated LLVM-IR becomes defined, and for this, @llvm.sideeffect, sounded like a pretty good solution.

Fair enough. However, as you said, the issue (the mismatch between Rust semantics and LLVM semantics) is actually about non-termination, not about loops. So I think that's what we should be tracking here.

@zackw

If I understand the problem correctly, to fix the infinite-loop case, it should be sufficient to insert llvm.sideeffect into loop { ... } and while { ... } where the body of the loop contains no break expressions. This captures the difference between C++ semantics and Rust semantics for infinite loops: in Rust, unlike C++, the compiler is not allowed to assume that a loop terminates when it is knowable at compile time that it doesn't. (I'm not sure how much we need to worry about correctness in the face of loops where the body might panic, but that can always be improved later.)

What you describe holds for C. In Rust, any loop is allowed to diverge. Everything else would just be unsound to do.

So, for example

while test_fermats_last_theorem_on_some_random_number() { }

is an okay program in Rust (but neither in C nor C++), and it will loop forever without causing a side-effect. So, it has to be all loops, except for those we can prove will terminate.

[gnzlbg]

@zackw

is there any case that the "no break expressions in the body of the loop" rule gets wrong besides

It's not only if /*compile-time condition */. All control-flow is affected (while, match, for, ...) and run-time conditions are affected as well.

But we don't have to be perfect, just conservatively correct.

Consider:

fn foo(x: bool) { loop { if x { break; } } }

where x is a run-time condition. If we don't emit @llvm.sideeffect here, then if the user writes foo(false) somewhere, foo could be inlined and with constant propagation and dead code elimination, the loop optimized into an infinite loop without side-effects, resulting in a mis-optimization.

If that makes sense, one transformation that LLVM would be allowed to do is replacing foo with foo_opt:

fn foo_opt(x: bool) { if x { foo(true) } else { foo(false) } }

where both branches are optimized independently, and the second branch would be mis-optimized if we don't use @llvm.sideeffect.

That is, to be able to omit @llvm.sideeffect, we would need to prove that LLVM cannot mis-optimize that loop under any circumstances. The only way to prove this is to either prove that the loop always terminates, or to prove that if it does not terminate, that it unconditionally does one of the things that prevent mis-optimizations. Even then, optimizations like loop splitting/peeling could transform one loop into a series of loops, and it would be enough for one of them to not have @llvm.sideeffect for a mis-optimization to happen.

[Ekleog]

Everything about this bug sounds to me like it'd be much easier to solve from LLVM than from rustc. (disclaimer: I don't really know the code base of either of these projects)

As I understand it, the fix from LLVM would be changing optimizations from running on (prove non-termination || can't prove either) to running only when non-termination can be proven (or the opposite). I'm not saying this is easy (in any way), but LLVM already (I guess) includes code to try to prove (non-)termination of loops.

On the other hand, rustc can only do this adding @llvm.sideeffect, which will potentially have more impact to optimization than “just” disabling the optimizations that make inappropriate use of non-termination. And rustc would have to embed new code to try to detect (non-)termination of loops.

So I would think the path forward would be:

1. Add @llvm.sideeffect on every loop and function call to fix the issue
2. Fix LLVM to not perform wrong optimizations on non-terminating loops, and remove the @llvm.sideeffects

What do you think about this? I hope the performance impact of step 1 wouldn't be too horrible, though, even if it's meant to vanish once 2 is implemented…

[gnzlbg]

@Ekleog that's what @sunfishcode second patch might be about: https://lists.llvm.org/pipermail/llvm-dev/2017-October/118595.html

part of the function attribute proposal is to
change the default semantics of LLVM IR to have defined behavior on
infinite loops, and then add an attribute opting into potential-UB. So
if we do that, then the role of @llvm.sideeffect becomes a little
subtle -- it'd be a way for a frontend for a language like C to opt
into potential-UB for a function, but then opt out for individual
loops in that function.

[sunfishcode]

To be fair to LLVM, compiler writers don't approach this topic from the perspective of "I'm going to write an optimization that proves loops are non-terminating, so that I can pedantically optimize them away!" Instead, the assumption that loops will either terminate or have side effects just arises naturally in some common compiler algorithms. Fixing this isn't just a tweak to existing code; it'll require a significant amount of new complexity.

Consider the following algorithm for testing whether a function body "has no side effects": if any instruction in the body has potential side effects, then the function body may have side effects. Nice and simple. Then later, calls to functions "with no side effects" are deleted. Cool. Except, branch instructions are considered to have no side effects, so a function containing only branches will appear to have no side effects, even though it may contain an infinite loop. Oops.

It is fixable. If anyone else is interested in looking into this, my basic idea is to split the concept of "has side effects" into independent concepts of "has actual side effects" and "may be non-terminating". And then go through the whole optimizer and find all the places that care about "has side effects" and figure out which concept(s) they actually need. And then teach the loop passes to add metadata to branches that aren't part of a loop, or the loops they're in are provably finite, in order to avoid pessimizations.

---

A possible compromise might be to have rustc insert @llvm.sideeffect when a user literally writes an empty loop { } (or similar) or unconditional recursion (which already has a lint). This compromise would allow people who actually do intend an infinite effectless spinning loop to get it, while avoiding any overhead for everyone else. Of course, this compromise wouldn't make it impossible to crash safe code, but it would likely reduce the chances of it happening accidentally, and it seems like it should be easy to implement.

[RalfJung]

Instead, the assumption that loops will either terminate or have side effects just arises naturally in some common compiler algorithms.

It is entirely unnatural though if you even start to think about correctness of those transformations. To be frank I still think it was a huge mistake of C to ever allow this assumption, but well.

if any instruction in the body has potential side effects, then the function body may have side effects.

There's a good reason that "non-termination" is typically considered an effect when you start to look at things formally. (Haskell isn't pure, it has two effects: Non-termination and exceptions.)

A possible compromise might be to have rustc insert @llvm.sideeffect when a user literally writes an empty loop { } (or similar) or unconditional recursion (which already has a lint). This compromise would allow people who actually do intend an infinite effectless spinning loop to get it, while avoiding any overhead for everyone else. Of course, this compromise wouldn't make it impossible to crash safe code, but it would likely reduce the chances of it happening accidentally, and it seems like it should be easy to implement.

As you noted yourself, this is still incorrect. I do not think we should accept a "solution" which we know to be incorrect. Compilers are such an integral part of our infrastructure, we shouldn't just hope that nothing goes wrong. This is no way to build a solid foundation.

---

What happened here is that the notion of correctness was built around what compilers did, instead of starting with "What do we want from our compilers" and then making that their specification. A correct compiler does not turn a program that always diverges into one that terminates, period. I find this rather self-evident, but with Rust having a reasonable type system, this is even clearly witnessed in the types, which is why the issue is surfacing regularly.

Given the constraints we are working with (namely, LLVM), what we should do is start by adding llvm.sideeffect in enough places such that every diverging execution is guaranteed to "execute" infinitely many of those. Then we have reached a reasonable (as in, sound and correct) baseline and can talk about improvements by way of removing these annotations when we can guarantee they are not needed.

[RalfJung]

To make my point more precise, I think the following is a sound Rust crate, with pick_a_number_greater_2 returning (non-deterministically) some kind of big-int:

fn test_fermats_last_theorem() -> bool {
  let x = pick_a_number_greater_2();
  let y = pick_a_number_greater_2();
  let z = pick_a_number_greater_2();
  let n = pick_a_number_greater_2();
  // x^n + y^n = z^n is impossible for n > 2
  pow(x, n) + pow(y, n) != pow(z, n)
}

pub fn diverge() -> ! {
  while test_fermats_last_theorem() { }
  // This code is unreachable, as proven by Andrew Wiles
  unsafe { mem::transmute(()) }
}

If we compile away that diverging loop, that's a bug and it should be fixed.

We don't even have numbers so far for how much performance it would cost to fix this naively. Until we do, I see no reason to deliberately break programs like the above.

[gnzlbg]

In practice, fn foo() { foo() } will always terminate due to resource exhaustion, but since the Rust abstract machine has an infinitely large stack frame (AFAIK), it is valid to transform that code into fn foo() { loop {} } which will never terminate (or much later, when the universe freezes). Should this transformation be valid? I'd say yes, since otherwise we can't perform tail-call optimizations unless we can prove termination, which would be unfortunate.

Would it make sense to have an unsafe intrinsic that states that a given loop, recursion, ... always terminates? N1528 gives an example were, if loops cannot be assumed to terminate, loop fusion cannot be applied to pointer code traversing linked lists, because the linked lists could be circular, and proving that a linked list is not circular is not something that modern compilers can do.

[rkruppe]

I absolutely agree we need to fix this soundness issue for good. However, the way we go about that should be mindful of the possibility that "add llvm.sideeffect everywhere we can't prove it's unnecessary" may regress the code quality of programs that are compiled correctly today. While such concerns are ultimately overriden by the need to have a sound compiler, it might be prudent to proceed in a way that delays the proper fix a bit in exchange for avoiding performance regressions and improving quality of life for the average Rust programmer in the mean time. I propose:

• As with other potentially-performance-regressing fixes for long-standing soundness bugs (#10184) we should implement the fix behind a -Z flag to be able to evaluate the performance impact on code bases in the wild.
• If the impact turns out to be neglegible, great, we can just turn on the fix by default.
• But if there are real regressions from it, we can take that data to LLVM people and try to improve LLVM first (or we could choose to eat the regression and fix it later, but in any case we'd make an informed decision)
• If we decide to not turn on the fix by default due to regressions, we can at least go ahead with adding llvm.sideeffect to syntactically empty loops: they're rather common and them being miscompiled has lead to multiple people spending miserable hours debugging weird issues (#38136, #47537, #54214, and surely there's more), so even though this mitigation has no bearing on the soundness bug, it would have a tangible benefit for developers while we work out the kinks in the proper bug fix.

Admittedly, this perspective is informed by the fact that this issue has been standing for years. If it was a fresh regression, I would be more open to fixing it more quickly or reverting the PR that introduced it.

[NeoLegends]

Meanwhile, should this be mentioned in https://doc.rust-lang.org/beta/reference/behavior-considered-undefined.html as long as this issue is open?