Virtual Machine

はじめに

「見た目は JavaScript、頭脳(中身)は Ruby、（安定感は AC/DC）」 でお届けしているスクリプト言語 Kinx。作ったものの紹介だけではなく実現のために使った技術を紹介していくのも貢献。その道の人には当たり前でも、そうでない人にも興味をもって貰えるかもしれない。

前回のテーマは Switch-Case、今回のテーマは VM (Virtual Machine)。

参考
- 最初の動機 ... スクリプト言語 KINX（ご紹介）
  - 個別記事へのリンクは全てここに集約してあります。
- リポジトリ ... https://github.com/Kray-G/kinx
  - Pull Request 等お待ちしております。

Virtual Machine

仮想機械。Kinx の場合、構文解析した AST から IR (Intermediate Representation) を構築、それを直接実行する。命令数は現時点で 190。include/ir.h に一覧がある。一応、一通り第二オペランドの型がわかるものに関しては型ごとに命令を用意することで実行時コストを下げるようにはしてある。

出力例

今回は出力例から。以下のフィボナッチ数列のベンチマーク；

function fib(n) {
    if (n < 3) return n;
    return fib(n-2) + fib(n-1);
}

System.println("fib(34) = ", fib(34));

これをコンパイルしてみると、以下のようになる。

_startup:
  .L1
       0:   jmp                     .L2(2)
       1:   halt

_main1:
  .L2
       2:   enter                   37, vars(35), args(1)
       3:   pushf                   __anonymous_func58 => .L3(10)
       4:   call                    0
       5:   pop
       6:   pushf                   fib => .L460(d0a)
       7:   storevx                 $(0,33)
       8:   pushi                   34
       9:   callvl0                 $0(33), 1
       a:   pushs                   "fib(34) = "
       b:   pushvl0                 $0(1)
       c:   calls                   "println", 2
       d:   pop
       e:   ret                     null
       f:   halt

fib:
  .L460
     d0a:   enter                   23, vars(1), args(1)
  .L461
     d0b:   lt_v0i                  $0(0), 3
     d0c:   jz                      .L463(d0e)
  .L462
     d0d:   retvl0                  $0(0)
  .L463
     d0e:   pushvl0                 $0(0)
     d0f:   subi                    2
     d10:   callvl1                 $1(33), 1
     d11:   pushvl0                 $0(0)
     d12:   subi                    1
     d13:   callvl1                 $1(33), 1
     d14:   add
     d15:   ret
     d16:   halt

アドレスが飛んでいるのは、標準ライブラリの読み込みなど、スタートアップルーチンの表示を省略するようにしているからです（__anonymous_func58 のあたり）。

ダイレクト・スレッデッド・コード

gcc の場合、ラベルに対するジャンプ命令を生成できるので俗にいう ダイレクト・スレッデッド・コード が実現できる。残念ながら Visual Studio では実現できない。

まず、最初にラベルに対するアドレス用のテーブルを作成する。この時、命令コードの番号と配列位置を合わせておくことでアドレスを一発で引けるようにしておく。ちなみに、C のラベルは関数をまたげないので、関数内で閉じてないといけない。

static void *jumptable[] = {
    &&LBL_KX_HALT,
    &&LBL_KX_NOP,
    &&LBL_KX_DUP,
    &&LBL_KX_IMPORT,
    &&LBL_KX_ENTER,
    &&LBL_KX_CALL,
    &&LBL_KX_CALLV,
    &&LBL_KX_CALLVL0,
    ...
};

次に、命令を一通りスキャンして、命令に対するアドレスを設定する。

for (int i = 0; i < code_len; ++i) {
    kx_code_t *c = fixcode[i];
    c->gotolabel = jumptable[c->op];
    ...
}

準備が整っていれば、命令実行の最後で次の命令に移動して goto する。

LBL_KX_ENTER:
    ...
    cur = cur->next;
    goto *(cur->gotolabel);

この辺が、include/kxexec.h にマクロとして定義してある。マクロは gcc と Visual Studio での共通化用です。

ダイレクト・スレッディングに関しては、結構古い記事だが YARV Maniacs 【第 3 回】命令ディスパッチの高速化がやっぱり分かりやすいと思う。

スタック構造

スタックは演算で使用されるが、関数呼び出し時にフレームを作成する。フレームにはローカル変数を格納するバッファが用意されており、フレームが GC されない限り参照できる。関数呼び出し時のスタック構造は以下の通り。

