**Unformatted text preview:**

1CIS570 Lecture 9 Reuse Optimization II 2Reuse Optimization Last time– Discussion (SCC)– Loop invariant code motion– Reuse optimization: Value numbering Today– More reuse optimization– Common subexpression elimination (CSE)– Partial redundancy elimination (PRE)CIS570 Lecture 9 Reuse Optimization II 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 berecomputed2CIS570 Lecture 9 Reuse Optimization II 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 expressionsCIS570 Lecture 9 Reuse Optimization II 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 operators3CIS570 Lecture 9 Reuse Optimization II 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 1CIS570 Lecture 9 Reuse Optimization II 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 := a4CIS570 Lecture 9 Reuse Optimization II 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)CIS570 Lecture 9 Reuse Optimization II 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 := t15CIS570 Lecture 9 Reuse Optimization II 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 + yCIS570 Lecture 9 Reuse Optimization II 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 + c6CIS570 Lecture 9 Reuse Optimization II 12Implementing PRE Big picture– Use local properties (availability and anticipability) to determine whereredundancy can be created within a basic block– Use global analysis (data-flow analysis) to discover where partialredundancy can be converted to full redundancy– Insert code and remove redundant expressionsexprexprdelete computationinsertcomputationCIS570 Lecture 9 Reuse Optimization II 13Local Properties An expression is locally transparent in block b if its operands are notmodified in b An expression is locally available in block b if it is computed at least onceand its operands are not modified after its last computation in b An expression is locally anticipated if it is computed at least once and itsoperands are not modified before its first evaluation Example a := b + c d := a + eTransparent:Available:Anticipated:{b + c}{b + c, a + e}{b + c}7CIS570 Lecture 9 Reuse Optimization II 14Local Properties (cont) How are these properties useful?– They tell us where we can introduce redundancyThe expression can be redundantlyevaluated anywhere after its lastevaluation in the blockThe expression can be redundantlyevaluated anywhere in the blockTransparentAvailablea = b + cThe expression can be redundantlyevaluated anywhere before its firstevaluation in the blockAnticipateda = b + cCIS570 Lecture 9 Reuse Optimization II 15 Intuition– Global availability is the same as Available Expressions– If e is globally available at p, then an evaluation at p will create redundancyalong all paths leading to p Flow Functionsavailable_in[n] = ∩ p∈pred[n] available_out[p]available_out[n] = locally_available[n] ∪ (available_in[n] ∩ transparent[n])Global Availabilityexprpexpr8CIS570 Lecture 9 Reuse Optimization II 16(Global) Partial Availability Intuition– An expression is partially available if it is available along some path– If e is partially available at p, then ∃ a path from the entry node to p suchthat the evaluation of e at p would give the same result as the previousevaluation of e along the pathexprppartially_available_in[n] = ∪

View Full Document