MIT 28 More loop optimization, страница 2

However, these are awkwardunless the CFG is converted to single static assignment (SSA) form.5Common subexpression eliminationCommon subexpression elimination (CSE) is a classic optimization that replaces redundantly computedexpressions with a variable containing the value of the expression. It works on a general CFG. An expressionis a common subexpression at a given node if it is computed in another node that dominates this one, andnone of its operands have been changed on any path from the dominating node.For example, in Figure 2, the expression a+1 is a common subexpression at the bottom node. Therefore,it can be saved into a new temporary t in the top node, and this temporary can be used in the bottom one.It is worth noting that CSE can make code slower, because it may increase the number of live variables,causing spilling.

If there is a lot of register pressure, the reverse transformation, forward substitution, mayimprove performance. Forward substitution copies expressions forward when it is cheaper to recomputethem than to save them in a variable.5.1Available expressions analysisAn expression is available if it has been computed in a dominating node and its operands have not beenredefined. The available expressions analysis finds the set of such expressions. Implicitly, each such expressionis tagged with the location in the CFG that it comes from, to allow the CSE transformation to be done.Available expressions is a forward analysis.

We define out(n) to be the set of available expressions onedges leaving node n. An expression is available if it was evaluated at n, or was available on all edgesentering n, and it was not killed by n:in(n) =\out(n)n0 ≺nout(n) = in(n) ∪ exprs(n) − kill(n)Therefore, dataflow values are sets of expressions ordered by ⊆; the meet operator is set intersection(∩), and the top value is the set of all expressions, usually implemented as a special value that acts as theidentity for ∩.The expressions evaluated and killed by a node, exprs(n), are summarized in the following table. Notethat we try to include memory operands as expressions subject to CSE, because replacing memory accesseswith register accesses is a useful optimization.b=a+1c=3*bif c > 0t=a+1b=tc=3*bif c > 0b=0d=c+1d=a+1d=tFigure 2: Common subexpression elimination4b=0d=c+1nx=e[e1 ] = [e2 ]x = f (~e)exprs(n)e and all subexpressions of e[e2 ], [e1 ], and subexpressions~e and subexpressionsif ee and subexpressionskill(n)all expressions containing xall expressions [e0 ] that can alias [e1 ]expressions containing x and expressions [e0 ] thatcould be changed by function call to f∅If a node n computes an expression e that is used and available in other nodes, the optimization proceedsas follows:1.

In the node that the available expression came from, add a computation t = e, and replace the use of ewith t.2. Replace expression e in other nodes where it is used and available with t.CSE can work well with copy propagation. For example, the variable b in the above code may becomedead after copy propagation. However, CSE plus copy propagation can enable more CSE, because CSEonly recognizes syntactically identical expressions as the same. Copy propagation can make semanticallyidentical expressions look the same through its renaming of variables.

It is possible to generalize AvailableExpressions to keep track of equalities more semantically, though this makes the analysis much morecomplex.5.