部分的無効コードの効率的除去法

概要

論文の詳細を見る
コード最適化の分野において、制御の流れによっては,実行されないコードを除去するための手法が最近注目されている.このような制御依存で無効になるコードは部分的無効コード(Partial Dead Code)[BC][KOS]と呼ばれる.部分的無効コード除去において,特に,二次的効果を考慮した徹底的な解析を行う手法として,J.Knoop,O.Ruthing,B.Steffenの研究が発表されている.この手法は,コード降下(Code Sinking)と無効コード除去を交互に行うプログラム変形を,プログラムが不変になるまで,適用することによって実現されている.2つの相互に依存するアルゴリズムの形により,非常に大きな計算コストを必要とする.本稿では,この二次的効果を含む部分的無効コード除去を効率的に行う手法を提案する.コストを大きくする,コード降下と無効コード除去の相互依存性を排除し,それぞれ,独立に適用する.2つの解析の間で保存されるべき依存情報は,グラフの形(拡張値グラフ)で保持する.コード降下を行い,拡張値グラフにより,プログラムの意味を変えないよう,降下の範囲を修正したのち、無効コード除去を適用する.
1995-03-15