下面是普通算术表达式计算器的两个版本(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(是的,一个版本打印两次-不应影响要点)
2条答案
按热度按时间gxwragnw1#
不幸的是,与Clang不同,Rust在默认情况下不会成功执行尾调用消除。
然而,如果我们从递归切换到循环,我们可以在没有递归的情况下得到概念上相同的代码:
字符串
测试结果:
型
螺栓连接
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函数,然后依靠优化器将它们内联回去并丢弃冗余副本:
字符串