Inconsistent recursive fn call elimination

[Rudxain]

I tried this code:

#[inline(never)]
#[no_mangle]
const fn deep(n: usize) {
    match n {
        0 => (),
        _ => deep(n - 1),
    }
}

#[inline(always)]
const fn inf() -> ! {
    inf()
}

fn main() {
    deep(usize::MAX);
    println!("✅");
    inf();
}

I expected to see this happen: prints "✅" fast and successfully, then hangs in an infinite loop.

Instead, this happened: prints "✅" fast and panics with stderr:

   Compiling playground v0.0.1 (/playground)
    Finished `release` profile [optimized] target(s) in 0.38s
     Running `target/release/playground`

thread 'main' has overflowed its stack
fatal runtime error: stack overflow

It seems commenting-out the attributes is no-op here.

Meta

https://play.rust-lang.org/?version=nightly&mode=release&edition=2021&gist=ed0941cd328e49d8737fdff01cd4a4aa

rustc --version --verbose:

1.80.0-nightly

(2024-05-28 da159eb331b27df52818)

Backtrace

<no diff>

Apologies in advance, if this issue is a dupe. I tried my best to find similar ones

[workingjubilee]

This seems to be a duplicate of #102952 and many others like that one.

[Rudxain]

Weirdly enough, I tried this with #112788

#![feature(explicit_tail_calls)]
const fn inf() -> ! {
    become inf()
}

fn main() {
    inf();
}

It still overflows the stack! Even though the (unofficial) docs claim it must not.

I've been reading about the RFC, and it seems the syntax is the only thing that got implemented

[workingjubilee]

interesting.

[bjorn3]

The llvm ir correctly contains

; playground::inf
; Function Attrs: nofree noreturn nosync nounwind nonlazybind memory(none) uwtable
define internal fastcc void @_ZN10playground3inf17hbbe49911b1985149E() unnamed_addr #3 {
start:
; call playground::inf
  tail call fastcc void @_ZN10playground3inf17hbbe49911b1985149E() #7
  unreachable
}

[workingjubilee]

weird.

[DianQK]

In my view, the code behavior initially mentioned in the issue is reasonable. I want to know why you expect it won't overflow the stack, inline(always) doesn't guarantee that inline will definitely occur.

[bjorn3]

The behavior in #125698 (comment) is definitively wrong. It uses become which should force a tail call, yet doesn't get tail called.

[the8472]

The tail call feature (#112788) is still in progress, e.g. #113128 has not been merged yet.

[Rudxain]

why you expect it won't overflow the stack

What I actually find surprising is that the compiler was eager to obliterate deep(usize::MAX) as if it was never there, but inf() didn't get the same similar treatment.

inline(always) doesn't guarantee that inline will definitely occur.

I know, I just wanted to "add emphasis" (I'm unsure if this is the correct terminology?)

[WaffleLapkin]

The tail call feature (#112788) is still in progress, e.g. #113128 has not been merged yet.

Also note that #113128 by itself won't implement the feature correctly either, since it does not include llvm lowering.

[DianQK]

why you expect it won't overflow the stack

What I actually find surprising is that the compiler was eager to obliterate deep(usize::MAX) as if it was never there, but inf() didn't get the same similar treatment.

Although both will result in a stack overflow at runtime, deep is a non-infinite recursive function without side effects, which the compiler can completely eliminate.

inline(always) doesn't guarantee that inline will definitely occur.

I know, I just wanted to "add emphasis" (I'm unsure if this is the correct terminology?)

I think maybe your meaning is similar. inline(always) means to inline whenever possible. inline should adjust the threshold for the inlining cost.

[Rudxain]

deep is a non-infinite recursive function without side effects

Correct! It makes sense. But (I may be getting into philosophical territory here) an OOM panic could be considered a side-effect, at least from the POV of a system (doesn't apply to no_std lib crates).

From the POV of a Rust program, OOM panics can't exist (in the same way ! is a "never type") so Rust as a lang is allowed to "ignore" them. But rustc should know that a call-stack cannot have the same size as the entire address-space of any target-triple (except Harvard machines), otherwise the program itself cannot fit in memory, so an OOM panic should happen anyways.

inline should adjust the threshold for the inlining cost.

Thanks for explaining! I just had some problems communicating my thoughts. My intention was to add "emphasis" both for humans and rustc, if that makes sense 😅

[workingjubilee]

From the POV of a Rust program, OOM panics can't exist (in the same way ! is a "never type") so Rust as a lang is allowed to "ignore" them.

That's not really true at all. We have a defined set of behaviors in response to out-of-memory errors. The language has semantics for allocations, and it has a semantic for failing to allocate (some of the APIs represent this as returning nullptr, some of them as Result). You are referring to the behavior of very specific datatypes which effectively .unwrap() those Results. No one says "unwrap() can't exist". Instead, things that don't exist in Rust include the set of, e.g.

• dereferenced null pointers
• individual allocations larger than isize::MAX bytes
• two active &mut T to the same T

[Rudxain]

some of them as Result

Indeed, I've just read about try_reserve, and this crate which has try_push (I wish that was in std)

No one says "unwrap() can't exist"

I should've said something along the lines of "unreachable code", since a guaranteed panic is equivalent to FnOnce() -> !. Thanks for the correction 👍

[programmerjake]

  tail call fastcc void @_ZN10playground3inf17hbbe49911b1985149E() #7

tail means it may or may not become a tail call; to require LLVM to generate a tail call, you need to use musttail call ... instead