Cの末尾再帰
最近のCコンパイラは末尾再帰の最適化を行ってくれるそうです。
しかし、Cにはポインタがある以上、上手く最適化できない場合もあるよなー
みたいなことを一年ほど前に思いついたんですが、試すのが面倒で放置してました。
それが、今さらになって気になってきたので試してみることにしました。
コンパイラには『gcc (GCC) 4.2.1 20070719 [FreeBSD]』を使用。
まずは、最適化されそうな関数。
int f(int n, int acc) {
if (n <= 0) {
return acc;
}
return f(n-1, acc+nanika(n));
}
これを『gcc -c -S -O2』でコンパイルしたところ、以下のようになりました。
f: pushl %ebp movl %esp, %ebp pushl %esi pushl %ebx subl $16, %esp movl 8(%ebp), %ebx movl 12(%ebp), %esi testl %ebx, %ebx jle .L8 .p2align 4,,7 .L11: movl %ebx, (%esp) call nanika addl %eax, %esi subl $1, %ebx jne .L11 .L8: addl $16, %esp movl %esi, %eax popl %ebx popl %esi popl %ebp ret
再帰がジャンプになってます。さすがGCC。
で、次は去年思いついてた最適化されなさそうなコード。
int g(int x, int *p, int count)
{
x = 0;
x = *p + 1;
if (count <= 0) {
return x;
}
return g(x, &x, count -1);
}
もし、これがループに置き換われば、一つ前のxがx=0により消されてしまうため、
その後で*pで参照するときにおかしなことになってしまいます。
上と同様のオプションでコンパイルしたところ、以下のようになりました。
g: pushl %ebp movl %esp, %ebp subl $12, %esp movl 12(%ebp), %eax movl 16(%ebp), %ecx movl $0, 8(%ebp) movl (%eax), %edx addl $1, %edx testl %ecx, %ecx jle .L2 leal -1(%ecx), %eax movl %eax, 8(%esp) leal 8(%ebp), %eax movl %edx, 8(%ebp) movl %edx, (%esp) movl %eax, 4(%esp) call g movl %eax, %edx .L2: leave movl %edx, %eax ret
想像通り、最適化は行われずにcallになっていました。
Cにはポインタがある以上、末尾再帰の最適化は完全には行えないよなー、
という夢のないお話でした。