¿Cómo un compilador optimiza tan bien esta función factorial?

Question

Así que he estado viendo algo de la magia que es O3 en GCC (bueno, en realidad estoy compilando usando Clang, pero es lo mismo con GCC y supongo que una gran parte del optimizador fue retirado de GCC a Clang).

consideran este programa en C:

int foo(int n) { 
    if (n == 0) return 1; 
    return n * foo(n-1); 
} 

int main() { 
    return foo(10); 
} 

La primera cosa que era bastante WOW-ed al (que también era WOW-ed en en esta pregunta - https://stackoverflow.com/a/414774/1068248) era cómo int foo(int) (una función básica factorial) compila en un círculo cerrado. Este es el conjunto ARM para él:

.globl _foo 
    .align 2 
    .code 16 
    .thumb_func _foo 
_foo: 
    mov r1, r0 
    movs r0, #1 
    cbz r1, LBB0_2 
LBB0_1: 
    muls r0, r1, r0 
    subs r1, #1 
    bne LBB0_1 
LBB0_2: 
    bx lr 

Blimey, pensé. ¡Eso es bastante interesante! Bucle completamente cerrado para hacer el factorial. GUAU. No es una optimización de la cola de llamadas ya que, bueno, no es una llamada de cola. Pero parece haber hecho una optimización muy similar.

Ahora mira main:

.globl _main 
    .align 2 
    .code 16 
    .thumb_func _main 
_main: 
    movw r0, #24320 
    movt r0, #55 
    bx lr 

que acaba de soplar mi mente para ser honesto. Está pasando por alto totalmente foo y devolviendo 3628800 que es 10!.

Esto me hace comprender realmente cómo su compilador a menudo puede hacer un trabajo mucho mejor de lo que puede en la optimización de su código. Pero plantea la pregunta, ¿cómo se las arregla para hacer un buen trabajo? Así que, ¿alguien puede explicar (posiblemente mediante la vinculación con el código correspondiente) cómo funcionan las siguientes optimizaciones:

1. La optimización inicial foo para ser un bucle estrecho.

2. La optimización donde main simplemente va y devuelve el resultado directamente en lugar de ejecutar foo.

Otro efecto secundario interesante de esta pregunta sería mostrar algunas optimizaciones más interesantes que GCC/Clang puede hacer.

Answer 1

Si compila con gcc -O3 -fdump-tree-all, puede ver que el primer volcado en el que la recursión se ha convertido en un bucle es foo.c.035t.tailr1. Esto significa que la misma optimización que maneja otras llamadas de cola también maneja este caso ligeramente extendido. Recursion en el formulario de n * foo(...) o n + foo(...) no es tan difícil de manejar manualmente (ver a continuación), y dado que es posible describir exactamente cómo, el compilador puede realizar esa optimización automáticamente.

La optimización de main es mucho más simple: inline puede convertir esto en 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 1, y si todos los operandos de una multiplicación son constantes, entonces la multiplicación se puede realizar en tiempo de compilación.

Actualización: Aquí puede eliminar manualmente la recursión de foo, que se puede hacer automáticamente. No digo que este sea el método utilizado por GCC, pero es una posibilidad realista.

Primero, crea una función de ayuda.Se comporta exactamente como foo(n), excepto que sus resultados se multiplican por un parámetro adicional f.

int foo(int n) 
{ 
    return foo_helper(n, 1); 
} 

int foo_helper(int n, int f) 
{ 
    if (n == 0) return f * 1; 
    return f * n * foo(n-1); 
} 

A continuación, gire llamadas recursivas de foo en las llamadas recursivas de foo_helper, y se basan en el parámetro de factor de deshacerse de la multiplicación.

int foo(int n) 
{ 
    return foo_helper(n, 1); 
} 

int foo_helper(int n, int f) 
{ 
    if (n == 0) return f; 
    return foo_helper(n-1, f * n); 
} 

convertir esto en un bucle:

int foo(int n) 
{ 
    return foo_helper(n, 1); 
} 

int foo_helper(int n, int f) 
{ 
restart: 
    if (n == 0) return f; 
    { 
     int newn = n-1; 
     int newf = f * n; 
     n = newn; 
     f = newf; 
     goto restart; 
    } 
} 

Por último, en línea foo_helper:

int foo(int n) 
{ 
    int f = 1; 
restart: 
    if (n == 0) return f; 
    { 
     int newn = n-1; 
     int newf = f * n; 
     n = newn; 
     f = newf; 
     goto restart; 
    } 
} 

(Naturalmente, esto no es la manera más sensata para escribir manualmente la función.)