为什么gcc不能进行g ++尾调用优化? [英] Why isn't g++ tail call optimizing while gcc is?

问题描述

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

I wanted to check whether g++ supports tail calling so I wrote this simple program to check it: 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 ++似乎并没有真正注意到两个版本之间的任何区别:

When I compiled it normally it seems g++ doesn't really notice any difference between the two versions:

> 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，而尾部调用版本还需要一个 诠释(为什么?)
所以我认为优化可能很方便:

The stack difference is 48 in both of them, while the tail call version needs one more int. (Why?)
So I thought optimization might be handy:

> 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).
现在考虑编译器没有进行尾调用的原因，我认为这可能是异常，因为它们紧密依赖堆栈.所以我没有例外地尝试过:

The stack size increased in both cases, and while the compiler might think my CPU is slower than my memory (which its not anyway), I don't know why 80 bytes are necessary for a simple function. (Why is it?).
There tail call version also takes more space than the normal version, and its completely logical if an int has the size of 16 bytes. (no, I don't own a 128 bit CPU).
Now thinking what reason the compiler has not to tail call, I thought it might be exceptions, because they depend on the stack tightly. So I tried without exceptions:

> 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位). 然后我尝试了优化:

Which cut the normal version back to non-optimized stack size, while the optimized one has 8 bytes over it. still an int is not 8 bytes.
I thought there is something I missed in c++ that needs the stack arranged so I tried c: http://ideone.com/tJPpc
Still no tail calling, but the stack is much smaller (32 bit each frame in both version). Then I tried with optimization:

> 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 ++在平台上明显可用时却不执行尾部调用优化?有什么办法强迫它吗?

Not only it tail call optimized the first, it also tail call optimized the second!
Why doesn't g++ do tail call optimization while its clearly available in the platform? is there any way to force it?

推荐答案

因为您要将一个临时std :: string对象传递给PrintStackTop(std :: string)函数.该对象分配在堆栈上，因此无法进行尾部调用优化.

Because you're passing a temporary std::string object to the PrintStackTop(std::string) function. This object is allocated on the stack and thus prevent the tail call optimization.

我修改了您的代码:

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

Compile with: g++ -O2 -fno-exceptions -o tailcall tailcall.cpp

现在它使用了尾部呼叫优化.如果使用-S标志生成程序集，则可以看到它的作用:

And it now uses the tail call optimisation. You can see it in action if you use the -S flag to produce the assembly:

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

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

You see the recursive call inlined as a loop (jg L39).

这篇关于为什么gcc不能进行g ++尾调用优化?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！