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