Advanced Compilers CMPSCI 710 Spring 2003 Common Subexpression EliminationTopicsDetermining EquivalenceCommon Subexpression EliminationValue NumberingComputing Value NumbersValue Numbering SummaryMap UsageSlide 9Interesting PropertiesProblemsGlobal CSEAvailable ExpressionsAvailable Expressions: Dataflow EquationsAvailable Expressions, ExampleNext TimeValue Numbering ExampleSlide 18UUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer ScienceEmery BergerUniversity of Massachusetts, AmherstAdvanced CompilersCMPSCI 710Spring 2003Common Subexpression EliminationUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science2TopicsLast timeDynamic storage allocation, garbage collectionThis timeCommon subexpression eliminationValue numberingGlobal CSEUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science3Determining EquivalenceGoal: eliminate redundant computationsSparse conditional constant propagation:Eliminates multiple computationsEliminates unnecessary branchesCan we eliminate equivalent expressions without constants?UUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science4Common Subexpression EliminationRecognizes textually identical (or commutative) redundant computationsReplaces second computationby result of the firstHow do we do this efficiently?UUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science5Value NumberingEach variable, expression, and constant:unique value numberSame number ) computes same valueBased on information from within blockUse hash functions to compute theseUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science6Computing Value NumbersAssign values to variablesa = 3 ) value(a) = 3Map expressions to valuesa = b + 2 ) value(a) = hash(+,value(b),2)Use appropriate hash functionPlus: commutativehashc(+,value(b),2) = hashc(+,2,value(b))Minus: not commutativehash(-,value(b),2)  hash(-,2,value(b))UUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science7Value Numbering SummaryForward symbolic execution of basic blockEach new value assigned to temporaryPreserves value for later use even if original variable rewrittena = x+y; a = a+z; b = x+y) a = x+y; t = a; a = a+z; b = t;MapsVar to Valspecifies symbolic value for each variableExp to Valspecifies value of each evaluated expressionExp to Tmpspecifies tmp that holds value of each evaluated expressionUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science8Map UsageVar to Val Used to compute symbolic value of y and z when processing statement of form x = y + zExp to TmpUsed to determine which temp to use if value(y) + value(z) previously computed when processing statement of form x = y + zExp to ValUsed to update Var to Val when processing statement of the form x = y + z, andvalue(y) + value(z) previously computedUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science9b  v5b  v6a = x+yb = a+zb = b+yc = a+za = x+yt1 = ab = a+zt2 = bb = b+yt3 = bx  v1y  v2a  v3z  v4c  v5Original Basic BlockNew Basic BlockVarValv1+v2  v3v3+v4  v5ExpValv1+v2  t1v3+v4  t2ExpTmpc = t2v5+v2  v6v5+v2  t3Computing Value Numbers,ExampleUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science10Interesting PropertiesFinds common subexpressions even if they use different variables in expressionsy = a+b; x = b; z = a+x) y = a+b; t = y; x = b; z = tFinds common subexpressions even if variable that originally held the value was overwritteny = a+b; x = b; y = 1; z = a+x) y = a+b; t = y; x = b; y = 1; z = tUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science11ProblemsAlgorithm has a temporary for each new valuea = x+y; t1 = a;Introduceslots of temporarieslots of copy statements to temporariesIn many cases, temporaries and copy statements are unnecessaryEliminate with copy propagation and dead code eliminationUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science12Global CSEValue numbering eliminates some subexpressions but not alll’s value is not always equal to j’s or k’s valueUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science13Available ExpressionsGlobal CSE requires computation of available expressions for blocks b:Expressions on every path in cfg from entry to bNo operand in expression redefinedThen use appropriate temp variable for used available expressionsUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science14Available Expressions:Dataflow EquationsFor a block b:AEin(b) = expressions available on entry to bKILL(b) = expressions killed in bEVAL(b) = expressions defined in b and not subsequently killed in bUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science15Available Expressions,ExampleBuild control-flow graphSolve dataflow problemInitialize AEin(i) = universal set of expressionsAEin(b) = Åj 2 Pred(i)AEout(j)AEout(b) = EVAL(i) [ (AEin(i) – KILL(i))UUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science16Next TimePartial Redundancy