質問伝播に基づく投機的部分冗長除去
スポンサーリンク
概要
- 論文の詳細を見る
コンパイラが行うコード最適化の1つである部分冗長除去は,冗長な式を除去するとともに,ループ不変式をループの外に移動する強力な手法である.部分冗長除去に基づいて行うプログラム変形は,いずれの実行経路上にも式を増加させないことを保証しており,その意味で,安全な最適化であるといわれる.一方,ループ内に存在する計算のように,頻繁に実行されることが予想される式は,たとえ実行経路上の式の数を増加させても,ループの外に移動させる投機的な移動を行う方が,プログラムの効率的な実行に貢献する場合がある.本研究では,ループ内の式についてだけ,投機的な移動によって,ループの外に移動させる部分冗長除去法を提案する.従来,部分冗長除去において,一部の実行経路上で冗長な部分冗長な式とループ不変式とを見分けることは困難であった.本手法では,質問伝播という要求駆動型の解析法を用いることによって,任意の制御フローグラフに対して,ループ不変式だけを投機的にループ外に移動させることができる.本手法の効果を示すために,本手法をCコンパイラに実装し,評価を行った.その結果,従来法と比べ,実行効率が17%以上向上する場合があることを確認した.
- 2009-11-20
著者
関連論文
- プログラムスライシングに基づく関心事グラフ構築
- 質問伝播に基づく投機的部分冗長除去
- 特集「最新コンパイラ技術とCOINSによる実践」の編集にあたって
- 静的単一代入形式を用いた最適化(発展編)(最新コンパイラ技術とCOINSによる実践)
- 静的単一代入形式を用いた最適化(導入編)(最新コンパイラ技術とCOINSによる実践)
- 部分冗長除去に基づく大域命令スケジューリング
- 式の出現に基づく大域値番号付け
- 部分冗長除去の命令スケジューリングへの応用
- コンパイラ・インフラストラクチャにおける静的単一代入形式最適化部の実現
- 疎な要求駆動型データフロー解析
- 高階移動エージェント向けJavaパッケージの開発 : 関数型言語実装の一手段
- 高階移動エージェントのロボット制御への応用 : 実用システムに向けて
- 一般支配関係の効率的な検査法
- 別名情報に基づくレジスタ促進
- May別名除去
- 別名情報による段階的詳細化に基づいた等価式発見
- 依存グラフを用いたコード移動妨害領域の効果的な除去法
- 拡張値グラフを用いた部分無効コード除去法
- 効率的な完全冗長除去
- 配列の次元を考慮した大域ロード命令集約(学生及び若手(パラレルセッション:実装))
- 配列の次元を考慮した大域ロード命令集約(学生及び若手(パラレルセッション:実装))
- ARとジェスチャを用いたエージェント用インタフェースの開発(Al応用(1))