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

Slides:



Advertisements
Similar presentations
G ゼミ 2010/5/14 渡辺健人. パフォーマンスの測定 CUDA Visual Profiler CUDA の SDK に標準でついているパフォーマン ス測定用のツール 使い方: exe ファイルのパスと作業ディレクトリ指定して実 行するだけ 注意点 : GPU のコード実行後にプログラム終了前に,
Advertisements

バッファ・オーバフロー・アタックを動的に 検出するセキュア・キャッシュ ~安全性と消費エネルギーのトレードオフ~
コンパイラ 第13回 最適化 38号館4階N-411 内線5459
XHTML構文検証手法における スクリプト要素の静的解析アルゴリズム
ラベル付き区間グラフを列挙するBDDとその応用
プログラミング言語としてのR 情報知能学科 白井 英俊.
IaaS 仮想マシン(VM)をネットワーク経由で提供 負荷に応じてVM数や性能を変更できる ハードウェアの導入・管理・維持コストの削減
双方向CTLによるJava最適化器の生成
コンパイラ演習 第 8 回 (2011/12/01) 中村 晃一 野瀬 貴史 前田 俊行 秋山 茂樹 池尻 拓朗 鈴木 友博 渡邊 裕貴
2007/1/18 山下 諒蔵 佐藤 春旗 前田 俊行 大山 恵弘 佐藤 秀明 住井 英二郎
6.4 コード最適化 (1)コード最適化(code optimization)
2007/1/11 山下 諒蔵 佐藤 春旗 前田 俊行 大山 恵弘 佐藤 秀明 住井 英二郎
リファクタリングのための 変更波及解析を利用した テスト支援ツールの提案
プログラム静的解析手法の効率化と 解析フレームワークの構築に関する研究
変更文の移動を可能にした 静的単一代入形式上の部分冗長性除去
情報工学総合演習 D-I 近似アルゴリズム 埼玉大学 理工学研究科 山田 敏規、 橋口 博樹、 堀山 貴史
チーム FSEL 立命館大学情報理工学部 ソフトウェア基礎技術研究室
型付きアセンブリ言語を用いた安全なカーネル拡張
静的情報と動的情報を用いた プログラムスライス計算法
細かい粒度でコードの再利用を可能とするメソッド内メソッドのJava言語への導入
ソードコードの編集に基づいた コードクローンの分類とその分析システム
勉強会その3    2016/5/1 10 8分35秒 データの表現 演算.
独立大学法人・電気通信大学 大学院情報システム学研究科 情報ネットワーク学専攻・並列処理学講座
動的依存グラフの3-gramを用いた 実行トレースの比較手法
関数の定義.
帰納変数 iが基本帰納変数 変数iに対して、 i := i±c という形の代入が一つのみ jがiに対する帰納変数
最適化の方法 中田育男著 コンパイラの構成と最適化 朝倉書店, 1999年 第11章.
オブジェクト指向プログラムにおける エイリアス解析手法の提案と実現
インラインスクリプトに対するデータフロー 解析を用いた XHTML 文書の構文検証
コンピュータ系実験Ⅲ 「ワンチップマイコンの応用」 第1週目 アセンブリ言語講座
アルゴリズムとプログラミング (Algorithms and Programming)
実行時情報に基づく OSカーネルのコンフィグ最小化
Structured programming
Javaプログラムの変更を支援する 影響波及解析システム
Modern Compiler Implementation in C 19章後半(451ページから)
プログラミング言語論 第五回 理工学部 情報システム工学科 新田直也.
トーリックイデアルの グレブナ基底を求める アルゴリズム – F4およびF5 –
レジスタの割付け 中田育男著 コンパイラの構成と最適化 朝倉書店, 1999年 第12章5節.
通信機構合わせた最適化をおこなう並列化ンパイラ
オープンソース開発支援のための ソースコード及びメールの履歴対応表示システム
東京工業大学 情報理工学研究科 数理・計算科学専攻 千葉研究室 栗田 亮
Javaバイトコードの 動的依存解析情報を用いた スライシングシステムの実現
プログラミング言語論 第四回 理工学部 情報システム工学科 新田直也.
バイトコードを単位とするJavaスライスシステムの試作
C言語を用いたマシン非依存な JITコンパイラ作成フレームワーク
先週の復習: CPU が働く仕組み コンピュータの構造 pp 制御装置+演算装置+レジスタ 制御装置がなければ電卓と同様
コンパイラ 2011年10月20日
Javaバーチャルマシンを利用した 動的依存関係解析手法の提案
コーディングパターンの あいまい検索の提案と実装
JAVAバイトコードにおける データ依存解析手法の提案と実装
JavaScriptを含んだHTML文書に対する データフロー解析を用いた構文検証手法の提案
ガイダンス 電子計算機 電気工学科 山本昌志 1E
地域情報学 C言語プログラミング 第4回 while文、do~while文、switch文、 2次元配列、ポインタ 2017年11月10日
オブジェクト指向言語論 第五回 知能情報学部 新田直也.
欠陥検出を目的とした類似コード検索法 吉田則裕,石尾隆,松下誠,井上克郎 大阪大学 大学院情報科学研究科
エイリアス関係を考慮した Javaプログラム用静的スライシングツール
PROGRAMMING IN HASKELL
回帰テストにおける実行系列の差分の効率的な検出手法
プログラミング言語論 第九回 理工学部 情報システム工学科 新田直也.
プログラミング演習I 2003年6月11日(第9回) 木村巌.
オブジェクト指向言語論 第七回 知能情報学部 新田直也.
オブジェクト指向言語における セキュリティ解析アルゴリズムの提案と実現
プログラミング言語論 第九回 理工学部 情報システム工学科 新田直也.
オブジェクト指向言語論 第七回 知能情報学部 新田直也.
情報処理Ⅱ 小テスト 2005年2月1日(火).
情報処理Ⅱ 第3回 2004年10月19日(火).
情報処理Ⅱ 2006年10月20日(金).
情報処理Ⅱ 第8回:2003年12月9日(火).
プログラミング 2 静的変数.
Presentation transcript:

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

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

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

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

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

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形式では,データフロー解析や最適化が見通しよく行なえる.

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

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

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

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

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

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

最適化の例 条件付定数伝播 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や黒字の部分が削除される

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: 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

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

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

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

教育・研究への適用 教育への適用 研究への適用 COINSを用いたコンパイラの集中講義(2004年7月)内1日が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). 須藤大二朗,佐々政孝:比較照合法によるコンパイラ最適化器の正しさの検証,日本ソフトウェア科学会第7回プログラミングおよびプログラミング言語ワークショップ (PPL2005) 論文集,(2005年3月). 溝渕裕司,立川英,佐々政孝:変更文の移動を可能にした静的単一代入形式上での部分冗長性除去,日本ソフトウェア科学会第7回プログラミングおよびプログラミング言語ワークショップ (PPL2005) 論文集,(2005年3月).

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

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

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