コンパイラは、while文とdo-while文に対してどうコード生成するか実験した結果

clang-loop.ll

; ModuleID = 'loop.c'
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

define void @loop_while() nounwind uwtable {
entry:
  %i = alloca i32, align 4
  store i32 0, i32* %i, align 4
  br label %while.cond

while.cond:                                       ; preds = %while.body, %entry
  %0 = load i32* %i, align 4
  %cmp = icmp slt i32 %0, 100
  br i1 %cmp, label %while.body, label %while.end

while.body:                                       ; preds = %while.cond
  call void @g()
  %1 = load i32* %i, align 4
  %inc = add nsw i32 %1, 1
  store i32 %inc, i32* %i, align 4
  br label %while.cond

while.end:                                        ; preds = %while.cond
  ret void
}

declare void @g()

define void @loop_do() nounwind uwtable {
entry:
  %i = alloca i32, align 4
  store i32 0, i32* %i, align 4
  br label %do.body

do.body:                                          ; preds = %do.cond, %entry
  call void @g()
  %0 = load i32* %i, align 4
  %inc = add nsw i32 %0, 1
  store i32 %inc, i32* %i, align 4
  br label %do.cond

do.cond:                                          ; preds = %do.body
  %1 = load i32* %i, align 4
  %cmp = icmp sle i32 %1, 100
  br i1 %cmp, label %do.body, label %do.end

do.end:                                           ; preds = %do.cond
  ret void
}

clang-o0.s

	.file	"loop.c"
	.text
	.globl	loop_while
	.align	16, 0x90
	.type	loop_while,@function
loop_while:                             # @loop_while
	.cfi_startproc
# BB#0:                                 # %entry
	pushq	%rbp
.Ltmp2:
	.cfi_def_cfa_offset 16
.Ltmp3:
	.cfi_offset %rbp, -16
	movq	%rsp, %rbp
.Ltmp4:
	.cfi_def_cfa_register %rbp
	subq	$16, %rsp
	movl	$0, -4(%rbp)
.LBB0_1:                                # %while.cond
                                        # =>This Inner Loop Header: Depth=1
	cmpl	$100, -4(%rbp)
	jge	.LBB0_3
# BB#2:                                 # %while.body
                                        #   in Loop: Header=BB0_1 Depth=1
	callq	g
	movl	-4(%rbp), %eax
	addl	$1, %eax
	movl	%eax, -4(%rbp)
	jmp	.LBB0_1
.LBB0_3:                                # %while.end
	addq	$16, %rsp
	popq	%rbp
	ret
.Ltmp5:
	.size	loop_while, .Ltmp5-loop_while
	.cfi_endproc

	.globl	loop_do
	.align	16, 0x90
	.type	loop_do,@function
loop_do:                                # @loop_do
	.cfi_startproc
# BB#0:                                 # %entry
	pushq	%rbp
.Ltmp8:
	.cfi_def_cfa_offset 16
.Ltmp9:
	.cfi_offset %rbp, -16
	movq	%rsp, %rbp
.Ltmp10:
	.cfi_def_cfa_register %rbp
	subq	$16, %rsp
	movl	$0, -4(%rbp)
.LBB1_1:                                # %do.body
                                        # =>This Inner Loop Header: Depth=1
	callq	g
	movl	-4(%rbp), %eax
	addl	$1, %eax
	movl	%eax, -4(%rbp)
# BB#2:                                 # %do.cond
                                        #   in Loop: Header=BB1_1 Depth=1
	cmpl	$100, -4(%rbp)
	jle	.LBB1_1
# BB#3:                                 # %do.end
	addq	$16, %rsp
	popq	%rbp
	ret
.Ltmp11:
	.size	loop_do, .Ltmp11-loop_do
	.cfi_endproc


	.section	".note.GNU-stack","",@progbits

clang-o1.s

	.file	"loop.c"
	.text
	.globl	loop_while
	.align	16, 0x90
	.type	loop_while,@function
loop_while:                             # @loop_while
	.cfi_startproc
# BB#0:                                 # %entry
	pushq	%rbx
.Ltmp2:
	.cfi_def_cfa_offset 16
.Ltmp3:
	.cfi_offset %rbx, -16
	movl	$100, %ebx
	.align	16, 0x90
.LBB0_1:                                # %while.body
                                        # =>This Inner Loop Header: Depth=1
	callq	g
	decl	%ebx
	jne	.LBB0_1
# BB#2:                                 # %while.end
	popq	%rbx
	ret
