Effective Demand-driven Partial Redundancy Elimination

概要

論文の詳細を見る
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.
2013-08-29