mitsunari@cybozu labs

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にはスタックが無いのでそんなことはやってられません(苦笑)．
#一応メモリはあるので，このスタックを実装することは可能かもしれませんが…．
素直にループで書きます．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に変換するリコンパイラを作る

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ではnative Cに比べて10倍以上遅かったのが一気に肩を並べる速度にまで向上しました．
これは通常のVMでの本質である，switch + jmpがパイプラインを乱すため最近のCPUではコストが大きいためです．
ネイティブなコードへの変換が如何に重要であるかがわかります．

注意:gcc 4.3.0でfibCをコンパイルするともっとよいコードが生成されていました．その場合は上記よりもnative Cが何割か性能がよくなります．

7. リコンパイラを改良する

そのためのレジスタを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;

.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

すっきりしました．
ベンチマークをとってみます．

3割ほど速度が向上しました．
このサンプルを基にいろいろVMをいじってみるのも面白いかと思います．