文献

J-GLOBAL ID：201002252359011255   整理番号：10A0440776

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

Speculative Partial Redundancy Elimination Based on Question Propagation

著者 (1件)： 滝本宗宏 (東京理大)
資料名： 情報処理学会論文誌トランザクション(CD-ROM)  (情報処理学会論文誌 Computer Vision and Applications(CD-ROM))
巻： 2009  号： 2  ページ： PUROGURAMINGU.VOL.2,NO.5,15-27  発行年： 2010年04月15日 
JST資料番号： L7379A  ISSN： 1882-7772  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： コンパイラが行うコード最適化の1つである部分冗長除去は,冗長な式を除去するとともに,ループ不変式をループの外に移動する強力な手法である。部分冗長除去に基づいて行うプログラム変形は,いずれの実行経路上にも式を増加させないことを保証しており,その意味で,安全な最適化であるといわれる。一方,ループ内に存在する計算のように,頻繁に実行されることが予想される式は,たとえ実行経路上の式の数を増加させても,ループの外に移動させる投機的な移動を行う方が,プログラムの効率的な実行に貢献する場合がある。本研究では,ループ内の式についてだけ,投機的な移動によって,ループの外に移動させる部分冗長除去法を提案する。従来,部分冗長除去において,一部の実行経路上で冗長な部分冗長な式とループ不変式とを見分けることは困難であった。本手法では,質問伝播という要求駆動型の解析法を用いることによって,任意の制御フローグラフに対して,ループ不変式だけを投機的にループ外に移動させることができる。本手法の効果を示すために,本手法をCコンパイラに実装し,評価を行った。その結果,従来法と比べ,実行効率が17%以上向上する場合があることを確認した。(著者抄録)

シソーラス用語： *コンパイラ ,  最適化 ,  冗長性 ,  ループ ,  *プログラム実行 ,  質問 ,  伝搬 ,  流れ図 ,  フローグラフ ,  評価試験 ,  高速化
準シソーラス用語： コード最適化 ,  質問伝搬 ,  制御フロー ,  *投機的処理 ,  部分冗長除去

分類 (2件)： 言語プロセッサ  (JD03040F) ,  計算機システム開発  (JD02010R)

引用文献 (24件)：

• Aho, A. V., Sethi, R. and Ullman, J. D.: Compilers: Principles, Techniques and Tools, Addison Wesley (1986).
• Appel, A. W.: Modern Compiler Implementation in ML, Cambridge University Press (1998).
• Bodik, R., Gupta, R. and Soffa, M. L.: Complete Removal of Redundant Expressions, Proc. Programming Language Design and Implementation (PLDI’98), pp. 1-14, ACM (1998).
• Cai, Q. and Xue, J.: Optimal and Efficient Speculation-Based Partial Redundancy Elimination, Proc. IEEE/ACM Int. Symposium on Code Generation and Optimization (CGO 2003), San Francisco, pp. 91-102, IEEE Computer Society (2003).
• Click, C.: Global Code Motion Global Value Numbering, Proc. Programming Language Design and Implementation (PLDI’95), pp. 246-257, ACM (1995).

タイトルに関連する用語 (4件)： 質問 ,  伝播 ,  投機 ,  冗長