累積レジスタマシンで命令単位JITコンパイラの夢を見る
この記事は
言語実装のカレンダー | Advent Calendar 2021 - Qiita
https://qiita.com/advent-calendar/2021/lang_dev
の1日目のために書いた。
以前の投稿で紹介した「累積レジスタ割付による仮想マシンの高速化」。
https://abo-junghichi.hatenablog.jp/entry/2019/11/14/001142
興味深いのは、そこで使われるJITコンパイルが仮想命令単位ということ。
世の中には既に、実行時コンパイラ作成ツールが幾つかある。
SLJITやlightningやLibJIT、MIR、LLVM、PyPy…。
これらのJITツールは、最小のコンパイル単位が関数だ。
ということは、それより小さいな単位でのJIT手法が書きにくいということだ。
例えば、仮想マシンエミュレータとして有名なQEMUで使われるJIT手法では、分岐命令に達するまでのコードである「基本ブロック」までは一気にコンパイルするが、分岐命令以後のコードからは、先のJIT済み基本ブロックを走らせて分岐結果が得られるまで、コンパイルを後回しにする。
そして基本ブロック末尾の分岐命令は、最初はJITコンパイラの呼び出しだが、後続ブロックのJIT後は、その後続ブロックへの分岐命令に書き換えられる。
最近Ruby本家にmergeされたYJITも、QEMUと同様に基本ブロック末尾の書き換えをしている。
なのでこれらのJIT手法を用いるには、関数よりも小さな単位でコードをコンパイルしなければならない。
上記JITツールでも、末尾呼び関数で基本ブロックのエミュレーションはできるだろうが、分岐命令の書き換えについては、本来は分岐命令ひとつ書き換えれば済むところ、基本ブロック丸ごとJITし直すハメになる。
そもそもJITで一番辛いのは、異なる物理命令セット間での移植性がないことだ。
逆に言えば、仮想ISAによる移植性確保以上の機能は、JITツールには不要じゃないだろうか?
少なくとも、実行時コンパイル負荷の増加とのトレードオフにはなるはずで、ならば、コンパイル負荷低減の方向に思いっきり振った、仮想ISAを命令単位で機械語バイト列に変換するJITツールの意義はあるはず。
そんな累積レジスタ割付だが、ひとつ問題がある。
C言語の標準ライブラリ関数など、標準的なコンパイラで生成されたサブルーチンを呼び出すと、一部の物理レジスタの内容が書き換えられてしまうことだ。
関数呼び出しには
呼出規約 - Wikipedia
https://ja.wikipedia.org/wiki/%E5%91%BC%E5%87%BA%E8%A6%8F%E7%B4%84
という約束事がある。
関数を呼び出す側と呼び出された関数側の双方でこの約束事を守ることで、呼び出し側のプログラムと呼び出される関数を別々にコンパイルしたり、極端な話、別々の言語処理系でコンパイルしても、呼び出し側のプログラムでその関数を利用できる。
JITツールを作成する場合も呼出規約を利用することで、自分で機械語バイトを並べずに外部のコンパイラに仮想ISAの実装を丸投げできるし、ライブラリなどJITツール外のコードをJITコードから呼び出せる。
丸投げの例としては、
YETI: a graduallY Extensible Trace Interpreter
http://www.cs.toronto.edu/~matz/dissertation/matzDissertation-latex2html/matzDissertation-latex2html.html
で確立された、仮想命令のうちジャンプや分岐を伴わないものは全て外部関数呼び出しで済ませるcontext threadingがある。
というより、外部関数を扱えないというのは、言語処理系として致命的だ。
ファイル操作からウィンドウの描画まで、コンピュータの持つ機能のほぼ全ては、それらの機能をユーザーに直接触れさせない現代的なOSでは、ライブラリ関数として提供されているのだから。
その約束事の中に物理レジスタの使い方も含まれており、格納している値が関数呼び出し後に不定になる物理レジスタが定められている。
ここでは、外部関数呼び出しで値が不定になる物理レジスタを「破壊レジスタ」、値が保たれる物理レジスタを「保存レジスタ」と呼ぼう。
関数呼び出しを跨ぐ値には破壊レジスタを割り付けられないので、通常のAOTコンパイラでは、外部関数呼び出しを跨いで使用される値と跨がない値とを区別して、跨がない値には優先的に破壊レジスタを割り付ける。
ここで注意したいのは、保存レジスタならば、関数呼び出しを跨ぐ値と跨がない値のどちらにも割り付けできることだ。
破壊レジスタ・保存レジスタの数を知っている通常のAOTコンパイラであれば、破壊レジスタを使い尽くしたか保存レジスタが余るかどうかを考慮して、保存レジスタを破壊レジスタの用途に転用できる。
しかし、破壊・保存レジスタの数以前に物理レジスタの数を知ることが出来ない累積レジスタマシン用のAOTコンパイラでは、この転用の判断ができない。
これを改善する一つの方法が、破壊レジスタを割り付けられた仮想レジスタには保存用のメモリ領域も同時に割り付け、どちらの領域を使うかは仮想命令のJIT毎に、レジスタ番号と同時に指定することだ。
保存レジスタを割り付けられた仮想レジスタや、物理レジスタを割り付けられなかった仮想レジスタでは、破壊レジスタか保存用メモリ領域かの選択を無視する。
値が外部関数呼び出しを跨ぐかどうかまではAOTコンパイラで把握できるので、それをJITコンパイラに伝達する仕組みだ。
割り付けられている物理レジスタの種類に依らず仮想レジスタの使い方が揃っているので、AOTコンパイラ側では破壊・保存レジスタの数を気にする必要がなくなる。
逆に言えば、どの仮想レジスタに破壊レジスタの割り付けられているかをAOTコンパイラは分からず、破壊レジスタが空いているのに、関数呼び出しを跨がない値に保存レジスタを割り付けてしまう。
もっと良い方法があるかも知れない。