.Ltmp4:
	.size	loop_while, .Ltmp4-loop_while
	.cfi_endproc

	.globl	loop_do
	.align	16, 0x90
	.type	loop_do,@function
loop_do:                                # @loop_do
	.cfi_startproc
# BB#0:                                 # %entry
	pushq	%rbx
.Ltmp7:
	.cfi_def_cfa_offset 16
.Ltmp8:
	.cfi_offset %rbx, -16
	movl	$101, %ebx
	.align	16, 0x90
.LBB1_1:                                # %do.body
                                        # =>This Inner Loop Header: Depth=1
	callq	g
	decl	%ebx
	jne	.LBB1_1
# BB#2:                                 # %do.end
	popq	%rbx
	ret
.Ltmp9:
	.size	loop_do, .Ltmp9-loop_do
	.cfi_endproc


	.section	".note.GNU-stack","",@progbits

gcc-o0.s

	.file	"loop.c"
	.text
	.globl	loop_while
	.type	loop_while, @function
loop_while:
.LFB0:
	.cfi_startproc
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$16, %rsp
	movl	$0, -4(%rbp)
	jmp	.L2
.L3:
	call	g
	addl	$1, -4(%rbp)
.L2:
	cmpl	$99, -4(%rbp)
	jle	.L3
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE0:
	.size	loop_while, .-loop_while
	.globl	loop_do
	.type	loop_do, @function
loop_do:
.LFB1:
	.cfi_startproc
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$16, %rsp
	movl	$0, -4(%rbp)
.L5:
	call	g
	addl	$1, -4(%rbp)
	cmpl	$100, -4(%rbp)
	jle	.L5
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE1:
	.size	loop_do, .-loop_do
	.ident	"GCC: (Ubuntu 4.8.2-19ubuntu1) 4.8.2"
	.section	.note.GNU-stack,"",@progbits

gcc-o1.s

	.file	"loop.c"
	.text
	.globl	loop_while
	.type	loop_while, @function
loop_while:
.LFB0:
	.cfi_startproc
	pushq	%rbx
	.cfi_def_cfa_offset 16
	.cfi_offset 3, -16
	movl	$100, %ebx
.L3:
	call	g
	subl	$1, %ebx
	jne	.L3
	popq	%rbx
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE0:
	.size	loop_while, .-loop_while
	.globl	loop_do
	.type	loop_do, @function
loop_do:
.LFB1:
	.cfi_startproc
	pushq	%rbx
	.cfi_def_cfa_offset 16
	.cfi_offset 3, -16
	movl	$101, %ebx
.L7:
	call	g
	subl	$1, %ebx
	jne	.L7
	popq	%rbx
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE1:
	.size	loop_do, .-loop_do
	.ident	"GCC: (Ubuntu 4.8.2-19ubuntu1) 4.8.2"
	.section	.note.GNU-stack,"",@progbits

gfortran-o0.s

	.file	"loop.f90"
	.text
	.type	MAIN__, @function
MAIN__:
.LFB0:
	.cfi_startproc
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$16, %rsp
	movl	$1, -4(%rbp)
	cmpl	$100, -4(%rbp)
	jg	.L1
.L3:
	movl	$0, %eax
	call	g_
	cmpl	$100, -4(%rbp)
	sete	%al
	movzbl	%al, %eax
	addl	$1, -4(%rbp)
	testl	%eax, %eax
	jne	.L1
	jmp	.L3
.L1:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE0:
	.size	MAIN__, .-MAIN__
	.globl	main
	.type	main, @function
main:
.LFB1:
	.cfi_startproc
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$16, %rsp
	movl	%edi, -4(%rbp)
	movq	%rsi, -16(%rbp)
	movq	-16(%rbp), %rdx
	movl	-4(%rbp), %eax
	movq	%rdx, %rsi
	movl	%eax, %edi
	call	_gfortran_set_args
	movl	$options.0.1885, %esi
	movl	$7, %edi
	call	_gfortran_set_options
	call	MAIN__
	movl	$0, %eax
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE1:
	.size	main, .-main
	.section	.rodata
	.align 16
	.type	options.0.1885, @object
	.size	options.0.1885, 28
options.0.1885:
	.long	68
	.long	1023
	.long	0
	.long	0
	.long	1
	.long	1
	.long	0
	.ident	"GCC: (Ubuntu 4.8.2-19ubuntu1) 4.8.2"
	.section	.note.GNU-stack,"",@progbits

gfortran-o1.s

	.file	"loop.f90"
	.text
	.globl	main
	.type	main, @function
