Global OptimizationLecture OutlineLocal OptimizationGlobal OptimizationGlobal OptimizationGlobal OptimizationCorrectnessCorrectness (Cont.)Example 1 RevisitedExample 2 RevisitedDiscussionGlobal AnalysisGlobal Analysis (Cont.)Global Constant PropagationGlobal Constant Propagation (Cont.)ExampleUsing the InformationThe IdeaExplanationTransfer FunctionsRule 1 (unknown predecessor)Rule 2 (different predecessors)Rule 3 (exclude unreachable values)Rule 4 (unreachable propagation)The Other HalfRule 5Rule 6Rule 7Rule 8An AlgorithmThe Value #DiscussionThe Value # (Cont.)ExampleExampleExampleExampleOrderingsOrderings (Cont.)TerminationTermination (Cont.)Liveness AnalysisLive and DeadLivenessGlobal Dead Code EliminationComputing LivenessLiveness Rule 1Liveness Rule 2Liveness Rule 3Liveness Rule 4AlgorithmTerminationForward vs. Backward AnalysisAnalysisOther parts of optimizationProf. Fateman CS 164 Lecture 22 1Global OptimizationLecture 22Prof. Fateman CS 164 Lecture 22 2Lecture Outline• Global flow analysis• Global constant propagation• Liveness analysisProf. Fateman CS 164 Lecture 22 3Local OptimizationRecall the simple basic-block optimizations– Constant propagation– Dead code eliminationX := 3Y := Z * WQ := X + YX := 3Y := Z * WQ := 3 + YY := Z * WQ := 3 + YProf. Fateman CS 164 Lecture 22 4Global OptimizationThese optimizations can be extended to an entire control-flow graphX := 3B > 0Y := Z + W Y := 0A := 2 * XProf. Fateman CS 164 Lecture 22 5Global OptimizationThese optimizations can be extended to an entire control-flow graphX := 3B > 0Y := Z + W Y := 0A := 2 * XProf. Fateman CS 164 Lecture 22 6Global OptimizationThese optimizations can be extended to an entire control-flow graphX := 3B > 0Y := Z + W Y := 0A := 2 * 3Prof. Fateman CS 164 Lecture 22 7Correctness• How do we know it is OK to globally propagate constants?• There are situations where it is incorrect:X := 3B > 0Y := Z + WX := 4Y := 0A := 2 * XProf. Fateman CS 164 Lecture 22 8Correctness (Cont.)To replace a use of x by a constant k we must know that:On every path to the use of x, the last assignment to x is x := k **Prof. Fateman CS 164 Lecture 22 9Example 1 RevisitedX := 3B > 0Y := Z + W Y := 0A := 2 * XProf. Fateman CS 164 Lecture 22 10Example 2 RevisitedX := 3B > 0Y := Z + WX := 4Y := 0A := 2 * XProf. Fateman CS 164 Lecture 22 11Discussion• The correctness condition is not trivial to check• “All paths” includes paths around loops and through branches of conditionals• Checking the condition requires global analysis– An analysis of the entire control-flow graphProf. Fateman CS 164 Lecture 22 12Global AnalysisGlobal optimization tasks share several traits:– The optimization depends on knowing a property X at a particular point in program execution– Proving X at any point requires knowledge of the entire function body– It is OK to be conservative. If the optimization requires X to be true, then want to know either•Xis definitely true• Don’t know if X is true– It is always safe to say “don’t know”Prof. Fateman CS 164 Lecture 22 13Global Analysis (Cont.)•Global dataflow analysisis a standard technique for solving problems with these characteristics• Global constant propagation is one example of an optimization that requires global dataflow analysisProf. Fateman CS 164 Lecture 22 14Global Constant Propagation• Global constant propagation can be performed at any point where ** holds• Consider the case of computing ** for a single variable X at all program pointsProf. Fateman CS 164 Lecture 22 15Global Constant Propagation (Cont.)• To make the problem precise, we associate one of the following values with X at every program pointvalue interpretation#This statement never executescX= constant c* Don’t know if X is a constantProf. Fateman CS 164 Lecture 22 16ExampleX = *X = 3X = 3X = 3X = 4X = *X := 3B > 0Y := Z + WX := 4Y := 0A := 2 * XX = 3X = 3X = *Prof. Fateman CS 164 Lecture 22 17Using the Information• Given global constant information, it is easy to perform the optimization– Simply inspect the x = ? associated with a statement using x–If x is constant at that point replace that use of xby the constant• But how do we compute the properties x = ?Prof. Fateman CS 164 Lecture 22 18The IdeaThe analysis of a complicated program can be expressed as a combination of simple rules relating the change in information between adjacent statementsProf. Fateman CS 164 Lecture 22 19Explanation• The idea is to “push” or “transfer” information from one statement to the next• For each statement s, we compute information about the value of x immediately before and after sCin(x,s) = value of x before sCout(x,s) = value of x after sProf. Fateman CS 164 Lecture 22 20Transfer Functions• Define a transfer functionthat transfers information one statement to another• In the following rules, let statement s have immediate predecessor statements p1,…,pnProf. Fateman CS 164 Lecture 22 21Rule 1 (unknown predecessor)if Cout(x, pi) = * for any predecessor i, then Cin(x, s) = *sX = *X = *X = ?X = ?X = ?Prof. Fateman CS 164 Lecture 22 22Rule 2 (different predecessors)If Cout(x, pi) = c and Cout(x, pj) = d and d <> c then Cin(x, s) = *sX = dX = *X = ?X = ?X = cProf. Fateman CS 164 Lecture 22 23Rule 3 (exclude unreachable values)if Cout(x, pi) = c or # for all i,then Cin(x, s) = csX = cX = cX = #X = # X = cProf. Fateman CS 164 Lecture 22 24Rule 4 (unreachable propagation)if Cout(x, pi) = # for all i,then Cin(x, s) = #sX = #X = #X = #X = # X = #Prof. Fateman CS 164 Lecture 22 25The Other Half• Rules 1-4 relate the out of one or more statements to the inof the successor statement• Now we need rules relating the in of a statement to the outof the same statementProf. Fateman CS 164 Lecture 22 26Rule 5Cout(x, s) = # if Cin(x, s) = #sX = #X = #Prof. Fateman CS 164 Lecture 22 27Rule 6Cout(x, x := c) = c if c is a constantx := cX = ?X = cProf. Fateman CS 164 Lecture 22 28Rule 7Cout(x, x := f(…)) = *x := f(…)X = ?X = *Prof. Fateman CS 164 Lecture 22 29Rule 8Cout(x, y := …) = Cin(x, y := …) if x <> yy := . . .X = aX = aProf. Fateman CS 164 Lecture 22 30An Algorithm1. For every entry s to the program, set Cin(x, s) = *2. Set Cin(x, s) = Cout(x, s) = # everywhere else3. Repeat until all points satisfy 1-8:Pick s not satisfying 1-8 and update using the appropriate ruleProf. Fateman CS 164 Lecture 22
View Full Document
Unlocking...