Effective Partial Redundancy Elimination

Effective Partial Redundancy EliminationPreston BriggsKeith D. CooperDepartment of Computer ScienceRice UniversityHouston, Texas 77251–1892AbstractPartial redundancy elimination is a code optimizationwith a long history of literature and implementation. Inpractice, its effectiveness depends on issues of namingand code shape.

This paper shows that a combinationof global reassociation and global value numbering canincrease the effectiveness of partial redundancy elimination. By imposing a discipline on the choice of namesand the shape of expressions, we are able to expose moreredundancies.As part of the work, we introduce a new algorithmfor global reassociation of expressions. It uses global information to reorder expressions, creating opportunitiesfor other optimizations. The new algorithm generalizesearlier work that ordered FORTRAN array address expressions to improve optimization [25].1IntroductionPartial redundancy elimination is a powerful optimization that has been discussed in the literature for manyyears (e.g., [21, 8, 14, 12, 18]).

Unfortunately, partialredundancy elimination has two serious limitations. Itcan only recognize lexically-identical expressions; thismakes effectiveness a function of the choice of names inthe front end. It cannot rearrange subexpressions; thismakes effectiveness a function of the shape of the codegenerated by the front end. The net result is that decisions made in the design of the front end dictate theeffectiveness of partial redundancy elimination.This paper shows how an optimizer can use globalreassociation (see Section 3.1) and a form of partitionbased global value numbering [2] to improve the effectiveness of partial redundancy elimination.

We considerthese to be enabling transformations. They do not im-prove the code directly; instead, they rearrange the codeto make other transformations more effective. The combination of these transformations with partial redundancy elimination results in removing more redundantexpressions, hoisting more loop-invariant expressions(and sometimes hoisting them farther), and removingsome partially-dead expressions.

By using global reassociation and partition-based global value numbering togenerate the code shape and name space automatically,the optimizer can isolate partial redundancy eliminationfrom the vagaries of the front end. This lets the optimizer obtain good results on code generated by sourcesother than a careful front end – for example, on code resulting from other optimization passes or from restructuring front ends.The primary contributions of this paper are: (1) theuse of reassociation to achieve a canonical code shape forexpressions, (2) the use of partition-based global valuenumbering to achieve a canonical naming, and (3) a newtechnique for global reassociation of expressions. Additionally, we present experimental evidence that demonstrates the effectiveness of partial redundancy elimination, with and without our transformations.2Partial Redundancy EliminationPartial redundancy elimination (PRE) is a global optimization introduced by Morel and Renvoise [21].

Itcombines and extends two other techniques.common subexpression elimination An expression is redundant at some point p if and only if it is computed along every path leading to p and none of itsconstituent subexpressions has been redefined. If eis redundant at p, the evaluation of e at p can bereplaced with a reference.This work has been supported by ARPA through ONR grantN00014-91-J-1989.loop-invariant code motion An expression is loop invariant if it is computed inside a loop and its valueis identical in all the iterations of the loop. If e isinvariant in a loop, it can be computed before theloop and referenced, rather than evaluated, insidethe loop.To appear in Sigplan PLDI, June 1994.PRE combines and extends these two techniques.Source codeCodex+y+zTree+@?,Rx y zLow-level, three-address coder1 ← rx + ryr2 ← r1 + rzr1 ← rx + rzr2 ← r1 + ryr1 ← ry + rzr2 ← r1 + rx+ AU+ rzAUrx ry+ UA+ ryAUrx rz+ UA+ rxAUry rzFigure 1: Alternate Code ShapesAn expression is partially redundant at point p if itis redundant along some, but not all, paths that reachp.

PRE converts partially-redundant expressions intoredundant expressions. The basic idea is simple. First,it uses data-flow analysis to discover where expressionsare partially redundant. Next, it solves a data-flowproblem that shows where inserting copies of a computation would convert a partial redundancy into a fullredundancy. Finally, it inserts the appropriate code anddeletes the redundant copy of the expression.A key feature of PRE is that it never lengthens anexecution path.

