Advanced Compilers M. LamLecture 5Partial Redundancy EliminationI Forms of redundancy-- global common subexpression elimination-- loop invariant code motion-- partial redundancy II Lazy Code Motion Algorithm Reading: Chapter 9.5Advanced Compilers 2 L5: Partial Redundancy EliminationOverview• Eliminates many forms of redundancy in one fell swoop• Originally formulated as 1 bi-directional analysis• Lazy code motion algorithm• formulated as 4 separate uni-directional passes(backward, forward, forward, backward)Advanced Compilers 3 L5: Partial Redundancy EliminationI. Common Subexpression Elimination• A common expression may have different values on different paths!• On every path reaching p, • expression b+c has been computed • b, c not overwritten after the expressiond=b+ca=b+cd=b+ca=b+cb=7a=b+cb=7f=b+cd=b+cAdvanced Compilers 4 L5: Partial Redundancy EliminationLoop Invariant Code Motion• Given an expression (b+c) inside a loop, does the value of b+c change inside the loop? is the code executed at least once?a=b+ca=tt=b+ca=b+cb=read()a=b+cexitAdvanced Compilers 5 L5: Partial Redundancy EliminationPartial Redundancy• Can we place calculations of b+csuch that no path re-executes the same expression• Partial redundancy elimination (PRE)• subsumes: • global common subexpression (full redundancy)• loop invariant code motion (partial redundancy for loops)a=b+cd=b+cAdvanced Compilers 6 L5: Partial Redundancy EliminationII. Increasing the Chance of Optimization• Critical edges• source basic block has multiple successors• destination basic block has multiple predecessors• Assume every statement is a basic block• Only place statements at the beginning of a basic block• Add a basic block for every edge that leads to a basic block with multiple predecessorsb+cb+cAdvanced Compilers 7 L5: Partial Redundancy EliminationFull Redundancy• Full redundancy at p: expression a+b redundant on all paths• cutset: nodes that separate entry from p• cutset contains calculation of a+b• a, b, not redefineda+bp:entrya+ba+ba+bcutseta=...b=...Advanced Compilers 8 L5: Partial Redundancy EliminationPartial Redundancy• Partial redundancy at p: redundant on some but not all paths• Add operations to create a cutset containing a+b• Note: Moving operations up can eliminate redundancy• Constraint on placement: no wasted operation• a+b is “anticipated” at B if its value computed at Bwill be used along ALL subsequent paths• a, b not redefined, no branches that lead to exit with out use• Range where a+b is anticipated --> Choicea+bp:entrya+ba+bcutseta=...b=...Advanced Compilers 9 L5: Partial Redundancy EliminationPass 1: Anticipated Expressions• Backward pass: Anticipated expressionsAnticipated[b].in: Set of expressions anticipated at the entry of b• An expression is anticipated if its value computed at point p will be used along ALL subsequent pathsAnticipated ExpressionsDomain Sets of expressionsDirection backwardTransfer function fb(x) = EUseb ∪ (x -EKillb)EUse: used expEKill: exp killed∧ ∩Boundary in[exit] = ∅Initialization in[b] = {all expressions}Advanced Compilers 10 L5: Partial Redundancy EliminationExamples (1)x=a+bx=a+bz=a+by=a+ba=10r=a+bAdvanced Compilers 11 L5: Partial Redundancy EliminationExamples (2)a+ba+bAdvanced Compilers 12 L5: Partial Redundancy EliminationExamples (3)x=a+by=a+ba=10x=a+by=a+ba=10Advanced Compilers 13 L5: Partial Redundancy EliminationPass 2: Place As Early As Possible• First approximation: frontier between “not anticipated” & “anticipated”• Complication: Anticipation may oscillate• Assume: place expression e such that it is available where it is anticipated.• e will be available at p if e has been anticipated but not subsequently killed on all paths reaching pAvailable ExpressionsDomain Sets of expressionsDirection forwardTransfer function fb(x) = (Anticipated[b].in ∪ x) - EKillb∧ ∩Boundary condition out[entry] = ∅ Initialization out[b] ={all expressions}x=a+by=a+bAdvanced Compilers 14 L5: Partial Redundancy EliminationEarly Placement• earliest(b)• set of expressions added to block b under early placement• Place expression at the earliest point anticipated and not already available• earliest(b) = anticipated[b].in − available[b].in• Algorithm• For all basic block b, if x+y ∈ earliest[b]• at beginning of b: create a new variable tt = x+y, replace every original x+y by tAdvanced Compilers 15 L5: Partial Redundancy EliminationPass 3: Lazy Code Motion• Delay without creating redundancy to reduce register pressure• An expression e is postponable at a program point p if• all paths leading to p have seen the earliest placement of e but not a subsequent usePostponable ExpressionsDomain Sets of expressionsDirection forwardTransfer function fb(x) = (earliest[b] ∪ x) -EUseb∧ ∩Boundary condition out[entry] = ∅Initialization out[b] = {all expressions}y=b+cx=b+cAdvanced Compilers 16 L5: Partial Redundancy EliminationLatest: frontier at the end of “postponable” cut set• latest[b] = (earliest[b] ∪ postponable.in[b]) ∩ (EUseb ∪ ¬(∩s ∈ succ[b](earliest[s] ∪ postponable.in[s])))• OK to place expression: earliest or postponable• Need to place at b if either• used in b, or• not OK to place in one of its successors• Note because of pre-processing step: • if one of its successors cannot accept postponement,b has only one successor• The following does not existOK to placenot OK to placeOK to placeAdvanced Compilers 17 L5: Partial Redundancy EliminationPass 4: Cleaning Up• Eliminate temporary variable assignments unused beyond current block • Compute: Used.out[b]: sets of used (live) expressions at exit of b.Used ExpressionsDomain Sets of expressionsDirection backwardTransfer function fb(x) = (EUse[b] ∪ x) -latest[b]∧ ∪Boundary condition in[exit] = ∅Initialization in[b] = ∅x=a+bnot used afterwardsAdvanced Compilers 18 L5: Partial Redundancy EliminationCode Transformation• For all basic blocks b, if (x+y) ∈ (latest[b] ∩ used.out[b])at beginning of b: add new t = x+yif (x+y) ∈ (EUseb ∩ ¬ (latest[b] ∩ ¬ used.out[b]))replace every original x+y by tAdvanced Compilers 19 L5: Partial Redundancy EliminationSummary• Cannot execute any operations not executed originally• Pass 1: Anticipation: range of code motion• Eliminate as many redundant calculations of an expression as possible, without duplicating