Я получил мотивацию от вопроса оптимизации хвостового вызова Что такое оптимизация хвостового вызова ?
Итак, я решил посмотреть, как я могу сделать это на чистом C.
Итак, я написал 2 факториальные программы, 1-я, где можно применить оптимизацию хвостовых вызовов. Я называю эту функцию факта фактом (n, 1).
unsigned long long int fact(int n, int cont)
{
if(n == 0)
return cont;
else return fact(n-1, n * cont);
}
2nd — это обычная рекурсия, когда требуется несколько кадров стека.
unsigned long long int fact(int n)
{
if(n == 0)
return 1;
else return n * fact(n-1);
}
Это сборка, сгенерированная 32-битным компилятором для первого с -O2.
0x8048470 : push %ebp
0x8048471 : mov %esp,%ebp
0x8048473 : mov 0x8(%ebp),%edx
0x8048476 : mov 0xc(%ebp),%eax
0x8048479 : test %edx,%edx
0x804847b : je 0x8048488
0x804847d : lea 0x0(%esi),%esi
0x8048480 : imul %edx,%eax
0x8048483 : sub $0x1,%edx
0x8048486 : jne 0x8048480
0x8048488 : mov %eax,%edx
0x804848a : sar $0x1f,%edx
0x804848d : pop %ebp
0x804848e : ret
Это сборка, сгенерированная 32-битным компилятором для последнего с -O2.
0x8048470 : push %ebp
0x8048471 : mov %esp,%ebp
0x8048473 : push %edi
0x8048474 : push %esi
0x8048475 : push %ebx
0x8048476 : sub $0x14,%esp
0x8048479 : mov 0x8(%ebp),%eax
0x804847c : movl $0x1,-0x18(%ebp)
0x8048483 : movl $0x0,-0x14(%ebp)
0x804848a : test %eax,%eax
0x804848c : je 0x80484fc
0x804848e : mov %eax,%ecx
0x8048490 : mov %eax,%esi
0x8048492 : sar $0x1f,%ecx
0x8048495 : add $0xffffffff,%esi
0x8048498 : mov %ecx,%edi
0x804849a : mov %eax,%edx
0x804849c : adc $0xffffffff,%edi
0x804849f : sub $0x1,%eax
0x80484a2 : mov %eax,-0x18(%ebp)
0x80484a5 : movl $0x0,-0x14(%ebp)
0x80484ac : sub -0x18(%ebp),%esi
0x80484af : mov %edx,-0x20(%ebp)
0x80484b2 : sbb -0x14(%ebp),%edi
0x80484b5 : movl $0x1,-0x18(%ebp)
0x80484bc : movl $0x0,-0x14(%ebp)
0x80484c3 : mov %ecx,-0x1c(%ebp)
0x80484c6 : xchg %ax,%ax
0x80484c8 : mov -0x14(%ebp),%ecx
0x80484cb : mov -0x18(%ebp),%ebx
0x80484ce : imul -0x1c(%ebp),%ebx
0x80484d2 : imul -0x20(%ebp),%ecx
0x80484d6 : mov -0x18(%ebp),%eax
0x80484d9 : mull -0x20(%ebp)
0x80484dc : add %ebx,%ecx
0x80484de : add %ecx,%edx
0x80484e0 : addl $0xffffffff,-0x20(%ebp)
0x80484e4 : adcl $0xffffffff,-0x1c(%ebp)
0x80484e8 : mov -0x1c(%ebp),%ebx
0x80484eb : mov %eax,-0x18(%ebp)
0x80484ee : mov -0x20(%ebp),%eax
0x80484f1 : mov %edx,-0x14(%ebp)
0x80484f4 : xor %edi,%ebx
0x80484f6 : xor %esi,%eax
0x80484f8 : or %eax,%ebx
0x80484fa : jne 0x80484c8
0x80484fc : mov -0x18(%ebp),%eax
0x80484ff : mov -0x14(%ebp),%edx
0x8048502 : add $0x14,%esp
0x8048505 : pop %ebx
0x8048506 : pop %esi
0x8048507 : pop %edi
0x8048508 : pop %ebp
0x8048509 : ret
При компиляции обеих программ и просмотре сгенерированной сборки обе программы по-прежнему имеют рекурсивные вызовы. Но когда я компилирую с опцией -O2 (сборка, опубликованная выше) в первом, я вообще не вижу рекурсивных вызовов, и поэтому я думаю, что gcc выполняет оптимизацию хвостовых вызовов.
Но когда я компилирую последний с опцией -O2, он также удаляет рекурсивные вызовы и вместо этого помещает довольно большое количество ассемблерных инструкций по сравнению с тем, что происходит с первым на -O2.
Я хотел понять, что именно компилятор делает в последнем, и почему он не может преобразовать сборку, сгенерированную первым, даже с O4.