拡張値グラフに基づく効果的な部分冗長除去法

概要

論文の詳細を見る
プログラミング言語処理系が行うコード最適化の中で, 部分冗長除去の手法は, 共通部分式の除去ばかりでなく, ループ不変コードのループ外移動をも統合的に行える優れたコード最適化である. しかし, 通常の部分冗長除法は, 構文上での同じ (構文等価)式を処理の対象にしているので, 構文上は異なっていても, 同じ値を計算する (意味等価)式を除去の対象にはできなかった. 本論文では, 意味等価な式の解析を行い, その後, 意味等価な式に対して部分冗長除去を適用するという, 効果的で効率の良い部分冗長計算の除去法を提案する. 本手法では, 拡張値グラフと呼ぶデータ構造を新たに導入する. 拡張値グラフは, 与えられたプログラム中の式を各計算点に移動したときの大域的な構造と等価関係を統一的に表現する. 拡張値グラフの上では, 計算順序を考慮することなく, 意味等価な式を見つけることができる. 部分冗長除去のためのデータフロー解析は, 式どうしの依存関係を保ちながら行うことができるので, アルゴリズムを簡素化し, 高速化することができる. さらに, 拡張値グラフ上での定数畳込みによって, 従来, 原始プログラムに現れる式だけを対象にしていた定数畳込みを,新たに畳込み可能な式を算出する手法に拡張することができる.
1997-11-15

拡張値グラフに基づく効果的な部分冗長除去法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク