May別名除去

情報処理学会 Web Site 参考文献27件

書誌事項

タイトル別名
  • May ベツミョウ ジョキョ
  • Eliminating May - aliases

この論文をさがす

説明

コード最適化やプログラム解析は，変数の定義と使用の関係（def-use relation ，定義?使用関係）を基にして行われるものが多い．与えられたプログラムにおいて，別名変数が用いられていると，変数の定義?使用関係が曖昧になるので，別名変数を見つけ出すこと（alias analysis ，別名解析）は，コード最適化の効果や解析の精度に大きく貢献する．別名解析によって得られる別名は，一般にMust別名とMay 別名の2 つに分類される．Must 別名は，つねに同一のメモリ領域を表す別名であり，プログラム中のMust 別名は，統一的な名前の付替えによって定義?使用関係を正確に示すことができる．これに対してMay 別名はどのメモリ領域を表すのかが特定できないので，May 別名が用いられている場合には，定義?使用関係を正確に示すことができない．本研究では，May 別名を，制御フローに依存して参照先が変わる部分Must 別名と，その他のMay 別名とに区別する．制御フロー上のあるプログラム点における部分Must 別名は，特定の実行パスからそのプログラム点に少なくとも1 つのMust 別名が到達するという性質をもつ．本稿では，このような部分Must 別名をコード巻上げの手法によってMust 別名に変換し，従来法よりもさらに正確な定義?使用関係を明らかにする手法を提案する．本手法は，別名解析が終了していることを前提として，部分冗長除去に用いられるデータフロー解析と類似の解析法によって，まず部分Must 別名を見つけ出し，次にそれらがMust別名となるプログラム点を求める．これらの解析は，ビットベクタ表現を用いた単方向データフロー解析によって実現でき，プログラムサイズをn とした計算量は，O n 2 )で抑えられる．

Collecting aliasing information is useful to practical code optimizations and sophisticate static program analysis,because aliases make relations between definitions and uses of program variables ambiguous.The aliases introduced by pointer dereferences,is classified into must-aliases which always refer to the same memory locationand may-aliases which may refer to different memory locations.Especially,the must-alias information can be effectively used to deal with their dereferences as referenced variables and to expose more relations between de ?nitions and uses.We propose a new technique for replacing may-aliases with must-aliases. This approach pays attention to may-aliases of a specific property,which represents references to the same memory locationona certainexecutionpath.Such alias,called as partial mustalias can be hoisted to the program points where they turn to be must-alias.This eliminating partial must-aliases will lead to an effective result as a pre-transformationthat proceeds to application of various techniques based on static analysis.Since our approach can be implemented by a simple data ?ow analysis using bit-vector representation similar with partial redundancy elimination,its complexity is shown by O n 2 )pessimistically.

収録刊行物

参考文献 (27)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