How Not To Do Global Optimizations 1 One Slide Summary A global optimization changes an entire method consisting of multiple basic blocks We must be conservative and only apply global optimizations when they preserve the original semantics We use global flow analyses to determine if it is OK to apply an optimization Flow analyses are built out of simple transfer functions and can work forwards or backwards 2 Lecture Outline Global flow analysis Global constant propagation Liveness analysis 3 Local Optimization Recall the simple basic block optimizations Constant propagation Dead code elimination X 3 X 3 Y Z W Y Z W Y Z W Q X Y Q 3 Y Q 3 Y 4 Global Optimization These optimizations can be extended to an entire control flow graph X 3 B 0 Y Z W Y 0 A 2 X 5 Global Optimization These optimizations can be extended to an entire control flow graph X 3 B 0 Y Z W Y 0 A 2 X 6 Global Optimization These optimizations can be extended to an entire control flow graph X 3 B 0 Y Z W Y 0 A 2 3 7 Correctness How do we know it is OK to globally propagate constants There are situations where it is incorrect X 3 B 0 Y Z W Y 0 X 4 A 2 X 8 Correctness Cont To replace a use of x by a constant k we must know this correctness condition On every path to the use of x the last assignment to x is x k 9 Example 1 Revisited X 3 B 0 Y Z W Y 0 A 2 X 10 Example 2 Revisited X 3 B 0 Y Z W Y 0 X 4 A 2 X 11 Discussion 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 Global an analysis of the entire control flow graph for one method body 12 Global Analysis Global optimization tasks share several traits The optimization depends on knowing a property P at a particular point in program execution Proving P at any point requires knowledge of the entire method body Property P is typically undecidable 13 Undecidability of Program Properties Rice s Theorem Most interesting dynamic properties of a program are undecidable Does the program halt on all some inputs This is called the halting problem Is the result of a function F always positive Assume we can answer this question precisely Take function H and find out if it halts by testing function F x H x return 1 whether it has positive result Contradition Syntactic properties are decidable e g How many occurrences of x are there Programs without looping are also decidable 14 Conservative Program Analyses So we cannot tell for sure that x is always 3 Then how can we apply constant propagation It is OK to be conservative 15 Conservative Program Analyses So we cannot tell for sure that x is always 3 Then how can we apply constant propagation It is OK to be conservative If the optimization requires P to be true then want to know either P is definitely true Don t know if P is true Let s call this truthiness 16 Conservative Program Analyses So we cannot tell for sure that x is always 3 Then how can we apply constant propagation It is OK to be conservative If the optimization requires P to be true then want to know either P is definitely true Don t know if P is true It is always correct to say don t know We try to say don t know as rarely as possible All program analyses are conservative 17 Global Optimization Review X 3 B 0 Y Z W Y 0 A 2 X 18 Global Optimization Review X 3 X 3 B 0 B 0 Y Z W Y 0 Y Z W Y 0 X 4 A 2 3 A 2 X 19 Global Optimization Review X 3 X 3 B 0 B 0 Y Z W Y 0 Y Z W Y 0 X 4 A 2 3 A 2 3 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 20 Review The correctness condition is hard to check Checking it requires global analysis An analysis of the entire control flow graph for one method body We said that was impossible right 21 Global Analysis Global dataflow analysis is a standard technique for solving problems with these characteristics Global constant propagation is one example of an optimization that requires global dataflow analysis 22 Global 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 points Valid points cannot hide We will find you sometimes 23 Global Constant Propagation Cont To make the problem precise we associate one of the following values with X at every program point value interpretation c This statement is not reachable X constant c Don t know if X is a constant 24 Example Get out a piece of paper Let s fill in these blanks now X 3 X X X B 0 Y Z W X 4 X X X Y 0 A 2 X X X Recall not reachable c constant don t know 25 Example Answers X 3 X 3 X 3 X 3 B 0 Y Z W X 4 X 4 X X 3 Y 0 A 2 X X X 3 X 26 Using 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 x by the constant But how do we compute the properties x 27 The Idea The analysis of a complicated program can be expressed as a combination of simple rules relating the change in information between adjacent statements 28 Explanation 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 s Cin x s value of x before s Cout x s value of x after s 29 Transfer Functions Define a transfer function that transfers information from one statement to another 30 Rule 1 X s X Cout x s if Cin x s Recall unreachable code 31 Rule 2 X x c X c Cout x x c c if c is a constant 32 Rule 3 X x f X Cout x x f This is a conservative approximation It might be possible to figure out that f always returns 5 but we won t even try 33 Rule 4 X a y X a Cout x y Cin x y if x y 34 The Other Half Rules 1 4 relate the in of a statement to the out of the same statement they propagate information across …