Infinite loop optimized out by inlining?

[zackw]

This crate

fn noret() -> ! { loop { } }
pub fn test_noret() -> () { noret() }

when compiled without optimization (rustc --crate-type rlib --emit asm), produces

_ZN4test5noret17hecd4eea31d87a48aE:
        .cfi_startproc
        jmp     .LBB0_1
.LBB0_1:
        jmp     .LBB0_1
.Lfunc_end0:
        .size   _ZN4test5noret17hecd4eea31d87a48aE, .Lfunc_end0-_ZN4test5noret17hecd4eea31d87a48aE
        .cfi_endproc
_ZN4test10test_noret17h492e3702bacafd6bE:
        .cfi_startproc
        pushq   %rax
.Lcfi0:
        .cfi_def_cfa_offset 16
        callq   _ZN4test5noret17hecd4eea31d87a48aE
.Lfunc_end1:
        .size   _ZN4test10test_noret17h492e3702bacafd6bE, .Lfunc_end1-_ZN4test10test_noret17h492e3702bacafd6bE
        .cfi_endproc

but when compiled with optimization on (rustc --crate-type rlib --emit asm -O), no assembly instructions at all are emitted for test_noret:

_ZN4test10test_noret17h492e3702bacafd6bE:
        .cfi_startproc
.Lfunc_end0:
        .size   _ZN4test10test_noret17h492e3702bacafd6bE, .Lfunc_end0-_ZN4test10test_noret17h492e3702bacafd6bE
        .cfi_endproc

I expected to get something like

_ZN4test10test_noret17h492e3702bacafd6bE:
        .cfi_startproc
.LBB0_1:
        jmp     .LBB0_1
.Lfunc_end0:
        .size   _ZN4test10test_noret17h492e3702bacafd6bE, .Lfunc_end0-_ZN4test10test_noret17h492e3702bacafd6bE
        .cfi_endproc

Identical behavior observed with rustc 1.17.0 (56124baa9 2017-04-24) and rustc 1.19.0-nightly (386b0b9d3 2017-05-14).

[hanna-kruppe]

#28728

[zackw]

This smells like LLVM deducing that test_noret can never be called, but it is my understanding that you are allowed to call a function whose signature is (...) -> !, it just never returns. In any case, under no circumstances should a public function compile to zero assembly instructions; a public function that can genuinely never be called by correct code (e.g. pub fn dont_call_me() -> ! { unreachable!() } should at least produce a trap instruction.

[RalfJung]

Well, but this function can be called, so emitting a trap would be wrong.
What is the behavior of a public function with no code? Does it just do nothing, or is this a violation of the ABI?

EDIT: Oh, I guess "no code" means it doesn't return to the caller, but instead "falls through" to whatever is next in the text? That's indeed bad. LLVM is probably responsible for removing the loop, but that doesn't explain why there is no return.

[zackw]

@RalfJung From a low-level perspective, yes, it is possible to call the function, but any program that does call it is incorrect. This gets into the argument about the scope of "undefined behavior"...

And yes, a function containing no machine instructions will indeed fall through to whatever is next. LLVM is trying to have cake and eat it too -- it has removed the return instruction because it was unreachable, but it was only unreachable because of the infinite loop, which has also been removed.

Note that If you actually write pub fn dont_call_me() -> ! { unreachable!() }, that works out fine, because unreachable!() compiles to an unconditional call to rust_begin_panic, which doesn't get removed.

[RalfJung]

Are we sure LLVM is doing both of these transformations? I think that would be incorrect even in C, and I cannot get clang to do the same: https://godbolt.org/g/tyCz9C
C says you may assume any loop without side-effects terminates, but IIRC that doesn't mean diverging programs are UB.

Couldn't it be be that rustc is already removing/not emitting the return (because it thinks the function will never terminate), and then LLVM removes the loop (because C says you can do that)?

[hanna-kruppe]

@RalfJung The direct Rust equivalent of your C code doesn't have the loop eliminated either. In both languages, there is no return left in the IR by the time the optimizer is done with it (and presumably already long before that), for example the clang IR reads:

; Function Attrs: norecurse noreturn nounwind readnone uwtable
define i32 @square()() local_unnamed_addr #0 {
  br label %1

; <label>:1:                                      ; preds = %0, %1
  br label %1
}

