基本模式
让我们从一个包含简单斐波那契计算函数的 C 程序开始。
#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;
}
编译它：
$ gcc fibo.c -o fibo0
默认情况下，GCC 根本不会做任何优化。打开你那闪亮的 iaito，进入 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
这里你可以看到在 0x0000898 处调用了 sym.fibonacci。打开这个函数，看看它的图：
你会看到 sym.fibonacci 分别在 0x0000854 和 0x0000864 处调用了它自己。
如果你去掉了符号信息，那么你看不到 sym.fibonacci，但你仍然会在这里看到类似 bl fcn.00000828 的东西。总之，函数调用自身的这种模式表示 递归。
优化
我们把 Fibonacci 函数换成阶乘函数：
#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;
}
编译它：
$ gcc fact.c -o fact0
在 iaito 中打开后，你会得到一个调用 sym.fact 的 main 函数：
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
被调用的 sym.fact 函数的反汇编如下：
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
以及它的图：
那么，如果我们打开优化会怎样？试试看：
$ gcc fact.c -O2 -o fact2
在 iaito 中打开并检查 main 函数。你会看到：
调用 sym.fact 的那条指令不见了。取而代之的是，main 函数内部出现了一个循环来完成工作。
回到包含 Fibonacci 函数的 C 代码，在开启优化的情况下重新编译，然后检查 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
0x00000aac cmp w12, 1
0x00000ab0 b.ne 0x8b8 ; likely
0x00000ab4 add x3, x3, 1
0x00000ab8 sub w7, w7, 2
0x00000abc add x3, x3, x4
0x00000ac0 cmp w11, 1
0x00000ac4 b.ne 0x8a4 ; likely
0x00000ac8 add x0, x1, 1
0x00000acc sub w6, w6, 2
0x00000ad0 add x1, x0, x3
0x00000ad4 cmp w10, 1
0x00000ad8 b.ne 0x890 ; likely
0x00000adc add x0, x1, 1
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
不过，你仍然可以从 0x00000970 处的自调用看出这是递归。
这两者为什么不同？在 fact() 函数中，调用关系是一条单一的线性链：
这样一条线性的调用链可以等价为一个循环。因此，编译器会将其优化，以节省栈空间。
递归与循环等价的一个典型例子是尾递归，也就是最后一个操作是调用自身。例如：
void f(unsigned int x, int *a)
{
if (x == 0) return;
else
{
*a += x;
return f(x - 1, a);
}
}
这种递归已经被证明可以转换为等价的循环，因此编译器会对其进行优化。上面的 fact() 示例虽然不是尾递归，但它仍然是线性的，编译器识别出了这个模式，所以也把它优化了。
不过，fibonacci() 不是这种情况：
它的调用关系不是线性的，而是一棵树。因此，不可能把它转换成循环——编译器也就保留了递归模式。