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/12e73f45f3/rust/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 no 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.