SSA形式

SSA形式に関して


COINSの静的単一代入形式最適化部

SSA形式の最適化に関して説明されてます。

COINSの静的単一代入形式最適化システムの外部仕様書

支配関係やループ、コンパイラ固有の概念に関して説明されてます。
※COINSの回し者ではありません。

SSA形式に関する貴重なリンク集

SSA形式を前提とした最適化に関しては、上記リンクで主なものが紹介されています。

SSA形式の実装の関して


最近のOSSのコンパイラは、SSA形式のIRを使用しているものが非常に多いです。

例を挙げると、
LLVMのBitcode(機種非依存の中間言語)
gccのTree SSA Gimple(機種非依存の中間言語)
oracle JavaVM HotSpot C1コンパイラのHIRとC2コンパイラのHIR(Ideal)
Android4.0 ICSのMIR(機種非依存の中間言語)
V8 Crankshaft のHIR(通称Hydrogen 機種非依存の中間言語)
などなど。大体はSSA形式。

SSA形式を採用する利点として、SSA形式を前提とした強力な最適化アルゴリズムを使用することができます。
SSA形式を前提とすると、どのように強力かというと、最適化にそれほど時間をさかずに効率よく最適化することができます。
具体的には、
SSA形式を使用した場合、代入が単一になるため、変数の扱いがシンプルになります。
また、支配関係を使用して、CFGの解析を簡略化することができます。

SSA形式を前提とした最適化のアルゴリズムとして、最も代表的なものは、GVNです。
GVNは、式(ex a = b + c)をhash関数に変換し(例えば、右辺のop+, b, cの各bitを左shiftしながら繋げてhashに変換する)
そのhashをCFGの順番にmapにputしていきます。
もしそのhashが衝突したら、衝突した式は冗長であるため、削除可能とみなします。
GVNがmapへputする際にCFGをたどる順番は、CFGを順に辿るのではなく、支配関係のみ参照して辿るかどうかを決めます。

※上記のICS以外の全てで採用されているはず。Global Value Numberingでなく、XXX Value Numberingかもしれませんが、、
SSA形式は、最適化に時間をかけれないJITコンパイラの要件と合うため、最近のJITコンパイラは例外なくSSA形式を採用しているように思います。

SSA形式を採用する場合、いくつかのデメリットが存在します。
1つ目は、SSA形式と支配木の維持コストが存在することです。最適化や変換に応じて、漸化的に維持、更新する必要があります。
2つ目は、HPC由来のネストしたループ最適化が行い難いことです。

  • 最終更新:2013-12-09 00:46:38

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

認証パスワード