動的コンパイル

動的コンパイルとは、実行時(Runtime)の情報をコンパイラにフィードバックして行う最適化全般のことを指します。

オフラインフィードバック

実行時の情報(プロファイル情報、トレース情報)を保存しておき、再コンパイル時に活用する方法。
商用のコンパイラ(Intel, IBM, MS, HP)やgcc/llvmはサポートしている。
gccのプロファイル情報が良く活用される。gcc/llvm/iccで参照できるはず。

profile base optimization, profile guided optimizationが代表かも。

オンラインフィードバック

VMと連携するJITコンパイラが行うことが多い手法。
VMはインタプリタ実行時やICコンパイルされたコードを実行時に情報を収集し、
hotcodeを再コンパイルする際に活用する。

Smalltalkが起源らしい。
dynamic recompilation, adaptive compilation, adaptive optimizationが代表かも。


代表的な活用方法

スケジューリングの改善(トレース・スケジューリング、スーパーブロック・スケジューリング)
スーパーブロック・フォーメーション
LoopUnrollingのパラメータ改善
inline展開のパラメータ改善
脱仮想化(手続き呼出の固定化)
手続き呼出の特殊化

IA64向けJVMの活用方法

ハイパブロック・フォーメーション
分岐予測・コンプリータの改善


JVMの動的最適化

JVMのサーバ版は、最初インタプリタ実行を行い、その中でも特に10000回くらい繰り返す手続きをJITコンパイルする。
その際、インタプリタ実行時に取得していたプロファイル情報を元に、最適化を行うことができる。
以後、JITコンパイルで生成されたオブジェクトコードに置き換えられる。
※オブジェクトコードになったメソッドであっても、ちゃんとredefineの対象になる。


JVMが行うプロファイル情報取得と、その情報の活用方法
profiling
メソッドの実行回数のカウント
   --> JITコンパイルするかどうかの判定に利用
 ループの実行回数のカウント
   --> JITコンパイルするかどうかの判定に利用
   --> ループ最適化のパラメータの最適化に利用
 仮想関数呼び出しの、呼び出し先関数の統計
   --> 脱仮想化に利用
 calleeの引数の値の統計
   --> 関数の特殊化に利用
 分岐の統計
   --> コード配置の最適化に利用 キャッシュや分岐予測を改善できる。
 キャスト先の型の統計
   --> checkcastを省略できるかも
 DynamicCastの統計
   --> instanceofを省略できるかも
 Trapの統計
   --> ヤバい関数は最適化しませんし、インタプリタに戻します。

そういればJVMの出力するコードには、配列アクセスが連続する箇所に
x86向けのソフトウェアプリフェッチを自動的に挿入するはずだが、
挿入する際に何かプロファイル情報を参照したりするのだろうか。
挿入している箇所は、C2コンパイラのopto/macro expansionだったはずだが。

tracing
上記に加えて、
 変数の型の統計
   --> TypeSpecializeにより、型が静的な区間を仮定。
 変数の値の統計
   --> 分岐潰し。
   --> 内部クラスの仮定。

MSのprofile guide optimization

※MSDNのページからこぴってます。

最適化された出力ファイルを作成し、追加のプロファイリングによりさらに最適化されたイメージを作成できるかどうかを後で判断することもできます。 インストルメントされたイメージとその .pgd ファイルを使用できる場合は、追加のテストを実行し、最適化されたイメージをより新しい .pgd ファイルでビルドし直すことができます。

ガイド付き最適化のプロファイルの一覧を次に示します。

インライン展開

たとえば、関数 B を頻繁に呼び出す関数 A があり、関数 B が比較的小さい場合は、ガイド付き最適化のプロファイルにより、関数 B が関数 A にインライン展開されます。

仮想呼び出し推理

仮想呼び出し、または関数ポインターからのその他の呼び出しが特定の関数を頻繁に呼び出す場合は、ガイド付き最適化のプロファイルにより、条件付きで実行される直接呼び出しを頻繁に呼び出される関数に挿入し、その直接呼び出しをインライン展開できます。

レジスタの割り当

プロファイル データで最適化を行うと、レジスタの割り当てが改善されます。

基本ブロックの最適化

基本ブロックの最適化を行うと、一定のフレーム内で一時的に実行する一般的な実行基本ブロックをローカルの同じページ セットに配置できます。 これにより使用されるページ数が最小限に抑えられ、メモリのオーバーヘッドが最小限になります。

サイズ/速度の最適化

プログラムで時間を要する関数の速度を最適化できます。

関数のレイアウト

呼び出しグラフおよびプロファイリングされた呼び出し元/呼び出し先の動作に基づいて、同じ実行パスになる傾向のある関数を同じセクション内に配置します。

条件付き分岐の最適化

値プローブを使用し、switch ステートメント内の特定の値が他の値よりも頻繁に使用されているかどうかを、ガイド付き最適化のプロファイルで検出できます。 この値は switch ステートメントから取得できます。 また、if ブロックまたは else ブロックのどちらがより頻繁に true になるかに応じて、このどちらかのブロックを最初に置くようにオプティマイザーが if/else を並べ替えることができる場合には、これと同じことを if/else 命令でも行うことができます。

実行されないコードの分離

プロファイリングの実行中に呼び出されないコードを、一連のセクションの最後に追加した特別なセクションに移動します。 これにより、頻繁に使用されるページからこのセクションが切り離されます。

EH コードの分離

例外的な条件の場合にのみ例外が発生することがガイド付き最適化のプロファイルで判断できる場合は、例外的に実行される EH コードを別のセクションに移動できます。

メモリの組み込み

組み込みが頻繁に呼び出されるかどうかを判断できる場合は、組み込みの拡張をより的確に判断できます。 また、組み込みは、移動またはコピーのブロック サイズに基づいて最適化することもできます。 


chapuniが効果抜群と信じているもの


そのうち実装してみせます。つーかこれらがやりたかったから LLVM に飛びついたのだ。乞うご期待!

JIT: 実行時定数を用いた特化



実行時定数とは、関数の引数に限ったことじゃありません。

nothingcosmos memo

実行時定数といえば、
書籍Beautiful Code 第8章 画像処理のためのその場コード生成
で、クラス内実行時定数を畳み込んでインスタンスを生成するコード生成器を作ってました。

JVMでは、幾つかの変数を実行時定数だと見越して動的コンパイルを行い、
実行時定数だと見越していた変数が更新されたら、脱最適化を行い、インタプリタ実行に戻したりするらしいです。

inline展開の閾値を上げるだけで、性能はx0%以上あがります。ただし、閾値を上げすぎると、性能劣化します。
LoopUnrollingのパラメータ(最大展開数)を上げるだけで、性能はx0%以上あがります。ただし、閾値を上げすぎると、性能劣化します。
性能が劣化する理由は、ループ内のローカル変数が増えた結果、ループ内でスピルが多発したり、
コードが巨大になりすぎてキャッシュに乗らなくなるからです。

VMと機能を折檻すれば、実行時にクラス自体を特殊化する、メタクラスを使って動的コンパイルの適用範囲を広げて、
テンプレートの実行時特殊化
みたいなことができそうな気がするんだけど、オーバーヘッドと性能向上のトレードオフかなぁ。

  • 最終更新:2012-08-12 02:41:48

このWIKIを編集するにはパスワード入力が必要です

認証パスワード