optimizaciones de compilador en un programa recursivo

Question

me motivados de llamada de cola pregunta optimización What Is Tail Call Optimization?

Por lo tanto, decidí ver cómo puedo hacer de manera clara C.

Así, escribí los 2 programas factoriales , 1º donde se puede aplicar la optimización de la cola de cola. Llamo a esto hecho función como hecho (n, 1).

unsigned long long int fact(int n, int cont) 
{ 
     if(n == 0) 
      return cont; 

     else return fact(n-1, n * cont); 
} 

La segunda es la recursión normal en la que se requieren varios fotogramas de pila.

unsigned long long int fact(int n) 
{ 
    if(n == 0) 
     return 1; 

    else return n * fact(n-1); 
} 

Este es el conjunto generado por un compilador de 32 bits para el primero con -O2

0x8048470 <fact>: push %ebp 
0x8048471 <fact+1>: mov %esp,%ebp 
0x8048473 <fact+3>: mov 0x8(%ebp),%edx 
0x8048476 <fact+6>: mov 0xc(%ebp),%eax 
0x8048479 <fact+9>: test %edx,%edx 
0x804847b <fact+11>: je  0x8048488 <fact+24> 
0x804847d <fact+13>: lea 0x0(%esi),%esi 
0x8048480 <fact+16>: imul %edx,%eax 
0x8048483 <fact+19>: sub $0x1,%edx 
0x8048486 <fact+22>: jne 0x8048480 <fact+16> 
0x8048488 <fact+24>: mov %eax,%edx 
0x804848a <fact+26>: sar $0x1f,%edx 
0x804848d <fact+29>: pop %ebp 
0x804848e <fact+30>: ret  

Este es el conjunto generado por un compilador de 32 bits para este último con -O2.

0x8048470 <fact>: push %ebp 
0x8048471 <fact+1>: mov %esp,%ebp 
0x8048473 <fact+3>: push %edi 
0x8048474 <fact+4>: push %esi 
0x8048475 <fact+5>: push %ebx 
0x8048476 <fact+6>: sub $0x14,%esp 
0x8048479 <fact+9>: mov 0x8(%ebp),%eax 
0x804847c <fact+12>: movl $0x1,-0x18(%ebp) 
0x8048483 <fact+19>: movl $0x0,-0x14(%ebp) 
0x804848a <fact+26>: test %eax,%eax 
0x804848c <fact+28>: je  0x80484fc <fact+140> 
0x804848e <fact+30>: mov %eax,%ecx 
0x8048490 <fact+32>: mov %eax,%esi 
0x8048492 <fact+34>: sar $0x1f,%ecx 
0x8048495 <fact+37>: add $0xffffffff,%esi 
0x8048498 <fact+40>: mov %ecx,%edi 
0x804849a <fact+42>: mov %eax,%edx 
0x804849c <fact+44>: adc $0xffffffff,%edi 
0x804849f <fact+47>: sub $0x1,%eax 
0x80484a2 <fact+50>: mov %eax,-0x18(%ebp) 
0x80484a5 <fact+53>: movl $0x0,-0x14(%ebp) 
0x80484ac <fact+60>: sub -0x18(%ebp),%esi 
0x80484af <fact+63>: mov %edx,-0x20(%ebp) 
0x80484b2 <fact+66>: sbb -0x14(%ebp),%edi 
0x80484b5 <fact+69>: movl $0x1,-0x18(%ebp) 
0x80484bc <fact+76>: movl $0x0,-0x14(%ebp) 
0x80484c3 <fact+83>: mov %ecx,-0x1c(%ebp) 
0x80484c6 <fact+86>: xchg %ax,%ax 
0x80484c8 <fact+88>: mov -0x14(%ebp),%ecx 
0x80484cb <fact+91>: mov -0x18(%ebp),%ebx 
0x80484ce <fact+94>: imul -0x1c(%ebp),%ebx 
0x80484d2 <fact+98>: imul -0x20(%ebp),%ecx 
0x80484d6 <fact+102>: mov -0x18(%ebp),%eax 
0x80484d9 <fact+105>: mull -0x20(%ebp) 
0x80484dc <fact+108>: add %ebx,%ecx 
0x80484de <fact+110>: add %ecx,%edx 
0x80484e0 <fact+112>: addl $0xffffffff,-0x20(%ebp) 
0x80484e4 <fact+116>: adcl $0xffffffff,-0x1c(%ebp) 
0x80484e8 <fact+120>: mov -0x1c(%ebp),%ebx 
0x80484eb <fact+123>: mov %eax,-0x18(%ebp) 
0x80484ee <fact+126>: mov -0x20(%ebp),%eax 
0x80484f1 <fact+129>: mov %edx,-0x14(%ebp) 
0x80484f4 <fact+132>: xor %edi,%ebx 
0x80484f6 <fact+134>: xor %esi,%eax 
0x80484f8 <fact+136>: or  %eax,%ebx 
0x80484fa <fact+138>: jne 0x80484c8 <fact+88> 
0x80484fc <fact+140>: mov -0x18(%ebp),%eax 
0x80484ff <fact+143>: mov -0x14(%ebp),%edx 
0x8048502 <fact+146>: add $0x14,%esp 
0x8048505 <fact+149>: pop %ebx 
0x8048506 <fact+150>: pop %esi 
0x8048507 <fact+151>: pop %edi 
0x8048508 <fact+152>: pop %ebp 
0x8048509 <fact+153>: ret  

Compilando ambos programas y mirando el conjunto generado, ambos programas aún tienen llamadas recursivas. Pero, cuando compilo con la opción -O2 (ensamblado publicado arriba) en el primero, no veo llamadas recursivas y creo que gcc hace todo lo posible por optimizar las llamadas.

Pero cuando compilo este último con la opción -O2, también elimina las llamadas recursivas y en su lugar coloca un número bastante grande de instrucciones de ensamblaje en comparación con lo que sucede con el anterior en -O2.

Quería entender con precisión qué hace el compilador en este último y por qué no podría transformarse en el ensamblado generado por el anterior incluso con O4.

Answer 1

El programa 2 no hace long long cálculos, progtlram 1 no.

Answer 2

La diferencia es que la primera versión usa una variable int para el cálculo, que luego se extiende a unsigned long long al final, mientras que la última usa un unsigned long long hasta el final.

Answer 3

El compilador parece haber optimizado las llamadas recursivas en bucles. Tenga en cuenta que su código C solo tiene ramas hacia adelante (if-then-else), pero el ensamblador tiene ramas hacia atrás (bucles).

Si realmente desea ver una optimización de la cola de llamada en acción, haga que invoque una función diferente. Por supuesto, eso no es recursividad, pero el compilador es demasiado inteligente para pequeños casos de prueba como este.