编译器如何如此好地优化这个阶乘函数？

所以我一直在研究一些神奇的东西O3在 GCC 中（实际上我正在使用 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://stackoverflow.com/a/414774/1068248 https://stackoverflow.com/a/414774/1068248）是怎样的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并返回3628800这是10!.

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

1. 最初的foo优化成为一个紧密的循环。

2. 优化在哪里main只是直接返回结果而不是实际执行foo.

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

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

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

Update：以下是如何手动删除递归的方法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;
    }
}

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