gcc 4.3.0 評価3
すごいっ。とうとうgccがやってくれたっ。
static int foo(int count) { if (count <= 0) return 1; return count * foo(count - 1); } int main(int argc, char* argv[]) { printf("%d\n", foo(10)); return 0; }
gcc 4.2.3 -O3の場合、こんな簡単な関数でもやっぱり再帰呼び出しなのです。
ちなみにinlineつけようが__attribute__((pure))つけようが結果はちっとも変わりません。
_Z3fooi: pushl %ebp movl $1, %eax movl %esp, %ebp subl $40, %esp movl %ebx, -12(%ebp) movl 8(%ebp), %ebx movl %esi, -8(%ebp) movl %edi, -4(%ebp) testl %ebx, %ebx jle .L4 (省略) movl -4(%ebp), %edi movl %ebp, %esp popl %ebp ret .L31: leal -9(%ebx), %eax movl %eax, (%esp) call _Z3fooi # 悲しきかな再帰呼び出し imull -16(%ebp), %eax jmp .L28 main: leal 4(%esp), %ecx andl $-16, %esp pushl -4(%ecx) pushl %ebp movl %esp, %ebp pushl %ecx subl $20, %esp movl $9, (%esp) call _Z3fooi movl $.LC0, (%esp) leal (%eax,%eax,4), %eax addl %eax, %eax movl %eax, 4(%esp) call printf addl $20, %esp xorl %eax, %eax popl %ecx popl %ebp leal -4(%ecx), %esp ret
で、gcc-4.3.0 RC1 -O3の場合。
main: leal 4(%esp), %ecx andl $-16, %esp pushl -4(%ecx) pushl %ebp movl %esp, %ebp pushl %ecx subl $20, %esp movl $3628800, 4(%esp) movl $.LC0, (%esp) call printf addl $20, %esp xorl %eax, %eax popl %ecx popl %ebp leal -4(%ecx), %esp ret
やった! とうとう再帰呼び出しを無くせましたっ。それどころか即値になってるよ。おめでとう!ありがとう!
ちなみにfoo関数の引数をvolatileな変数に変えると、mainj関数内のループに変換してくれます。
末尾再帰がループに変換された瞬間です。素敵すぎだgcc 4.3.0！
static int foo(int count) { if (count <= 0) return 1; return count * foo(count - 1); } int main(int argc, char* argv[]) { volatile int i = 10; printf("%lld\n", foo(i)); return 0; }
main: leal 4(%esp), %ecx andl $-16, %esp pushl -4(%ecx) pushl %ebp movl %esp, %ebp pushl %ecx movl $1, %ecx subl $36, %esp movl $10, -8(%ebp) movl -8(%ebp), %eax testl %eax, %eax jg .L4 jmp .L3 .L7: movl %edx, %eax .L4: leal -1(%eax), %edx imull %eax, %ecx testl %edx, %edx jg .L7 .L3: movl %ecx, 4(%esp) movl $.LC0, (%esp) call printf addl $36, %esp xorl %eax, %eax popl %ecx popl %ebp leal -4(%ecx), %esp ret
