gcc 编译双递归函数时可疑的程序集膨胀

ie3xauqp  于 2023-03-02  发布在  其他
关注(0)|答案(1)|浏览(72)

假设有一个递归函数foo(),类似于斐波那契数列:

constexpr inline int foo(const int i)
{
    if(i == 0) 
        return 1;
    return foo(i - 1) + foo(i - 2);
}

int main(int argc, const char* argv[])
{
    const int ret = foo(argc);
    return ret;
}

然后在https://gcc.godbolt.org/z/fETb6Px33to上使用GCC-Os -std=c++2b -fno-exceptions等不同的优化级别下编译,我想知道为什么O2/O3版本看起来比O1/Os版本大,就像怪兽哥斯拉一样。显然,一些关键的优化触发了二进制大小的膨胀,也许O3试图以大小为代价提高运行时的执行速度。
O0

foo(int):
        push    rbp
        mov     rbp, rsp
        push    rbx
        sub     rsp, 24
        mov     DWORD PTR [rbp-20], edi
        cmp     DWORD PTR [rbp-20], 0
        jne     .L2
        mov     eax, 1
        jmp     .L3
.L2:
        mov     eax, DWORD PTR [rbp-20]
        sub     eax, 1
        mov     edi, eax
        call    foo(int)
        mov     ebx, eax
        mov     eax, DWORD PTR [rbp-20]
        sub     eax, 2
        mov     edi, eax
        call    foo(int)
        add     eax, ebx
.L3:
        mov     rbx, QWORD PTR [rbp-8]
        leave
        ret
main:
        push    rbp
        mov     rbp, rsp
        sub     rsp, 32
        mov     DWORD PTR [rbp-20], edi
        mov     QWORD PTR [rbp-32], rsi
        mov     eax, DWORD PTR [rbp-20]
        mov     edi, eax
        call    foo(int)
        mov     DWORD PTR [rbp-4], eax
        mov     eax, DWORD PTR [rbp-4]
        leave
        ret

O3

foo(int):
        test    edi, edi
        je      .L44
        push    r15
        push    r14
        xor     r14d, r14d
        push    r13
        push    r12
        lea     r12d, [rdi-1]
        push    rbp
        mov     ebp, r12d
        push    rbx
        sub     rsp, 56
.L7:
        test    ebp, ebp
        je      .L45
.L3:
        lea     r13d, [rbp-1]
        xor     ebx, ebx
        mov     eax, r14d
        mov     r15d, ebp
.L10:

        lea     ebx, [r15-1]
 .... // much much more to follow

Os

foo(int):
        push    rbp
        xor     ebp, ebp
        push    rbx
        mov     ebx, edi
        push    rcx
.L3:
        test    ebx, ebx
        je      .L5
        lea     edi, [rbx-1]
        sub     ebx, 2
        call    foo(int)
        add     ebp, eax
        jmp     .L3
.L5:
        lea     eax, [rbp+1]
        pop     rdx
        pop     rbx
        pop     rbp
        ret
main:
        jmp     foo(int)
woobm2wo

woobm2wo1#

-O3更改了代码大小与猜测“速度”启发式的设置/阈值,使得GCC比-O2更愿意内联。
使用GCC12.2 -O3为代码使用Godbolt编译器资源管理器的树转储窗格,看起来“内联”GCC优化通道是真正膨胀其中间表示(GIMPLE)大小的通道。
GCC根据GIMPLE进行优化,GIMPLE是程序逻辑的SSA表示。树转储选项打印优化过程决定要做什么的一些状态信息,以及程序逻辑当前状态的C表示,还有一些额外的局部变量来表示发明的临时变量。在inlining过程之后,有很多局部变量和代码。而在此之前,代码并不比原始源代码多多少。
inlining状态信息包括一些成本模型评估(代码大小与速度),还包括类似下面这样的内容,这些内容可以确切地确认它正在做什么:

Performing recursive inlining on constexpr int foo(int)/0

GCC会尽力将递归转换为迭代,但是这个函数是双递归的,所以它只能对其中一个递归进行转换。(它不够聪明,无法将其从O(Fib(n))时间优化为O(n)次,即使告诉GCC它是输入的纯函数,不阅读任何全局状态(__attribute__((const)))没有帮助。更改基本情况以捕获i<=1没有帮助。您的版本将始终导致无限递归,因为一个调用获得i==0,另一个获得i==-1,如果您不首先溢出堆栈,最终导致INT_MIN-2的UB。但显然这并不是阻止GCC优化的原因。)
总之,GCC可以把它变成一个函数,在一个循环中调用它自己,而不是双递归的。它递归地内联到那个循环中,使循环体变大。但是对于相同的n,执行的call/ret更少。
一个相关的问题是,对于较大的n(如10 k左右,Fib(n)肯定会溢出,因此首选unsigned i),这是否最终运行得更快,即,这种优化是否潜在有用,或者GCC是否只是白白浪费了一堆代码。
显然,如果你想快速计算Fib(n),一开始就不会写这个源代码,但是双递归函数对于遍历二叉树之类的事情来说是很正常的,不过这段代码可以很好地用来看看GCC是如何处理双递归函数的。

相关问题