Effective Demand-driven Partial Redundancy Elimination

• Item type: Trans(1)
• 公開日: 2013-08-29
• タイトル: Effective Demand-driven Partial Redundancy Elimination
• タイトル / 言語: en
• タイトル: Effective Demand-driven Partial Redundancy Elimination
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [通常論文] compiler, code optimization, partial redundancy elimination, global value numbering
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Tokyo University of Science
• 著者所属: Tokyo University of Science
• 著者所属(英): en
• 著者所属(英): Tokyo University of Science
• 著者所属(英): en
• 著者所属(英): Tokyo University of Science
• 著者名: Yasunobu, Sumikawa; Munehiro, Takimoto
• 著者名(英): Yasunobu, Sumikawa; Munehiro, Takimoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Partial Redundancy Elimination (PRE) is a technique that not only removes redundant expressions but also moves loop-invariant expressions out of a loop based on the lexical equality among expressions. Traditional PRE analyzes the entire program exhaustively to remove any redundancy, whereas demand-driven PRE, which propagates a query about whether the expression is redundant, can be applied to each expression with lower costs so that it, can remove the redundancy efficiently, including that which is not exposed initially by using copy propagation in the topological sort order. Furthermore, demand-driven PRE allows loop-invariant expressions to be moved out of a loop speculatively by tracing the query propagations, which allows more redundant expressions to be eliminated through algebraic transformations. However, the demand-driven approach with copy propagation is sometimes more costly than the exhaustive approach because it may entail unnecessary analyses. Thus, we propose a technique that suppresses unnecessary query propagations, which does not require any copy propagation. This is achieved by applying global value numbering and recording the value numbers reached at each program point before the query propagation. We implemented our technique using a real compiler and evaluated it with SPEC benchmarks. The experimental results showed that our technique can improve the analysis efficiency by about 56.8% in the best case.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Partial Redundancy Elimination (PRE) is a technique that not only removes redundant expressions but also moves loop-invariant expressions out of a loop based on the lexical equality among expressions. Traditional PRE analyzes the entire program exhaustively to remove any redundancy, whereas demand-driven PRE, which propagates a query about whether the expression is redundant, can be applied to each expression with lower costs so that it, can remove the redundancy efficiently, including that which is not exposed initially by using copy propagation in the topological sort order. Furthermore, demand-driven PRE allows loop-invariant expressions to be moved out of a loop speculatively by tracing the query propagations, which allows more redundant expressions to be eliminated through algebraic transformations. However, the demand-driven approach with copy propagation is sometimes more costly than the exhaustive approach because it may entail unnecessary analyses. Thus, we propose a technique that suppresses unnecessary query propagations, which does not require any copy propagation. This is achieved by applying global value numbering and recording the value numbers reached at each program point before the query propagation. We implemented our technique using a real compiler and evaluated it with SPEC benchmarks. The experimental results showed that our technique can improve the analysis efficiency by about 56.8% in the best case.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 6, 号 2, p. 33-44, 発行日 2013-08-29
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会