今時のgcc に驚いた。kernel/VM advent cal. 2012/ DEC/07

kernelVM advent calendar 2012/ DEC/07
今時のgcc に驚いた話。
(kernelともVMとも関係なくて、スマソ)

-- a.c
main()
{
  foo();
}

foo()
{
 printf("FOO");
 bar();
}
 
bar()
{
 printf("BAR");
 foo();
}

--

というソースを書く。
foo()とbar()は、お互いに呼びあい無限ループを描く。

% cc -S -O0 a.c
で、出たオブジェクトは

-- a.s -O0
	    (略)
main:
.LFB0:
	    (略)
	movl	$0, %eax
	call	foo
	    (略)
	ret
	.cfi_endproc
.LFE0:
	    (略)
.LC0:
	.string	"FOO"
	.text
	.globl	foo
	.type	foo, @function
foo:
.LFB1:
	    (略)
	movl	$.LC0, %edi
	movl	$0, %eax
	call	printf
	movl	$0, %eax
	call	bar
	    (略)
	ret
	.cfi_endproc
.LFE1:
	    (略)
.LC1:
	.string	"BAR"
	.text
	.globl	bar
	.type	bar, @function
bar:
.LFB2:
	    (略)
	movl	$.LC1, %edi
	movl	$0, %eax
	call	printf
	movl	$0, %eax
	call	foo
	    (略)
	ret
	.cfi_endproc
	    (略)

--

と、普通の Callが出ている。
ほのぼのと、無限に、呼び出しスタック(invocation stack)を消費する。いつか、スタックが枯渇して止まるであろう。



しかし、計算機科学の教科書をみれば書いてあるとおり…
これらの関数は、末尾再帰な呼び出しになっている。これは最適化すると、ただのループに変換できることが知られている。

gccの最適化はどれぐらい賢いのだろう???

% cc -S -O4 a.c

-- a.s -O4
	.file	"a.c"
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"FOO"
.LC1:
	.string	"BAR"
	.text
	.p2align 4,,15
	.globl	foo
	.type	foo, @function
foo:
.LFB1:
	.cfi_startproc
	pushq	%rax
	.cfi_def_cfa_offset 16
	.p2align 4,,10
	.p2align 3
.L2:
	movl	$.LC0, %edi
	xorl	%eax, %eax
	call	printf
	movl	$.LC1, %edi
	xorl	%eax, %eax
	call	printf
	movl	$.LC0, %edi
	xorl	%eax, %eax
	call	printf
	movl	$.LC1, %edi
	xorl	%eax, %eax
	call	printf
	movl	$.LC0, %edi
	xorl	%eax, %eax
	call	printf
	movl	$.LC1, %edi
	xorl	%eax, %eax
	call	printf
	movl	$.LC0, %edi
	xorl	%eax, %eax
	call	printf
	movl	$.LC1, %edi
	xorl	%eax, %eax
	call	printf
	movl	$.LC0, %edi
	xorl	%eax, %eax
	call	printf
	movl	$.LC1, %edi
	xorl	%eax, %eax
	call	printf
	jmp	.L2
	.cfi_endproc
.LFE1:
	.size	foo, .-foo
	.section	.text.startup,"ax",@progbits
	.p2align 4,,15
	.globl	main
	.type	main, @function
main:
.LFB0:
	.cfi_startproc
	subq	$8, %rsp
	.cfi_def_cfa_offset 16
	xorl	%eax, %eax
	call	foo
	.cfi_endproc
.LFE0:
	.size	main, .-main
	.text
	.p2align 4,,15
	.globl	bar
	.type	bar, @function
bar:
.LFB2:
	.cfi_startproc
	subq	$8, %rsp
	.cfi_def_cfa_offset 16
	movl	$.LC1, %edi
	xorl	%eax, %eax
	call	printf
	movl	$.LC0, %edi
	xorl	%eax, %eax
	call	printf
	movl	$.LC1, %edi
	xorl	%eax, %eax
	call	printf
	xorl	%eax, %eax
	call	foo
	.cfi_endproc
.LFE2:
	.size	bar, .-bar
	.ident	"GCC: (Ubuntu/Linaro 4.6.1-9ubuntu3) 4.6.1"
	.section	.note.GNU-stack,"",@progbits

--

foo()は、
printf("FOO"); printf("BAR"); が5回展開された上で、
単なる無限ループになっている。

bar()は、
printf("BAR");printf("FOO");printf("BAR");
を実行してから、foo()をcallしている。
"BAR"をprintfしてから、"FOO"のprintfを実行すべきだから、最初のprintf("BAR")は必要。だが、とりあえず、多めに展開している。
ソフトウェア・パイプラインなのだろう(か?)

main()は、即座にfoo()を呼んでいる。

ちなみに、a.cの初頭に static bar(); と書くと、
bar()のコードは生成されなくなってしまう。


うーむ、すごい。


昔は、C言語は、伝統的に、末尾再帰の最適化はしないことになっていた。
たしか、gcc ver.3 ぐらい(だったか?もう、忘れた昔)に、末尾再帰最適化が行われるようになって、他のコンパイラ・メーカのコンパイラも追従した。

とはいえ、当時は、自分自身を再帰的に呼ぶ関数の最適化が行われた程度だ。
すなわち、

-- 
int
fact_tailRec(int n,int fa)
{
 if(n==0) return fa;
 else return fact_tailRec(n-1, fa*n);
}
--

