如何优化掉这个递归调用，需要哪些编译器优化？

Question

这里有两个版本的简单算术表达式求值器（游乐场链接：https://play.rust-lang.org/?version=nightly&mode=release&edition=2021&gist=d3da06b0077b29e0e3ac85720c567dd8）。 第二个版本使用递归调用来重用一些代码（显然在这个玩具示例中不值得这样做，但这就是为什么它是一个玩具示例）。 我相信一个足够聪明的编译器可以意识到对eval_slow(Sum(...))的递归调用本身并没有进行任何递归调用，因此是安全的进行内联，并且eval_slow实际上应该编译成与eval_fast相同的汇编代码。实际上，rustc目前并没有执行这种优化，eval_slow包含一个递归调用（请参见游乐场链接中的汇编输出）。

有没有能够进行这种类型优化的优化编译器（适用于任何语言）？在编译器文献中是否有一个对这种类型优化的名称？这个问题在不久的将来是否有望得到正确优化，还是说（一般版本的）这是一个非常困难的开放性问题？

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

// simple and fast
pub fn eval_fast(expr: Expr) -> isize {
    use Expr::*;
    match expr {
        Lit(x) => x,
        Sum(x, y) => x + y,
        Sub(x, y) => x - y
    }
}

// we'd like to inline the recursive call to `eval_slow(Sum(...))`, but it doesn't happen. 
pub fn eval_slow(expr: Expr) -> isize {
    use Expr::*;
    match expr {
        Lit(x) => x,
        Sum(x, y) => x + y,
        Sub(x, y) => eval_slow(Sum(x, -y))
    }
}

注意：我也将此标记为C++，因为我的问题并不特定于Rust，尽管我的示例是（据我所知，这种优化可能存在于LLVM的与语言无关的传递中）

编辑： TCO（尾调用优化）不是我要找的 - 上面的逻辑不依赖于递归调用处于尾位置。另外，与一些最初的评论相反，Clang在C++的一般情况下并不能解决这个问题 - 这里有一个被修改过的示例，其中递归调用不在尾位置，并且递归调用没有内联。https://godbolt.org/z/cGabvvvro（是的，一个版本打印了两次 - 不影响主要观点）

- ajp

---

我只知道对于Visual Studio C++编译器，你可能想要查看一下__force_inline关键字。你可以在这里找到更多相关信息。 - HelpfulHelper

@chrysante 使用 -O2。 - n. m. could be an AI

如果你将函数标记为#[inline(always)]，它会进行内联，所以我猜这回答了问题吧？ - Chayim Friedman

@ChayimFriedman 在这里使用 #[inline(always)] 是无效的。它只是延迟了该函数的代码生成（所有 inline 函数都在调用点生成），所以你在 godbolt 上看不到代码，但它会在调用点生成递归。请参考：https://godbolt.org/z/cveh447T7 - Angelicos Phosphoros

为Rust编译器开了一个问题：https://github.com/rust-lang/rust/issues/114312 - Angelicos Phosphoros

Answer 1

不幸的是，与Clang不同，Rust默认情况下不能成功执行尾调用消除。

然而，如果我们从递归转换为循环，我们可以在没有递归的情况下获得概念上相同的代码.

pub fn eval_slow(mut expr: Expr) -> isize {
    use Expr::*;
    loop{
        expr = match expr {
            Lit(x) => return x,
            Sum(x, y) => return x + y,
            Sub(x, y) => Sum(x, -y),
        };
    }
}

结果：

example::eval_slow:
        mov     rax, qword ptr [rdi]
        test    rax, rax
        je      .LBB0_3
        cmp     rax, 2
        jne     .LBB0_2
        mov     rcx, qword ptr [rdi + 8]
        xor     eax, eax
        sub     rax, qword ptr [rdi + 16]
        mov     qword ptr [rdi], 1
        mov     qword ptr [rdi + 16], rax
        add     rax, rcx
        ret
.LBB0_3:
        mov     rax, qword ptr [rdi + 8]
        ret
.LBB0_2:
        mov     rcx, qword ptr [rdi + 8]
        mov     rax, qword ptr [rdi + 16]
        add     rax, rcx
        ret

godbolt link

- Angelicos Phosphoros

---

谢谢！部分有用，但我不满意，因为这里不应该需要“尾调用” - 请参见主贴的编辑。 - ajp

Answer 2

GCC将此称为“递归内联”。

• max-inline-insns-recursive

• max-inline-insns-recursive-auto

  • 指定自递归内联函数的外部副本通过执行递归内联可以增长到的最大指令数。

  • --param max-inline-insns-recursive 适用于声明为 inline 的函数。对于未声明为 inline 的函数，只有在启用了 -finline-functions（包含在 -O3 中）时才会发生递归内联；相反，应使用 --param max-inline-insns-recursive-auto。

• max-inline-recursive-depth

• max-inline-recursive-depth-auto

  • 指定用于递归内联的最大递归深度。

  --param max-inline-recursive-depth 适用于声明为 inline 的函数。对于未声明为 inline 的函数，只有在启用了 -finline-functions（包含在 -O3 中）时才会发生递归内联；相反，应使用 --param max-inline-recursive-depth-auto。

（等等）

根据2015年的此演示文稿，LLVM不会考虑对自递归（非尾递归）函数进行内联。我还没有查看代码以确定添加起来是否简单；这必然需要一定程度的启发式算法。

一个有趣的技巧是使用（C++）模板机制生成多个函数副本，以强制LLVM内联非尾递归调用，然后依靠优化器将它们再次内联并丢弃冗余的副本。

template<int I = 0>
int eval_slow(expr e)
{
    int ret;
    switch (e.op)
    {
        case expr::lit: ret = e.i1; break;
        case expr::plus: ret = e.i1 + e.i2; break;
        case expr::minus: ret = eval_slow<(I + 1) % 2>(expr{expr::plus, e.i1, -e.i2}); break;
    }
    std::cout << ret;
    return ret;
}
int eval_slow(expr e) { return eval_slow<>(e); }

- ecatmur