Infinite recursion can be "optimized" into LLVM undef which produces a garbage value

[nodakai]

fn f(x: i32) -> i32 {
    f(x)
}

fn main() {
    println!("{}", f(0));
}

0
Program ended.

• http://is.gd/46GQ4K

Note we get a stack overflow as expected(!?) with -O0 (observation by mboeh)

[mahkoh]

Infinite recursion is undefined behavior.

[Thiez]

@mahkoh I couldn't find that in the reference, do we document that somewhere?

[thestinger]

Infinite recursion is undefined behavior.

It's not undefined behaviour in Rust or LLVM.

[swgillespie]

For what it's worth, clang does the same thing: http://goo.gl/SA5x5b , so not sure if it's an issue.

[mahkoh]

It's undefined behavior in C++ and it looks like there is an LLVM bug from 2006 that causes this behavior: https://web.archive.org/web/20140911163336/http://llvm.org/bugs/show_bug.cgi?id=965

[thestinger]

It's a well known optimization bug in LLVM. It occurs because it doesn't try to model halting as an effect.

[thestinger]

@mahkoh: It's not undefined behaviour in C or LLVM. The C++11 standard allowed optimizing out infinite loops, but LLVM never actually intended to do it. It's just an age old bug in how it models purity.

[mboeh]

Digging some more:

• f doesn't even appear in the generated IR.
• replacing f(0) with 0 as i32 generates the same IR, except it actually stores the 0.
• the 'evaluates to 0' behavior can propagate over multiple expressions, as long as they do not have side effects: http://is.gd/WsCfGq http://is.gd/LqGqTY
• once it's passed to println, it goes from being a value that causes all expressions to evaluate to 0 to actually 0: http://is.gd/qQXqFp
• any side effect and some comparisons in f will cause it to instead be (correctly) compiled into a tail-recursive function that never returns.

[huonw]

cc #17899 which would help paper over this bug.

[bstrie]

I think it's important that we publicly acknowledge the threat that this represents, given that it's going to be a known source of unsafety in safe Rust code as of 1.0. The fact that it's LLVM's fault doesn't get us off the hook, the least we can do is be forthright about it.

[klutzy]

Note that this causes undef:

pub fn f() -> isize { fn rec() -> isize { rec() } rec() }

define i64 @_ZN1f20hfbe7b5e4892376b9eaaE() unnamed_addr #0 {
entry-block:
  ret i64 undef
}

[thestinger]

@bstrie: There are hundreds of open LLVM bugs representing soundness issues, and this is just one. I don't think there's anything special about it.