Register Promotion Based on Alias Information

IPSJ Web Site 26 References

Bibliographic Information

Other Title
  • 別名情報に基づくレジスタ促進
  • ベツミョウ ジョウホウ ニ モトヅク レジスタ ソクシン

Search this article

Description

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

Program forms e.g.the static single assignment form have brought about development of a variety of effective but complex algorithms for static analyses or code optimizations.Since these forms are based on relations between de ?nition and use of variables,called def-use relation,their availability depends on how precisely accesses to memory locations can be represented explicitly.In general,explicit representation of def-uses are often realized by register promotion techniques,which allocate variables to virtual registers.In the virtual register form,accesses to unknown memory locations are explicitly represented by load and store instructions,which restrict the region for available def-use relations.Therefore,removing load and store which expand such region contributes to improvement of traditional program analyses on accuracy of their results.We propose a new technique to remove redundant load operations fromvirtual register forms based on partial must-aliases and show its effectiveness by experimental results.Our approach can detect the redundant loads of variables aliasing with a unique memory location,while in conventional techniques,detection of them is limited to same access pattern.Furthermore,our technique has effectiveness to transform a part of may-aliases into must-aliases.Since our approach can be implemented by simple data ?ow analysis using bit-vector representation similar with partial redundancy elimination,its complexity is given by O( n 2 )pessimistically.

Journal

References(26)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top