というような関数のみが、ループに変換できた。
関数一つだけを見ればいいので、かなり簡単に見つけれられる最適化である。


今の gccは、複数の関数に渡って、その関係をみて、
両方の関数が互いに呼び合っていることを見抜いて、
中に展開した上で、ループにしてしまっている。
すごい。

アホのような無限ループだけではなく、

--
extern baz();

foo(int c1)
{
 printf("FOO");
 if(!c1) return baz();
 else bar(--c1);
}
 
bar(int c)
{
 printf("BAR");
 foo(c);
}
--

のような、実用的な関数でもループに最適化される。

---

もっと驚いたことがある。

--
int
fa1(int n)
{
  if(n==0) return 1;
  else return fa1(n-1)*n;
}
--

このような関数は、末尾再帰ではない(ただの再帰)ので、
単純な規則では、ループ変換されない。
しかし、gcc -O4 でコンパイルすると、
乗算の繰り返しループに変換されてしまった。
しかも、mmxを駆使したものになった。

--
	.globl	fa1
	.type	fa1, @function
fa1:
.LFB1:
	.cfi_startproc
	testl	%edi, %edi
	movl	$1, %eax
	je	.L14
	movl	%edi, %edx
	movl	%edi, %esi
	shrl	$2, %edx
	cmpl	$6, %edi
	leal	0(,%rdx,4), %ecx
	jbe	.L20
	testl	%ecx, %ecx
	je	.L20
	leal	-1(%rdi), %eax
	movl	%edi, -24(%rsp)
	movdqa	.LC1(%rip), %xmm4
	movl	%eax, -20(%rsp)
	leal	-2(%rdi), %eax
	movd	-20(%rsp), %xmm2
	movl	%eax, -16(%rsp)
	leal	-3(%rdi), %eax
	movd	-16(%rsp), %xmm1
	movl	%eax, -12(%rsp)
	xorl	%eax, %eax
	movd	-12(%rsp), %xmm0
	punpckldq	%xmm0, %xmm1
	movd	-24(%rsp), %xmm0
	punpckldq	%xmm2, %xmm0
	punpcklqdq	%xmm1, %xmm0
	movdqa	.LC0(%rip), %xmm1
	.p2align 4,,10
	.p2align 3
.L16:
	movdqa	%xmm1, %xmm3
	psrldq	$4, %xmm1
	addl	$1, %eax
	movdqa	%xmm0, %xmm2
	cmpl	%eax, %edx
	pmuludq	%xmm0, %xmm3
	paddd	%xmm4, %xmm0
	psrldq	$4, %xmm2
	pmuludq	%xmm1, %xmm2
	pshufd	$8, %xmm3, %xmm1
	pshufd	$8, %xmm2, %xmm2
	punpckldq	%xmm2, %xmm1
	ja	.L16
	movdqa	%xmm1, %xmm2
	subl	%ecx, %edi
	cmpl	%ecx, %esi
	psrldq	$8, %xmm2
	movdqa	%xmm2, %xmm0
	psrldq	$4, %xmm2
	pmuludq	%xmm1, %xmm0
	psrldq	$4, %xmm1
	pshufd	$8, %xmm0, %xmm0
	pmuludq	%xmm2, %xmm1
	pshufd	$8, %xmm1, %xmm1
	punpckldq	%xmm1, %xmm0
	movdqa	%xmm0, %xmm1
	psrldq	$4, %xmm1
	movdqa	%xmm1, %xmm2
	psrldq	$4, %xmm1
	pmuludq	%xmm0, %xmm2
	psrldq	$4, %xmm0
	pmuludq	%xmm0, %xmm1
	pshufd	$8, %xmm2, %xmm0
	pshufd	$8, %xmm1, %xmm1
	punpckldq	%xmm1, %xmm0
	movd	%xmm0, -24(%rsp)
	movl	-24(%rsp), %eax
	je	.L24
	.p2align 4,,10
	.p2align 3
.L21:
	imull	%edi, %eax
	subl	$1, %edi
	jne	.L21
.L14:
	rep
	ret
.L20:
	movl	$1, %eax
	jmp	.L21
.L24:
	.p2align 4,,6
	ret
	.cfi_endproc
.LFE1:
	.size	fa1, .-fa1
	.section	.rodata.cst16,"aM",@progbits,16
	.align 16
.LC0:
	.long	1
	.long	1
	.long	1
	.long	1
	.align 16
.LC1:
	.long	-4
	.long	-4
	.long	-4
	.long	-4
--

うーむ。その辺のヘボいプログラマより、はるかに頭がいいなぁ。

でも、こんなに変換してしまっては、そもそも低級言語であるはずの C言語が違うものに…

以上でおしまい。


ここで使用したコンパイラ

% gcc -v
組み込み spec を使用しています。
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.6.1/lto-wrapper
ターゲット: x86_64-linux-gnu
configure 設定: ../src/configure -v --with-pkgversion='Ubuntu/Linaro 4.6.1-9ubuntu3' --with-bugurl=file:///usr/share/doc/gcc-4.6/README.Bugs --enable-languages=c,c++,fortran,objc,obj-c++,go --prefix=/usr --program-suffix=-4.6 --enable-shared --enable-linker-build-id --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.6 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-plugin --enable-objc-gc --disable-werror --with-arch-32=i686 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
スレッドモデル: posix
gcc バージョン 4.6.1 (Ubuntu/Linaro 4.6.1-9ubuntu3)

---