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

• Item type: Trans(1)
• 公開日: 2002-09-15
• タイトル: 別名情報に基づくレジスタ促進
• タイトル / 言語: en
• タイトル: Register Promotion Based on Alias Information
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京理科大学理工学部情報科学科
• 著者所属: 慶應義塾大学理工学部情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Information Sciences, Faculty of Science and Technology, Tokyo University of Science
• 著者所属(英): en
• 著者所属(英): Department of Information and Computer Science, Faculty of Science and Technology, Keio University
• 著者名: 滝本, 宗宏; 原田, 賢一
• 著者名(英): Munehiro, Takimoto; Kenichi, Harada
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 静的単一代入形式をはじめとするプログラム解析用のプログラム形式は，多くの有効かつ複雑な解析アルゴリズムの実現を可能にした．これらのプログラム形式のほとんどが変数の定義と使用の関係に基づいているので，解析の精度は，変数へのアクセスをどれほど詳細に明示化できるかに依存する．一般に，変数の定義と使用の明示化は，レジスタ促進によって仮想レジスタレベルで行われることが多い．仮想レジスタは，その定義あるいは使用が不明な場合に，対応する変数からのロード命令またはストア命令の挿入がそれぞれ必要になる．このとき，解析に利用可能な定義と使用は，ロード命令からストア命令までの範囲内に限定される．したがって，その範囲を拡大することは，解析の詳細化に直接貢献するので，冗長なロード/ストア命令を除去することが重要である．本研究は，従来考慮されなかったMay 別名の1 種である部分Must 別名に基づいて，冗長なロード命令を除去する手法を提案する．従来，ロード命令の除去は，ロード対象になる記憶場所への参照式が同じものだけを取り扱ってきた．これに対して，部分Must 別名に基づく冗長除去は，同じ記憶場所を表しているすべての別名を対象にすることができる．本手法では，また，部分Must 別名をMust 別名に変換して，間接参照除去を同時に行うことができる．本手法の実現は，ビットベクタ表現を用いた単方向データフロー解析を用いて行うことができるので，プログラムサイズをn とした計算量は，O( n 2 )で抑えられる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 43, 号 SIG08(PRO15), p. 49-61, 発行日 2002-09-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会