DOC PREVIEW
CSU CS 553 - Reuse Optimization

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

CSU CS 553 - Reuse Optimization

Download Reuse Optimization
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Reuse Optimization and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Reuse Optimization 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?