1CS553 Lecture Reuse Optimization: Common SubExpr Elim 2Reuse Optimization Last time– Value numbering Today– Common subexpression elimination (CSE)CS553 Lecture Reuse Optimization: Common SubExpr Elim 3Common Subexpression Elimination Idea– Find common subexpressions whose range spans the same basic blocksand eliminate unnecessary re-evaluations– Leverage available expressions Recall available expressions– An expression (e.g., x+y) is available at node n if every path from theentry node to n evaluates x+y, and there are no definitions of x or y afterthe last evaluation along that path Strategy– If an expression is available at a point where it is evaluated, it need not berecomputed2CS553 Lecture Reuse Optimization: Common SubExpr Elim 4CSE Example2i := i + 1b := 4 * i1i := ja := 4 * i3c := 4 * i2i := i + 1t := 4 * ib := t1i := jt := 4 * ia := t3c := t Will value numbering find this redundancy?– No; value numbering operates on values– CSE operates on expressionsCS553 Lecture Reuse Optimization: Common SubExpr Elim 5Another CSE ExampleBefore CSEc := a + bd := m & ne := b + df := a + bg := -bh := b + aa := j + ak := m & nj := b + da := -bif m & n goto L2Summary11 instructions12 variables9 binary operatorsAfter CSEt1 := a + bc := t1t2 := m & nd := t2t3 := b + de := t3f := t1g := -bh := t1a := j + ak := t2j := t3a := -bif t2 goto L2Summary14 instructions15 variables4 binary operators3CS553 Lecture Reuse Optimization: Common SubExpr Elim 6 e := t1f := t2 Notation– Avail(b) is the set of expressions available at block b– Gen(b) is the set of expressions generated and not killed at block b If we use e and e ∈ Avail(b)– Allocate a new name n– Search backward from b (in CFG) to find statements (one for each path)that most recently generate e– Insert copy to n after generators– Replace e with n Problems– Backward search for each use is expensive– Generates unique name for each use– |names| ∝ |Uses| > |Avail|– Each generator may have many copies Example a := b + c t1 := a t2 := a e := b + cf := b + cCSE Approach 1CS553 Lecture Reuse Optimization: Common SubExpr Elim 7 Idea– Reduce number of copies by assigning a unique name to each uniqueexpression Summary– ∀e Name[e] = unassigned– if we use e and e ∈ Avail(b)– if Name[e]=unassigned, allocate new name n and Name[e] = nelse n = Name[e]– Replace e with n– In a subsequent traversal of block b, if e ∈ Gen(b) and Name[e] ≠unassigned, then insert a copy to Name[e] after the generator of e Problem– May still insert unnecessary copies– Requires two passes over the codeCSE Approach 2 Example a := b + c t1 := a4CS553 Lecture Reuse Optimization: Common SubExpr Elim 8CSE Approach 3 Idea– Don’t worry about temporaries– Create one temporary for each unique expression– Let subsequent pass eliminate unnecessary temporaries At an evaluation of e– Hash e to a name, n, in a table– Insert an assignment of e to n At a use of e in b, if e ∈ Avail(b)– Lookup e’s name in the hash table (call this name n)– Replace e with n Problems– Inserts more copies than approach 2 (but extra copies are dead)– Still requires two passes (2nd pass is very general)CS553 Lecture Reuse Optimization: Common SubExpr Elim 9Extraneous Copies Extraneous copies degrade performance Let other transformations deal with them– Dead code elimination– Coalescing– Greatly simplifies CSECoalesce assignments to t1 and t2 into a single statementt1 := b + ct2 := t15CS553 Lecture Reuse Optimization: Common SubExpr Elim 10Partial Redundancy Elimination (PRE) Partial Redundancy– An expression (e.g., x+y) is partially redundant at node n if some pathfrom the entry node to n evaluates x+y, and there are no definitions of xor y between the last evaluation of x+y and n Elimination– Discover partially redundant expressions– Convert them to fully redundant expressions– Remove redundancy PRE subsumes CSE and loop invariant code motionx + yx + ynx + yx + ynx + yx + ynx + yCS553 Lecture Reuse Optimization: Common SubExpr Elim 11Loop Invariance Example PRE removes loop invariants– An invariant expression is partially redundant– PRE converts this partial redundancy to full redundancy– PRE removes the redundancy Example2 ...a := b + c1x := y * z2 ...a := b + c1x := y * za := b + c2 ...1x := y * za := b +
View Full Document