Effective Partial Redundancy Elimination, страница 2

In broad terms, ituses commutativity, associativity, and distributivity toexpose common subexpressions and loop-invariant expressions. The effects can be substantial; Cocke andMarkstein note that as much as 50% of the code in someinner loops can be eliminated as a result of reassociation [9, page 225]. Our approach has three steps:1. Compute a rank for every expression.2. Propagate expressions forward to their uses.3. Reassociate expressions, sorting their operands byranks.FUNCTION foo(y, z)s = 0x = y + zDO i = x, 100s = 1 + s + xENDDORETURN sEND fooFigure 2: Source CodeThe next three sections discuss these steps and introduce several important refinements.

To help clarifythe process, we provide a running example. Figure 2shows the source code and Figure 3 shows a translation into a simple intermediate form. This translationdoes not conform to the naming discipline discussed inSection 2.2.Computing Ranks To guide reassociation, the optimizer assigns a rank to each expression and subexpression. Intuitively, we want loop-invariant expressions tohave lower ranks than loop-variant expressions. In adeeply nested loop, we would like the rank of an expression that is invariant in the inner two loops to belower than the rank of an expression that is invariantonly in the innermost loop.

In practice, we computeranks on the SSA form of the routine during a reversepostorder traversal of the control-flow graph; therefore,our first step is to build the pruned SSA form of the routine [11, 7]. During the renaming step [11, Figure 12], weremove all copies, effectively folding them into φ-nodes.This approach simplifies the intermediate code by removing our dependence on the programmer’s choice ofvariable names (recall Section 2.2).Given the SSA form, we traverse the control-flowgraph in reverse postorder, assigning ranks.

Each blockis given a rank as it is visited, where the first block visited is given rank 1, the second block is given rank 2,enter(ry , rz )rs ← 0rx ← ry + rzri ← rxif ri > 100 branch?r1 ← rs + 1 rs ← r1 + rxri ← ri + 1if ri ≤ 100 branch?- return rsFigure 3: Intermediate Formenter(r0 , r1 )r2 ← 0r3 ← r0 + r1if r3 > 100 branch?r4 ← φ(r3 , r8 ) r5 ← φ(r2 , r7 )r6 ← r5 + 1r7 ← r6 + r3r8 ← r4 + 1if r8 ≤ 100 branch?- r9 ← φ(r7 , r2 )return r9Figure 4: Pruned SSA Formand so forth. Each expression in a block is ranked usingthree rules:1. A constant receives rank zero.2. The result of a φ-node receives the rank of theblock, as do any variables modified by procedurecalls.

This includes the result of a load instruction.3. An expression receives a rank equal to its highestranked operand. Since the code is in SSA form, eachoperand will have one definition point and will havebeen ranked before it is referenced.Figure 4 shows the result of rewriting into pruned SSAform (minimal SSA would have required many more φnodes). Notice that the copy ri ← rx has been foldedinto the first φ-node. The rank of r2 is 0, the rank ofr0 , r1 , and r3 is 1, the rank of r4 , r5 , .

. . , r8 is 2, and therank of r9 is 3. These ranks have the intuitive properties described above – loop-invariant expressions are oflower rank than loop-variant expressions and the rankof a loop-variant expression corresponds to the nestingdepth of the loop in which it changes.Forward Propagation After ranks have been computed, we copy expressions forward to their uses. Forward propagation is important for several reasons. Itbuilds large expressions from small expressions, allowing more scope for reassociation. Additionally, withoutforward propagation into loops, the compiler would haveto cycle between reassociation and PRE to ensure bestresults with deeply-nested loops. Finally, forward propagation avoids a subtle problem in PRE that arises fromthe distinction between variable names and expressionnames (see Section 5.1). As a matter of correctness, thelast reason seems to require forward propagation.We propagate each expression and subexpression asfar forward as possible, effectively building expressiontrees for φ-node inputs, values used to control programflow, parameters passed to other routines, and valuesreturned from the current routine.

In practice, we firstremove each φ-node x ← φ(y, z) by inserting the copiesx ← y and x ← z at the end of the appropriate predecessor blocks, then trace from each copy back alongthe SSA graph to construct the expression trees. (Ifnecessary, the entering edges are split and appropriatepredecessor blocks are created.)Continuing our example, Figure 5 shows how φ-nodesare eliminated by inserting copies. New blocks wererequired to hold the copies.

Figure 6 shows the effect offorward propagation.It is interesting to note that forward propagationeliminates partially-dead expressions [15, 19]. An expression is live at its definition point if its result is usedon some path to an exit. Alternatively, an expressionis dead if its result will never be used on any path. Bycopying expressions to their use points, forward propagation trivially ensures that every expression is used onevery path to an exit. Subsequent application of PREwill preserve this invariant, since PRE will never placean expression on a path where it is partially dead.On the other hand, forward propagation is not reallyan optimization. Since it duplicates code, it can expandthe size of the routine (see Section 4.3).

