仮想マシン

言語の仮想マシンは、バイトコードを読み状態を変えるループだ。ADD は二値をポップして結果をプッシュする操作で、ソースの加号を読み直すわけではない。1 + 2 * 3 で MUL を先に生成するのは、乗算時に 2 と 3 がスタック上に必要だからだ。

LOAD_CONST は値を置き、MUL は上の二値を取り、積を一つ戻す。ソースで + が先でも関係なく、VM は命令列に従う。この順序が結果 7 とアンダーフローを分ける。

言語 VM の仕組み

左の一覧がプログラムだ。前のレッスンは AST の子を先、演算子を後にして生成し、ここでは実行する。CPython、JVM などの言語実行系や教材 VM は、ソース文字の順序ではなく命令流を実行できる。本レッスンの命令は次のとおり。

ループの順序は op = code[pc]; pc += 1; dispatch(op)。プログラムのループは特別な構文ではなく、PC に小さい値を書き戻すジャンプで表す。

オペランド順は重要だ。SUB は b、a の順に取り、a - b を計算する。LOAD n, LOAD 1, SUB は n - 1。逆に計算すれば 1 - n になり、カウントダウンの意味が壊れる。

JIT タブはホットネス検査を加える。後方ジャンプが閾値に達すると、そのバイトコードの個別取得をやめ、コンパイル済みの本体を実行する。同じコードを別の実行方式で動かす。

仮想マシンのステップ

既定は 1 + 2 * 3 のインタープリターで、列は LOAD_CONST 1, LOAD_CONST 2, LOAD_CONST 3, MUL, ADD, HALT。スタックは空。

1. 六行のプログラムを示す。PC=0、値はない。
2. LOAD_CONST 1 で 1 を置き、高さ 1。
3. LOAD_CONST 2 で 2 を置き、高さ 2。
4. LOAD_CONST 3 で 3 を置き、高さ 3。全ての葉が入り、演算はまだ行っていない。
5. MUL が 3、2 を取り、6 を戻す。高さは 3 から 2。AST で深い乗算を先に生成したので、ここでも先に実行する。
6. ADD が 6、1 を取り、7 を置く。元の 2 ではなく、既に計算した 6 を使う。
7. HALT で止まり、スタックに一値が残る。
8. 結果は 7。HALT を含む六命令で、MUL が ADD より先。

(1 + 2) * 3 に替えると、一覧が ADD、MUL の順になり、同じ VM で先に 3、次に 9 を得る。ADD first の誤りプリセットは演算子を先に置き、空スタックの ADD が Underflow を投げる。後のロードは動かない。

JIT の既定カウントダウンは n=3、閾値 2。二周を解釈し、コンパイルして、残りの n = n - 1 を一つのネイティブ場面で実行する。以後そのループのバイトコードは取得しない。冷たいループは閾値 5 でホットネスが 2/5 に止まり、コンパイルも Native 表示もない。JIT は発動方針で、毎回のコンパイルを約束しない。

コードパネルは実際の分岐だけを示す。正常な ADD はポップと追加、アンダーフローは raise を光らせる。インタープリターの JUMP は、そのコードにない compile_loop を光らせない。JIT の THRESHOLD はスライダーに従い、冷たい例では 5 を表示する。

命令順と計算量

一覧は木から生まれ、スタック機械は先にオペランドを必要とするため、生成器は帰りがけ順を使う。(1 + 2) * 3 は加算が深く、先に ADD を実行し、最大高さは既定の 3 ではなく 2 となる。解析、生成、実行は別の段階だ。

本レッスンの小さい値のモデルでは各命令 O(1)、直線の k 命令は k 回取得する。n 周のループは解釈中 O(n) 回取得する。JIT 後の残り r 周は一つのネイティブ場面にまとめるが、算術は Θ(r) のまま。取得と分派を省くだけで、結果へ直接飛ぶわけではない。スタック空間はソース長ではなく最大高さで決まる。

境界ケース

• 空の初期スタックでは TOP を隠し、古い stack=0 を結果のように空欄の横へ出さない。
• ADD、MUL、SUB は二値未満なら例外で停止する。残る一覧は見えるが実行しない。停止フレームでは、結果に見える右ヘッダーも出さない。
• x + 2 * 3 で x=10 なら LOAD_NAME はローカルから 10 を積み、乗算が 6、最後が 16 になる。名前のロードは定数ロードではない。
• カウントダウンは JUMP 時にスタックが空で、各周の高さを保つ。持続する状態はローカル n。
• 冷たいループは二周、ホットネス 2、閾値 5 で still interpreting · hot 2/5 となり、Native は出ない。
• HALT は実際の最終行で、一覧外へ落ちて止まるのではない。前の五命令へ本レッスンが HALT を追加し、既定六命令のうち五つがスタックを変える。
• PC は分派前に一つ進み、JUMP が上書きする。ジャンプ後に増やすと JUMP 2 が 3 に着地する。CPU の JNZ でも同じ区別が必要だ。

よくある間違い

• ADD をソースの + として直接読む。解析は既に木を決め、ADD は一覧の位置で二ポップ一プッシュを行う。
• 演算子を先に生成し、ADD first のアンダーフローを起こす。レジスター VM は別の機械モデルになる。
• 実行スタックを IR と混同する。前の一覧は作ったプログラム、今のセルは実行データだ。
• JIT が算術を省くと思う。ネイティブも n = n - 1 を繰り返す。直接 n=0 にするのは別の最適化で、本実行と同じに描けない。
• JUMP の後に PC を増やし、目的地を飛び越える。

モデルの範囲

教材用スタック命令で、呼び出しフレーム、ヒープ、オブジェクト、GC、型はない。Native の帯は融合したソース相当の n = n - 1 / goto loop で、x86 でもなく、脱最適化もない。LuaJIT、V8、Dalvik などに関係するレジスター式バイトコードは別のオペランドモデルを持つ。KVM や第一種・第二種ハイパーバイザーはシステム仮想化で、この言語 VM とは別の分類だ。

ここで保つ仕組みは、取得、スタック操作、次の命令。ループは PC を書くジャンプで、JIT はホットネスを検査して実行本体を切り替える。