静的単一代入形式からの逆変換アルゴリズムの比較と評価
スポンサーリンク
概要
- 論文の詳細を見る
SSA形式(静的単一代入形式)は, φ関数という仮想的な関数を用いることで, 変数の定義を字面上1カ所だけになるように表した中間表現である.しかし, SSA形式を用いたプログラム中に現れるφ関数が仮想的であることから, SSA形式から直接目的コードを出すことはできない.そこで, 目的コードを出す前段階として, φ関数を消去して通常形式に戻すことが必要である.これをSSA逆変換と呼ぶ.SSA逆変換には主なアルゴリズムが2つある.以前から用いられているBriggsらのアルゴリズム, およびこれとは異なるアプローチによるSreedharらのアルゴリズムである.SSA逆変換アルゴリズムはそれぞれ異なった特徴を持つが, これらを実際に比較した研究はほとんどなされていない.このため, SSA形式を最適化コンパイラに採用するにあたって, どのSSA逆変換を用いるかの選択の指標となるものがなかった.そこで本研究では, BriggsらとSreedharらのアルゴリズムの長所と短所を明確にした.また, Briggsらのアルゴリズムに対する改良案を提案した.さらに, Briggsらのアルゴリズムとその改良案, Sreedharらのアルゴリズムの3つを実装し, 同一のコンパイラ上で, SPECベンチマークを用いて種々の条件を変えながら比較した.本研究により, Briggsらの方法ではコアレッシングすることのできないコピー文が数多く挿入されること, 実証的にはSreedharらの方法が最も優れていること, が判明した.
- 一般社団法人情報処理学会の論文
- 2005-10-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を例として