toge's diary

コンピュータ関連の趣味をつらつらと。

GCC4.0.0で遊ぶ

C++

帰宅も遅かったし新たなネタをやるのは自粛して、GCCで遊んでみます。
お題はこんなソースコード。所謂末尾再帰ってやつですね。
末尾再帰はループで表わせるので、ループっぽいアセンブラコードを吐いてくれると嬉しいのですけど。果たして。

int add(int n)
{
  if (n <= 1)
  {
    return n; 
  }

  return n * add(n - 1);
}

gcc 3.4.2 -O3 -march=athlon-xp での結果。

_Z3addi:
        pushl   %ebp
        movl    %esp, %ebp
        pushl   %ebx
        subl    $4, %esp
        movl    8(%ebp), %ebx
        cmpl    $1, %ebx
        movl    %ebx, %eax
        jle     .L1
        leal    -1(%ebx), %eax
        movl    %eax, (%esp)
        call    _Z3addi
        imull   %ebx, %eax
.L1:
        addl    $4, %esp
        popl    %ebx
        leave
        ret

うーん、最高に面白くないコードですね。

gcc 4.0.0 -O3 -march=athlon-xp での結果。

_Z3addi:
        pushl   %ebp
        movl    %esp, %ebp
        subl    $40, %esp
        movl    %ebx, -12(%ebp)
        movl    8(%ebp), %ebx
        movl    %esi, -8(%ebp)
        movl    %edi, -4(%ebp)
        cmpl    $1, %ebx
        jle     .L2
        leal    -1(%ebx), %esi
        cmpl    $1, %esi
        jle     .L4
        leal    -2(%ebx), %edi
        cmpl    $1, %edi
        jle     .L6
        leal    -3(%ebx), %eax
        movl    %eax, -36(%ebp)
        decl    %eax
        jle     .L8
        leal    -4(%ebx), %eax
        movl    %eax, -32(%ebp)
        decl    %eax
        jle     .L10
        leal    -5(%ebx), %eax
        movl    %eax, -28(%ebp)
        decl    %eax
        jle     .L12
        leal    -6(%ebx), %eax
        movl    %eax, -24(%ebp)
        decl    %eax
        jle     .L14
        leal    -7(%ebx), %eax
        movl    %eax, -20(%ebp)
        decl    %eax
        jle     .L16
        leal    -8(%ebx), %eax
        movl    %eax, -16(%ebp)
        decl    %eax
        jle     .L18
        leal    -9(%ebx), %eax
        movl    %eax, (%esp)
        call    _Z3addi
        imull   -16(%ebp), %eax
        movl    %eax, -16(%ebp)
.L18:
        movl    -20(%ebp), %eax
        imull   -16(%ebp), %eax
        movl    %eax, -20(%ebp)
.L16:
        movl    -24(%ebp), %eax
        imull   -20(%ebp), %eax
        movl    %eax, -24(%ebp)
.L14:
        movl    -28(%ebp), %eax
        imull   -24(%ebp), %eax
        movl    %eax, -28(%ebp)
.L12:
        movl    -32(%ebp), %eax
        imull   -28(%ebp), %eax
        movl    %eax, -32(%ebp)
.L10:
        movl    -36(%ebp), %eax
        imull   -32(%ebp), %eax
        movl    %eax, -36(%ebp)
.L8:
        imull   -36(%ebp), %edi
.L6:
        imull   %edi, %esi
.L4:
        imull   %esi, %ebx
.L2:
        movl    %ebx, %eax
        movl    -8(%ebp), %esi
        movl    -12(%ebp), %ebx
        movl    -4(%ebp), %edi
        leave
        ret

頑張っている感が出てます。
更にもっと頑張ってみましょう。(あんまり考えずにオプション入れてます)

g++-4.0.0 -O3 -march=athlon-xp -ftree-based-profiling -ftree-dominator-opts -ftree-lrs -ftree-ccp -ftree-ch -ftree-combine-temps -ftree-loop-im -ftree-loop-ivcanon -ftree-loop-linear -ftree-loop-optimize -ftree-vectorize

_Z3addi:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$40, %esp
	movl	%ebx, -12(%ebp)
	movl	8(%ebp), %ebx
	movl	%esi, -8(%ebp)
	movl	%edi, -4(%ebp)
	cmpl	$1, %ebx
	jg	.L22
.L2:
	movl	%ebx, %eax
	movl	-8(%ebp), %esi
	movl	-12(%ebp), %ebx
	movl	-4(%ebp), %edi
	leave
	ret
.L22:
	leal	-1(%ebx), %esi
	cmpl	$1, %esi
	jg	.L23
	imull	%esi, %ebx
	jmp	.L2
.L23:
	leal	-2(%ebx), %edi
	cmpl	$1, %edi
	jg	.L24
	imull	%edi, %esi
.L26:
	imull	%esi, %ebx
	jmp	.L2
	.p2align 4,,7
.L24:
	leal	-3(%ebx), %eax
	movl	%eax, -36(%ebp)
	decl	%eax
	jg	.L25
	imull	-36(%ebp), %edi
(中略)
.L32:
	leal	-9(%ebx), %eax
	movl	%eax, (%esp)
	call	_Z3addi
	imull	-16(%ebp), %eax
	movl	%eax, -16(%ebp)
	jmp	.L18

うぬ、かなりお腹一杯です。果たしてこれって差が出るんでしょうか？

ということで1000!を1000万回実行した結果です。

ということで下手にtree_ssa周りをonにすると痛い目を見るよという結果になりました。がっくし。(T_T)
しかしgcc 4.0.0は賢いなぁと再認識する結果となりました。

可能ならばループに展開してくれると最高なんですけどね。
ちなみにループで実装するとこんな感じ。

あれ？なんかgcc4.0.0負けてますけど...、細かいことは気にしないで寝よう。