2006-08-16

http://www.pqrs.org/~tekezo/nikki/2006/08/15.html#y2006m08d15c1p2
なんだか面白そうなので調査。

まず、予想としては、中間形式での最適化時に__builtin_expectがただの関数扱いされて、最適化を控えているのではないかと思われます。

if ( bi == NULL ) の場合、副作用が無いとわかるので、なんか最適化をする
if ( __builtin_expect( bi==NULL, 0 ) ) は、中間形式の状態では、副作用があるか無いかわからんので最適化を控える

と、そういう感じではないかと。この場合だと、if ( bi == NULL )のほうは、ループ用の最適化をしてて、__builtin_expectのほうはそれをやってない感じですかね。

ループが変形してるのは、ループ脱出条件の最適化としては、結構簡単にできる有名な奴ではないかと思われます。

while ( cond ) {
	....
	loop_body;
	....
}

ていうのは、普通にコンパイルすれば

	...

loop_begin:
	cmp	cond
	jcc	exit

loop_body:
	... ( ループ内処理 )

	jmp	loop_begin

exit:
	...

こんな感じ。ですが、これを

	jmp	loop_cond
loop_body:
	... ( ループ内処理 )

loop_cond
	cmp	cond
	jcc	loop_body # 条件ジャンプを後ろにする

exit:
	...

こんな風にしてやれば、ループ中の分岐が「条件分岐 + 無条件」から、「条件分岐一個」に減らせます。
と、思ったけど、よく見てみたら、continueがあるのでなんか違うような気がしてきましたが、「通常時」のほうの、eaeの前の命令が、「b ec6」もしくは、「NULLチェックしてループ処理飛ばす」みたいな感じだと、なんかそれに近いことをやってるんだと思います。(適当)

ただ、この最適化をやるには、「どこらへんがループで、どれが脱出条件か」というのを見つけないというのがあって、__builtin_expectを使ったほうは、多分、そこらへんができてないのではないかと。

対処法としては、手元にあった、GCC4.1の場合、

for ( ; __builtin_expect(nanika!=NULL,1); ) {
	// ループ処理
}

こんなふうにしてやれば、Cフロントエンドが「forループ→中間形式」変換時に上のループ最適化をやってくれるようなのでなんとかなるようです。

（うーん…ていうことは、多少汚くなっても無理矢理forとかwhile使ったほうがいいってことなのか…？僕はbreak使うほうが好きなんだけど…）

あと、__builtin_expectは、PowerPCみたいな条件分岐に命令に直接分岐ヒント付けられるCPUじゃないとあんまり効果が無いような気がしたんですが、そこらへんは、誰か偉い人が。

w_o’s diary

■

builtin_expect