コンパイラの最適化とは？

最近のCコンパイラは、プログラマが意図して行った最適化よりも賢く、

最適なコードを生成するといいます。

昔「2の倍数で割るなら割り算使うより、シフト演算の方が早いからそう書け！」と言われたことがあります。確かに、div命令とsar命令ではクロック数はdiv命令の方が遥かに多かったと思いますが、実際のところそこまで意識する必要があるのでしょうか？

と、思いつつシフト演算を使っていたんですが、コンパイラの出力するコードを見る事はありませんでした。そこで実際にどの程度のものなのかを実験してみました。

関連記事：

• コンパイラの最適化によるデメリット
• 暗黙の型変換と符号拡張とは？
• NULL文字を含むときはstrcmp/strncmpを使わない

環境は

Microsoft Windows Vista(32bit)

Microsoft VisualStudio.Net(2002)

※載せてあるコードは必要な部分だけを抜き出してあります。このままではアセンブルできません

割り算の最適化

test01.c

#include <stdio.h>

int main(void)
{
	int numA = 128;

	int numB = numA / 2;

	return 0;
}

上記のコードをアセンブリ言語を出力しつつコンパイルしてみましょう。

cl /FA test01.c

すると、test01.asmができるはずです。

テキストエディタで開くとアセンブリ言語でのソースが記述されています。

ここで注目するのは14行目の; Line 7以降の部分です。

PUBLIC	_main
; Function compile flags: /Odt
_TEXT	SEGMENT
_numA$ = -8
_numB$ = -4
_main	PROC NEAR
; File x:devworkcasmtest01.c
; Line 4
	push	ebp
	mov	ebp, esp
	sub	esp, 8
; Line 5
	mov	DWORD PTR _numA$[ebp], 128		; 00000080H
; Line 7
	mov	eax, DWORD PTR _numA$[ebp]
	cdq
	sub	eax, edx
	sar	eax, 1
	mov	DWORD PTR _numB$[ebp], eax
; Line 10
	xor	eax, eax
; Line 11
	mov	esp, ebp
	pop	ebp
	ret	0
_main	ENDP
_TEXT	ENDS
END

mov	eax, DWORD PTR _numA$[ebp]
cdq
sub	eax, edx
sar	eax, 1
mov	DWORD PTR _numB$[ebp], eax

sar命令で1ビット右にシフトしています。

なるほど。確かにコンパイラが

int numB = numA / 2;

の部分をシフト演算に置き換えてくれています。

最適化がかかっていますね。

人がシフト演算するより、明示的に割ると書いた方が、幾分可読性があがります。

いまやこのような小手先テクニックは必要ないのかもしれません。

最適化レベル最高時の動作

次にコンパイラの最適化レベルを最高に上げた時のソースを見てみましょう。

cl /FA /O2 test01.c

出力されたコードを見てみると・・・

PUBLIC	_main
; Function compile flags: /Ogty
;	COMDAT _main
_TEXT	SEGMENT
_main	PROC NEAR					; COMDAT
; File x:devworkcasmtest01.c
; Line 10
	xor	eax, eax
; Line 11
	ret	0
_main	ENDP
_TEXT	ENDS
END

まいりました。割り算部分どころか、mainの直後にreturnして終わっています。

確かに変数numAやnumBはどこからも使用されていないので、そもそも計算する必要ないですね。

では、割り算後の変数が使用される場合はどのように最適化されるのでしょうか？コードを以下のように変更します。

#include <stdio.h>

int main(void)
{
	int numA = 128;

	int numB = numA / 2;

	printf("result=%dn", numB);
	return 0;
}

では最適化レベルを最高に上げて、コンパイルします。

cl /FA /O2 test01.c

生成されたコードは・・・

PUBLIC	_main
PUBLIC	??_C@_0L@IPKPMLPK@result?$DN?$CFd?6?$AA@	; `string'
EXTRN	_printf:NEAR
;	COMDAT ??_C@_0L@IPKPMLPK@result?$DN?$CFd?6?$AA@
; File x:devworkcasmtest01.c
CONST	SEGMENT
??_C@_0L@IPKPMLPK@result?$DN?$CFd?6?$AA@ DB 'result=%d', 0aH, 00H ; `string'
; Function compile flags: /Ogty
CONST	ENDS
;	COMDAT _main
_TEXT	SEGMENT
_main	PROC NEAR					; COMDAT
; Line 9
	push	64					; 00000040H
	push	OFFSET FLAT:??_C@_0L@IPKPMLPK@result?$DN?$CFd?6?$AA@
	call	_printf
	add	esp, 8
; Line 10
	xor	eax, eax
; Line 11
	ret	0
_main	ENDP
_TEXT	ENDS
END

さっきより複雑になりましたが、注目する点は13行目の; Line 9の部分です。ここでは関数呼び出しの前に引数の2つをスタックに積んで、printf関数を呼び出しています。

	push	64					; 00000040H
	push	OFFSET FLAT:??_C@_0L@IPKPMLPK@result?$DN?$CFd?6?$AA@
	call	_printf

はい。既に128/2は計算済みです。

