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

В дополнение к комментариям выше обратите внимание, что рекурсия была развернута в хвостовой вызов путем замены:

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 примерно с gcc 2.3 (теперь все внутри совсем другое!).

Проще говоря, 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), что довольно умно для рекурсивной функции.

Эта первая часть гарантирует, что регистры, которые должны быть сохранены в соответствии с соглашением о вызовах, не удаляются. Я предполагаю, что здесь используется соглашение о вызовах 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 эквивалентно выполнению %2 на x.

Вот что делает код на высоком уровне:

• Устанавливает стековый фрейм и сохраняет регистры
• Если x < 2, вернуть x.
• Продолжайте набирать и суммировать fib(x-...), пока x не станет меньше 2. В этом случае переходите к случаю x < 2.

Оптимизация состоит в том, что GCC разворачивает случаи, когда x >= 2, выполняя их в цикле, а не рекурсивно.