To see this more clearly, consider theexample below. In the fragment on the left, the secondcomputation of x + y is partially redundant; it is onlyavailable along one path from the if. Inserting an evaluation of x+y on the other path makes the computationredundant and allows it to be eliminated, as shown inthe right-hand fragment.

Note that the left path staysthe same length while the right path has been shortened.if p branch??y ← ...x ← ...←x+y-if p branch⇒?←x+ypartially redundant?y ← ...← x+y?x ← ...←x+y-?H←x+HyredundantLoop-invariant expressions are also partially redundant,as shown in the example below. On the left, x + y ispartially redundant since it is available from one predecessor (along the back edge of the loop), but not theother.

Inserting an evaluation of x + y before the loopallows it to be eliminated from the loop body.x←?← x+y···if p branch ⇒partially redundantx←← x+y?H←x+Hy ···if p branchredundant2.1Code ShapeThe optimizer in our compiler uses a low-level intermediate language. Most operations have three addresses:two source operands and a target.

Translating a sourceexpression to three-address code can introduce artificialordering constraints. Figure 1 shows the different possibilities for the source expression x + y + z.Consider the case where rx = 3, rz = 2, and ry isa variable. Only the middle shape will allow constantpropagation to transform the expression into y + 5. Alternatively, if ry and rz are both loop invariant, onlythe rightmost shape will allow PRE to hoist the loopinvariant subexpression. This case is quite important,since it arises routinely in multi-dimensional array addressing computations.The choice of expression ordering occurs with associative operations such as add, multiply, and, or, min, andmax. In general, there are a combinatorial number of orderings for an associative expression having n operands.Source language specifications sometimes restrict possible reorderings, especially in the case of floating-pointarithmetic where numerical precision may be affected.The large number of possible orderings makes an exhaustive search for optimal solutions impractical.2.2NamingAnother important issue is the selection of names.

Ourimplementation of PRE distinguishes between variablenames and expression names. This distinction was introduced by Morel and Renvoise [21, page 97]. A variable name is the target of a copy instruction; conceptually, these correspond to source-level assignments. Anexpression name is the target of a computation – inpractice, an instruction other than a branch or copy.This gives every expression (and subexpression) a name.Thus, the statement i = i + 1 might be represented as:r1 ← 1r2 ← ri + r1ri ← r2where ri is the name of the variable i, r1 is the nameof the expression “1”, and r2 is the name of expression“ri + r1 ”.

Within a single routine, lexically-identicalexpressions always receive the same name. Therefore,whenever we see the expression ri + r1 , we would expectto see it named r2 .This naming discipline can be implemented in thecompiler’s front end by maintaining a hash table of expressions and creating a new name whenever a new expression is discovered [3]. Unfortunately, relying on thefront end limits the applicability of PRE. It is difficult tomaintain the naming rules across other optimizations;thus, PRE must be run first and only once. Furthermore, the ability of PRE to recognize identities is limitedby the programmer’s choice of variable names. Considerthe following source sequence and its corresponding intermediate representation:x = y + za = yb = a + zr1 ← ry + rzrx ← r1ra ← ryr2 ← ra + rzrb ← r2Obviously, r1 and r2 receive the same value (that is,the expression named by r2 is redundant).

PRE cannot discover this fact even though value numbering caneliminate this redundancy [10]. Of course, this is a simple example, but its very simplicity should suggest thelarge number of opportunities missed by PRE when considering an entire routine.3Effective PRETo address the limitations of PRE, we propose a set oftechniques that reorder and rename expressions. Globalreassociation uses information about global code shapeto rearrange individual expressions.

Global value numbering uses knowledge about run-time equivalence ofvalues to rename expressions. In combination, theytransform the program in a way that exposes more opportunities to PRE.3.1Global ReassociationTo address the code shape problems, we use a techniquecalled global reassociation. It uses algebraic propertiesof arithmetic to rearrange the code.