トレーシング実行時コンパイル

トレーシング実行時コンパイル（トレーシングJIT）とは

トレーシング実行時コンパイル（Tracing just-in-time compilation）、略してトレーシングJITは、プログラムの実行中に、仮想マシンがプログラムの最適化のために用いる技術の一つです。この技術は、頻繁に実行されるコードの並びを記録し、それをネイティブコードにコンパイルしてから実行することで、プログラムのパフォーマンスを向上させます。従来の実行時コンパイラ（JIT）がメソッド単位でコンパイルを行うのに対し、トレーシングJITはループなどの特定のコード領域を対象とすることが特徴です。

概要

JITコンパイルは、プログラムの実行時に、プログラムの一部を機械語に変換することで、実行速度を向上させる技術です。JITコンパイラは、コンパイル対象の範囲によって分類でき、メソッド単位でコンパイルを行うものと、トレーシングJITのように特定の実行パスをコンパイルするものがあります。トレーシングJITは、プログラムの実行時間の大半が、プログラムの一部のループ（ホットループ）の実行に費やされているという前提に基づいています。また、そのループが再度実行される場合、前回と同様の実行パスを辿ることが多いという性質を利用しています。トレーシングJIT機能を備えた仮想マシンは、通常、インタプリタやメソッドコンパイラなど、他の実行環境モードもサポートしています。

技術詳細

トレーシング実行時コンパイラは、実行時に以下のステップを経て処理を行います。

1. プロファイリングフェーズ: ループに関するプロファイリング情報を収集し、ホットループを特定します。
2. トレーシングフェーズ: ホットループが特定されたら、トレーシングモードに移行し、そのループで実行される全ての演算を記録します。記録された演算列はトレースと呼ばれます。
3. 最適化とコード生成フェーズ: 記録されたトレースを最適化し、機械語にコンパイルします。
4. 実行フェーズ: 同じループが再び実行される場合、コンパイル済みのトレースを実行します。

プロファイリングフェーズ

プロファイリングの目的は、ホットループを特定することです。一般的に、ループの繰り返し回数をカウントし、その回数が特定の閾値を超えた場合にホットループとみなします。そして、トレーシングモードが有効化されます。

トレーシングフェーズ

トレーシングフェーズでは、ループの実行は通常通り行われますが、それに加えて、実行された全ての演算がトレースに記録されます。記録される演算は、中間言語として保存されることが多いです。ループ内からの関数呼び出しも追跡され、場合によってはトレース内にインライン展開されます。トレーシングは、ループが終了するか、スタート地点にジャンプするまで継続されます。

トレースは、特定の実行パスのみを記録するため、その後の実行が記録されたパスと異なる場合もあります。このため、条件が同じかどうかを判定するガード命令がトレースに挿入されることがあります。ガードは、条件が満たされているかどうかを判定し、満たされていない場合はトレースを中止します。

トレーシングは実行時に行われるため、実行時型情報などの実行時情報を含めることができます。これらの情報は、最適化においてコードの品質を高めるために使用されます。

最適化とコード生成フェーズ

トレースは、制御フローのない一連の実行パスであるため、最適化が容易です。以下は、典型的な最適化の例です。

共通部分式除去
デッドコード削除
レジスタ割り当て
ループ不変コード移動
定数畳み込み
エスケープ解析

最適化後、トレースは機械語に変換されます。トレースは分岐のない一連のデータであるため、機械語への変換も容易です。

実行フェーズ

トレースが機械語にコンパイルされた後、同じループが再度実行される場合は、機械語のトレースが実行されます。トレースの実行は、ガードが失敗するまで続けられます。

歴史

実行時コンパイルのアイデア自体は1960年代まで遡りますが、トレーシングJITが注目されるようになったのは最近のことです。トレーシングJITのアイデアが最初に述べられたのは1970年であり、実行時にインタープリターで実行した際の動作を記録することで、コンパイル済みコードを生成できることが示されました。

最初のトレーシング実装は、Dynamoと呼ばれるシステムです。Dynamoは、実行される機械語命令列を監視し、「ホット」な命令列を特定した後、その命令列を最適化して実行する動的最適化システムです。Dynamoは後にDynamoRIOに拡張され、トレーシングと部分評価が可能なインタープリター構築基盤となりました。

2006年には、HotpathVMという最初の高水準言語用トレーシングJITコンパイラが開発されました。この仮想マシンは、頻繁に実行されるバイトコード命令列を特定し、トレースしてマシンコードにコンパイルすることができました。マシンコードには静的単一代入（SSA）が使用されました。HotpathVMの主な目的は、モバイル端末のようなリソースが限られた環境で効率的なJVMを提供することでした。

トレーシングJITの別の例としては、TraceMonkeyがあります。これは、MozillaによるFirefox向けのJavaScript実装の一つであり、頻繁に実行されるJavaScriptのループをコンパイルし、同じ動的型がループ内で使用される場合にはコンパイルされたコードを使用しました。

また、PyPyもトレーシングJITを活用しています。PyPyを実装するためのツールチェーンにトレーシングJITが適用されており、PyPyインタープリターを使用する全てのプログラムのパフォーマンスが向上します。これは、PyPy自身をトレース対象としているためです。

トレーシングJITは、マイクロソフトのSPURプロジェクトでも使用されました。SPURは、共通中間言語（CIL）の汎用トレーサーで、JavaScript実装のトレースにも使用することができました。

トレースの例

1から10,000までの全ての数の二乗和を計算する次のプログラムを例に考えてみましょう。


sum = 0
for i in range(1, 10001):
sum += i i


このプログラムのトレース例は次のようになります。


loopstart(i1, y1)
i2 = int_mul(i1, i1) # xx
y2 = int_add(y1, i2) # y += ii
b1 = int_gt(y2, 100000)
guard_false(b1)
i3 = int_add(i1, 1) # i = i+1
jump(i3, y2)


この例では、square関数の呼び出しがインライン化されており、if文がguard_falseに変換されていることが分かります。

まとめ

トレーシングJITは、プログラムの実行中にホットループを特定し、最適化された機械語に変換することで、プログラム全体のパフォーマンスを向上させる効果的な技術です。この技術は、特にループ処理の多いプログラムで高い効果を発揮し、従来のJITコンパイラよりも優れたパフォーマンスを実現することができます。

参考文献

コンパイラ
インタプリタ
HotSpot
PyPy
実行時コンパイラ
* Official website of LuaJIT

もう一度検索