Why did/does disable-optimize expose a hidden infinite loop

[pnkfelix]

This is spawned off of Issues #6061 and #6049

Those were bugs were some developers could not bootstrap Rust because it was hitting stack exhaustion issues during the bootstrap process. The stack exhaustion was due to an infinite loop in a core routine. However, the curious question is why that core routine was not being invoked uniformly for all builds.

From my attempts to isolate the problem (see notes on #6061), it appears like the behavior of the binaries generated by configure --disable-optimize have significant semantically-visible differences from binaries generated by configure.

We have since plugged in a fix for the infinite loop in the core routine, so that everyone can bootstrap and we're all happy. Except we're not, because there's still a bug here that was exposed by the infinite loop (namely the difference when you toggle --disable-optimize) and was not fixed when the infinite loop was fixed.

There are at least two ways to go about reproducing this problem at this stage (where we have not narrowed it down too much). The first and most robust way is to actually check out the code from the commit where this bug was encountered and before it the infinite loop was removed, say for example SHA: 1d53bab
(The problem with that strategy is that if the underlying bug gets fixed in the meantime by someone else, you might not know it, and waste a lot of time investigating an issue that has since been resolved.)

The second way to reproduce the problem is to revert the fix to the infinite loop (which is a tiny patch) and then attempt a bootstrap build with and without --disable-optimize. I demonstrate that strategy here:

% git diff
diff --git a/src/libcore/rand.rs b/src/libcore/rand.rs
index 80f69f0..8b77539 100644
--- a/src/libcore/rand.rs
+++ b/src/libcore/rand.rs
@@ -843,7 +843,7 @@ pub fn task_rng() -> @IsaacRng {
 // Allow direct chaining with `task_rng`
 impl<R: Rng> Rng for @R {
     #[inline(always)]
-    fn next(&self) -> u32 { (**self).next() }
+    fn next(&self) -> u32 { (*self).next() }
 }

 /**
% mkdir objdir-default
% mkdir objdir-dis-opt
% cd objdir-default/
% ../configure > ../invoke-config-default.log
sed: 1: "tools/Makefile": undefined label 'ools/Makefile'
% make rustc-stage1 -j4 >> ../invoke-make-default.log 2>&1
% cd ../objdir-dis-opt/
% ../configure --disable-optimize > ../invoke-config-dis-opt.log
sed: 1: "tools/Makefile": undefined label 'ools/Makefile'
% make rustc-stage1 -j4 > ../invoke-make-dis-opt.log  2>&1
[ERROR#1] % tail ../invoke-make-dis-opt.log
                                                         ^~~~~
warning: no debug symbols in executable (-arch x86_64)
compile_and_link: x86_64-apple-darwin/stage0/lib/rustc/x86_64-apple-darwin/bin/rustc
cp: x86_64-apple-darwin/stage1/lib/librustc.dylib
warning: no debug symbols in executable (-arch x86_64)
cp: x86_64-apple-darwin/stage1/bin/rustc
compile_and_link: x86_64-apple-darwin/stage1/lib/rustc/x86_64-apple-darwin/lib/libcore.dylib
rust: task 7ff2a040ac80 ran out of stack
/bin/sh: line 1: 80249 Abort trap: 6           x86_64-apple-darwin/stage1/bin/rustc --cfg stage1 --target=x86_64-apple-darwin -o x86_64-apple-darwin/stage1/lib/rustc/x86_64-apple-darwin/lib/libcore.dylib /tmp/rust/src/libcore/core.rc
make: *** [x86_64-apple-darwin/stage1/lib/rustc/x86_64-apple-darwin/lib/libcore.dylib] Error 134
% 

[nikomatsakis]

Huh. That is very surprising!

[skinner]

There is, maybe, an easier way to reproduce this, using @huonw's test case from #6061:

$ cat trait-recursive-iloop.rs 
trait Foo {
    fn x(&self);
}

impl Foo for int {
    fn x(&self) {}
}

impl<F:Foo> Foo for @F {
    fn x(&self) {
        (*self).x()
    }
}

fn main() {
    (@1i).x()
}
$ rustc --opt-level 0 trait-recursive-iloop.rs 
$ ./trait-recursive-iloop 
rust: task 794060 ran out of stack
Aborted (core dumped)
$ rustc --opt-level 1 trait-recursive-iloop.rs 
$ ./trait-recursive-iloop 
$ rustc --version
rustc 0.6 (1f65e4a 2013-05-04 00:48:37 -0700)
host: x86_64-unknown-linux-gnu

it runs out of stack with --opt-level 0 but not with --opt-level 1. This is on Fedora 17 x86_64 with a rustc that I just built from incoming (without --disable-optimize).

[cscott]

Here's another simple test case:

pub struct IString(uint);

impl Eq for IString {
    fn eq(&self, other: &IString) -> bool { *self == *other }
    fn ne(&self, other: &IString) -> bool { *self != *other }
}

pub fn foo(a: IString, b: IString) -> bool { a==b }

This code is buggy -- the implementation of eq actually needs to read { **self == **other }; as written foo() contains an infinite recursion. However, when compiled with -O this infinite loop goes away -- the resulting assembly is:

_ZN3foo17_1773c175964f18a23_00E:
    .cfi_startproc
    cmpl    %gs:48, %esp
    ja  .LBB3_2
    pushl   $16
    pushl   $4
    calll   __morestack
    ret
.LBB3_2:
    pushl   %ebp
.Ltmp15:
    .cfi_def_cfa_offset 8
.Ltmp16:
    .cfi_offset %ebp, -8
    movl    %esp, %ebp
.Ltmp17:
    .cfi_def_cfa_register %ebp
    popl    %ebp
    ret
.Ltmp18:
    .size   _ZN3foo17_1773c175964f18a23_00E, .Ltmp18-_ZN3foo17_1773c175964f18a23_00E
    .cfi_endproc

Look! No more infinite loop! (I always knew that rust was fast! It executes infinite loops faster than any other language --- so long as you use -O.)

[Aatch]

This may be because of the fact that LLVM will optimize infinite loops into no-opts, if it can prove that the infinite loops do nothing. This is part of C++11 (I think).

With inlining, it's possible that it finds that it can do that optimization.

I don't think this should be blocking 0.7 though.

[thestinger]

@Aatch: I don't think they're actually doing that yet though despite C++11 allowing it, because C and older C++ revisions don't allow it.

[huonw]

@Aatch seems to be mostly correct, although LLVM considers this to be a bug: http://llvm.org/bugs/show_bug.cgi?id=965

$ clang -x c - <<< 'int main() { main(); return 0; }' && ./a.out
Segmentation fault
$ clang -O -x c - <<< 'int main() { main(); return 0; }' && ./a.out # runs fine
$ rustc - <<< 'fn main() { main() }' && ./rust_out
rust: task efc060 ran out of stack
Aborted
$ rustc -O - <<< 'fn main() { main() }' && ./rust_out # runs fine

(Clang actually optimises that C to xorl %eax,%eax; ret)

[catamorphism]

I think this is now a moot point because the bots are running with both optimize and disable-optimize. Reopen if you disagree.

[pnkfelix]

Hmm. I might still like to fix the underlying LLVM bug here (assuming that is what is indeed the cause of the problem), but that task should probably be forked off into a different bug at this point.

[thestinger]

@pnkfelix: it's an open LLVM bug so I don't think we need our own issue open, we have all their other bugs too :P