什么是gcc -O2对递归Fibonacci函数做什么？

Question

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

我有一个简单的递归整数Fibonacci函数:

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

使用Intel-syntax汇编程序编译该函数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

所以我猜调用约定是参数at [esp+4]并返回值eax.它从推动开始edi,esi然后ebx.然后它声称堆栈帧的另外16个字节,足够4个临时的int.然后edi从中读取[esp+32],这是参数.如果参数是<=1那么它跳转到L4哪个零(？)esi然后跳回到哪个只是参数的L2集合.如果参数是,那么参数被复制到并且在落入之前为零.在,它在递归计算之前将结果(n-1)设置并存储在堆栈帧中.结果被添加到,设置为,并返回到是否另有它提取的低位直至落下之前.eax=esi+ediedi>1ebxesiL3L3eax=ebx-1espfib(n-1)esiebxn-2L3ebx>1ediL2

为什么这段代码如此复杂(例如,是否有一个我已经没有看到的优化名称？)？

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

这是什么目的and edi, 1？

这是什么目的mov DWORD PTR [esp], eax？

为什么堆栈框架如此之大？

你可以将这个算法反汇编回C,以便更清楚地发生了什么吗？

我的初步印象是GCC生成了相当差的x86汇编程序.在这种情况下,相同性能的代码超过2倍(对于这两个程序,此1.6GHz Atom上的fib(40)为3.25s).那是公平的吗？

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优化.