データフローグラフに基づく部分的冗長計算除去の拡張

概要

論文の詳細を見る
冗長計算の除去は、コード最適化において重要な課題であり、ループの内部からの冗長計算の除去は実行時の計算量の軽減に大きく貢献する.冗長計算の除去だけでなく、除去できないものでも、より計算量の少なくなる場所に計算を移動する手法としてMorelとRenvoiseの部分的冗長計算(partial redundant computation)の除去[MR]がある。この手法はループ外コード移動、共通部分式の除去などを同時に行える強力なものである。近年、このMorelとRenvoiseの手法を拡張しようとする研究が盛んである.この中で、式が生成する値に注目し、同じ値を生成する式を検出することによって、冗長計算の認識レベルを上げようとする試みがある。本研究では、フローグラフからデータ依存グラフのみを取り出し、データフローモデルを用いずに、同じ値を生成する定義を粗に結び合わせたデータフローグラフを構築する手法を提案する。この手法を用いることによって過去の同様な研究[RWZ][SKR]よりも強力かつ効率的に最適化を行うことができる。
1994-03-07