SEA & FSIJ 合同フォーラムでビット演算による最適化の妙味とJITアセンブラの中でデモに使ったVMを紹介します．
JITの紹介のために前日に2時間ででっちあげたVMなので本当に小さい(200行程度)ですが，エッセンスは楽しめるかなと思います．
ソースはXbyak.zipです．この中のxbyak/sample/toyvm.cppが今回作ったVMです(Win, Linuxと多分Intel Macでも動きます)．
このサンプルはフィボナッチ数列を計算して表示するだけのものです．
ここではどのように作ったかの説明をします．一つ前のエントリの資料も参考にしてください．
話の流れ
- toyVMのスペック，命令セットと命令フォーマットを決める
- toyVMのアセンブラを作る
- toyVMの実行部分を作る
- toyVM用のフィボナッチ数列プログラムを作って実行する
- toyVMのマシン語をx86に変換するリコンパイラを作る
- パフォーマンスを見る
- リコンパイラを改良する
1. toyVMのスペックを決める
高性能なVMを作りたいかもしれませんが，そこは本質ではないのでざくっと簡単なものを考えます．
スタックベースかレジスタベースかなどの議論もあるのでしょうが，なんとなくレジスタベースにしました．
- 32bitレジスタA, Bの二つ．あとPC(program counter)
- メモリは4byte単位のみでのアクセス．4byte x 65536
- すべての命令は4byte固定
- 即値は全て16bit
スタックはばっさり捨てました．また命令長を4byte固定にすることで実行部が簡単になります．
またその結果必然的に即値は32bit未満となり，四つ目の条件をつけました．
命令群は次のものを用意しました．
| 命令(R = A or B) | 意味 |
|---|
| vldiR, imm | R = imm |
|---|
| vldR, idx / vstR, idx | R = mem[idx] / mem[idx] = R |
|---|
| vaddiR, imm / vsubiR imm | R += imm / R -= imm |
|---|
| vaddR, idx / vsubR, idx | R += mem[idx] / R -= mem[idx] |
|---|
| vputR | print R |
|---|
| vjnzR, offset | if (R != 0) then jmp(PC += offset(signed)) |
|---|
メモリとレジスタの間の転送命令と加算，減算命令にレジスタの内容を出力する命令と，分岐命令だけです．
スタックが無いのでcall/retもありません．興味があれば自分で作ってみるのもよいかもしれません．
命令は4byteのうち先頭1byteに命令種別(code)，次の1byteにレジスタ種別(r)，最後の2byteに即値(imm)を入れることにします．
使われない場合は全て0にします．(code, r, imm)のペアと4byteデータの変換方法は次のようにします．簡単ですね．
void decode(uint32& code, uint32& r, uint32& imm, uint32 x)
{
code = x >> 24;
r = (x >> 16) & 0xff;
imm = x & 0xffff;
}
void encode(Code code, Reg r, uint16 imm = 0)
{
uint32 x = (code << 24) | (r << 16) | imm;
code_.push_back(x);
}
2. toyVMのアセンブラを作る
アセンブラを作るといっても，外部ファイルに書いたものを読み込んでパースして，というのはまた大変なのでCの関数として作って関数を呼び出すことがアセンブルすること，としました．
そうすると，パーサをざっくりCコンパイラに任せられるので極めて簡単になります．上で定義したencode()を呼び出す関数を作れば終わりです．
void vldi(Reg r, uint16 imm) { encode(LDI, r, imm); }
void vld(Reg r, uint16 idx) { encode(LD, r, idx); }
void vst(Reg r, uint16 idx) { encode(ST, r, idx); }
void vadd(Reg r, uint16 idx) { encode(ADD, r, idx); }
void vaddi(Reg r, uint16 imm) { encode(ADDI, r, imm); }
void vsub(Reg r, uint16 idx) { encode(SUB, r, idx); }
void vsubi(Reg r, uint16 imm) { encode(SUBI, r, imm); }
void vjnz(Reg r, int offset) { encode(JNZ, r, static_cast(offset)); }
void vput(Reg r) { encode(PUT, r); }
3. toyVMの実行部分を作る
上で書き忘れましたが，アセンブルした結果はstd::vector
code_;に格納させる実装にしました．
実行部というのはこのcode_内に入っている命令セットを順次呼び出して実行するだけのものになります．
void run()
{
uint32 reg[2] = { 0, 0 }; // A, B
const uint32 end = code_.size();
uint32 pc = 0;
for (;;) {
uint32 code, r, imm;
decode(code, r, imm, code_[pc]);
switch (code) {
...
}
pc++;
if (pc >= end) break;
} // for (;;)
}
基本構造は上記のようになります．
pc(プログラムカウンタ)を0から順に増やしつつ，4byteずつcode_からデータを読みます．
読んだデータをdecode()でパラメータに分解し，codeに従って各命令を実行させるswitch文に突入します．
そのあとpcを一つ増やして繰り返します．
switch文の中身は各命令に対して実際行う処理を書きます．
switch (code) {
case LDI:
reg[r] = imm;
break;
case LD:
reg[r] = mem_[imm];
break;
case ST:
mem_[imm] = reg[r];
break;
case ADD:
reg[r] += mem_[imm];
break;
case ADDI:
reg[r] += imm;
break;
case SUB:
reg[r] -= mem_[imm];
break;
case SUBI:
reg[r] -= imm;
break;
case PUT:
printf("%c %8d(0x%08x)\n", 'A' + r, reg[r], reg[r]);
break;
case JNZ:
if (reg[r] != 0) pc += static_cast<signed short>(imm);
break;
default:
assert(0);
break;
}
とくに難しいところは無いでしょう．これでVM自体は完成です．なんと簡単．
4. toyVM用のフィボナッチ数列プログラムを作って実行する
VMを作ったのでその上で動かすプログラムを作ります．
フィボナッチと言えばちまたではやる再帰ですが，このVMにはスタックが無いのでそんなことはやってられません(苦笑)．
#一応メモリはあるので，このスタックを実装することは可能かもしれませんが…．
素直にループで書きます．for()を使うと分かりにくくなるのでgotoを使います．
まずCで書いてみましょう．
void fibC(uint32 n)
{
uint32 p, c, t;
p = 1;
c = 1;
lp:
t = c;
c += p;
p = t;
n--;
if (n != 0) goto lp;
printf("c=%d(0x%08x)\n", c, c);
}
このコードが正しく動作することを確認したら，これをtoyVMのアセンブリ言語で書きます．
その前に変数をどう扱うかを決めておく必要があります．
toyVMにレジスタは二つありますが，両方をフィボナッチで使う変数に割り当てると困るのでとりあえずcをAレジスタに割り当てることにします．
Bはテンポラリに残しておきましょう．
あと，fibCにはp, t, nという変数があるのでこれらはtoyVMのメモリ上に置くことにします．
ここではmem[0] : p, mem[1] : t, mem[2] : nとしました．
ではfibCのアセンブリ言語版を書きます．
Fib(int n)
{
vldi(A, 1); // c = 1
vst(A, 0); // p = 1
vldi(B, n);
vst(B, 2); // n
// lp
vst(A, 1); // t = c
vadd(A, 0); // c += p
vld(B, 1); // mem[1]の値をBを経由してmem[2]に移動する
vst(B, 0); // p = t
vld(B, 2);
vsubi(B, 1);
vst(B, 2); // n--
vjnz(B, -8); // PCを8減らせばlpのところにもどる．
vput(A);
}
ちょっと分かりにくいかもしれませんが，1行ずつfibCと比べれば同じ処理をしようとしていることがわかるでしょう．
実行してみます．
Fib fib(10);
fib.run();
>A 144(0x00000090)
正しく動作しているようです．
5. toyVMのマシン語をx86に変換するリコンパイラを作る
ここからが昨日の本題です．上記のFib(1000)を実行するとcode_上にVM用のマシン語が展開されて，run()で実行しているわけですが，そのマシン語をx86ネイティブなものに変換しましょう．
そうすればきっと高速に動作するようになるはずです．
recompile()のためにXbyakを使います．
まずtoyVMをx86上でどのように実装するかを考えます．レジスタはA, Bの二つなので適当なレジスタに割り当てましょう．
ここではA = esi, B = ediとしました．またmem_へのアクセスに使うレジスタをebxにします．
リコンパイルはcode_を読み込んでdeocde()し，switch()して順次実行するというrun()とほぼ同じ形をとります．
void recompile()
{
push(ebx);
push(esi);
push(edi);
const Reg32 reg[2] = { esi, edi };
const Reg32 mem(ebx);
xor(reg[0], reg[0]);
xor(reg[1], reg[1]);
mov(mem, (int)mem_);
const uint32 end = code_.size();
uint32 pc = 0;
uint32 labelNum = 0;
for (;;) {
uint32 code, r, imm;
decode(code, r, imm, code_[pc]);
L(toStr(labelNum++));
switch (code) {
...
pc++;
if (pc >= end) break;
} // for (;;)
pop(edi);
pop(esi);
pop(ebx);
ret();
違うのはx86用のコードを生成させるところです．と言っても見た目はそれほど変わりません．
switch (code) {
case LDI:
mov(reg[r], imm);
break;
case LD:
mov(reg[r], ptr[mem + imm * 4]);
break;
case ST:
mov(ptr [mem + imm * 4], reg[r]);
break;
case ADD:
add(reg[r], ptr [mem + imm * 4]);
break;
case ADDI:
add(reg[r], imm);
break;
case SUB:
sub(reg[r], ptr [mem + imm * 4]);
break;
case SUBI:
sub(reg[r], imm);
break;
概ねrun()と一対一に対応していることがわかるでしょう．分岐のみちょっと変わったことをする必要があります．
toyVMでは命令長が4byte固定だったので命令数だけポインタを減らせば分岐ができたのですが，x86ではそうではありません．
ここでは簡単にすませるために，一命令毎に数値のラベルを生成させて，そのラベルへ分岐するようにしました．
L(toStr(labelNum++));
switch (code) {
...
case JNZ:
test(reg[r], reg[r]);
jnz(toStr(labelNum + static_cast<signed short>(imm)));
break;
以下は実行時にrecompile()して得たx86のコードです．
.lp:
mov dword ptr [ebx+4],esi
add esi,dword ptr [ebx]
mov edi,dword ptr [ebx+4]
mov dword ptr [ebx],edi
mov edi,dword ptr [ebx+8]
sub edi,1
mov dword ptr [ebx+8],edi
test edi,edi
jne .lp
問題なさそうです．
6. パフォーマンスを見る
ではどの程度改善されたのか見てみましょう．
n = 10000のときにかかった時間を測定しました．マシンはCore2Duo 2.6GHz + Visual Studio 2005です．
| 通常VM | JIT | native C(fibC) |
|---|
| 1216K | 136K | 84K |
|---|
通常のVMではnative Cに比べて10倍以上遅かったのが一気に肩を並べる速度にまで向上しました．
これは通常のVMでの本質である，switch + jmpがパイプラインを乱すため最近のCPUではコストが大きいためです．
ネイティブなコードへの変換が如何に重要であるかがわかります．
注意:gcc 4.3.0でfibCをコンパイルするともっとよいコードが生成されていました．その場合は上記よりもnative Cが何割か性能がよくなります．
7. リコンパイラを改良する
せっかくですので少しだけrecompileを改良してみましょう．
上記のx86のコードでは不要なメモリアクセスが目立ちます．
不要な命令を減らすことはJITの重要な課題ですが，それは難しいので，メモリアクセスではなくレジスタアクセスをさせるようにしましょう．
幸いフィボナッチでは三つしかmemを使わないのでそれらをレジスタに割り当てることにします．
VMに対して，memの先頭12byteだけが特別に速いメモリになったかのように思わせるということです．
そのためのレジスタをeax, ecx, edxとしました．それらを初期化するコードを追加します．
const Reg32 memTbl[] = { eax, ecx, edx };
const size_t memTblNum = NUM_OF_ARRAY(memTbl);
for (size_t i = 0; i < memTblNum; i++) xor(memTbl[i], memTbl[i]);
そしてrecompileでメモリにアクセスする部分を変更します．
case ADD:
if (imm < memTblNum) { //
add(reg[r], memTbl[imm]); // 追加部分
} else { //
add(reg[r], ptr [mem + imm * 4]);
}
break;
mem[]の先頭にアクセスするときのみレジスタへのアクセスに変更しました．
これによりリコンパイルで生成されるコードは以下のようになりました．
.lp:
mov ecx,esi
add esi,eax
mov edi,ecx
mov eax,edi
mov edi,edx
sub edi,1
mov edx,edi
test edi,edi
jne .lp
すっきりしました．
ベンチマークをとってみます．
| 通常VM | JIT | 改良版JIT | native C(fibC) |
|---|
| 1216K | 136K | 101K | 84K |
|---|
3割ほど速度が向上しました．
このサンプルを基にいろいろVMをいじってみるのも面白いかと思います．