编译器是如何对这个阶乘函数进行如此优秀的优化？

Question

我一直在研究GCC中的一些神奇功能O3（实际上我正在使用Clang编译，但是它与GCC相同，我猜优化器的很大部分是从GCC移植到Clang的）。

考虑这个C程序：

int foo(int n) {
    if (n == 0) return 1;
    return n * foo(n-1);
}

int main() {
    return foo(10);
}

我第一次感到非常惊讶的是（这也在这个问题中引起了注意 - https://dev59.com/EXRC5IYBdhLWcg3wG9Xo#414774），int foo(int)（一个基本阶乘函数）如何编译成一个紧凑的循环。这是它的ARM汇编代码：

    .globl  _foo
    .align  2
    .code   16
    .thumb_func _foo
_foo:
    mov r1, r0
    movs    r0, #1
    cbz r1, LBB0_2
LBB0_1:
    muls    r0, r1, r0
    subs    r1, #1
    bne LBB0_1
LBB0_2:
    bx  lr

哇，我想了一下。这很有趣！完全使用紧密循环来计算阶乘。哇。它并不是尾调用优化，因为它不是尾调用。但它似乎进行了类似的优化。

现在看看 main ：

    .globl  _main
    .align  2
    .code   16
    .thumb_func _main
_main:
    movw    r0, #24320
    movt    r0, #55
    bx  lr

说实话，这让我大开眼界。它完全绕过了foo函数，并返回了10！的值3628800。

这让我真正意识到编译器通常可以比你更好地优化代码。但是，它引出了一个问题，它是如何做到如此出色的工作的？所以，有人能解释一下（可能通过链接相关代码）以下优化是如何工作的吗：

1. 将初始的foo优化为紧凑循环。

2. 优化main直接返回结果而不是实际执行foo函数。

此外，这个问题的另一个有趣的副作用是展示GCC/Clang可以进行的一些更有趣的优化。

- mattjgalloway

Answer 1

如果您使用gcc -O3 -fdump-tree-all进行编译，您可以看到递归被转换为循环的第一个转储是foo.c.035t.tailr1。这意味着处理其他尾调用的相同优化也处理了这种稍微扩展的情况。以n * foo(...)或n + foo(...)形式的递归并不难手动处理（见下文），而且由于可以准确描述如何处理，编译器可以自动执行该优化。

main的优化要简单得多：内联可以将其转换为10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 1，如果乘法的所有操作数都是常量，则可以在编译时执行乘法。

更新：以下是您可以手动从foo中删除递归的方法，这可以自动完成。我不是说这是GCC使用的方法，但这是一个现实的可能性。

首先，创建一个辅助函数。它的行为与foo(n)完全相同，只是其结果乘以额外的参数f。

int foo(int n)
{
    return foo_helper(n, 1);
}

int foo_helper(int n, int f)
{
    if (n == 0) return f * 1;
    return f * n * foo(n-1);
}

然后，将foo的递归调用转换为foo_helper的递归调用，并依靠因子参数来消除乘法。

int foo(int n)
{
    return foo_helper(n, 1);
}

int foo_helper(int n, int f)
{
    if (n == 0) return f;
    return foo_helper(n-1, f * n);
}

将此转换为循环：

int foo(int n)
{
    return foo_helper(n, 1);
}

int foo_helper(int n, int f)
{
restart:
    if (n == 0) return f;
    {
        int newn = n-1;
        int newf = f * n;
        n = newn;
        f = newf;
        goto restart;
    }
}

最后，内联foo_helper：

int foo(int n)
{
    int f = 1;
restart:
    if (n == 0) return f;
    {
        int newn = n-1;
        int newf = f * n;
        n = newn;
        f = newf;
        goto restart;
    }
}

（当然，这并不是手动编写函数的最明智方式。）

- user743382

---

非常出色的答案！而且“main”优化确实可以用常数相乘来替代，这样就容易了。我喜欢你对“foo”优化的演示 :-)。 - mattjgalloway