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)

[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.

[thestinger]

@mboeh: It's a well known bug in how LLVM models effects. It removes calls to pure functions when the result is unused and it doesn't model halting as part of purity. The work that needs to be done to fix it is known. There are lots of bugs in LLVM and they aren't going to remove an optimization simply because there's a fixable issue with it.

[thestinger]

You have a lot of writing to do if you want to mention each known soundness bug in LLVM in Rust documentation... note that Rust isn't hurt by this any more than other safe languages building on it.

[steveklabnik]

Triage: Today, this program stack overflows in debug mode, and prints 32579 in release mode.

[nodakai]

The unconditional_recursion lint (#20373) is cool!

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

$ rustc --crate-type=lib --emit llvm-ir -O inf.rs            
inf.rs:1:1: 3:2 warning: function cannot return without recurring, #[warn(unconditional_recursion)] on by default
inf.rs:1 pub fn f(x: i32) -> i32 {
inf.rs:2     f(x)
inf.rs:3 }
inf.rs:2:5: 2:9 note: recursive call site
inf.rs:2     f(x)
             ^~~~
inf.rs:1:1: 3:2 help: a `loop` may express intention better if this is on purpose

; ModuleID = 'inf.0.rs' 
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

; Function Attrs: nounwind readnone uwtable
define i32 @_ZN1f20ha114846844acb461eaaE(i32) unnamed_addr #0 {
entry-block:
  ret i32 undef
}

attributes #0 = { nounwind readnone uwtable }

I wonder if we should turn it into a hard error, as it can be disastrous to dereference a garbage pointer:

• https://play.rust-lang.org/?gist=04cbe3784803742bf45b&version=stable

fn f(x: &String) -> &String { f(x) }

fn main() {
    println!("{}", f(&String::from("abc")));
}

playpen: application terminated abnormally with signal 11 (Segmentation fault)
Program ended.

Such a crash is a violation of the language's guarantee stated here:

• https://doc.rust-lang.org/reference.html#behavior-considered-undefined

12.3 Behavior considered undefined

The following is a list of behavior which is forbidden in all Rust code, including within unsafe blocks and unsafe functions. Type checking provides the guarantee that these issues are never caused by safe code.

...

• Dereferencing a null/dangling raw pointer

[DemiMarie]

I agree that unconditional recursion should be turned into a hard error – as long as Rust does not guarantee tail call elimination unconditional recursion is always a bug (except when the function is intended to panic before overflowing the stack).

[bstrie]

It wouldn't be wholly unprecedented to have a lint which gradually progressed from allow to deny, but it would require an RFC. I suggest someone write one. :)

[nodakai]

@DemiMarie

as long as Rust does not guarantee tail call elimination unconditional recursion is always a bug (except when the function is intended to panic before overflowing the stack).

Some system programs might want to issue the exit(2) syscall via process::exit() and skip any pending calls to destructors as the final step of an "infinite" recursion. Super edge case, though.

fn f(x: i32) -> String {
    if 0 < x {
        f(x - 1)
    } else {
        std::process::exit(0)
    }
}

[arielb1]

@nodakai

Functions may also call some other function with an infinite loop

fn f(x: i32) -> String {
    if 0 < x {
        f(x - 1)
    } else {
        main_loop() // fn main_loop() -> !
    }
}

[alexcrichton]

Closing in favor of #28728, which I believe is the same issue as this.

[nagisa]

I’ll reopen this issue, as the loop issue is somewhat separate from the recursion issue in terms of what parts of LLVM cause the issue to happen.

I investigated the code reported in #54049 and found that there, starting with a code as seen below, will dataflow-propagate a constant value.

define i32 @bar(i32 %i) unnamed_addr #0 {
start:
  %0 = icmp slt i32 %i, 1000
  br i1 %0, label %bb4, label %bb6

bb4:                                              ; preds = %bb3
  %1 = srem i32 %i, 2
  %2 = call i32 @bar(i32 %1)
  br label %bb6

bb6:                                              ; preds = %bb4, %bb2
  %_0.0 = phi i32 [ %2, %bb4 ], [ 1234567, %start ]
  ret i32 %_0.0
}

attributes #0 = { uwtable }

Running this code through the interprocedural sparse conditional constant propagation (opt -ipsccp f.ll) will propagate via dataflow the %_0.0 = 1234567, then %2 = 1234567 and end up with a %_0.0 = phi i32 [ 1234567, %bb4 ], [ 1234567, %start ], reaching a fixed point. This phi is then replaced with constant 1234567.

Unlike with loops, @llvm.sideeffect (the solution for the loop problem) will not help here, so I’m inclined to reopen this and track it separately from the loop issue.

[nagisa]

My bad. Adding a @llvm.sideeffect does help with the issue above. It will still optimise out return to 1234567, but will also prevent passes further along the pipeline from removing the recursive call to @bar.

[arielb1]

My bad. Adding a @llvm.sideeffect does help with the issue above. It will still optimise out return to 1234567, but will also prevent passes further along the pipeline from removing the recursive call to @bar.

In that case, I don't think there's a bug everywhere outside of rustc - the code before xpSCCP is semantically equivalent to the code after it, and the recursive call removal occurs only because we lack @llvm.sideffect.

[hanna-kruppe]

My understanding, too, is that this is basically the same issue as #28728 (just modulo tail recursion optimization, which is definitely permitted) and the fix for the UB it causes is the same, inserting enough llvm.sideeffect calls. It seems like @nagisa withdrew their objection, so I'm going to close this as duplicate again.