Furthermore, itcan move code into loops, substantially increasing pathlengths. However, recall that our plan is to transformthe code so that later application of PRE will achievegreater optimization. We expect that PRE will be ableto reverse the negative effects of forward propagationand achieve significantly improved code as a result ofthe opportunities afforded by forward propagation.enter(r0 , r1 )r2 ← 0r3 ← r0 + r1if r3 > 100 branch?r4 ← r3r5 ← r2r4 ← r8 r5 ← r7?- r6 ← r5 + 1r7 ← r6 + r3r8 ← r4 + 1if r8 ≤ 100 branch?r9 ← r7?r9 ← r2?- return r9Figure 5: After Inserting Copiesenter(r0 , r1 )r3 ← r0 + r1if r3 > 100 branch?r2r3r4r5←0← r0 + r1← r3← r2r7r8r4r5← 1 + r0 + r1 + r5 ← r4 + 1← r8← r7?- r8 ← r4 + 1if r8 ≤ 100 branch?r7 ← 1 + r0 + r1 + r5r9 ← r7partially, giving a+b×(c+d)+b×e.

This allows PRE tohoist a + b × (c + d) even if b × e cannot be hoisted. Notethat a complete distribution would result in extra multiplications without allowing any additional code motion.It is important to re-sort sums after distribution.3.2?r2 ← 0r9 ← r2?- return r9Figure 6: After Forward PropagationSorting Expressions Given ranks and expressiontrees, we are almost ready to reassociate expressions.First, though, we rewrite certain operations to exposemore opportunities for reassociation.

As suggested byFrailey [17], we rewrite expressions of the form x − y + zas x + (−y) + z, since addition is associative and subtraction is not. We also perform similar transformationsfor Boolean operations. On the other hand, we avoidrewriting x/y as x × 1/y to avoid introducing precisionproblems. We rely on a later pass, a form of global peephole optimization, to reconstruct the original operationswhen profitable.To reassociate, we traverse each expression, sortingthe operands of each associative operation by rank sothat the low-ranked operands are placed together. Thisallows PRE to hoist the maximum number of subexpressions the maximum distance. Furthermore, sinceconstants are given rank 0, all the constant operands ina sum will be sorted together.

For example, the expression 1+rx +2 becomes 1+2+rx. Constant propagationcannot improve the original form; it can easily turn thereordered expression into 3 + rx.Figure 7 shows the result of reassociation. Noticethat the low-ranked expressions, 1, r0, and r1 , have beensorted to the beginning of the sums.After sorting expressions, we look for opportunitiesto distribute multiplication over addition; that is, werewrite expressions of the form w × (x + y + z) asw × x + w × y + w × z. This distribution is not always profitable, so we again use ranks as a guide. Inour current implementation, we distribute a low-rankedmultiplier over a higher-ranked sum. For example, if wehave an expression a + b × ((c + d) + e)), where a, b, c,and d have rank 1 and e has rank 2, we would distributeGlobal RenamingTo address the naming problems, we use a global renaming scheme based on Alpern, Wegman, and Zadeck’salgorithm for determining when two variables have thesame value [2].

We refer to their technique as “partitionbased global value numbering”. Instead of building upcomplex equality relationships from simpler ones, as intraditional value numbering, their technique works fromthe “optimistic” assumption that all variables are equivalent and uses the individual statements in the code todisprove equivalences.We use a straightforward version of their algorithmto discover when two names have the same value andthen rename all values to reflect these equivalences. Renaming encodes the value equivalences into the namespace; this exposes new opportunities to PRE.

It alsoconstructs the name space required by PRE (recall Section 2.2). Each lexically-identical expression will havethe same name; copies inserted during reassociation willonly target variable names. Of course, the “variables”named at this point do not necessarily correspond tosource variables; instead, they correspond to the φnodes introduced during conversion to SSA form. Thenames are the only things changed during this phase;no instructions are added, deleted, or moved.enter(r0 , r1 )r3 ← r0 + r1if r3 > 100 branch?r2r3r4r5←0← r0 + r1← r3← r2ra ← r0 + 1 rb ← ra + r1r7 ← rb + r5r8 ← r4 + 1r4 ← r8r5 ← r7?- r8 ← r4 + 1if r8 ≤ 100 branch?rc ← r0 + 1rd ← rc + r1r7 ← rd + r5r9 ← r7?r2 ← 0r9 ← r2?- return r9Figure 7: After Reassociationenter(r0 , r1 )r3 ← r0 + r1if r3 > 100 branch?r2r3r4r5←0← r0 + r1← r3← r2r6r7r8r9r4r5←←←←←←r0 + 1 r6 + r1r7 + r5r4 + 1r9r8?- r9 ← r4 + 1if r9 ≤ 100 branch?r6 ← r0 + 1r7 ← r6 + r1r8 ← r7 + r5r10 ← r8enter(r0 , r1 )r3 ← r0 + r1if r3 > 100 branch?r2r4r5r6r7?r2 ← 0r10 ← r2←0← r3← r2← r0 + 1← r6 + r1r8 ← r7 + r5 r4 ← r9r5 ← r8?- r9 ← r4 + 1if r9 ≤ 100 branch?r8 ← r7 + r5r10 ← r8?- return r10Figure 8: After Value Numbering?r2 ← 0r10 ← r2?- return r10Figure 9: After Partial Redundancy EliminationFigure 8 shows a naming that might be discovered byglobal value numbering.