質問伝播に基づく投機的部分冗長除去

• Item type: Trans(1)
• 公開日: 2009-11-20
• タイトル: 質問伝播に基づく投機的部分冗長除去
• タイトル / 言語: en
• タイトル: Speculative Partial Redundancy Elimination Based on Question Propagation
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京理科大学
• 著者所属(英): en
• 著者所属(英): Tokyo University of Science
• 著者名: 滝本, 宗宏
• 著者名(英): Munehiro, Takimoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: コンパイラが行うコード最適化の1つである部分冗長除去は，冗長な式を除去するとともに，ループ不変式をループの外に移動する強力な手法である．部分冗長除去に基づいて行うプログラム変形は，いずれの実行経路上にも式を増加させないことを保証しており，その意味で，安全な最適化であるといわれる．一方，ループ内に存在する計算のように，頻繁に実行されることが予想される式は，たとえ実行経路上の式の数を増加させても，ループの外に移動させる投機的な移動を行う方が，プログラムの効率的な実行に貢献する場合がある．本研究では，ループ内の式についてだけ，投機的な移動によって，ループの外に移動させる部分冗長除去法を提案する．従来，部分冗長除去において，一部の実行経路上で冗長な部分冗長な式とループ不変式とを見分けることは困難であった．本手法では，質問伝播という要求駆動型の解析法を用いることによって，任意の制御フローグラフに対して，ループ不変式だけを投機的にループ外に移動させることができる．本手法の効果を示すために，本手法をCコンパイラに実装し，評価を行った．その結果，従来法と比べ，実行効率が17%以上向上する場合があることを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Partial redundancy elimination (PRE) is the code optimization which not only removes redundant expressions but also moves loop-invariant expressions out of a loop, and therefore it is known as one of the strongest optimizations. Since the program transformation performed by PRE guarantees that it never makes the number of expressions increase on any execution path, it is a safe code optimization. On the other hand, frequently executed expressions such as ones inside a loop may contribute to efficient execution of the program due to moving them out of it even if they make the number of expressions increase on some execution paths. In this paper, we propose a new PRE moving only loop-invariant expressions out of the loop based on speculation. Previously, PRE could not distinguish loop-invariant expressions from the partially redundant expressions which are redundant on some execution paths. Our approach achieves such a speculative loop-invariant code motion on any control flow graphs using demand-driven method which is called question propagation. We implemented our approach on a C compiler, and evaluated it for some benchmarks. As a result, we found that some programs were more than 17% improved in efficiency.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 2, 号 5, p. 15-27, 発行日 2009-11-20
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会