Rekursionen in AArch64
2026-07-23T17:57:11+08:00
Grundmuster
Beginnen wir mit einem C-Programm, das eine einfache Fibonacci-Funktion enthält.
#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;
}
Kompilieren Sie es:
$ gcc fibo.c -o fibo0
Standardmässig führt GCC überhaupt keine Optimierung durch. Öffnen Sie Ihr schickes iaito und gehen Sie zur Funktion 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
Hier sehen Sie einen Aufruf von sym.fibonacci bei 0x0000898. Öffnen Sie diese Funktion und betrachten Sie den Graphen:
Sie werden sehen, dass sich sym.fibonacci bei 0x0000854 und 0x0000864 jeweils selbst aufruft.
Wenn Sie die Symbole entfernt haben, sehen Sie sym.fibonacci nicht mehr, aber Sie werden hier trotzdem etwas wie bl fcn.00000828 sehen. Solche Muster, bei denen Funktionen sich selbst aufrufen, weisen auf Rekursion hin.
Optimierung
Ersetzen wir die Fibonacci-Funktion durch eine Fakultätsfunktion:
#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;
}
Kompilieren Sie es:
$ gcc fact.c -o fact0
Beim Öffnen in iaito erhalten Sie eine main-Funktion, die sym.fact aufruft:
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
Die Disassemblierung der aufgerufenen Funktion sym.fact lautet:
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
und auch der Graph davon:
Was passiert also, wenn wir die Optimierung einschalten? Versuchen wir es:
$ gcc fact.c -O2 -o fact2
Öffnen Sie es in iaito und untersuchen Sie die Funktion main. Sie werden Folgendes sehen:
Die Anweisung, die sym.fact aufruft, ist verschwunden. Stattdessen sehen Sie eine Schleife innerhalb der Funktion main, die die Arbeit erledigt.
Gehen Sie zurück zu dem C-Code mit unserer Fibonacci-Funktion, kompilieren Sie ihn mit aktivierter Optimierung, und untersuchen Sie die Funktion 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
Die Anweisung, die sym.fibonacci aufruft, ist noch vorhanden.
Wenn Sie die Disassemblierung von sym.fibonacci öffnen, werden Sie die Raffinesse des Compilers zu schätzen wissen:
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
Sie können aber immer noch erkennen, dass es sich um Rekursion handelt, anhand der Anweisung, die sich bei 0x00000970 selbst aufruft.
Wodurch entsteht dieser Unterschied? In der Funktion fact() ist die Aufrufbeziehung eine einzelne lineare Kette:
Eine solche einzelne lineare Aufrufkette kann einem Loop entsprechen. Deshalb hat der Compiler sie optimiert, um Stack-Speicher zu sparen.
Ein typisches Beispiel für Rekursion, die einem Loop entspricht, ist die Endrekursion, bei der die letzte Operation ein Selbstaufruf ist. Zum Beispiel:
void f(unsigned int x, int *a)
{
if (x == 0) return;
else
{
*a += x;
return f(x - 1, a);
}
}
Solche Rekursionen lassen sich nachweislich in äquivalente Schleifen umwandeln, daher optimiert der Compiler sie. Das obige fact()-Beispiel ist nicht endrekursiv, aber es ist trotzdem linear, und der Compiler hat das Muster erkannt, also wurde es ebenfalls optimiert.
fibonacci() ist jedoch nicht der Fall:
Die Aufrufbeziehung ist nicht linear. Sie ist ein Baum. Daher ist eine Umwandlung in eine Schleife nicht möglich; deshalb hat der Compiler das Rekursionsmuster beibehalten.
