静的単一代入形式上で通常形式部分冗長除去を実現する汎用的手法
スポンサーリンク
概要
- 論文の詳細を見る
部分冗長除去(PRE)は,部分的に冗長な式を除去する変換で,共通部分式除去とループ不変式移動の効果を含んだ効果的なプログラム最適化である.このPREを,最適化に適した形式である静的単一代入(SSA)形式上で行おうという従来研究がいくつかあるが,これは一般には容易ではない.その理由は,SSA形式の特徴である,変数名の一意性に関する規則がPREの実装の妨げになるからである.たとえば,同じ名前であった変数どうしがSSA形式化にともない異なる名前になり,変数名の同一性の判断ができなくなるといった問題があげられる.このような問題に対し,従来手法では,PREをSSA形式上で実現するために特別なデータ構造を用いるなど複雑な処理を行っていた.これに対し本論文では,SSA形式でありながら通常形式にも近い性質を持つCSSA形式とphicongruence classというものを利用すれば,SSA形式でも通常形式における変数名の同一性が判断できることに着目した.その事実に基づいて,通常形式のPREアルゴリズムをSSA形式に適用する手法を提案した.この手法は汎用的なものであり,挿入点の決定・式の挿入・式の置き換え(冗長性の除去)という通常の手順に従うPREであれば,原則としてアルゴリズムによらずSSA形式に対応させることができ,また元々のPREのアルゴリズムの枠組みを変える必要もない.本手法を確かめる実験として,代表的なPREアルゴリズムの1つであるLazy Code MotionをSSA形式上のアルゴリズムに変換し,変換後でも部分冗長除去の効果が変わりなく発揮されていることを確認した.
- 一般社団法人情報処理学会の論文
- 2008-01-15
著者
関連論文
- 属性文法に基づくテストプログラム生成器の設計と実装
- 属性文法の系統的デバッグ法
- 双方向CTLによるJava最適化器の生成
- VoIPにおける音声品質補償方式の検討
- 自動的等価性差分の抽出によるSSAコンパイラ最適化器の生成するコードの正しさの検証
- リサーチ9 コンパイラにおける字句解析・構文解析過程の視覚化
- コンパイラにおける構文解析過程の視覚化
- 静的単一代入形式を用いた最適化(発展編)(最新コンパイラ技術とCOINSによる実践)
- 静的単一代入形式を用いた最適化(導入編)(最新コンパイラ技術とCOINSによる実践)
- 式の出現に基づく大域値番号付け
- コンパイラ・インフラストラクチャにおける静的単一代入形式最適化部の実現
- 疎な要求駆動型データフロー解析
- Java言語上の細粒度マルチスレッドフレームワークにおける問題点の考察
- BDDを利用したCプログラムのfield-sensitiveなポインタ解析(プログラム解析,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- Array SSAとそれを用いた最適化の実装と評価(プログラム解析,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- BDDを利用したCプログラムのfield-sensitiveなポインタ解析(プログラム解析,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- Array SSAとそれを用いた最適化の実装と評価(プログラム解析,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- COINSコンパイラ・インフラストラクチャの開発(ソフトウェア論文,最新コンパイラ技術とCOINSによる実践)
- 静的単一代入形式上で通常形式部分冗長除去を実現する汎用的手法
- コンパイラ・インフラストラクチャCOINSを用いたSSA最適化(その2)(21世紀のコンパイラ道しるべ・・COINSをベースにして,連載6)
- コンパイラ・インフラストラクチャCOINSを用いたSSA最適化(その1)(21世紀のコンパイラ道しるべ・・COINSをベースにして)
- 静的単一代入形式からの逆変換アルゴリズムの比較と評価
- 属性文法の系統的デバッグ法におけるバグ絞り込みの効率化(プログラミングおよびプログラミング言語)
- アセンブリ言語上でのプログラム特化
- SSA形式によるレジスタ割付
- LR属性文法に基づいたインクリメンタルな属性評価
- 属性文法に基づくグラフィカルユーザインタフェース生成系とその評価
- SSA形式を利用したPredicated Execution向け命令スケジューリング手法
- SSA形式を利用したPredicated Execution向け命令スケジューリング手法
- SSA形式を中間言語とするコンパイラの属性文法による定式化と開発(一般発表)
- 属性文法によるSSA上の最適化器記述
- 属性文法に対するデバッガ
- 循環属性文法に基づく生成系Junについて
- 属性文法に対するデバッグ方式の構想
- 木属性文法とGUI生成系を利用したデバッガの作成
- 異機種分散環境上でのDcamlバイトコードコンパイラの設計と実現
- 異機種分散環境上でのDcamlネイティブコンパイラの設計と実現
- 異機種分散環境上のアプリケーション開発環境Dcamlシステムの構想
- プログラミング言語処理系SqueakのSHARP Zaurusへの移植とその評価
- 低レベル命令セット仮想計算機を利用した混成環境におけるプロセス移送
- 高速実行可能な低レベル命令セット仮想計算機の設計
- 東京工業大学における情報教育(物理と情報)
- 属性文法に対する系統的デバッグ方式
- 属性文法記述に基づくプログラミング環境の生成方式
- 1パス型属性文法に基づくコンパイラ生成系Rie
- フリーソフトウェアの開発と保守作業に関する考察 : コンパイラ生成系Rieを例として