mi sono motivati dalla chiamata coda domanda ottimizzazione What Is Tail Call Optimization?ottimizzazioni di compilatore in un programma ricorsivo
Così, ho deciso di vedere come posso farlo in pianura C.
Così, ho scritto i 2 programmi fattoriali , 1 ° luogo in cui è possibile applicare l'ottimizzazione della chiamata di coda. Io chiamo questa funzione di fatto come fatto (n, 1).
unsigned long long int fact(int n, int cont)
{
if(n == 0)
return cont;
else return fact(n-1, n * cont);
}
La seconda è la normale ricorsione in cui sono necessari più frame di stack.
unsigned long long int fact(int n)
{
if(n == 0)
return 1;
else return n * fact(n-1);
}
Questo è il gruppo generato da un compilatore 32 bit per il primo 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
Questo è il gruppo generato da un compilatore a 32 bit per secondo 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 entrambi i programmi e guardando l'assieme generato, entrambi i programmi hanno ancora chiamate ricorsive. Ma quando compilo con l'opzione -O2 (assembly pubblicato sopra) nel primo caso, non vedo affatto chiamate ricorsive e quindi penso che gcc faccia roba per ottimizzare le chiamate.
Ma quando compilo quest'ultimo con l'opzione -O2, rimuove anche le chiamate ricorsive e invece mette un numero piuttosto elevato di istruzioni di assemblaggio rispetto a quello che succede all'ex su -O2.
Volevo capire con precisione cosa fa il compilatore in quest'ultimo e perché non potrebbe trasformarsi nell'assembly generato da ex anche con O4.
È necessario includere l'assembly generato nella domanda (le parti pertinenti), che potrebbe aiutare i rispondenti a commentare ciò che sta accadendo. –