余計な計算は可能な限りコンパイル時に済ませて、無駄なステップを省いていますね。

ちなみに

if(numB == 64) {
	printf("result=%dn", numB);
}

と書き換えたところで、結果は同じです。

容易に(?)計算可能なレベルで、省略できるものは全てなくしてコンパイルしています。

インラインアセンブラを含んだコードの場合

さて、一方インラインアセンブラで記述するとコンパイラのオプティマイズがかからない(かかりにくく)なる

と言われています。

それも実際に動作を見てみます。

下記のコードは内容は最初のものと同じなのですが、使う命令の都合上ステップ数が多くなっています。

実は、ワザと多くしています。

例えば、割り算命令のidivはオペランドにはメモリ(変数numB)を指定できるのにもかかわらず、あえてレジスタ(ebx)を使っています。

また、idiv命令の都合上アキュムレータ(eax)に割られる数の変数を代入しなければいけないので、movで事前に代入しています。

さらに、符号ありの割り算なので、cdqを事前に行っています。

test02.c

int main(void)
{
	int numA, numB;

	__asm {
		mov numA, 128
		xor edx, edx
		mov eax, numA
		mov ebx, 2
		cdq
		idiv ebx
		mov numB, eax
	}
	return 0;
}

これをコンパイルしてみます。

cl /FA test02.c

すると、C言語で割り算をしていた時はシフト命令に最適化されていた箇所が、インラインアセンブラで書いたそのままになっています。

※変数部分は若干記述が変わっていますが、意味は同じです

PUBLIC	_main
; Function compile flags: /Odt
_TEXT	SEGMENT
_numA$ = -8
_numB$ = -4
_main	PROC NEAR
; File x:devworkcasmtest02.c
; Line 2
	push	ebp
	mov	ebp, esp
	sub	esp, 8
	push	ebx
; Line 6
	mov	DWORD PTR _numA$[ebp], 128		; 00000080H
; Line 7
	xor	edx, edx
; Line 8
	mov	eax, DWORD PTR _numA$[ebp]
; Line 9
	mov	ebx, 2
; Line 10
	cdq
; Line 11
	idiv	ebx
; Line 12
	mov	DWORD PTR _numB$[ebp], eax
; Line 14
	xor	eax, eax
; Line 15
	pop	ebx
	mov	esp, ebp
	pop	ebp
	ret	0
_main	ENDP
_TEXT	ENDS

全く最適化されていません。

では次に最適化レベルを最高にしてコンパイルしてみます。先ほどは不必要と判断されてコードが丸ごと切り取られましたが、今回はどうでしょうか。

cl /FA /O2 test02.c

結果は、8～9行目の; Line2の初期化が若干変わったのと

変数のアクセスがベースポインタ(ebp)からスタックポインタ(esp)に変わっただけでした。

実際の割り算処理のステップ数は全く変わっていません。

PUBLIC	_main
; Function compile flags: /Ogty
;	COMDAT _main
_TEXT	SEGMENT
_numA$ = -8
_numB$ = -4
_main	PROC NEAR					; COMDAT
; File x:devworkcasmtest02.c
; Line 2
	sub	esp, 8
	push	ebx
; Line 6
	mov	DWORD PTR _numA$[esp+12], 128		; 00000080H
; Line 7
	xor	edx, edx
; Line 8
	mov	eax, DWORD PTR _numA$[esp+12]
; Line 9
	mov	ebx, 2
; Line 10
	cdq
; Line 11
	idiv	ebx
; Line 12
	mov	DWORD PTR _numB$[esp+12], eax
; Line 14
	xor	eax, eax
	pop	ebx
; Line 15
	add	esp, 8
	ret	0
_main	ENDP
_TEXT	ENDS
END

まとめ

以上のことから割り算をあえてシフト演算で代用する等、小手先の最適化を行ったりインラインアセンブラを使ったりせずに、C言語の一般的なの書き方でプログラムを書いても、コンパイル後は自分で行う最適化と同等かそれ以上の最適化が自動でかかります。

ソースの可読性を上げるためにも普通に書くのが一番だと思います。

もし速度を求めるならコンパイラ・CPUの特性を学んでからプログラムを書かないと、殆どのケースにおいてコンパイラの最適化に負けてしまいそうです。

余談

下記の記事を見ると、最近のCPUは従来のものよりも高速な除算器を積んでるみたいです。

「割り算=遅い」というのも、近い未来には都市伝説となるかもしれません。

【インテルが定例アップデート、Penrynの実機動作デモのほかNehalemの話題も】

Wide Dynamic Execution : 4命令/1クロックは変わらない。除算器が高速化される。Penrynでは2進数で4bitの計算を処理する除算器回路(Radix-16 Divider)を搭載するが、Core 2 Duoでは2bitの除算器回路(Radix-4 Divider相当)を搭載していたという。また、Virtualization Technology(VT)も拡張版を搭載する。

関連記事：

• コンパイラの最適化によるデメリット
• 暗黙の型変換と符号拡張とは？
• NULL文字を含むときはstrcmp/strncmpを使わない