GCCのインラインアセンブラと間接分岐

Ruby

この記事を書いている途中に@miura1729さんがmrubyにインラインメソッドキャッシュを実装したという発言が。
https://github.com/miura1729/mruby/commit/ed3ef94a4a50946dfe237c27d53375cc4e31ca84
インラインメソッドキャッシュというのは命令列の中にメソッド検索の結果を書き込んで、次の呼び出しはその情報を利用してメソッド検索を省くテクニックだ。Ruby1.9のVMにも実装されている。
ただ、Rubyではメソッドを動的に書き換えることができるため、インラインメソッドキャッシュの内容が古くなってしまうと使えない。その判定や更新についてはコードをざっと見た限りは実装されていないっぽいので、実際に取り込まれるまでにはもうちょっといじる必要があるだろう。
いつか可変長OP_SENDを実装したらインラインメソッドキャッシュもついでに、と思っていたので先を越された感が。
でもまあ、俺は俺で地味にやる。

今回は間接分岐の予測対策をインラインアセンブラで実現してみる話。


いままでOP_MOVEのアセンブラをブログに貼ることがあったが、あれは途中のjmp命令を省いて繋げたものだ。なぜjmpがはさまるかと言うと、GCCがNEXTルーチンを共有化してそこに飛ばしているからである。
手元のやつをコンパイルするとこんなかんじになる。

L24:
LBB370:
	.loc 1 455 0
	movl	%ebx, %eax
	shrl	$23, %eax
	.loc 1 458 0
	sall	$4, %eax
	addl	-768(%ebp), %eax
	.loc 1 456 0
	shrl	$10, %ebx
LVL278:
	.loc 1 458 0
	andl	$8176, %ebx
	movl	-768(%ebp), %edx
	addl	%ebx, %edx
	movb	8(%edx), %cl
	movb	%cl, 8(%eax)
	.loc 1 459 0
	movl	4(%edx), %ecx
	movl	(%edx), %edx
	movl	%edx, (%eax)
	movl	%ecx, 4(%eax)
	jmp	L423

L423:
LBB332:
	.loc 1 1612 0
	addl	$4, -764(%ebp)
L427:
	movl	-764(%ebp), %eax
	movl	(%eax), %ebx
LVL150:
	movl	%ebx, %eax
	andl	$127, %eax
	movl	_optable.3821(,%eax,4), %eax
LBE332:
	.loc 1 444 0
	jmp	*%eax

L423というのがNEXTルーチンのラベルで、他の命令からもここに飛び込んでくる。GCCはgotoを見つけると必ず飛ぶと認識するようで、gotoが飛ばなかったら、という想定はしない。従って、goto直前のロジックが共通だったらそのあたりをまとめて共有化してしまう。これはただでさえ効率の悪い間接分岐をさらに遅くする。と想像する。
これを抑止する。手段はインラインアセンブラである。GCCはインラインアセンブラを見つけるとユーザーが何かしらのコードをそこに突っ込んだと認識する。中身は見ない。なので、NEXTルーチン内にインラインアセンブラが存在すれば共有化することはできない。具体的にはvm.cのマクロをこのように変更する。

//#define NEXT i=*++pc; goto *optable[GET_OPCODE(i)]
//#define JUMP i=*pc; goto *optable[GET_OPCODE(i)]
#define NEXT i=*++pc; asm (""); goto *optable[GET_OPCODE(i)]
#define JUMP i=*pc; asm (""); goto *optable[GET_OPCODE(i)]
L24:
LBB366:
	.loc 1 457 0
	movl	%ebx, %eax
	shrl	$23, %eax
	.loc 1 460 0
	sall	$4, %eax
	addl	-768(%ebp), %eax
	.loc 1 458 0
	shrl	$10, %ebx
LVL298:
	.loc 1 460 0
	andl	$8176, %ebx
	movl	-768(%ebp), %edx
	addl	%ebx, %edx
	movb	8(%edx), %cl
	movb	%cl, 8(%eax)
	.loc 1 461 0
	movl	4(%edx), %ecx
	movl	(%edx), %edx
	movl	%edx, (%eax)
	movl	%ecx, 4(%eax)
	.loc 1 465 0
	addl	$4, -764(%ebp)
	movl	-764(%ebp), %eax
	movl	(%eax), %ebx
