式の出現に基づく大域値番号付け

• Item type: Trans(1)
• 公開日: 2007-03-15
• タイトル: 式の出現に基づく大域値番号付け
• タイトル / 言語: en
• タイトル: Global Value Numbering Based on Occurrences of Expressions
• 言語: 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
• 著者名: 滝本, 宗宏; 福岡, 岳穂; 佐々, 政孝
• 著者名(英): Munehiro, Takimoto; Takeaki, Fukuoka; Masataka, Sassa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 静的単一代入形式に基づくコード最適化の1つに大域値番号付けがある．大域値番号付けは，プログラム全体から冗長な式を除去する手法であり，バージョンが一致するオペランドを持つ式を対象にすることによって，効率的な解析を可能にする．従来の大域値番号付けは，冗長を除去する1つの最適化フェーズとして考慮されることがほとんどであったので，プログラム中のすべての式の出現を対象にしていた．一方，命令スケジューリングの際に，投棄的なスケジューリングを許すと，冗長な式を生成することがあり，各命令のスケジューリングを行うたびに，冗長除去を適用することが効果的であることが知られている．命令スケジューリングは，各命令ごとに適用されるので，従来のすべての式を対象にする冗長除去法を用いるのは，非効率であった．本発表では，各式の出現ごとに，除去可能かどうかを判定し，可能であれば除去する大域値番号付けを提案する．本手法を，命令スケジューリングの際に適用する冗長除去として採用することによって，コード最適化のコストを低減させることができる．本研究では，本手法を，COINSコンパイラインフラストラクチャ上に実現し，実験を行った．本発表では，その実験結果も示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Global value numbering (GVN) is one of effective code optimizations based on static single assignment form. It achieves efficiently removing redundant expressions in entire program because of ease of detecting equality among expression occurrences. In most cases, since each previous GVNs have been considered as a redundancy elimination phase, they had to be applied to all expression occurrences. On the other hand, combining redundancy elimination with instruction scheduling is known as an effective strategy. In such strategy, using partial redundancy elimination as a redundancy elimination method enables not only compensation code to be inserted to suitable locations but also loop-shifting. Since instruction scheduling is applied to each instruction, applying exhaustive redundancy elimination to it makes such an optimization costly. We propose a new GVN approach which can be applied to each expression occurrence. Our approach checks whether the occurrence can be eliminated or not, and after that, if that is possible, it transforms the program in order to eliminate it. Such a GVN enables the instruction scheduling with redundancy elimination as mentioned to be performed efficiently. We implemented our approach as an optimization phase on COINS which is a compiler infrastructure. Its efficiency will be shown by experimental results.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 48, 号 SIG4(PRO32), p. 80-80, 発行日 2007-03-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会