C言語末尾再帰

最近マイブームなので、ちょっと気になってテストしてみました。
以下末尾再帰関数の具体例のメモです。
実際にスタックを消費せずループしているかどうか。
動作環境はMac Snow Leopardのコンソール。

/*test.c*/
#include<stdio.h>
void loop(int x)
{
        if(x == 0){
                return;
        }
        printf("%d ", x);
        loop(x + 1);
}
main()
{
        loop(1);
}

cc -o test test.c でコンパイルした場合、261623で、Segmentation fault.
cc -o test -O2 test.c でコンパイルした場合、無限ループ
アセンブラコードを見てみると、前者は、

_loop:
Leh_func_begin1:
pushq %rbp
Ltmp0:
movq %rsp, %rbp
Ltmp1:
subq $16, %rsp
Ltmp2:
movl %edi, -4(%rbp)
movl -4(%rbp), %eax
cmpl $0, %eax
je LBB1_2
movl -4(%rbp), %eax
xorb %cl, %cl
leaq L_.str(%rip), %rdx
movq %rdx, %rdi
movl %eax, %esi
movb %cl, %al
callq _printf
movl -4(%rbp), %eax
addl $1, %eax
movl %eax, %edi
callq _loop

後者は、

_loop:
Leh_func_begin1:
pushq %rbp
Ltmp0:
movq %rsp, %rbp
Ltmp1:
pushq %r14
pushq %rbx
Ltmp2:
leaq L_.str(%rip), %rbx
movl %edi, %r14d
jmp LBB1_1
.align 4, 0x90
LBB1_3:
leal 1(%r14), %esi
xorb %al, %al
movq %rbx, %rdi
callq _printf
addl $2, %r14d
LBB1_1:
testl %r14d, %r14d
je LBB1_4
xorb %al, %al
movq %rbx, %rdi
movl %r14d, %esi
callq _printf
cmpl $-1, %r14d
jne LBB1_3
LBB1_4:
popq %rbx
popq %r14
popq %rbp
ret

確かに関数呼び出しがなくなっている。
最適化しないと末尾再帰にならないみたいである。

Tags: ,

Leave a Reply