別名情報に基づくレジスタ促進

概要

論文の詳細を見る
静的単一代入形式をはじめとするプログラム解析用のプログラム形式は,多くの有効かつ複雑な解析アルゴリズムの実現を可能にした.これらのプログラム形式のほとんどが変数の定義と使用の関係に基づいているので,解析の精度は,変数へのアクセスをどれほど詳細に明示化できるかに依存する.一般に,変数の定義と使用の明示化は,レジスタ促進によって仮想レジスタレベルで行われることが多い.仮想レジスタは,その定義あるいは使用が不明な場合に,対応する変数からのロード命令またはストア命令の挿入がそれぞれ必要になる.このとき,解析に利用可能な定義と使用は,ロード命令からストア命令までの範囲内に限定される.したがって,その範囲を拡大することは,解析の詳細化に直接貢献するので,冗長なロード/ストア命令を除去することが重要である.本研究は,従来考慮されなかったMay別名の1種である部分Must別名に基づいて,冗長なロード命令を除去する手法を提案する.従来,ロード命令の除去は,ロード対象になる記憶場所への参照式が同じものだけを取り扱ってきた.これに対して,部分Must別名に基づく冗長除去は,同じ記憶場所を表しているすべての別名を対象にすることができる.本手法では,また,部分Must別名をMust別名に変換して,間接参照除去を同時に行うことができる.本手法の実現は,ビットベクタ表現を用いた単方向データフロー解析を用いて行うことができるので,プログラムサイズをnとした計算量は,O(n^2)で抑えられる.
2002-09-15

別名情報に基づくレジスタ促進

スポンサーリンク

概要

著者

関連論文

スポンサーリンク