[ 0] frame obj   .lex = previous lexical frame.
---------------------------------------------------------
[-1] return address
[-2] param count
[-3] function obj (.lex)
[-4] param 1
[-5] param 2
[  ] ...
[..] param n
[  ] ...
[  ] frame obj -- previous frame
---------------------------------------------------------

.lex はレキシカル・フレームへのポインタ。リンクリストの形でさかのぼることができる。

余談だが、ここで演算用のスタックをフレームごとに個別に持たせれば Fiber でスタック状態も復元できると想定しているのだが、そこまで頑張る必要があるかどうかよく分からない。自分自身は困っていない。というのも、スタック状態を復元して良くなる点といえば式の中に yield を書くといった以下のようなコードだが、こういうの使えなくても良い気がする。

var x = (yield 10)[0] + 50;
var y = func(yield a, ++a);

ちなみに現在の関数呼び出し時の引数評価は 後ろから だが、一般的にこれをあまり保証したくないので、上記のうちの関数呼び出しで使われる yield の a の値はインクリメント後か前かは保証されないことになるだろう。

レキシカル変数

レキシカル変数は関数オブジェクト作成時にリストとして関数オブジェクト自体に設定される。関数呼び出しの際、関数オブジェクトに格納されていたレキシカルスコープへのポインタが、作成されたフレームに設定される。関数内で関数が定義されると、その時のフレームをレキシカル・フレームとして登録することで数珠つなぎの形で参照できるようになる、といった算段。

スタック上のイメージは、フレームごとにレキシカル参照が設定されている状態。

|↑| frame -> lex -> lex -> ...
|ス|  │
|タ|  │
|ッ|  ↓
|ク| frame -> lex -> lex -> ...
|↓|  │

尚、レキシカル参照されているフレームは GC で回収されないようにマークを付けなければならない。

スプレッド演算子（`...`）

関数呼び出しの際のスプレッド演算子（例：func(...a)等）は、呼び出しの段階で個別のパラメータに展開される。その際、その数に合わせて param count の値が調整された形で格納される。

例えば以下のコード；

b = [1,2,3];
func(a, ...b);

これは実行時に以下のように展開されたのと同じ動作をする。

b = [1,2,3];
func(a, 1, 2, 3);

もちろんコンパイル時には決定できないので、実行時に展開される。

eval

eval() は、VM をネストさせるのが大変そうだったので、動的にコンパイルした結果を現在のコードの最後に追記し、同じ VM 上で単にジャンプするように実装している。こうしておくと例外発生時の扱いも単純になる。

その他

どうも Visual Studio は Switch-Case の Case 数がある閾値を超えると 最適化をやめてしまう 模様。ちゃんとした公式文書が発見できなかったので、このあたりに詳しい方がいたら教えてください。目に見えてコンパイル時間が短くなり、パフォーマンスが悪くなる。

それにしても最適化が有効な時の src/ir_exec.c の Visual Studioでのコンパイル時間が泣きたいほどに遅い。かといってココを最適化しとかないと実行時速度がやばことになる。（今は WSL 上でやっている）gcc だと全然苦にならないほどコンパイルが速い。それでもダイレクト・スレッデッド・コードのおかげか、gcc でコンパイルしたほうがパフォーマンスも良い。実行ファイルに依存性を持たせない意味で Windows 上でのビルドは Visual Studio がいいんだけどなー。どうにかならんかな。

今後

IR のセーブ・ロード機能を付けたいところ。命令ごとに使うフィールドは決まっているので、それをルール化して書き出せばよいし、同じように読めばよい。やることはわかっているのだが、時間が追い付いていないな。

おわりに

今回も時間を割いて読んでいただいてありがとうございます。最後はいつもの以下の定型フォーマットです。興味がありましたら ★ とか 「~~いいね~~ LGTM」 ボタンとか押してもらえるとモチベーションにつながります。どうぞよろしくお願いします。

最初の動機はスクリプト言語 KINX（ご紹介）を参照してください（もし宜しければ「~~いいね~~ LGTM」ボタンをポチっと）。
リポジトリはここ（https://github.com/Kray-G/kinx）です。こちらももし宜しければ★をポチっと。

Kinx 実現技術 - VM（Virtual Machine）

Virtual Machine

はじめに

Virtual Machine

出力例

ダイレクト・スレッデッド・コード

スタック構造

レキシカル変数

スプレッド演算子（...）

eval

その他

今後

おわりに

スプレッド演算子（`...`）