疎な要求駆動型データフロー解析

• Item type: Trans(1)
• 公開日: 2005-08-15
• タイトル: 疎な要求駆動型データフロー解析
• タイトル / 言語: en
• タイトル: Sparse Demand-driven Dataflow Analysis
• 言語: 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
• 著者所属(英): Kanrikogaku Kenkyusho, Ltd.
• 著者所属(英): en
• 著者所属(英): Department of Mathematical and Computing Sciences Graduate School of Information Science and Engineering Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Information and Computer Science Faculty of Science and Technology, Keio University
• 著者名: 滝本, 宗宏; 福岡, 岳穂; 佐々, 政孝; 原田, 賢一
• 著者名(英): Munehiro, Takimoto; Takeaki, Fukuoka; Masataka, Sassa; Ken’ichi, Harada
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: プログラム解析やコード最適化においては，データフロー解析がよく使用される．この解析は，目的とする情報をプログラム全体から収集することを仮定しているので，プログラムの一部分だけを解析したい場合や，一部の解析結果を用いてプログラムを変形し，さらに変形後のプログラム上で他の部分の解析を行うことを繰り返す場合には，余分なコストが必要になる．このような場合には，情報を必要とするプログラム点について，そこに影響を及ぼす部分だけを解析する要求駆動型のデータフロー解析が有効である．しかしながら，一般のデータフロー解析には，1 ワード分の情報を並列計算するビットベクタ法や，解析に不要な部分を訪問せずに解析を行う疎な解析法が考案されているのに対して，要求駆動型のデータフロー解析については，これまで高速化手法の提案が行われていない．本稿では，解析に不要なプログラム点を訪問しない疎な要求駆動型のデータフロー解析を提案する．あるプログラム点での解析結果に基づいてプログラムを変形した後に，他のプログラム点についての解析を行おうとすると，その変形にともなって，解析が不要な部分も変わる可能性がある．本手法では，プログラムの深さに相当するランク情報を用いて不要なプログラム点を動的に計算するので，プログラム変形が行われた場合でも，変形後のプログラムを反映した疎な解析が実現できる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Demand-driven dataflow analysis (DFA), which propagates queries as to a specific dataflow fact at a program point, is more efficient than exhaustive DFA if it is used for interactive program analyzing tools or incremental code optimizations. However, though the exhaustive DFA can be implemented by efficient solving methods like sparse propagation method, there is no such efficient method proposed for demand-driven analysis. This is because, in case where demand-driven DFA and program transformation based on its result are repeatedly applied, sparse information cannot be reflected by results of previous transformation. So we propose sparse demand-driven DFA which computes sparse information on demand. Our technique enables avoiding unnecessary propagations to some program points by propagating queries along dominator tree edges. To propagate queries on dominator tree edges, validity checking of the propagation is needed. For implementation of the efficient checking, we introduce ranks which mean depth of node from start node in CFG. If the ranks of target program points to be propagated are within range between current program point’s rank and its dominator’s rank, the shortcut propagation are suppressed. We show the efficiency of our technique by comparing experimental results applying a traditional demand-driven DFA to available expressions.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 46, 号 SIG11(PRO26), p. 16-26, 発行日 2005-08-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会