[RalfJung]

Ah, so it takes that indirection through another function to trigger the bug. Interesting.
And indeed, the same thing then happens in clang: https://godbolt.org/g/1ApTJq
I don't think this is allowed even by C...

[hanna-kruppe]

Indeed LLVM's current behavior also violates the C standard, because it doesn't account for C's provisions for loop with cetain conditions being allowed to loop forever.

Couldn't it be be that rustc is already removing/not emitting the return (because it thinks the function will never terminate), and then LLVM removes the loop (because C says you can do that)?

Other parts of LLVM will gladly assume that code after an infinite loop is dead (e.g., simplifycfg will kill blocks not reachable from the entry block), so even if we added redundant instructions after diverging expressions this wouldn't be a robust workaround. In fact I'm wouldn't be surprised if simplifycfg ran at least once before the passes which remove infinite loops, so it may never help.

[hanna-kruppe]

Regardless, it seems pretty clear now this is a duplicate, so let's close this and continue discussion in the older issue.

[RalfJung]

I disagree. The other issue is not about a bug in LLVM or LLVM violating the C spec. It is about a mismatch between the Rust semantics and the LLVM IR semantics, where the latter permits removing infinite loops under some circumstances and the former does not.

OTOH, this bug here seems to actually be about a bug in LLVM, where LLVM performs optimizations that are not even valid under the LLVM IR semantics.

[hanna-kruppe]

We don't track LLVM bugs on this issue tracker, though. We track bugs in Rust (some of which may be ultimately rooted in LLVM bugs).

But aside from that, I would strongly argue that both are the exaxct same LLVM issue — both issues are a matter of no-progress loops getting optimized out, whether you want to describe this as "invalid optimization" or "lacking ability to express no-progress loops in IR". In fact, there's a single bug on the LLVM bugzille for this: https://bugs.llvm.org//show_bug.cgi?id=965 (note the many duplicates).

[RalfJung]

We don't track LLVM bugs on this issue tracker, though. We track bugs in Rust (some of which may be ultimately rooted in LLVM bugs).

Sure.

But aside from that, I would strongly argue that both are the exaxct same LLVM issue

I see. My latest information on #28728 was that currently, there's not enough interest from the LLVM side to support languages that do not permit removing infinite side-effect-free loops. Seems I was wrong, and the issue is more severe than that -- they don't even support C properly...

What I am saying is LLVM could fix https://bugs.llvm.org//show_bug.cgi?id=965 by compiling https://godbolt.org/g/1ApTJq to a function that returns immediately. That would be a correct fix for the bug as far as C is concerned, but #28728 would remain unfixed. In contrast, any fix to https://bugs.llvm.org//show_bug.cgi?id=965 will fix this bug at hand.

[zackw]

C does not permit the loop to be removed in static int diverge() { while(1){} }. The exact wording of the C standard (quoted in #28728) is "An iteration statement whose controlling expression is not a constant expression [and whose body has no observable side effects] ... may be assumed to terminate." while(1){} has a constant controlling expression and therefore must be preserved. If I understand the discussion at http://lists.llvm.org/pipermail/llvm-dev/2015-July/088095.html correctly, this is a difference from C++, which does allow the implementation to assume that all loops eventually terminate.

[RalfJung]

Oh, I see. I was not aware C and C++ differ here.
However, for Rust, even the "lighter" C version of this is unsound -- there is no "free lunch" when it comes to loop termination, as the type system otherwise becomes unsound. C doesn't have an empty type like ! (nor a sound type system, for that matter), so it doesn't really care. It was my understanding that's what #28728 tracks.

But, yeah, considering how LLVM treats this bug and comments like #28728 (comment), I have to agree this is a duplicate.

[arielb1]

@RalfJung

A while COND { FOO } Rust loop can be "lowered" to a

while (true) {
    if(!COND) break;
    FOO
}

loop, which §6.8.5.6 seems to imply to be well-defined even when divergent.

[RalfJung]

Ah, nice hack. :) If LLVM implemented the C spec properly, that should indeed be a sound compilation scheme.

Funny enough, this shouldn't even make any difference (in the CFG, after some normalization) compared to lowering the loop the "obvious" way. Which I guess is the reason why LLVM is broken.

[alexcrichton]

I'm going to close this in favor of #28728