Advanced Compilers CMPSCI 710 Spring 2003 Partial Redundancy EliminationTopicsPartial RedundancyPRE ExamplePRE: ProblemPRE: SolutionBig Example: Critical EdgesBig Example: Critical Edges RemovedPRE Dataflow EquationsStep 1: Local TransparencyLocal TransparencyStep 2: Locally AnticipatableLocally AnticipatableStep 3: Globally AnticipatableGlobally Anticipatable Expressions: Dataflow EquationsGlobally AnticipatableStep 4: Earliest ExpressionsEarly ExpressionsPRE TransformationOPT, REDN, PREConclusionUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer ScienceEmery BergerUniversity of Massachusetts, AmherstAdvanced CompilersCMPSCI 710Spring 2003Partial Redundancy EliminationUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science2TopicsLast timeCommon subexpression eliminationValue numberingGlobal CSEThis timePartial redundancy eliminationUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science3Partial RedundancyPartial redundancy:Expression computed more than onceon so me path through control-flow graphPartial-redundancy elimination (PRE):Minimizes partial redundanciesInserts and deletes computations (adds temps)Each path contains no more (usually fewer) occurrences of any computation than beforeDominates global CSE & loop-invariant code motionUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science4PRE ExampleUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science5PRE: ProblemCritical edge prevents redundancy eliminationConnects node with two or more successors to one with two or more predecessorsWhy is it a problem?UUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science6PRE: SolutionSplit critical edges!Insert empty basic blocksAllows PRE to continueUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science7Big Example:Critical EdgesUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science8Big Example:Critical Edges RemovedUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science9PRE Dataflow EquationsFirst formulation [Morel & Renvoise 79]bidirectional dataflow analysisUglyThis version [Knoop et al. 92]Based on “lazy code motion”Places computations as late as possibleSame reductions as classic algorithmMinimizes register pressureMost complex dataflow problem we’ve ever seen…UUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science10Step 1: Local TransparencyExpression’s value is locally transparent in a basic block ifNo assignments to variables that occur in expressionSet of locally transparent expressions:TRANSloc(i)Note: Ignore expressions in branchesUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science11Local TransparencyTransLoc – no assignmentsto variables in expressionUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science12Step 2: Locally AnticipatableExpression is locally anticipatable in basic block ifThere is computation of expression in blockMoving to beginning of block has no effectNo uses of expression nor assignments of variable in block ahead of computationSet of locally anticipatable expressions:ANTloc(i)UUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science13Locally AnticipatableANTloc – computes expr,can move to frontUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science14Step 3: Globally AnticipatableExpression’s value globally anticipatable on entry to basic block ifEvery path from that point includes computation of expressionExpression yields same value all along pathSet of globally anticipatable expressions:ANTin(i)UUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science15Globally Anticipatable Expressions:Dataflow EquationsANTout(exit) = ANTin(i) = ANTloc(i) [ (TRANSloc(i) Å ANTout(i))ANTout(i) = Åj 2 Succ(i) ANTin(j)What’s the analysis direction?UUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science16Globally AnticipatableANTout(exit) = ANTin(i) =ANTloc(i) [ (TRANSloc(i) Å ANTout(i))ANTout(i) = Åj 2 Succ(i) ANTin(j)UUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science17Step 4: Earliest ExpressionsExpression is earliest at entrance to block ifNo block from entry to block both:Evaluates expression andProduces same value as at entrance to blockDefined in terms of local transparency and globally anticipatable expressionsEARLin(i) = [j 2 Pred(i) EARLout(j)EARLout(i) = inv(TRANSloc(i)) [ (inv(ANTin(i)) Å EARLin(i))Initialize EARLin(entry) = UexpUUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science18Early ExpressionsEARLin(i) = [j 2 Pred(i) EARLout(j)EARLout(i) = inv(TRANSloc(i)) [ (inv(ANTin(i) Å EARLin(i))UUNIVERSITY OF NIVERSITY OF MMASSACHUSETTSASSACHUSETTS, A, AMHERST • MHERST • Department of Computer Science Department of Computer Science19PRE TransformationWe’ll cut to the chase:Latest, Isolated expressionsUse earliest, globally anticipatableOPT(i) =