Carnegie Mellon Lecture 5 Partial Redundancy Elimination I. Forms of redundancy • global common subexpression elimination • loop invariant code motion • partial redundancy II. Lazy Code Motion Algorithm • Mathematical concept: a cut set • Basic technique (anticipation) • 3 more passes to refine algorithm Reading: Chapter 9.5 M. Lam CS243: Partial Redundancy Elimination 1Carnegie Mellon Overview • 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 M. Lam CS243: Partial Redundancy Elimination 2Carnegie Mellon I. 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 expression M. Lam CS243: Partial Redundancy Elimination 3 Build up intuition about redundancy elimination with examples of familiar concepts d = b + c a = b + c b = 7 d = b + c a = b + c b = 7 f = b + c d = b + c a = b + cCarnegie Mellon Loop 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? M. Lam CS243: Partial Redundancy Elimination 4 a = t t = b + c a = b + c a = b + c b = read() a = b + c exitCarnegie Mellon Partial Redundancy • Can we place calculations of b+c such 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) M. Lam CS243: Partial Redundancy Elimination 5 Unifying theory: More powerful, elegant  but less direct. d = b + c a = b + cCarnegie Mellon II. Preparing the Flow Graph • Key observation • Can replace a bi-directional (!) data flow with several unidirectional data flows  much easier • Better result as well! • Definition: Critical edges • source basic block has multiple successors • destination basic block has multiple predecessors • Modify the flow graph: (treat every statement as a basic block) • To keep algorithm simple: restrict placement of instructions to the beginning of a basic block • Add a basic block for every edge that leads to a basic block with multiple predecessors (not just on critical edges) M. Lam CS243: Partial Redundancy Elimination 6 d = b + c a = b + c d = b + c a = b + cCarnegie Mellon Full Redundancy: A Cut Set in a Graph • Full redundancy at p: expression a+b redundant on all paths – a cut set: nodes that separate entry from p – a cut set contains calculation of a+b – a, b, not redefined M. Lam CS243: Partial Redundancy Elimination 7 Key mathematical conceptCarnegie Mellon Partial Redundancy: Completing a Cut Set • Partial redundancy at p: redundant on some but not all paths • Add operations to create a cut set 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 B will 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  Choice M. Lam CS243: Partial Redundancy Elimination 8Carnegie Mellon Pass 1: Anticipated Expressions • Backward pass: Anticipated expressions Anticipated[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 paths • First approximation: • place operations at the frontier of anticipation (boundary between not anticipated and anticipated) M. Lam CS243: Partial Redundancy Elimination 9 This pass does most of the heavy lifting in eliminating redundancy Anticipated Expressions Domain Sets of expressions Direction backward Transfer Function fb(x) = EUseb ∪ (x -EKillb) EUse: used exp, EKill: exp killed ∧ ∩ Boundary in[exit] = ∅ Initialization in[b] = {all expressions}Carnegie Mellon Examples (1) M. Lam CS243: Partial Redundancy Elimination 10 See the algorithm in action x = a + b z = a + b y = a + b x = a + b r = a + b a = 10Carnegie Mellon Examples (2) • Cannot eliminate all redundancy M. Lam CS243: Partial Redundancy Elimination 11 z = a + b x = a + bCarnegie Mellon Examples (3) Do you know how the algorithm works without simulating it? M. Lam CS243: Partial Redundancy Elimination 12Carnegie Mellon Pass 2: Place As Early As Possible • First approximation: frontier between “not anticipated” & “anticipated” • Complication: Anticipation may oscillate • An anticipation frontier may cover a subsequent frontier. • Once an expression has been anticipated, it is “available” to subsequent frontiers  no need to re-evaluate. • e will be available at p if e has been “anticipated but not subsequently killed” on all paths reaching p M. Lam CS243: Partial Redundancy Elimination There is still some redundancy left! a = 1 x = a+b y = a+bCarnegie Mellon Available Expressions • e will be available at p if e has been “anticipated but not subsequently killed” on all paths reaching p M. Lam CS243: Partial Redundancy Elimination 14 Available Expressions Domain Sets of expressions Direction forward Transfer Function fb(x) = (Anticipated[b].in ∪ x) - EKillb ∧ ∩ Boundary out[entry] = ∅ Initialization out[b] = {all expressions}Carnegie Mellon Early 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 t t = x+y, replace every original x+y by t M. Lam CS243: Partial Redundancy Elimination 15Carnegie Mellon Pass 3: Lazy Code Motion 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 use M. Lam CS243: Partial Redundancy Elimination 16 Let’s be lazy without introducing redundancy.