Recursion using `extern "C"` causes miscompilation

[AngelicosPhosphoros]

I tried this code:

pub enum Expr {
    Lit(isize),
    Sum(isize, isize),
    Sub(isize, isize),
}

pub fn eval_slow(expr: Expr) -> isize {
    use Expr::*;
    extern "C" fn eval_inner(expr: Expr)->isize{
        match expr {
            Lit(x) => x,
            Sum(x, y) => x + y,
            Sub(x, y) => eval_inner(Sum(x, -y)),
        }
    }
    eval_inner(expr)
}

I expected to see this happen: compiled function correctly handles Sub(x, y)

Instead, this happened: compiler generates code with infinite loop.

See asm (from -Copt-level=3):

example::eval_slow:
        mov     rax, qword ptr [rdi]
        test    rax, rax
        je      .LBB0_3
        cmp     eax, 1
        jne     .LBB0_2
        mov     rax, qword ptr [rdi + 16]
        add     rax, qword ptr [rdi + 8]
        ret
.LBB0_2:                            ;  <--------- Infinite loop header
        jmp     .LBB0_2          ;  <--------- Unconditional jump to previous instruction
.LBB0_3:
        mov     rax, qword ptr [rdi + 8]
        ret

Meta

rustc --version --verbose:

rustc 1.71.0 (8ede3aae2 2023-07-12)
binary: rustc
commit-hash: 8ede3aae28fe6e4d52b38157d7bfe0d3bceef225
commit-date: 2023-07-12
host: x86_64-unknown-linux-gnu
release: 1.71.0
LLVM version: 16.0.5
Compiler returned: 0

[AngelicosPhosphoros]

It seems, that bug was introduced between 1.69 and 1.70:

godbolt

[asquared31415]

I am not particularly well versed in miscompilations, but the IR we emit to LLVM looks fine. Investigating more later, but I suspect an LLVM update affects this.

[lukas-code]

reduced LLVM IR: https://godbolt.org/z/Yncqrjfr7

define void @foo(ptr noalias byval(i64) %x) {
start:
  %new_x = alloca i64, align 8
  %x_val = load i64, ptr %x, align 8
  %is_zero = icmp eq i64 %x_val, 0
  br i1 %is_zero, label %end, label %recurse

recurse:
  store i64 0, ptr %new_x, align 8
  call void @foo(ptr %new_x)
  br label %end

end:
  ret void
}

optimizes to

define void @foo(ptr noalias nocapture readonly byval(i64) %x) {
  %x_val = load i64, ptr %x, align 8
  %is_zero = icmp eq i64 %x_val, 0
  br i1 %is_zero, label %end, label %recurse

recurse:
  br label %recurse

end:
  ret void
}

Needs noalias + byval to reproduce. Looks like the tail call optimization pass writes into the argument, even thou it is readonly at that point.

Did not bisect, but this was probably introduced by the upgrade to LLVM 16: #109474

@rustbot label A-llvm I-unsound

[asquared31415]

If anyone's interested in a Rust level test, it can be reduced a decent amount:

#[repr(C)]
pub enum Expr {
    Sum,
    // must have more than usize data
    Sub(usize, u8),
}

pub extern "C" fn eval_inner(expr: Expr) {
    match expr {
        Expr::Sum => {}
        Expr::Sub(_, _) => eval_inner(Expr::Sum),
    }
}

godbolt

looking at that LLVM IR it could probably be reduced more, but really at this point there's not a whole lot left to remove.

[erikdesjardins]

Yeah, it looks like tailcallelim introducing a write to a readonly parameter is the culprit.

Strangely, Alive2 is okay with writing to a readonly byval argument, and only thinks it's UB if it's non-byval: https://alive2.llvm.org/ce/z/T6yxU-.

This makes some sense semantically (since the hidden copy of the argument means modifications aren't visible to the caller), but seems to be in contradiction with the langref, which says:

The copy is considered to belong to the caller not the callee (for example, readonly functions should not write to byval parameters).

Opened llvm/llvm-project#64289