gcc - 编译器如何优化这个阶乘函数？

Question

所以我一直在研究 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)是如何 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! .

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

初始foo优化是一个紧密的循环。

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

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

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

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