静的単一代入形式に基づく最適化に関する研究東京工業大学大学院情報理工学研究科佐々政孝目標  静的単一代入形式（SSA形式）    データフロー解析や最適化を見通しよく行える SSA形式に基づく変換と最適化をCOINSの低水準中間表現LIRの上に組み込む  SSA形式への変換と逆変換  SSA形式上の種々の最適化と有用な変換これにより，共通インフラストラクチャを教育，研究用基盤として有用なものとする設計と実装の方針複数のアルゴリズムが知られているもの → 比較検討の上，採用するアルゴリズムを決定  共通インフラストラクチャとして → 基本的な最適化を含める  研究基盤として活用できることの例示 → オリジナルなアルゴリズムによる最適化も含める  アルゴリズムの比較評価のため → アルゴリズムのヴァリエーションをオプションで指定できる教育・研究基盤として → 詳しい仕様書を提供，読解性・保守性のよいコーディング   SSA形式 a = x + y a = a + 3 b = x + y (a) 通常形式 a1 = x0 + y0 a2 = a1 + 3 b1 = x0 + y0 (b) SSA形式 SSA形式：各変数の定義が字面上一つ． SSA形式 L1 a = 1 L3 L2 a = 2 … = a (a) 通常形式 φ関数 L1 a1 = 1 L3 L2 a2 = 2 a3 = f(a1:L1,a2:L2) … = a3 (b) SSA形式 SSA形式最適化の例 a = x + y a = a + 3 b = x + y a1 = x0 + y0 a2 = a1 + 3 b1 = x0 + y0 SSA変換 (b) SSA形式 (a) 通常形式 SSA形式最適化（共通部分式除去） a1 = x0 + y0 a2 = a1 + 3 b1 = a1 (c) SSA形式最適化後 SSA逆変換 a1 = x0 + y0 a2 = a1 + 3 b1 = a1 (d) 最適化された通常形式 SSA形式では，データフロー解析や最適化が見通しよく行なえる．静的単一代入(SSA)形式最適化の構成図基盤部ソースプログラム言語解析 SSA最適化 LIR->SSA変換 (３種類のヴァリエーション) 高水準中間表現(HIR) SSA形式LIR HIR to LIR 低水準中間表現(LIR) (通常形式LIR) コード生成目的コード SSA最適化コピー伝播共通部分式除去質問伝播大域値番号付条件付定数伝播無用命令除去ループ不変式移動帰納変数の最適化 SSA形式上の有用な変換危険辺の除去無用φ除去空ブロック除去最適化された SSA形式LIR SSA->LIR逆変換２種類 (１つは３種類のヴァリエーション) ＋合併(２種類) 約14,000行 SSA形式への変換２つの有力なアルゴリズムをプロトタイプで比較し， Cytron法（支配辺境を用いる）を採用．変換時間 (milli sec) 900 800 700 600 500 Cytron Sreedhar 400 300 200 100 0 0 1000 2000 3000 4000 通常プログラムの制御フローグラフのノード数 SSA形式から通常形式への逆変換    主なアルゴリズム  Briggsらの方法  Sreedharらの方法これらを比較検討したところ，SSA逆変換の際に挿入されるコピー文の数などからSreedharらの方法が優位性があると認められた．既存のコンパイラでは採用が稀であったが， Sreedharらの方法を採用した．その後この方針の妥当性が実証された Sreedhar法による目的コードの実行時間が最小（後にBriggs法もCOINSに組み込んだ） SSA最適化（1）基本的な最適化（共通インフラストラクチャとして基本的な最適化を含める）   コピー伝播，条件分岐を考慮した定数伝播，支配関係に基づく共通部分式除去，無用命令除去，無用φ命令除去，空ブロック除去，ループ不変計算のループ外移動，ループの帰納変数に関わる演算の強さの軽減と判定の置き換え．この他，前処理として，ループ構造の変換（while型ループを if-do-while型ループへ）． SSA最適化（2）高度最適化  大域的再結合(global reassociation)  メモリ全体を一つの塊とみなす素朴な別名解析  効率的な質問伝播を用いた部分冗長性除去（後者２つはこのSSA最適化部が研究基盤になることの例示として新たに考案したものを入れた）最適化の例条件付定数伝播 i = 1; j = 1; k = 0; while (k < 100) { if (j < 20) { j = i; k = k + 1; } else { j = k; k = k + 2; } } printf("%d¥n",j); k = 0; while (k < 100) { k = k + 1; } printf("%d¥n",1); (in structured program style) ‘j’ が常に 1であることが解析できる whileの中の if-elseや黒字の部分が削除される SSA最適化部の評価 (SPEC CPU2000) SUN Fire V440 (UltraSPARC III, 1GHz*4, メモリ8 GB）．単位はsec． gcc2 ssa1 ssa2 ssa3 ssa4 -------------------------------------------------------------------164.gzip 2.74 3.97 4.02 4.03 3.97 175.vpr 3.57 5.84 5.82 5.85 5.88 181.mcf 0.741 0.812 0.738 0.826 0.736 197.parser 5.12 6.73 6.77 6.82 6.72 254.gap 2.07 2.32 2.31 2.47 2.45 256.bzip2 9.99 26.6 26.3 26.6 26.3 300.twolf 0.489 0.623 0.622 0.645 0.623 171.swim 2.67 2.50 3.04 3.06 2.50 172.mgrid 78.2 108 123 123 107 173.applu 0.687 1.19 1.37 1.45 1.21 177.mesa 4.83 5.28 5.28 5.36 5.46 179.art 12.4 17.0 16.7 16.9 16.2 183.equake 3.00 3.13 3.32 3.17 3.34 188.ammp 18.5 24.0 22.4 22.6 23.4 -------------------------------------------------------------------gcc2: ssa1: ssa2: ssa3: ssa4: gcc -O2 or g77 -O2 prun/divex/cse/cstp/dce/hli/osr/hli/cpyp/cstp/cse/cpyp/cstp/dce/ebe/srd3 prun/divex/cpyp/cse/cstp/dce/hli/cstp/osr/cse/cstp/cse/dce/cbb/ebe/srd3 prun/gra/divex/cpyp/cse/cstp/dce/hli/cstp/osr/cse/cstp/cse/dce/cbb/ebe/srd3 prun/divex/cse/cstp/hli/osr/hli/cstp/cse/dce/srd3 SSA最適化部の評価 (SPEC CPU2000) SUN Fire V440 (UltraSPARC III, 1GHz*4, メモリ8 GB）．単位はsec． coins-noopt coins-ssa gcc2 ------------------------------------------------------------------164.gzip 4.32 3.97 2.74 175.vpr 8.12 5.88 3.57 181.mcf 0.743 0.736 0.741 197.parser 6.73 6.72 5.12 254.gap 2.63 2.45 2.07 255.vortex 13.9 12.8 9.84 256.bzip2 28.2 26.3 9.99 300.twolf 0.671 0.623 0.489 171.swim 9.11 2.50 2.67 172.mgrid 851 107 78.2 173.applu 10.1 1.21 0.687 177.mesa 5.30 5.46 4.83 179.art 18.2 16.2 12.4 183.equake 4.17 3.34 3.00 188.ammp 29.6 23.4 18.5 ------------------------------------------------------------------coins-ssa: -coins:ssa-opt=prun/divex/cse/cstp/hli/osr/hli/cstp/cse/dce/srd3 gcc2: gcc -O2 or g77 -O2 lu SPECベンチマークの実行時間（相対比） 188 .am ke mp 183 .eq ua 179 .art 177 .me sa 173 .ap p 300 .tw ol f 171 .s w im 172 .mg rid 2 tex 256 .bz ip 255 .vo r 254 .g a p f 197 .pa rs e r 181 .mc 175 .vp r 164 .g z ip SSA最適化部の評価 (SPEC CPU2000) 1.2 1 0.8 0.6 coins-noopt coins-ssa gcc-O2 0.4 0.2 0 SSA最適化の評価考察     前図は他の最適化を適用せずにSSA最適化のみを適用した結果．現時点では，SSA最適化の結果はgccの-O2オプションの結果に全体としては及ばない．その原因として，gccの目的コードではレジスタプロモーションや命令スケジューリングがなされているが，これはSSA最適化だけでは処理できないこと，SSA最適化は集合体を対象としていないこと，また全体としてSSA最適化の結果には詰めが不十分な所が残っていること，が挙げられる．今後さらに検討する予定．教育・研究への適用 ■ 教育への適用 ■ ■ ■ ■ COINSを用いたコンパイラの集中講義（2004年7月）内１日がSSA最適化このときに用いた豊富な例題と使用法はウェブページで公開 COINSインフラストラクチャを用いた学士論文研究研究への適用 ■ ■ 効率的な質問伝播を用いた部分冗長性除去 [滝本ほか2005]（前述）．もともとはCOINSの外のユーザ．のちに本システムに組み込んだ．その他，本研究室の大学院生による研究も多い[伊藤ほか2005] [須藤ほか2005] [溝渕ほか2005] 発表論文査読付き論文・国際会議  Sassa, M., Nakaya, T., Kohama, M., Fukuoka, T. and Takahashi, M.: Static Single Assignment Form in the COINS Compiler Infrastructure, SSGRR 2003w, L'Aquila, Italy, No. 54, (Jan. 2003).  滝本宗宏, 武田正之: 一般支配関係の効率的な検査法, 情報処理学会論文誌：プログラミング, Vol. 44, No.SIG16 (PRO20), pp. 28-40 (Dec. 2003).  Sassa, M., Kohama, M. and Ito, Y.: Comparison and Evaluation of Back Translation Algorithms for Static Single Assignment Form, in Proc. IPSI-2004 Prague, Czech, ISBN: 86-7466-117-3 (Dec. 2004). (keynote at IPSI-2004 Prague)  滝本宗宏,福岡岳穂，佐々政孝，原田賢一: 疎な要求駆動型データフロー解析，情報処理学会論文誌：プログラミング, submitted for publication (2005).  須藤大二朗，佐々政孝：比較照合法によるコンパイラ最適化器の正しさの検証，日本ソフトウェア科学会第７回プログラミングおよびプログラミング言語ワークショップ (PPL2005) 論文集，(2005年3月).  溝渕裕司，立川英，佐々政孝：変更文の移動を可能にした静的単一代入形式上での部分冗長性除去，日本ソフトウェア科学会第７回プログラミングおよびプログラミング言語ワークショップ (PPL2005) 論文集，(2005年3月). まとめ ■ ■ ■ ■ ■ ■ 当初の目標である，共通インフラストラクチャにおけるSSA形式最適化の実現，は十分達成． SSA形式への変換と逆変換については，いくつかの方法を比較評価して，良いものを採用．基本的なSSA形式最適化をほとんど実装．ユーザがSSA形式の変換や最適化の種々のヴァリエーションを用いたり，新しいモジュールを追加して，実験・評価を行えるよう，十分な配慮を行った．関連研究として，SSA形式最適化を組み込んだコンパイラはいくつかあるが，インフラストラクチャとして使えるものは少ない [Sassaほか2003のサーベイ]．これを教育，研究用基盤として用いて，SSA形式の研究の進展が期待できる．今後の課題 ■ ■ SSA最適化の効果がgcc等にまだ及ばない点を検討し，さらなる改良を施す．仕様書の英文化もほぼなされているので，海外への情報発信に努める．アクセス方法 COINSプロジェクトURL http://www.coins-project.org/ からSSA最適化のページへ概要 SSA最適化の例 SSA形式とは SSA最適化の詳しいスライド集中講義資料（デモ）仕様書論文発表資料