リカーシブコードをアセンブラで考察

# リカーシブコードを最適化有無でコンパイルしアセンブラレベルで比較
リカーシブ（再帰的）ソースコードを最適化有無でコンパイルすると面白い（差がある）ことに気がついたので記録してみる。

## 対象となるソースコード
```c:f.c
#include <stdio.h>

int fact(int);

void main() {
	printf("v=%d\n", fact(97));
}

int fact(int n) {
	if (n == 0) {
		return(1);
	} else {
		return(n*fact(n-1));
	}
}
```
97の階乗を求めるプログラムである。これをデバッグオプション付加してコンパイルする。

```
% gcc -g f.c -o f0      (最適化なし）
% gcc -g -O f.c -o f1   (最適化小）
% gcc -g -O2 f.c -o f2  (最適化大）
```

で、アセンブリされた結果を見る。

```
% objdump -S -M intel f0 > O0.txt
% objdump -S -M intel f1 > O1.txt
% objdump -S -M intel f2 > O2.txt
```

## 最適化なしのアセンブル（O0.txtの一部）
関連しないところは省略して記述。以下、同様。

```
0000000000001050 <printf@plt>:
    1050:	f3 0f 1e fa          	endbr64 
    1054:	f2 ff 25 75 2f 00 00 	bnd jmp QWORD PTR [rip+0x2f75]        # 3fd0 <printf@GLIBC_2.2.5>
    105b:	0f 1f 44 00 00       	nop    DWORD PTR [rax+rax*1+0x0]

.....

0000000000001149 <main>:
#include <stdio.h>

int fact(int);

void main() {
    1149:	f3 0f 1e fa          	endbr64 
    114d:	55                   	push   rbp
    114e:	48 89 e5             	mov    rbp,rsp
	printf("v=%d\n", fact(97));
    1151:	bf 61 00 00 00       	mov    edi,0x61
    1156:	e8 16 00 00 00       	call   1171 <fact>
    115b:	89 c6                	mov    esi,eax
    115d:	48 8d 3d a0 0e 00 00 	lea    rdi,[rip+0xea0]        # 2004 <_IO_stdin_used+0x4>
    1164:	b8 00 00 00 00       	mov    eax,0x0
    1169:	e8 e2 fe ff ff       	call   1050 <printf@plt>
}
    116e:	90                   	nop
    116f:	5d                   	pop    rbp
    1170:	c3                   	ret    

0000000000001171 <fact>:

int fact(int n) {
    1171:	f3 0f 1e fa          	endbr64 
    1175:	55                   	push   rbp
    1176:	48 89 e5             	mov    rbp,rsp
    1179:	48 83 ec 10          	sub    rsp,0x10
    117d:	89 7d fc             	mov    DWORD PTR [rbp-0x4],edi
	if (n == 0) {
    1180:	83 7d fc 00          	cmp    DWORD PTR [rbp-0x4],0x0
    1184:	75 07                	jne    118d <fact+0x1c>
		return(1);
    1186:	b8 01 00 00 00       	mov    eax,0x1
    118b:	eb 11                	jmp    119e <fact+0x2d>
	} else {
		return(n*fact(n-1));
    118d:	8b 45 fc             	mov    eax,DWORD PTR [rbp-0x4]
    1190:	83 e8 01             	sub    eax,0x1
    1193:	89 c7                	mov    edi,eax
    1195:	e8 d7 ff ff ff       	call   1171 <fact>
    119a:	0f af 45 fc          	imul   eax,DWORD PTR [rbp-0x4]
	}
}
    119e:	c9                   	leave  
    119f:	c3                   	ret    

```

1149番地がmain()の開始番地。1156番地で、関数fact()を呼び出している。fact()の開始番地は、1171番地。

最適化無し時、関数fact()の1195番地の「call 1171」により、再度fact()が呼ばれていることがわかる、つまり、再帰呼び出しとなっている。nが0となった時点で一番底からもどり、掛け算が何度も行われる（119f番地の「ret」が119a番地となり、「imul」が何度も呼び出される）。至って予想通りのコード。関数fact()のサイズは「2F」バイト。

