トレーシング実行時コンパイル（トレーシングじっこうじコンパイル、トレーシングJIT、英: Tracing just-in-time compilation）は、プログラムの実行を最適化するために、実行時（runtime）に仮想マシンが用いる技術の一つ。頻繁に実行される演算の並びを記録し、それをネイティブコードにコンパイルしてから実行する。通常の実行時コンパイラ（just-in-time compiler、JIT）はメソッド毎にこれを行っており、この点が異なる。
概要
JITコンパイルは実行時にプログラムの一部を機械語にコンパイルすることでプログラムを高速に実行させる技術である。コンパイル対象の範囲によってJITコンパイラを分類すると、メソッド単位を基本とするJITコンパイラは一度に一つのメソッドを機械語に変換するが、トレーシングJITは頻繁に実行されるループをコンパイル対象の単位としている。 トレーシングJITは、プログラムの実行時間の大半はプログラムの一部のループ（ホットループ）の実行に費やされており、かつそのループが再び実行される場合はたいてい前回と同様の実行パスを経る、という仮定に基づいている。通常、トレーシングJIT機能を有する仮想マシンは代替となる実行環境モードであるインタプリタやメソッドコンパイラも具備する。
技術詳細
トレーシング実行時コンパイラは実行時に以下のステップを経る：第一に、ループに関するプロファイリング情報を収集する。次にホットループを特定した後、トレーシング実行モードに移行し、そのループを実行するのに用いられたすべての演算を記録する。記録された演算列はトレース（trace）と呼ばれる。その後トレースは最適化され機械語にコンパイルされる。再びそのループが実行される際はオリジナルのコードではなくコンパイル済みのトレースを実行する。
以下で各ステップを詳細に説明する。
プロファイリングフェーズ
プロファイリングの目的はホットループを特定することである。よく使われる方法は、すべてのループについて繰り返し回数を数えることである。この数がある特定のしきい値を超えた場合、そのループはホットループとみなされ、トレーシングモードが有効化される。
トレーシングフェーズ
トレーシングフェーズ下ではループの実行は通常通りだが、加えてすべての実行された演算がトレースに記録される。記録される演算はたいていは中間言語として保存される。ループ内からの関数コールも追跡され、場合によってはトレース内にインライン展開される。トレーシングはループが終了するかスタート点にジャンプするまで継続される。
トレースが記録できるのは、ある１つの実行パス条件のみであり、その後の実行がこの記録された実行パスとは異なる条件で実行される場合も考えられる。条件が同じかどうかを判定するためにガード命令がトレースに挿入される場合がある。if 文は挿入される場所の一例である。ガードは仮定していた条件が成り立っているかどうかを判定する。条件が成り立っていなければトレースは中止させられる。
トレーシングは実行時において行われるため実行時情報を含むことができる（例、実行時型情報）。この情報は最適化においてコードの品質を上げるのに使うことができる。
最適化とコード生成フェーズ
トレースは制御フローのない一列の実行パスでしかないため最適化は容易である。以下は典型的な最適化例である：
最適化の後トレースは機械語に変換される。最適化と同様に、トレースは分岐のない一列のデータであるため機械語変換は容易である。
実行
トレースが機械語にコンパイルされた後に再びこのループが実行される場合は機械語の方を実行する。トレースの実行はガードが失敗するまで続けられる。
歴史
実行時コンパイルのアイデアは1960年代まで遡るが、トレーシングJITが注目されるようになったのは最近である。今日あるようなトレーシングJITのアイデアが最初に述べられたのは1970年である。[2] 実行時にインタプリタ実行した際に使われた動作を単純に記録したものからコンパイル済みコードを派生させられることが示された。
最初のトレーシングの実装はDynamoである。Dynamoは「プロセッサ上で実行される機械語命令列を透過的に性能向上させることができる動的最適化システムを備えたソフトウェア」である。 [3] 実行されるネイティブ命令列を監視して「ホット」命令列を見つけた後、この命令列を最適化して実行した。
Dynamoは後に(DynamoRIO)に拡張された。DynamoRIO上には、トレーシングと部分評価が可能なインタプリタ構築基盤があり、これはプログラム言語のインタプリタ実装のオーバーヘッドを動的に除去するものである。[4]
2006年にHotpathVMという最初の高級言語用トレーシングJITコンパイラが開発された。[5] この仮想マシンは頻繁に実行されるバイトコード命令列を特定しトレースしマシンコードにコンパイルすることができた。マシンコードは静的単一代入（Static Single Assignment、SSA）が使われた。HotpathVMの主目的はモバイル端末等のリソースが制限された環境上で効率的なJVMを提供することにあった。
トレーシングJITの別の例として(TraceMonkey)がある。これはMozillaによるFirefox (2009)向けのJavaScript実装の一つである。[6] TraceMonkeyは動的言語JavaScript上で頻繁に実行されるループを実行時にコンパイルし、再び同じ動的型が当該ループで使われた場合にコンパイルしたコードを使用した。
トレーシングJITを活用しているもう一つの例にPyPyがある。PyPyを実装するためのツールチェーンにトレーシングJITが適用されているためPyPyインタプリタを用いているすべてのプログラムのパフォーマンスが向上する。これが可能なのは、PyPyが実行するプログラムではなくPyPy自身をトレース対象としているからである。 [7]
トレーシングJITはマイクロソフトのSPURプロジェクトでも使用された。SPURは共通中間言語 (Common Intermediate Language、CIL) のための汎用トレーサーで、JavaScript実装のトレースにも使うことができた。[8]
トレースの例
次のプログラムを考える。1から10000までのすべての数の平方の和を計算している。
def square(x): return x * x i = 0 y = 0 while True: y += square(i) if y > 100000: break i = i + 1 以下はこのプログラムのトレース例である：
loopstart(i1, y1) i2 = int_mul(i1, i1) # x*x y2 = int_add(y1, i2) # y += i*i b1 = int_gt(y2, 100000) guard_false(b1) i3 = int_add(i1, 1) # i = i+1 jump(i3, y2)
square関数のコールがインライン化されていることと、if 文がguard_falseに変換されている。
脚注
- ^ "Allocation removal by partial evaluation in a tracing JIT" Carl Friedrich Bolz, Antonio Cuni, Maciej Fijałkowski, Michael Leuschel, Samuele Pedroni, Armin Rigo - PEPM '11 Proceedings of the 20th ACM SIGPLAN workshop on Partial evaluation and program manipulation - doi:10.1145/1929501.1929508. Retrieved April, 24 2012
- ^ MITCHELL, J. G. 1970. The design and construction of flexible and efficient interactive programming systems. Ph.D. dissertation. Carnegie-Mellon University, Pittsburgh, PA.
- ^ "Dynamo: A Transparent Dynamic Optimization System" Vasanth Bala, Evelyn Duesterwald, Sanjeev Banerjia - PLDI '00 Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation - pages 1 to 12 - doi:10.1145/349299.349303. Retrieved March, 28 2012
- ^ "Dynamic native optimization of interpreters" Gregory T. Sullivan, Derek L. Bruening, Iris Baron, Timothy Garnett, Saman Amarasinghe - Proceeding IVME '03 Proceedings of the 2003 workshop on Interpreters, virtual machines and emulators doi:10.1145/858570.858576. Retrieved March, 21 2012
- ^ "HotpathVM: an effective JIT compiler for resource-constrained devices (Andreas Gal), Christian W. Probst, Michael Franz - Proceeding VEE '06 Proceedings of the 2nd international conference on Virtual execution environments doi:10.1145/1134760.1134780.
- ^ "Trace-based Just-in-Time Type Specialization for Dynamic Languages" A. Gal, M. Franz, B. Eich, M. Shaver, and D. Anderson - Proceedings of the ACM SIGPLAN 2009 conference on Programming language design and implementation, 2009 doi:10.1145/1542476.1542528.
- ^ "Tracing the Meta-Level: PyPy’s Tracing JIT Compiler" Carl Friedrich Bolz, Antonio Cuni, Maciej Fijałkowski, Armin Rigo - ICOOOLPS '09 Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems - pages 18 to 25 - doi:10.1145/1565824.1565827. Retrieved March, 21 2012
- ^ "SPUR: A Trace-Based JIT Compiler for CIL" M. Bebenita et al. - Proceedings of the ACM international conference on Object oriented programming systems languages and applications doi:10.1145/1869459.1869517.
関連項目
外部リンク
- Official website of LuaJIT