main:
.LFB1:
	.cfi_startproc
	pushq	%rbx
	.cfi_def_cfa_offset 16
	.cfi_offset 3, -16
	call	_gfortran_set_args
	movl	$options.0.1885, %esi
	movl	$7, %edi
	call	_gfortran_set_options
	movl	$100, %ebx
.L3:
	movl	$0, %eax
	call	g_
	subl	$1, %ebx
	jne	.L3
	movl	$0, %eax
	popq	%rbx
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE1:
	.size	main, .-main
	.section	.rodata
	.align 16
	.type	options.0.1885, @object
	.size	options.0.1885, 28
options.0.1885:
	.long	68
	.long	1023
	.long	0
	.long	0
	.long	1
	.long	1
	.long	0
	.ident	"GCC: (Ubuntu 4.8.2-19ubuntu1) 4.8.2"
	.section	.note.GNU-stack,"",@progbits

loop.c

extern void g(void);

void loop_while() {
  int i = 0;
  while (i < 100) {
    g();
    i++;
  }
}

void loop_do() {
  int i = 0;
  do {
    g();
    i++;
  } while (i <= 100);
}

loop.f95

      program do_loop
        implicit none
        external g
        integer i
        do i=1,100
         call g()
        end do
      end program do_loop

opt -S -instcombine -loop-rotate -stats loop.ll

; ModuleID = 'loop.ll'
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

define void @loop_while() nounwind uwtable {
entry:
  %i = alloca i32, align 4
  store i32 0, i32* %i, align 4
  br label %while.body

while.body:                                       ; preds = %entry, %while.body
  call void @g() nounwind
  %0 = load i32* %i, align 4
  %inc = add nsw i32 %0, 1
  store i32 %inc, i32* %i, align 4
  %cmp = icmp slt i32 %inc, 100
  br i1 %cmp, label %while.body, label %while.end

while.end:                                        ; preds = %while.body
  ret void
}

declare void @g()

define void @loop_do() nounwind uwtable {
entry:
  %i = alloca i32, align 4
  store i32 0, i32* %i, align 4
  br label %do.body

do.body:                                          ; preds = %do.cond, %entry
  call void @g() nounwind
  %0 = load i32* %i, align 4
  %inc = add nsw i32 %0, 1
  store i32 %inc, i32* %i, align 4
  br label %do.cond

do.cond:                                          ; preds = %do.body
  %1 = load i32* %i, align 4
  %cmp = icmp slt i32 %1, 101
  br i1 %cmp, label %do.body, label %do.end

do.end:                                           ; preds = %do.cond
  ret void
}
===-------------------------------------------------------------------------===
                          ... Statistics Collected ...
===-------------------------------------------------------------------------===

6 instcombine - Number of insts combined
1 loop-rotate - Number of loops rotated

観察してわかること：

• gccでは一度下に無条件分岐した上で、jneで前方へ条件分岐することでループを実現している
• clangの-O0では先頭に条件分岐があり、ループのbody末尾にジャンプが付いているので、わずかに非効率なはず
• clangにおいてもloop-rotateをかけると効率的なループになってくれる

ここから推測できること。なぜそうなっているか：

• gccでは最適化なしでも、事前の枠組みとして前方への条件分岐の形に当てはめている
  • この場合では無駄なジャンプ命令が残る
  • 「ループの構造として条件分岐では前方分岐を使う」という知識が共有されており、CPUでの実行も効率がよかったから？
  • FortranのDO文由来かもしれない
• Clangはもっと素直な変換をしているように見える
• いずれの場合でも、このような単純なループの場合はloop rotateがうまく効いてくれて、効率の悪さは無い

gfortranで似たようなループを書いてみたが、jneとjmpを使った、またちょっと違う感じのコードを生成した。

全体として想像できる流れとしては、こんな感じだろうか。

1. FortranのDO文については、は前方分岐するコードを生成するのが最も効率がよい
2. CPUもそれに合わせて、前方分岐を効率よく実行するように分岐予測などを調整している？
   • 参考：http://news.mynavi.jp/column/architecture/167/
3. while文についても前方分岐をするようにコードが生成されるようになった
4. 最適化される場合は、分岐の方向だけでなく分岐命令の個数的な観点でも、loop rotateができるならその方がよい

それっぽいような、なんか嘘っぽいような。

いや、そもそもループを構成する場合に下から前方分岐をするのが最も効率が良いのは当たり前だ。
最適化とか関係ない。

• むしろGCCのコード生成が自然で、既にループに関する知識が入っている。
• Clangは単純な制御フローグラフをそのまま変換したようなコード生成をする。効率の良さは最適化に求める

ぐらいかなあ。