gcc -O2对递归斐波那契函数做什么？

Question

我正在学习x86汇编器以编写一个编译器。特别是，我正在使用各种简单的递归函数，并通过不同的编译器（OCaml，GCC等）提供它们以便更好地理解不同编译器生成的汇编程序的种类。

我有一个简单的递归整数斐波那契功能：

int fib(int x) { return (x < 2 ? x : fib(x-1)+fib(x-2)); } 

我的手编汇编程序是这样的：

fib: 
    cmp eax, 2 
    jl fin 
    push eax 
    dec eax 
    call fib 
    push eax 
    mov eax, [esp+4] 
    add eax, -2 
    call fib 
    add eax, [esp] 
    add esp, 8 
fin: 
    ret 

使用gcc -O2产生这种编译该函数英特尔语法汇编神秘的代码：

_fib: 
    push edi 
    push esi 
    push ebx 
    sub esp, 16 
    mov edi, DWORD PTR [esp+32] 
    cmp edi, 1 
    jle L4 
    mov ebx, edi 
    xor esi, esi 
L3: 
    lea eax, [ebx-1] 
    mov DWORD PTR [esp], eax 
    call _fib 
    sub ebx, 2 
    add esi, eax 
    cmp ebx, 1 
    jg L3 
    and edi, 1 
L2: 
    lea eax, [esi+edi] 
    add esp, 16 
    pop ebx 
    pop esi 
    pop edi 
    ret 
L4: 
    xor esi, esi 
    jmp L2 

所以我猜callin g约定为[esp+4]，返回值为eax。它开始时按edi,esi和ebx。然后它声称另一个16字节的堆栈帧，足够4个临时整数。然后从[esp+32]读取edi，这是参数。如果参数是<=1那么它跳转到L4，其在返回到L2之前将（？）esi清零，其设置eax=esi+edi，其仅为参数edi。如果参数是>1那么参数将被复制到ebx中，并且在落入L3之前为零esi。在L3中，它设置eax=ebx-1，并在递归计算fib(n-1)之前将结果（n-1）存储在堆栈帧中的esp。将结果添加到esi,ebx设置为n-2，并且如果返回L3，则返回ebx>1，否则在下降到L2之前提取edi的较低位。

为什么这个代码如此复杂（例如，有没有一个名称为已经完成，我没有看到？）？

递归调用fib(n-2)似乎已被替换为在esi中积累的循环，但该调用不在尾部位置，所以这是如何完成的？

and edi, 1的用途是什么？

mov DWORD PTR [esp], eax的用途是什么？

为什么堆栈帧如此之大？

您可以将此算法反汇编回C以使其更清晰吗？

我的初步印象是GCC生成很差的x86汇编。在这种情况下，超过2 ×更多性能相同的代码（这两个程序在1.6GHz Atom上fib 3.40s（对于fib（40））。这是公平的吗？

Answer 1

除了上述意见，注意递归已被展开成一个尾调用替换：

return x < 2 ? x : fib(x - 2) + fib(x - 1); 

有：

if ((xprime = x) < 2) { 
    acc = 0; 
} else { 
    /* at this point we know x >= 2 */ 
    acc = 0; /* start with 0 */ 
    while (x > 1) { 
     acc += fib(x - 1); /* add fib(x-1) */ 
     x -= 2; /* now we'll add fib(x-2) */ 
    } 
    /* so at this point we know either x==1 or x==0 */ 
    xprime = x == 1 ? 1 : 0; /* ie, x & 1 */ 
} 
return xprime + acc; 

我怀疑这相当棘手的循环出现从多个优化步骤来看，并不是因为gcc 2.3（现在它们完全不同），我已经摆脱了gcc优化。

Answer 2

很简单，fib(x-2)等于fib(x-3) + fib(x-4)，fib(x-4)等于fib(x-5) + fib(x-6)等，让fib(x)被计算为fib(x-1) + fib(x-3) + fib(x-5) + ... + fib(x&1)（fib(x&1)等于x&1）即GCC有内联调用fib(x-2)，这是一个相当聪明的事做一个递归函数。

Answer 3

第一部分是确保根据调用约定保留的寄存器不被丢弃。我想这里使用的调用约定是cdecl。

_fib: 
    push edi 
    push esi 
    push ebx 
    sub esp, 16 

DWORD PTR[esp+32]是你x：

mov edi, DWORD PTR [esp+32] 
    cmp edi, 1 
    jle L4 

如果x小于或等于1（这相当于您x < 2），然后去L4是：

L4: 
    xor esi, esi 
    jmp L2 

这清零esi和分支到L2：

L2: 
    lea eax, [esi+edi] 
    add esp, 16 
    pop ebx 
    pop esi 
    pop edi 
    ret 

这设置eax（返回值）esi+edi。由于esi已为0，所以edi仅在0和1的情况下加载。这对应于x < 2 ? x。

现在我们来看看情况时x不< 2：

mov ebx, edi 
    xor esi, esi 
L3: 
    lea eax, [ebx-1] 
    mov DWORD PTR [esp], eax 
    call _fib 

首先，x被复制到ebx，然后esi归零。

接下来，eax设置为x - 1。这个值被移动到堆栈顶部并调用_fib。这对应于fib(x-1)。

sub ebx, 2 
    add esi, eax 

这减去2从ebx（x）。然后eax（从_fib呼叫的返回值被添加到esi，之前被设置为0）。因此esi现在保存fib(x-1)的结果。

cmp ebx, 1 
    jg L3 
    and edi, 1 

ebx与1进行比较。如果它大于1，则我们返回到L3。否则（它是0或1的情况），我们执行and edi, 1并落入L2（我们已经分析了此前已经做过的事情）。 and edi, 1相当于在x上执行%2。

从一个高的水平，这是代码做什么：

• 设置堆栈帧并保存寄存器
• 如果x < 2，然后返回x。
• 保持呼叫并求和fib(x-...)，直到x小于2.在这种情况下，通过x < 2的情况。

优化是GCC解除了其中x >= 2通过循环而不是递归执行它们的情况。