optimization - 为什么 g++ 尾部调用没有优化，而 gcc 却可以？

Question

我想检查 g++ 是否支持尾部调用，所以我编写了这个简单的程序来检查它:http://ideone.com/hnXHv

using namespace std;

size_t st;

void PrintStackTop(const std::string &type)
{
    int stack_top;
    if(st == 0) st = (size_t) &stack_top;
    cout << "In " << type << " call version, the stack top is: " << (st - (size_t) &stack_top) << endl;
}

int TailCallFactorial(int n, int a = 1)
{
    PrintStackTop("tail");
    if(n < 2)
        return a;
    return TailCallFactorial(n - 1, n * a);
}

int NormalCallFactorial(int n)
{
    PrintStackTop("normal");
    if(n < 2)
        return 1;
    return NormalCallFactorial(n - 1) * n;
}


int main(int argc, char *argv[])
{
    st = 0;
    cout << TailCallFactorial(5) << endl;
    st = 0;
    cout << NormalCallFactorial(5) << endl;
    return 0;
}

当我正常编译它时，g++ 似乎并没有真正注意到两个版本之间的任何差异:

> g++ main.cpp -o TailCall
> ./TailCall
In tail call version, the stack top is: 0
In tail call version, the stack top is: 48
In tail call version, the stack top is: 96
In tail call version, the stack top is: 144
In tail call version, the stack top is: 192
120
In normal call version, the stack top is: 0
In normal call version, the stack top is: 48
In normal call version, the stack top is: 96
In normal call version, the stack top is: 144
In normal call version, the stack top is: 192
120

两者的堆栈差异都是48，而尾调用版本需要多一个 国际。 (为什么？)
所以我认为优化可能会很方便:

> g++ -O2 main.cpp -o TailCall
> ./TailCall
In tail call version, the stack top is: 0
In tail call version, the stack top is: 80
In tail call version, the stack top is: 160
In tail call version, the stack top is: 240
In tail call version, the stack top is: 320
120
In normal call version, the stack top is: 0
In normal call version, the stack top is: 64
In normal call version, the stack top is: 128
In normal call version, the stack top is: 192
In normal call version, the stack top is: 256
120

这两种情况下堆栈大小都会增加，虽然编译器可能认为我的 CPU 比内存慢(无论如何都不是)，但我不知道为什么一个简单的函数需要 80 个字节。 (为什么会这样？)。
尾部调用版本也比普通版本占用更多空间，如果 int 的大小为 16 字节，则完全合乎逻辑。 (不，我没有 128 位 CPU)。
现在思考编译器不进行尾部调用的原因是什么，我认为可能是异常，因为它们紧密依赖于堆栈。所以我毫无异常(exception)地尝试了:

> g++ -O2 -fno-exceptions main.cpp -o TailCall
> ./TailCall
In tail call version, the stack top is: 0
In tail call version, the stack top is: 64
In tail call version, the stack top is: 128
In tail call version, the stack top is: 192
In tail call version, the stack top is: 256
120
In normal call version, the stack top is: 0
In normal call version, the stack top is: 48
In normal call version, the stack top is: 96
In normal call version, the stack top is: 144
In normal call version, the stack top is: 192
120

这将普通版本削减回非优化堆栈大小，而优化版本多了 8 个字节。 int 仍然不是 8 个字节。
我认为在 c++ 中我错过了一些需要安排堆栈的东西，所以我尝试了 c: http://ideone.com/tJPpc
仍然没有尾部调用，但堆栈要小得多(两个版本中每帧 32 位)。 然后我尝试优化:

> gcc -O2 main.c -o TailCall
> ./TailCall
In tail call version, the stack top is: 0
In tail call version, the stack top is: 0
In tail call version, the stack top is: 0
In tail call version, the stack top is: 0
In tail call version, the stack top is: 0
120
In normal call version, the stack top is: 0
In normal call version, the stack top is: 0
In normal call version, the stack top is: 0
In normal call version, the stack top is: 0
In normal call version, the stack top is: 0
120

它不仅优化了第一个尾调用，还优化了第二个尾调用!
为什么 g++ 不进行尾部调用优化，而它在平台上显然可用？有什么办法可以强制吗？

Answer 1

因为您将临时 std::string 对象传递给 PrintStackTop(std::string) 函数。该对象分配在堆栈上，从而防止尾调用优化。

我修改了你的代码:

void PrintStackTopStr(char const*const type)
{
    int stack_top;
    if(st == 0) st = (size_t) &stack_top;
    cout << "In " << type << " call version, the stack top is: " << (st - (size_t) &stack_top) << endl;
}

int RealTailCallFactorial(int n, int a = 1)
{
    PrintStackTopStr("tail");
    if(n < 2)
        return a;
    return RealTailCallFactorial(n - 1, n * a);
}

编译为:g++ -O2 -fno-exceptions -o tailcall tailcall.cpp

现在它使用尾调用优化。如果您使用 -S 标志来生成程序集，您可以看到它的运行情况:

L39:
        imull   %ebx, %esi
        subl    $1, %ebx
L38:
        movl    $LC2, (%esp)
        call    __Z16PrintStackTopStrPKc
        cmpl    $1, %ebx
        jg      L39

您会看到内嵌为循环的递归调用 (jg L39)。