LVL299:
	movl	%ebx, %eax
	andl	$127, %eax
	movl	_optable.3821(,%eax,4), %eax
LBE366:
	.loc 1 446 0
	jmp	*%eax

途中のjmpがなくなった。インラインアセンブラは中身からっぽだが、GCCは中身を見ないので、実際には何も無いのにNEXTルーチンが共有化できなくなる。
ではこれで間接分岐のBTBが分散して、予測効率が上がるか。

D:\test>mruby test.rb
2.03125

理屈では上がっても良さそうなのだが、まったく速くなっていない。
ところでGCCはgotoを見つけると必ずジャンプするとみなすので、アセンブラを命令単位で貼っているだけではわからないが、全体を見ると命令順は勝手に並び替えられてしまっている。命令を呼び出しパターンにあわせて並び替えてもこれでは静的予測のフォールスルーは期待できない。その対策もあるにはあるが、そもそもmrubyは小さいのでBTBがあふれる気がしない。この状況では静的予測の分岐については検証できない。

さて、なにはともあれ間接分岐が速くなっていないというのはわかった。なぜ速くなっていないのかはさっぱりわからないが、解明するためのヒントぐらいはつかんでおこう。
たとえばVM命令のうち、ある命令Aの次は別の命令Bだと100%いえるパターンがあれば、その間接分岐を固定の分岐に置き換えることで、速くなるか変わらないかを知ることができる。変わらないなら関節分岐予測はもともと高確率で当たっていたと言える。速くなるようだと間接分岐は分散させたのに予測がはずれまくっている、もしくはそもそも予測されていない。と言える。
問題はそのようなVM命令があるかという話なのだが、困ったことに思いつかない。一時的な実験ということで、ベンチ用コードで100%成り立つパターンを使うことにする。

irep 150 nregs=6 nlocals=4 pools=0 syms=3
000 OP_ENTER    0:0:0:0:0:0:1
001 OP_LOADI    R2      0
002 OP_JMP              012
003 OP_MOVE     R4      R1
004 OP_MOVE     R5      R2
005 OP_LOADNIL  R6
006 OP_SEND     R4      :call   1
007 OP_MOVE     R4      R2
008 OP_LOADI    R5      1
009 OP_LOADNIL  R6
010 OP_ADD      R4      :+      1
011 OP_MOVE     R2      R4
012 OP_MOVE     R4      R2
013 OP_LOADSELF R5
014 OP_LT       R4      :<      1
015 OP_JMPIF    R4      003
016 OP_LOADSELF R4
017 OP_RETURN   R4

いつものtimesだが、OP_JMPの次は確実にOP_MOVEである。他の部分にはOP_JMPは無い（はず）ので、これを使おう。
OP_JMPの命令を修正する。

    CASE(OP_JMP) {
      /* sBx    pc+=sBx */
      pc += GETARG_sBx(i);
//      JUMP;
      i=*pc;
      if (GET_OPCODE(i) != OP_MOVE) {
        goto *optable[GET_OPCODE(i)];
      }
      else{
        goto L_OP_MOVE;
      }
    }

固定でOP_MOVEに飛ぶようにしたらコケるのでたぶんmrblibにOP_JMPを使うやつがいるのだろう。しょうがないので条件を見て分岐した。
結果。

D:\test>mruby test.rb
2.046875

速くなっていない。っていうかやや遅い。固定ジャンプが遅くなるということは条件分岐の負荷(予測はヒットするので微々たるもの)が増えているせいだろう。つまり、間接分岐の予測は働いていて、ヒットしていた。
分岐を分散させて速くならなかったのは、何かしら別の要因で遅くなっている部分が存在しているからだ、と言える。
「何かしらの別の要因」が核心の問題だが、それはいまのところわからない。ここまで調べておけばそのうち何かの拍子にひらめくこともあるだろう。

追記：よく見たらOP_JMPは1回しか動いていないのでこれぜんぜん実験になってない。こんど改めて試すことにする。まえに条件分岐を突っ込んだOP_SENDは確かに効果があったから、OP_SENDでやってみるのがいいような気がする。
ということでやってみたところ、速くなった。結果は逆だ。固定ジャンプが速くなるということは、間接分岐の予測がまったく役に立ってないということだ。これはAMDのCPUだからなのか、どこかに落とし穴があるのか。機会があったら調べてみよう。