Recursions in AArch64
2026-07-23T17:57:11+08:00
Basic patterns
Let’s start with a C program that contains a simple Fibonacci function.
#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;
}
Compile it:
$ gcc fibo.c -o fibo0
By default, GCC does not perform any optimisation at all. Open your shiny iaito and go to the main function:
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
Here you can see a call to sym.fibonacci at 0x0000898. Open this function and look at the graph:
You will see that sym.fibonacci calls itself at 0x0000854 and 0x0000864, respectively.
If you have stripped the symbols, you will not see sym.fibonacci, but you will still see something like bl fcn.00000828 here. In any case, patterns in which functions call themselves indicate recursion.
Optimisation
Let’s replace the Fibonacci function with a factorial function:
#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;
}
Compile it:
$ gcc fact.c -o fact0
Opening it in iaito gives you a main function that calls 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
Here is the disassembly of the sym.fact function being called:
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
and also the graph of it:
So what happens if we turn optimisation on? Let’s try:
$ gcc fact.c -O2 -o fact2
Open it in iaito and inspect the main function. You will see:
The instruction that called sym.fact is gone. Instead, you see a loop inside the main function that does the work.
Go back to the C code containing our Fibonacci function, compile it with optimisation enabled, and inspect the main function:
;-- 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)
; int printf("%lu")
0x00000730 mov w0, 0
0x00000734 ldp x29, x30, [sp], 0x20
0x00000738 ret
The instruction calling sym.fibonacci is still there.
Open the disassembly of sym.fibonacci, and you will appreciate how ingenious the compiler is:
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
However, you can still tell that this is recursion from the instruction that calls itself at 0x00000970.
What makes this difference? In the fact() function, the call relationship is a single linear chain:
Such a single linear call chain can be equivalent to a loop. Therefore, the compiler optimised it to save stack space.
A typical example of recursion that is equivalent to a loop is tail recursion, where the last operation is a call to itself. For example:
void f(unsigned int x, int *a)
{
if (x == 0) return;
else
{
*a += x;
return f(x - 1, a);
}
}
Such recursion has been proved to be convertible into an equivalent loop, so the compiler will optimise it. The fact() example above is not tail-recursive, but it is still linear, and the compiler has detected the pattern, so it has been optimised as well.
However, fibonacci() is different:
The calling relationship is not linear. It is a tree. Therefore, conversion to a loop is not possible, so the compiler has kept the recursion pattern.
