まずは VM のおさらい

ここでいう VM(バーチャルマシン)はバイトコード的な何かを解釈実行するプログラムを指しています。FORTH を思い浮かべてほしいのですが、最近では FORTH といっても誰も反応しないので Java の VM を思い浮かべてくださいと言った方がいいのかもしれません。

バイトコード的な何か

Java VM を例にとると命令セットは 8 bit のバイトで、たとえば 00 なら NOP、01 なら aconst_null と定義されています。Java VM の場合はスタックを利用して計算するようになっているので、
1 + 2 を計算しようと思ったら

iconst_1 // スタックに 1 を積む
iconst_2 // スタックに 2 を積む
iadd // スタックにつんである上2を足して結果をスタックに積む

といった手順で計算をします。スタックマシンだとCPUのレジスタを考えなくて済むので VM の実装は楽になる(はず)です。
蛇足ながら、ここではバイトコードと言いつつ8bit以上を考えているのでバイトコード的なという表現になってしまっています。

switch/case で実装する

一番簡単な実装方法は switch/case で実装する方法です。C 風に書くとこんな感じ。

vm.c

op = inst[pc++];
switch (op) {
case NOP:
     // なにもしない
     break;
....
case ICONST_1:
     push(1);
     break;
case ICONST_2:
     push(2);
     break;
case IADD:
     i2 = pop();
     i1 = pop();
     i3 = i2 + i1;
     push(i3);
     break;
}

inst にあるバイトコードを一つ一つ実行していくとプログラムが実行されます。じゃ、print とかどうするの？という疑問がふとわきます。そう思った人は Little Smalltalk の実装を読むといいと思います。

スレッデッド・コード

Wikipedia に詳しい。
https://ja.wikipedia.org/wiki/%E3%82%B9%E3%83%AC%E3%83%83%E3%83%87%E3%83%83%E3%83%89%E3%82%B3%E3%83%BC%E3%83%89
だけど、一読しただけではわからない、、、

先の switch/case の例では"バイトコードを一つ一つ実行していく"と書きました。そのたびに switch の break を通り、先頭に飛んでといった、while ループが（例では書いてないけど）あります。これをもうちょい効率化しようという試みがあります。それがスレッデッド・コードを使用した実装です。

蛇足ながら、「スレッデッド・コード」の意味ですが、私は断片的なコードという意味だと解釈しています。その断片的なコードを連続して実行するとコンパクトで早い VM ができあがるという寸法です。

簡単にいうと switch/case をやめて、break のところで、次のコードに goto で飛んでしまいます。gcc には && を使ったラベルの参照をする機能があるのでそれを利用することが出来ます。

goto をつかった例

C 風に疑似的に書いてみましょう。

goto-vm.c


ICONST_1:
     push(1);
     goto ICONST_2;

....

ICONST_2:
     push(2);
     goto IADD;

.... 

IADD:
     push(pop()+pop()); // ちょっと最適化
     goto "どっか"

やりたいことはおおむねこんな感じです。このままだと ICONST_1 の次は必ず ICONST_2 を実行してしまうので、goto をフレキシブルにする必要があります。疑似コードではこんな感じ。

flex-goto-vm.c


ICONST_1:
     push(1);
     goto *inst[ip++];

gcc の特別な機能

普通の C では goto *inst[ip++] なんてできません。gcc では C を拡張していて、ラベルのアドレスを知ることが出来ます。

label.c

typedef void * Label;
static Label labels[] = {
...
     &&ICONST_1,
     &&ICONST_2,
     &&IADD,
...
};

ICONST_1:
...
ICONST_2:
...
IADD:
...

goto とラベルの組は関数内でしか使えないのに注意する必要があります。配列のアドレスを static で宣言して関数の外に持ち出しせるようにします。

サンプル実装

gcc-vm.

#include <stdio.h>
#include <stdint.h>
#include <assert.h>

typedef void * Label;
typedef void * Inst;

void engine(Inst *ip);

Label *labels;

static Inst inst[8];
static uint32_t stack[8];
static uint32_t* sp;

int
main()
{
    engine(0);

    inst[0] = labels[0]; // iconst_1
    inst[1] = labels[1]; // iconst_2
    inst[2] = labels[2]; // iadd
    inst[3] = labels[3]; // halt

    sp = &stack[sizeof(stack) - 1];

    engine(inst);
}

void push(uint32_t v)
{
    *sp++ = v;
}

uint32_t pop()
{
    return *--sp;
}

void engine(Inst *ip)
{
    int pc = 0;
    static Label _labels[] = {
        &&ICONST_1,
        &&ICONST_2,
        &&IADD,
        &&HALT
    };

    if ( ip == 0 ) {
        labels = _labels;
        return;
    }

    goto *ip[pc++];
    assert(0);

ICONST_1:
    push(1);
    goto *ip[pc++];

ICONST_2:
    push(2);
    goto *ip[pc++];

IADD:
    push(pop() + pop());
    goto *ip[pc++];

HALT:
    printf("halt %d\n", pop());
    return;
}

64bit の問題

64bit 環境だと sizeof(Label) が、、、つまり、sizeof(void *)が 64bit の 8 バイトになってしまいます。バイトマシンではなく quad-byte-machine といったところでしょうか？メモリ効率を考えると 64bit 環境ではサブルーチン・スレッディングが有効そうです（試したことはありません)。

長くなったので筒木は別の記事に(第一話に主人公が出てこない物語になってしまった）

vmgen で簡単なレジスタベースの VM を作る(1/2)