1CS553 Lecture Reuse Optimization: PRE 2Reuse Optimization Last time– Common subexpression elimination (CSE) Today– Partial redundancy elimination (PRE)CS553 Lecture Reuse Optimization: PRE 3Partial 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 + y2CS553 Lecture Reuse Optimization: PRE 4Loop 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 + cCS553 Lecture Reuse Optimization: PRE 5Implementing PRE [Morel & Renvoise 1979] 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 computationinsertcomputation3CS553 Lecture Reuse Optimization: PRE 6Local 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}CS553 Lecture Reuse Optimization: PRE 7Local 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 + c4CS553 Lecture Reuse Optimization: PRE 8 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 AvailabilityexprpexprCS553 Lecture Reuse Optimization: PRE 9(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 path Flow Functionspartially_available_in[n] = ∪ p∈pred[n] partially_available_out[p] partially_available_out[n] = locally_available[n] ∪ (partially_available_in[n] ∩ transparent[n])exprp5CS553 Lecture Reuse Optimization: PRE 10Global Anticipability Intuition– If e is globally anticipated at p, then an evaluation of e at p will make thenext evaluation of e redundant along all paths from p Flow Functionsanticipated_out[n] = ∩ s∈succ[n] anticipated_in[s]anticipated_in[n] = locally_anticipated[n] ∪ (anticipated_out[n] ∩ transparent[n])exprpexprexprCS553 Lecture Reuse Optimization: PRE 11Global Possible Placement Goal– Convert partial redundancies to full redundancies– Possible Placement uses a backwards analysis to identify locations wheresuch conversions can take place– e ∈ ppin[n] can be placed at entry of n– e ∈ ppout[n] can be placed at exit of nStart with locallyanticipated expressionsPush Possible Placement backwards as far as possible6CS553 Lecture Reuse Optimization: PRE 12Global Possible Placement (cont) Flow Functionsppout[n] = ∩ s∈succ[n] ppin[s]ppin[n] = anticipated_in[n] ∩ partially_available_in[n] ∩ (locally_anticipated[n] ∪ (ppout[n] ∩ transparent[n]))The placement will create a redundancyWill turn partial redundancy into full redundancyMiddle of chainThis block is at thebeginning of a chainon every edge out of the blockCS553 Lecture Reuse Optimization: PRE 13Updating Blocks Intuition– Perform insertions at top of the chain– Perform deletion at the bottom of the chain Functions– delete[n] = ppin[n] ∩ locally_anticipated[n]– insert[n] = ppout[n] ∩ (¬ppin[n] ∪ ¬ transparent[n]) ∩ ¬available_out[n]Don’t insert it where it’s fully redundant7CS553 Lecture Reuse Optimization: PRE 14Updating Blocks (cont) Intuition– Perform insertions at top of the chain– Perform deletion at the bottom of the chain Functions– delete[n] = ppin[n] ∩ locally_anticipated[n]– insert[n] = ppout[n] ∩ (¬ppin[n] ∪ ¬ transparent[n]) ∩ ¬available_out[n]¬ ppout[n] ? NoCan we omit this clause?CS553 Lecture Reuse Optimization: PRE 15Sandwich Examplea+ba+ba+ba+ba+ba+ba+bB0a+ba+ba+ba+ba+ba+ba+ba+ba+ba+bB4a+bdeleteinserta+bppina+ba+ba+bppouta+ba+ba+banticipated_ina+ba+ba+banticipated_outa+ba+ba+bpartially_available_outa+bpartially_available_ina+ba+ba+bavailable_outavailable_ina+ba+ba+blocally_anticipateda+ba+ba+blocally_availablea+ba+btransparentB3B2B18CS553 Lecture Reuse Optimization: PRE 16Example B1: a := b + c B2: b := b + 1B3: a := b + cdeleteinsertppinppoutanticipated_inanticipated_outpartially_available_outpartially_available_inavailable_outavailable_inlocally_anticipatedlocally_availabletransparentB3B2B1{b+c}{b+c}{b+c} {b+c}{b+c} {b+c}{b+c} {b+c}{b+c}{b+c} {b+c}{b+1}{b+c} {b+c}{b+c}{b+c}{b+1}{b+c} {b+c}{b+c}{b+c}{b+c}CS553 Lecture Reuse Optimization: PRE 17Comparing Redundancy Elimination Value numbering– Examines values not expressions– Symbolic CSE– Examines expressions PRE– Examines expressions– Subsumes CSE and loop invariant code motion– Other implementations are now available Constant propagation– Requires that values be statically known9CS553 Lecture Reuse Optimization: PRE 18PRE Summary What’s so great about PRE?– A modern optimization that subsumes earlier ideas– Composes several simple data-flow analyses to produce a powerful result– Finds