静的単一代入形式に基づく最適化に関する研究

Presentation on theme: "静的単一代入形式に基づく最適化に関する研究"— Presentation transcript:

1 静的単一代入形式に基づく最適化に関する研究
東京工業大学 大学院情報理工学研究科 佐々政孝

2 目標 静的単一代入形式（SSA形式） SSA形式に基づく変換と最適化をCOINSの低水準中間表現LIRの上に組み込む
データフロー解析や最適化を見通しよく行える SSA形式に基づく変換と最適化をCOINSの低水準中間表現LIRの上に組み込む SSA形式への変換と逆変換 SSA形式上の種々の最適化と有用な変換 これにより，共通インフラストラクチャを教育，研究用基盤として有用なものとする

3 設計と実装の方針 複数のアルゴリズムが知られているもの → 比較検討の上，採用するアルゴリズムを決定
複数のアルゴリズムが知られているもの 　→ 比較検討の上，採用するアルゴリズムを決定 共通インフラストラクチャとして 　→ 基本的な最適化を含める 研究基盤として活用できることの例示 　→ オリジナルなアルゴリズムによる最適化も含める アルゴリズムの比較評価のため 　→ アルゴリズムのヴァリエーションをオプションで指定できる 教育・研究基盤として 　→ 詳しい仕様書を提供，読解性・保守性のよいコーディング

4 SSA形式 a1 = x0 + y0 a = x + y a2 = a1 + 3 a = a + 3 b1 = x0 + y0
(b) SSA形式 SSA形式：各変数の定義が字面上一つ．

5 SSA形式 φ関数 L1 a = 1 L2 a = 2 L1 a1 = 1 L2 a2 = 2 L3 a3 = f(a1:L1,a2:L2)
(b) SSA形式

6 SSA形式最適化の例 a1 = x0 + y0 a2 = a1 + 3 b1 = x0 + y0 a = x + y a = a + 3
(b) SSA形式 SSA形式最適化（共通部分式除去） a1 = x0 + y0 a2 = a1 + 3 b1 = a1 a1 = x0 + y0 a2 = a1 + 3 b1 = a1 SSA逆変換 (c) SSA形式最適化後 (d) 最適化された通常形式 SSA形式では，データフロー解析や最適化が見通しよく行なえる．

7 静的単一代入(SSA)形式最適化の構成図
基盤部 SSA最適化 ソース プログラム LIR->SSA変換 (３種類のヴァリエーション) 言語 解析 高水準中間表現(HIR) SSA形式LIR SSA形式上の 有用な変換 　危険辺の除去 　無用φ除去 　空ブロック除去 HIR to LIR SSA最適化 　コピー伝播 　共通部分式除去 　質問伝播大域値番号付 　条件付定数伝播 　無用命令除去 　ループ不変式移動 　帰納変数の最適化 低水準中間表現(LIR) (通常形式LIR)　 最適化された SSA形式LIR コード 生成 SSA->LIR逆変換 ２種類 (１つは３種類のヴァリエーション) ＋ 合併(２種類) 目的 コード 約14,000行

8 通常プログラムの制御フローグラフのノード数
SSA形式への変換 ２つの有力なアルゴリズムをプロトタイプで比較し，Cytron法（支配辺境を用いる）を採用． 900 800 700 600 変換時間 (milli sec) 500 Cytron Sreedhar 400 300 200 100 1000 2000 3000 4000 通常プログラムの制御フローグラフのノード数

9 SSA形式から通常形式への 逆変換 主なアルゴリズム
Briggsらの方法 Sreedharらの方法 これらを比較検討したところ，SSA逆変換の際に挿入されるコピー文の数などからSreedharらの方法が優位性があると認められた． 既存のコンパイラでは採用が稀であったが，Sreedharらの方法を採用した．

10 その後この方針の妥当性が実証された Sreedhar法による目的コードの実行時間が最小 （後にBriggs法もCOINSに組み込んだ）

11 SSA最適化　 （1）基本的な最適化 （共通インフラストラクチャとして基本的な最適化を含める） コピー伝播，条件分岐を考慮した定数伝播，支配関係に基づく共通部分式除去，無用命令除去，無用φ命令除去，空ブロック除去，ループ不変計算のループ外移動，ループの帰納変数に関わる演算の強さの軽減と判定の置き換え． この他，前処理として，ループ構造の変換（while型ループを if-do-while型ループへ）．

12 SSA最適化 （2）高度最適化 大域的再結合(global reassociation) メモリ全体を一つの塊とみなす素朴な別名解析

