Récursions dans AArch64
2026-07-23T17:57:11+08:00
Schémas de base
Commençons par un programme C qui contient une fonction de calcul simple de Fibonacci.
#include <stdint.h>
#include <stdio.h>
uint64_t fibonacci(uint32_t index)
{
if (index <= 1) return 1;
else return fibonacci(index - 1) + fibonacci(index - 2);
}
int main()
{
uint32_t i;
scanf("%u", &i);
printf("%lu", fibonacci(i));
return 0;
}
Compilez-le :
$ gcc fibo.c -o fibo0
Par défaut, GCC n’effectue aucune optimisation du tout. Ouvrez votre splendide iaito et allez à la fonction main :
64: int main (int argc, char **argv, char **envp);
afv: vars(3:sp[0x4..0x20])
0x00000878 stp x29, x30, [var_20h]!
0x0000087c mov x29, sp
0x00000880 add x0, sp, 0x1c
0x00000884 mov x1, x0
0x00000888 adrp x0, 0
0x0000088c add x0, x0, 0x8d8
0x00000890 bl sym.imp.__isoc23_scanf
0x00000894 ldr w0, [var_1ch]
0x00000898 bl sym.fibonacci
0x0000089c mov x1, x0
0x000008a0 adrp x0, 0
0x000008a4 add x0, x0, 0x8e0 ; const char *format
0x000008a8 bl sym.imp.printf ; int printf(const char *format)
0x000008ac mov w0, 0
0x000008b0 ldp x29, x30, [sp], 0x20
0x000008b4 ret
Ici, vous pouvez voir un appel à sym.fibonacci à 0x0000898. Ouvrez cette fonction et regardez le graphe :
Vous verrez que sym.fibonacci s’appelle elle-même à 0x0000854 et 0x0000864, respectivement.
Si vous avez supprimé les symboles, vous ne verrez pas sym.fibonacci, mais vous verrez quand même quelque chose comme bl fcn.00000828 ici. Dans tous les cas, les schémas dans lesquels une fonction s’appelle elle-même indiquent une récursion.
Optimisation
Remplaçons la fonction de Fibonacci par une fonction factorielle :
#include <stdint.h>
#include <stdio.h>
uint64_t fact(uint32_t index)
{
if (index <= 1) return 1;
else return index * fact(index - 1);
}
int main()
{
uint32_t i;
scanf("%u", &i);
printf("%lu", fact(i));
return 0;
}
Compilez-le :
$ gcc fact.c -o fact0
L’ouvrir dans iaito vous donne une fonction main qui appelle sym.fact :
64: int main (int argc, char **argv, char **envp);
afv: vars(3:sp[0x4..0x20])
0x0000086c stp x29, x30, [var_20h]!
0x00000870 mov x29, sp
0x00000874 add x0, sp, 0x1c
0x00000878 mov x1, x0
0x0000087c adrp x0, 0
0x00000880 add x0, x0, 0x8d0 ; "%u"
0x00000884 bl sym.imp.__isoc23_scanf
0x00000888 ldr w0, [var_1ch]
0x0000088c bl sym.fact ; sym.fact(0x0)
0x00000890 mov x1, x0
0x00000894 adrp x0, 0
0x00000898 add x0, x0, 0x8d8 ; const char *format ; "%lu"
0x0000089c bl sym.imp.printf ; int printf(const char *format)
; int printf("%lu")
0x000008a0 mov w0, 0
0x000008a4 ldp x29, x30, [sp], 0x20
0x000008a8 ret
La désassemblage de la fonction appelée sym.fact est le suivant :
68: fact (int64_t arg1);
`- args(x0) vars(4:sp[0x4..0x30])
0x00000828 stp x29, x30, [var_30h]!
0x0000082c mov x29, sp
0x00000830 str x19, [var_10h]
0x00000834 str w0, [var_2ch] ; arg1
0x00000838 ldr w0, [var_2ch]
0x0000083c cmp w0, 1
0x00000840 b.hi 0x84c ; unlikely
0x00000844 mov x0, 1
0x00000848 b 0x860
0x0000084c ldr w19, [var_2ch]
0x00000850 ldr w0, [var_2ch]
0x00000854 sub w0, w0, 1
0x00000858 bl sym.fact ; sym.fact(-1)
0x0000085c mul x0, x19, x0
0x00000860 ldr x19, [var_10h]
0x00000864 ldp x29, x30, [sp], 0x30
0x00000868 ret
et aussi son graphe :
Alors, que se passe-t-il si l’on active l’optimisation ? Essayons :
$ gcc fact.c -O2 -o fact2
Ouvrez-le dans iaito et inspectez la fonction main. Vous verrez :
L’instruction qui appelait sym.fact a disparu. À la place, vous voyez une boucle à l’intérieur de la fonction main qui effectue le travail.
Retournez au code C contenant notre fonction de Fibonacci, compilez-le avec l’optimisation activée, puis inspectez la fonction main :
;-- section..text:
60: int main (int argc, char **argv, char **envp);
afv: vars(3:sp[0x4..0x20])
0x00000700 stp x29, x30, [var_20h]! ; [12] -r-x section size 1176 named .text
0x00000704 adrp x0, 0
0x00000708 add x0, x0, 0xbb8 ; "%u"
0x0000070c mov x29, sp
0x00000710 add x1, sp, 0x1c
0x00000714 bl sym.imp.__isoc23_scanf
0x00000718 ldr w0, [var_1ch]
0x0000071c bl sym.fibonacci ; sym.fibonacci(0x0, 0x177ffc, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0)
0x00000720 mov x1, x0
0x00000724 adrp x0, 0
0x00000728 add x0, x0, 0xbc0 ; const char *format ; "%lu"
0x0000072c bl sym.imp.printf ; int printf(const char *format)
0x00000730 mov w0, 0
0x00000734 ldp x29, x30, [sp], 0x20
0x00000738 ret
调用 sym.fibonacci 的指令仍然存在。
打开 sym.fibonacci 的反汇编，你会欣赏到编译器的巧妙：
792: fibonacci (uint32_t arg1, int64_t arg_60h, int64_t arg_70h, int64_t arg_80h, int64_t arg_88h, int64_t arg_90h, int64_t arg_98h, int64_t arg_a0h, int64_t arg_a8h);
`- args(x0, sp[0x60..0xa8]) vars(27:sp[0x4..0xb0])
0x00000880 sub w6, w0, 1 ; arg1
0x00000884 mov x1, 0
0x00000888 cmp w0, 1 ; arg1
0x0000088c b.ls 0xb68 ; likely
0x00000890 cmp w6, 1
0x00000894 b.eq 0xb70 ; unlikely
0x00000898 sub w10, w6, 1
0x0000089c mov x3, 0
0x000008a0 mov w7, w10
0x000008a4 cmp w7, 1
0x000008a8 b.eq 0xb4c ; unlikely
0x000008ac sub w11, w7, 1
0x000008b0 mov x4, 0
0x000008b4 mov w8, w11
0x000008b8 cmp w8, 1
0x000008bc b.eq 0xb30 ; unlikely
0x000008c0 sub w12, w8, 1
0x000008c4 mov x5, 0
0x000008c8 mov w9, w12
0x000008cc cmp w12, 1
0x000008d0 b.eq 0xa98 ; unlikely
0x000008d4 stp x29, x30, [var_b0h]!
0x000008d8 mov x29, sp
0x000008dc stp x19, x20, [var_10h]
0x000008e0 stp x21, x22, [var_20h]
0x000008e4 stp x23, x24, [var_30h]
0x000008e8 stp x25, x26, [var_40h]
0x000008ec stp x27, x28, [var_50h]
0x000008f0 sub w13, w9, 1
0x000008f4 mov w25, w13
0x000008f8 mov x20, 0
0x000008fc cmp w25, 1
0x00000900 b.eq 0xa90 ; unlikely
0x00000904 sub w27, w25, 1
0x00000908 mov x19, 0
0x0000090c mov w26, w27
0x00000910 cmp w26, 1
0x00000914 b.eq 0x9fc ; unlikely
0x00000918 sub w28, w26, 1
0x0000091c mov x22, 0
0x00000920 mov w2, w28
0x00000924 cmp w2, 1
0x00000928 b.eq 0x9dc ; unlikely
0x0000092c sub w15, w2, 1
0x00000930 mov x21, 0
0x00000934 mov w24, w15
0x00000938 cmp w24, 1
0x0000093c b.eq 0x9bc ; unlikely
0x00000940 mov w23, w24
0x00000944 mov x14, 0
0x00000948 sub w0, w23, 1
0x0000094c stp x1, x3, [arg_60h]
0x00000950 sub w23, w23, 2
0x00000954 stp x4, x5, [arg_70h]
0x00000958 stp w6, w10, [arg_80h]
0x0000095c str x14, [arg_88h]
0x00000960 stp w7, w11, [arg_90h]
0x00000964 stp w8, w12, [arg_98h]
0x00000968 stp w9, w13, [arg_a0h]
0x0000096c stp w2, w15, [arg_a8h]
0x00000970 bl sym.fibonacci ; sym.fibonacci(0x1d001efffffff8, 0x0, 0xfffffffa, 0x0, 0x0, 0x0, 0x0, -1, 0x0)
0x00000974 ldr x14, [arg_88h]
0x00000978 cmp w23, 1
0x0000097c ldp x1, x3, [arg_60h]
0x00000980 add x14, x14, x0
0x00000984 ldp x4, x5, [arg_70h]
0x00000988 ldp w6, w10, [arg_80h]
0x0000098c ldp w7, w11, [arg_90h]
0x00000990 ldp w8, w12, [arg_98h]
0x00000994 ldp w9, w13, [arg_a0h]
0x00000998 ldp w2, w15, [arg_a8h]
0x0000099c b.hi 0x948 ; likely
0x000009a0 add x21, x21, 1
0x000009a4 add x21, x21, x14
0x000009a8 cmp w24, 2
0x000009ac b.eq 0x9c0 ; unlikely
0x000009b0 sub w24, w24, 2
0x000009b4 cmp w24, 1
0x000009b8 b.ne 0x940 ; likely
0x000009bc add x21, x21, 1
0x000009c0 add x22, x22, 1
0x000009c4 sub w2, w2, 2
0x000009c8 add x22, x22, x21
0x000009cc cmp w15, 1
0x000009d0 b.eq 0x9e0 ; unlikely
0x000009d4 cmp w2, 1
0x000009d8 b.ne 0x92c ; likely
0x000009dc add x22, x22, 1
0x000009e0 add x19, x19, 1
0x000009e4 sub w26, w26, 2
0x000009e8 add x19, x19, x22
0x000009ec cmp w28, 1
0x000009f0 b.eq 0xa00 ; unlikely
0x000009f4 cmp w26, 1
0x000009f8 b.ne 0x918 ; likely
0x000009fc add x19, x19, 1
0x00000a00 add x20, x20, 1
0x00000a04 sub w25, w25, 2
0x00000a08 add x20, x20, x19
0x00000a0c cmp w27, 1
0x00000a10 b.ne 0x8fc ; likely
0x00000a14 add x5, x5, 1
0x00000a18 sub w9, w9, 2
0x00000a1c add x5, x5, x20
0x00000a20 cmp w13, 1
0x00000a24 b.eq 0xa34 ; unlikely
0x00000a28 cmp w9, 1
0x00000a2c b.ne 0x8f0 ; likely
0x00000a30 add x5, x5, 1
0x00000a34 add x4, x4, 1
0x00000a38 sub w8, w8, 2
0x00000a3c add x4, x4, x5
0x00000a40 cmp w12, 1
0x00000a44 b.eq 0xa64 ; unlikely
0x00000a48 cmp w8, 1
0x00000a4c b.eq 0xa60 ; unlikely
0x00000a50 sub w12, w8, 1
0x00000a54 mov x5, 0
0x00000a58 mov w9, w12
0x00000a5c b 0xa28
0x00000a60 add x4, x4, 1
0x00000a64 add x3, x3, 1
0x00000a68 sub w7, w7, 2
0x00000a6c add x3, x3, x4
0x00000a70 cmp w11, 1
0x00000a74 b.eq 0xae4 ; unlikely
0x00000a78 cmp w7, 1
0x00000a7c b.eq 0xae0 ; unlikely
0x00000a80 sub w11, w7, 1
0x00000a84 mov x4, 0
0x00000a88 mov w8, w11
0x00000a8c b 0xa48
0x00000a90 add x20, x20, 1
0x00000a94 b 0xa14
0x00000a98 add x5, x5, 1
0x00000a9c add x4, x4, 1
0x00000aa0 add x4, x4, x5
0x00000aa4 sub w8, w8, 2
0x00000aa8 cmp w12, 1
0x00000aac b.ne 0x8b8 ; likely
0x00000ab0 add x3, x3, 1
0x00000ab4 sub w7, w7, 2
0x00000ab8 add x3, x3, x4
0x00000abc cmp w11, 1
0x00000ac0 b.ne 0x8a4 ; likely
0x00000ac4 add x0, x1, 1
0x00000ac8 sub w6, w6, 2
0x00000acc add x1, x0, x3
0x00000ad0 cmp w10, 1
0x00000ad4 b.ne 0x890 ; likely
0x00000ad8 add x0, x1, 1
0x00000adc ret
0x00000ae0 add x3, x3, 1
0x00000ae4 add x0, x1, 1
0x00000ae8 sub w6, w6, 2
0x00000aec add x1, x0, x3
0x00000af0 cmp w10, 1
0x00000af4 b.eq 0xb78 ; unlikely
0x00000af8 cmp w6, 1
0x00000afc b.eq 0xb10 ; unlikely
0x00000b00 sub w10, w6, 1
0x00000b04 mov x3, 0
0x00000b08 mov w7, w10
0x00000b0c b 0xa78
0x00000b10 ldp x19, x20, [var_10h]
0x00000b14 add x0, x1, 2
0x00000b18 ldp x21, x22, [var_20h]
0x00000b1c ldp x23, x24, [var_30h]
0x00000b20 ldp x25, x26, [var_40h]
0x00000b24 ldp x27, x28, [var_50h]
0x00000b28 ldp x29, x30, [sp], 0xb0
0x00000b2c ret
0x00000b30 add x4, x4, 1
0x00000b34 add x3, x3, 1
0x00000b38 add x3, x3, x4
0x00000b3c sub w7, w7, 2
0x00000b40 cmp w11, 1
0x00000b44 b.ne 0x8a4 ; likely
0x00000b48 b 0xac4
0x00000b4c add x3, x3, 1
0x00000b50 add x0, x1, 1
0x00000b54 add x1, x0, x3
0x00000b58 sub w6, w6, 2
0x00000b5c cmp w10, 1
0x00000b60 b.ne 0x890 ; likely
0x00000b64 b 0xad8
0x00000b68 mov x0, 1
0x00000b6c ret
0x00000b70 add x0, x1, 2
0x00000b74 ret
0x00000b78 ldp x19, x20, [var_10h]
0x00000b7c add x0, x1, 1
0x00000b80 ldp x21, x22, [var_20h]
0x00000b84 ldp x23, x24, [var_30h]
0x00000b88 ldp x25, x26, [var_40h]
0x00000b8c ldp x27, x28, [var_50h]
0x00000b90 ldp x29, x30, [sp], 0xb0 ; 0x178000
0x00000b94 ret
Cependant, vous pouvez toujours reconnaître qu’il s’agit d’une récursion grâce à l’instruction qui s’appelle elle-même à 0x00000970.
Qu’est-ce qui explique cette différence ? Dans la fonction fact(), la relation d’appel forme une simple chaîne linéaire :
Une telle chaîne d’appels linéaire peut être équivalente à une boucle. Le compilateur l’a donc optimisée afin d’économiser de l’espace sur la pile.
Un exemple typique de récursion équivalente à une boucle est la récursion terminale, dont la dernière opération est un appel à elle-même. Par exemple :
void f(unsigned int x, int *a)
{
if (x == 0) return;
else
{
*a += x;
return f(x - 1, a);
}
}
Il a été démontré que ce type de récursion peut être transformé en une boucle équivalente ; le compilateur l’optimisera donc. L’exemple fact() ci-dessus n’est pas une récursion terminale, mais il est tout de même linéaire, et le compilateur a détecté ce motif, donc il l’a également optimisé.
En revanche, fibonacci() n’est pas dans ce cas :
La relation d’appel n’est pas linéaire. C’est un arbre. La conversion en boucle n’est donc pas possible ; le compilateur a donc conservé le schéma récursif.
