Je suis tombé sur un exemple de code qui contenait une fonction factorielle récursive qui n'était pas le centre du propos, mais mon coté expert CPC méprisant n'a pas pu s'empêcher de penser "C'est nul, c'est pas récursif terminal !" Mais est-ce vraiment le cas ? Je teste avec compiler explorer le code suivant :
Code:
int fact1(int n)
{
return n == 0 ? 1 : n*fact1(n-1);
}
int fact2(int n, int r = 1)
{
if (n == 0)
return r;
else
return fact2(n-1, r*n);
}
En me disant que fact1 va provoquer plein d'appels récursifs inutiles, alors que fact2 va pouvoir profiter de l'optimisation de l'appel terminal et se transformer en boucle.
Avec gcc (trunk) option -O2 :
Code:
fact1(int):
mov eax, 1
test edi, edi
je .L4
.L3:
imul eax, edi
sub edi, 1
jne .L3
ret
.L4:
ret
fact2(int, int):
mov eax, esi
test edi, edi
je .L11
.L8:
imul eax, edi
sub edi, 1
jne .L8
.L11:
ret
Ah ben non, c'est pareil (en fait fact1 est même un peu mieux puisqu'il n'y a pas le second paramètre à passer).
Avec MSVC (19.27) option /O2
Code:
n$ = 48
int fact1(int) PROC ; fact1, COMDAT
$LN6:
push rbx
sub rsp, 32 ; 00000020H
mov ebx, ecx
test ecx, ecx
jne SHORT $LN3@fact1
lea eax, QWORD PTR [rcx+1]
add rsp, 32 ; 00000020H
pop rbx
ret 0
$LN3@fact1:
dec ecx
call int fact1(int) ; fact1
imul eax, ebx
add rsp, 32 ; 00000020H
pop rbx
ret 0
int fact1(int) ENDP ; fact1
n$ = 8
r$ = 16
int fact2(int,int) PROC ; fact2, COMDAT
test ecx, ecx
je SHORT $LN12@fact2
$LL5@fact2:
imul edx, ecx
sub ecx, 1
jne SHORT $LL5@fact2
$LN12@fact2:
mov eax, edx
ret 0
int fact2(int,int) ENDP ; fact2
Cette fois fact1 n'est pas optimisé comme je m'y attendais.
Je vous épargne clang, qui génère un énorme charabia d'instructions SSE ou équivalentes. Dans une branche (n < 8), c'est similaire à GCC, dans l'autre avec les instructions SSE je ne comprends pas ce qu'il fait mais je n'ai pas vu de "call" non plus.
Y a-t-il des experts en optimisation de compilateurs par ici ? Je me demande ce qui permet à GCC/clang d'optimiser fact1 et dans quelle limite on peut compter dessus pour optimiser des récursions non-terminales.