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

Question

所以我一直在看一下O3GCC 中的一些魔法(实际上我正在使用Clang进行编译,但它与GCC相同,我猜测优化器的很大一部分是从GCC转到Clang) .

考虑这个C程序:

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

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

我在WOW-ed中遇到的第一件事(在这个问题中也是如此 - /sf/answers/29034211/)是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

Blimey我想.这很有趣!完全紧密循环来做阶乘.哇.这不是尾调用优化,因为它不是尾调用.但它似乎做了类似的优化.

现在看看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可以做的一些更有趣的优化.

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,并依赖factor参数来摆脱乘法.

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

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