13 最適化の例 条件付定数伝播 i = 1; j = 1; k = 0; k = 0; while (k < 100) {
最適化の例　条件付定数伝播 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や黒字の部分が削除される

14 SSA最適化部の評価 (SPEC CPU2000) SUN Fire V440 (UltraSPARC III, 1GHz*4, メモリ8 GB）．単位はsec． gcc ssa ssa ssa ssa4 164.gzip 175.vpr 181.mcf 197.parser 254.gap 256.bzip 300.twolf 171.swim 172.mgrid 173.applu 177.mesa 179.art 183.equake 188.ammp gcc2: gcc -O2 or g77 -O2 ssa1: prun/divex/cse/cstp/dce/hli/osr/hli/cpyp/cstp/cse/cpyp/cstp/dce/ebe/srd3 ssa2: prun/divex/cpyp/cse/cstp/dce/hli/cstp/osr/cse/cstp/cse/dce/cbb/ebe/srd3 ssa3: prun/gra/divex/cpyp/cse/cstp/dce/hli/cstp/osr/cse/cstp/cse/dce/cbb/ebe/srd3 ssa4: prun/divex/cse/cstp/hli/osr/hli/cstp/cse/dce/srd3

15 SSA最適化部の評価 (SPEC CPU2000) SUN Fire V440 (UltraSPARC III, 1GHz*4, メモリ8 GB）．単位はsec． coins-noopt coins-ssa gcc2 164.gzip 　 175.vpr 181.mcf 197.parser 254.gap 255.vortex 256.bzip 300.twolf 171.swim 172.mgrid 173.applu 177.mesa 179.art 183.equake 188.ammp coins-ssa: -coins:ssa-opt=prun/divex/cse/cstp/hli/osr/hli/cstp/cse/dce/srd3 gcc2: gcc -O2 or g77 -O2

16 SSA最適化部の評価 (SPEC CPU2000) SPECベンチマークの実行時間（相対比）

17 SSA最適化の評価 考察 前図は他の最適化を適用せずにSSA最適化のみを適用した結果．
現時点では，SSA最適化の結果はgccの-O2オプションの結果に全体としては及ばない． その原因として，gccの目的コードではレジスタプロモーションや命令スケジューリングがなされているが，これはSSA最適化だけでは処理できないこと，SSA最適化は集合体を対象としていないこと，また全体としてSSA最適化の結果には詰めが不十分な所が残っていること，が挙げられる． 今後さらに検討する予定．

18 教育・研究への適用 教育への適用 研究への適用 COINSを用いたコンパイラの集中講義（2004年7月）内１日がSSA最適化
このときに用いた豊富な例題と使用法はウェブページで公開 COINSインフラストラクチャを用いた学士論文研究 研究への適用 効率的な質問伝播を用いた部分冗長性除去 [滝本ほか2005]（前述）． もともとはCOINSの外のユーザ．のちに本システムに組み込んだ． その他，本研究室の大学院生による研究も多い[伊藤ほか2005] [須藤ほか2005] [溝渕ほか2005]

19 発表論文 査読付き論文・国際会議 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 (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: (Dec. 2004). (keynote at IPSI-2004 Prague) 滝本宗宏,福岡岳穂，佐々政孝，原田賢一: 疎な要求駆動型データフロー解析，情報処理学会論文誌：プログラミング, submitted for publication (2005). 須藤大二朗，佐々政孝：比較照合法によるコンパイラ最適化器の正しさの検証，日本ソフトウェア科学会第７回プログラミングおよびプログラミング言語ワークショップ (PPL2005) 論文集，(2005年3月). 溝渕裕司，立川英，佐々政孝：変更文の移動を可能にした静的単一代入形式上での部分冗長性除去，日本ソフトウェア科学会第７回プログラミングおよびプログラミング言語ワークショップ (PPL2005) 論文集，(2005年3月).

20 まとめ 当初の目標である，共通インフラストラクチャにおけるSSA形式最適化の実現，は十分達成．
関連研究として，SSA形式最適化を組み込んだコンパイラはいくつかあるが，インフラストラクチャとして使えるものは少ない [Sassaほか2003のサーベイ]． これを教育，研究用基盤として用いて，SSA形式の研究の進展が期待できる．

21 今後の課題 SSA最適化の効果がgcc等にまだ及ばない点を検討し，さらなる改良を施す．
仕様書の英文化もほぼなされているので，海外への情報発信に努める．

22 アクセス方法 COINSプロジェクトURL http://www.coins-project.org/ からSSA最適化のページへ 概要
　概要 　SSA最適化の例 　SSA形式とは 　SSA最適化の詳しいスライド 　集中講義資料（デモ）　 　仕様書 　論文発表資料