## 最適化小のアセンブル（O1.txtの一部）
```
0000000000001149 <fact>:

void main() {
	printf("v=%d\n", fact(97));
}

int fact(int n) {
    1149:	f3 0f 1e fa          	endbr64 
	if (n == 0) {
		return(1);
    114d:	b8 01 00 00 00       	mov    eax,0x1
	if (n == 0) {
    1152:	85 ff                	test   edi,edi
    1154:	75 01                	jne    1157 <fact+0xe>
	} else {
		return(n*fact(n-1));
	}
}
    1156:	c3                   	ret    
int fact(int n) {
    1157:	53                   	push   rbx
    1158:	89 fb                	mov    ebx,edi
		return(n*fact(n-1));
    115a:	8d 7f ff             	lea    edi,[rdi-0x1]
    115d:	e8 e7 ff ff ff       	call   1149 <fact>
    1162:	0f af c3             	imul   eax,ebx
}
    1165:	5b                   	pop    rbx
    1166:	c3                   	ret    

0000000000001167 <main>:
void main() {
    1167:	f3 0f 1e fa          	endbr64 
    116b:	48 83 ec 08          	sub    rsp,0x8
	printf("v=%d\n", fact(97));
    116f:	bf 61 00 00 00       	mov    edi,0x61
    1174:	e8 d0 ff ff ff       	call   1149 <fact>
    1179:	89 c2                	mov    edx,eax
}

__fortify_function int
printf (const char *__restrict __fmt, ...)
{
  return __printf_chk (__USE_FORTIFY_LEVEL - 1, __fmt, __va_arg_pack ());
    117b:	48 8d 35 82 0e 00 00 	lea    rsi,[rip+0xe82]        # 2004 <_IO_stdin_used+0x4>
    1182:	bf 01 00 00 00       	mov    edi,0x1
    1187:	b8 00 00 00 00       	mov    eax,0x0
    118c:	e8 bf fe ff ff       	call   1050 <__printf_chk@plt>
}
    1191:	48 83 c4 08          	add    rsp,0x8
    1195:	c3                   	ret    

```

1167番地がmain()の開始番地。1174番地で、関数fact()を呼び出している。fact()の開始番地は、1149番地。

最適化を行うと、関数呼び出し後に行われる「push rbp -> mov rbp, rsp」および最後に行われる「leave」が見当たらなくなる。情報の一貫性が保たれるよう、スタックをうまく使いこなしていると推測。

ここでも、関数fact()の115d番地の「call 1149」により、再度fact()が呼ばれていることがわかる、つまり、再帰呼び出しとなっている。nが0となった時点で一番底からもどり、掛け算が何度も行われる（先程と同じ）。これも予想通りのコード。関数fact()のサイズは「1E」バイト。最適化無し時の「2F」より小さい。


## 最適化大のアセンブル（O2.txtの一部）
```
0000000000001050 <__printf_chk@plt>:
    1050:	f3 0f 1e fa          	endbr64 
    1054:	f2 ff 25 75 2f 00 00 	bnd jmp QWORD PTR [rip+0x2f75]        # 3fd0 <__printf_chk@GLIBC_2.3.4>
    105b:	0f 1f 44 00 00       	nop    DWORD PTR [rax+rax*1+0x0]

0000000000001060 <main>:
#include <stdio.h>

int fact(int);

void main() {
    1060:	f3 0f 1e fa          	endbr64 
    1064:	ba 01 00 00 00       	mov    edx,0x1
    1069:	b8 61 00 00 00       	mov    eax,0x61
    106e:	66 90                	xchg   ax,ax

int fact(int n) {
	if (n == 0) {
		return(1);
	} else {
		return(n*fact(n-1));
    1070:	0f af d0             	imul   edx,eax
	if (n == 0) {
    1073:	83 e8 01             	sub    eax,0x1
    1076:	75 f8                	jne    1070 <main+0x10>
}

__fortify_function int
printf (const char *__restrict __fmt, ...)
{
  return __printf_chk (__USE_FORTIFY_LEVEL - 1, __fmt, __va_arg_pack ());
    1078:	48 8d 35 85 0f 00 00 	lea    rsi,[rip+0xf85]        # 2004 <_IO_stdin_used+0x4>
    107f:	bf 01 00 00 00       	mov    edi,0x1
    1084:	31 c0                	xor    eax,eax
    1086:	e9 c5 ff ff ff       	jmp    1050 <__printf_chk@plt>
    108b:	0f 1f 44 00 00       	nop    DWORD PTR [rax+rax*1+0x0]
```

1060番地がmain()の開始番地。関数fact()に相当する部分が消えており、掛け算が1070-1076番地で繰り返されている。「1 x 97 x 96 x ... x 1」といった掛け算になり、リカーシブ部分が消えている。コンパイラさんが最適化を行って、再帰処理不要と判断したのであろう。

## 感想
コンパイラを作った人は頭がいい。