Что gcc -O2 делает с рекурсивной функцией Фибоначчи?

Я изучаю ассемблер 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

Компиляция этой функции в Intel-синтаксический ассемблер с использованием 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

Итак, я предполагаю, что соглашение о вызовах - это аргумент в [esp+4]и возвращаемое значение в eax.Он начинается с нажатия edi, esiи ebx. Затем он требует еще 16 байтов для кадра стека, что достаточно для 4 временных целых чисел. Затем ediчитается из [esp+32], что является аргументом. Если аргумент равен <=1, то выполняется переход к L4, который обнуляет (?) esiперед возвратом к L2, который устанавливает eax=esi+ediкоторый является просто аргументом edi. Если аргумент был >1, то аргумент копируется в ebxи обнуляется esiперед попаданием в L3. В L3он устанавливает eax=ebx-1и сохраняет результат (n-1) в espв кадре стека перед рекурсивным вычислением выдумка(n-1). Результат добавляется к esi, ebxустанавливается в n-2и возвращается к L3, если ebx> 1, в противном случае он извлекает младший бит из ediперед переходом к L2.

Почему этот код такой запутанный (например,есть ли название выполненной оптимизации, которую я не вижу?)?

Рекурсивные вызовы fib(n-2), по-видимому, были заменены циклом, накапливающимся в esi, но этот вызов не был в хвостовой позиции, так как же это было сделано?

Какова цель и edi, 1?

Какова цель mov DWORD PTR [esp], eax?

Почему кадр стека такой большой?

Можете ли вы разобрать этот алгоритм обратно на C, чтобы было понятнее, что происходит?

Мое предварительное впечатление, что GCC генерирует довольно плохой ассемблер x86. В этом случае более чем в 2 раза больше кода для одинаковой производительности (3,25 с для fib(40) на этом 1,6 ГГц Atom для обеих программ). Это честно?