rust 需要什么编译器优化来优化这个递归调用?

ttcibm8c  于 2023-08-05  发布在  其他
关注(0)|答案(2)|浏览(101)

下面是普通算术表达式计算器的两个版本(playground链接:https://play.rust-lang.org/?version=nightly&mode=release&edition=2021&gist=d3da06b0077b29e0e3ac85720c567dd8)第二个版本使用递归调用来重用一些代码(显然不值得在这个玩具示例中花费精力,但这就是为什么它是一个玩具示例)。我相信,一个足够聪明的编译器可以意识到对eval_slow(Sum(...))的递归调用本身不会进行任何递归调用,因此内联是安全的,并且eval_slow实际上应该编译为与eval_fast相同的程序集。在实践中,rustc目前不执行这种优化,eval_slow包含一个递归调用(请参阅playground链接中的汇编输出)。
是否有优化编译器能够执行这种类型的优化(对于任何语言)?在编译器文献中有没有这种类型的优化的名称?这可能在不久的将来被正确地优化吗?或者这是一个非常困难的开放问题?

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的,尽管我的示例是(并且afaik这种优化很可能存在于LLVM的语言不可知的通道中)
编辑:TCO不是我想要的--上面的逻辑并不依赖于递归调用的尾部位置。此外,与一些最初的评论相反,Clang并没有在一般情况下解决C++的这个问题-这里有一个例子,它已经被修改,使得递归调用不在尾部位置,并且其中递归调用不是内联的。https://godbolt.org/z/cGabvvvro(是的,一个版本打印两次-不应影响要点)

gxwragnw

gxwragnw1#

不幸的是,与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


螺栓连接

7eumitmz

7eumitmz2#

GCC称之为“递归内联”:

  • 第一个月
  • 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适用。
(等等)
根据this presentation from 2015,LLVM不考虑自递归(除了尾部递归)函数进行内联。我还没有看过代码,看看添加它是多么简单;它必然需要某种程度试探。
强制LLVM内联非尾递归调用的一个有趣的技术是使用(C++)模板机制generate multiple copies函数,然后依靠优化器将它们内联回去并丢弃冗余副本:

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); }

字符串

相关问题