Project 4: Dataflow OptimizationAn “Optimizing” CompilerAn Optimizing CompilerLow IR (or Mid IR)Lowering Cont.Control-Flow AnalysisPeephole OptimizationsInline Function Expansion (Procedure Integration)ExampleSlide 10“Global” OptimizationsIterative Dataflow AnalysisExample: Reaching DefsSlide 14Slide 15Analysis Information Inside Basic BlocksTransformation Examples with Dataflow AnalysisConstant PropagationUseful Way to Store Reaching DefsCopy PropagationSlide 21Copy Propagation AnalysisSlide 23Slide 24Liveness AnalysisSlide 26Dead Code EliminationShortcoming of Liveness-Based DCE ExampleLoop Invariant Code MotionSlide 30General Dataflow Analysis FrameworkSlide 32Common Sub-Expression EliminationAvailable ExpressionsSlide 35Slide 36Slide 37Now What?Slide 39Slide 40Slide 416.035 Project 4: Dataflow Optimization Jason Ansel CSAILAn “Optimizing” Compiler ● Somehow make the code better (onaverage): – Faster – Smaller memory footprint of code – Less memory used during run ● How to prove this: – Experimentation on benchmark suite! ● Must preserve the meaning of the originalprogram! – Including errors!An Optimizing Compiler Lowering Dataflow Analysis Transformation Dataflow Analysis Control Flow Analysis Code Gen Transformation Optimization PeepholeLow IR (or Mid IR) ● Do analysis on low-level IR (does this fit what you had for code gen?) – Simple computations: a = b + c – explicit array accesses – gotos – labels – moves – calls ● See Tiger chp. 17 or Whale chp. 4Lowering Cont. ● Perform transformations on your IR: – Global CSE – Loop invariant code motion – Copy propagation – DCE ● Some optimizations may work better if you have info from high level IR – Parallelization – Maybe easier to do in High-level IR?Control-Flow Analysis ● Convert the intermediate code into graph ofbasic blocks ● Basic block: – sequence of instructions with a single entry anda single exit – Control must enter at beginning and leave at end ● Simple to convert to a control flow graph – find heads of basic block: ● after jump ● target of jumpPeephole Optimizations ● Examine a short sequence of instructions ● Try to replace with a better sequence ● Examples: – Flow of controls ● jumps to jumps – Algebraic Simplification ● x + 0  x – Strength Reduction ● x * 3  x + x + x ● Look at AMD64 documentationInline Function Expansion (Procedure Integration) ● Replace a function call with the body of the function ● Usually done on high-level IR (AST) ● Careful: – Performance? – Recursion?! – Names…Example Program { int x; void foo() { x = 2; } void main() { { int x; foo(); } print(x); }Example Program { int x; void foo() { x = 2; } void main() { { int x; x = 2; } print(x); }“Global” Optimizations ● Global mean inter-basic block and intra-procedural ● You can inline functions ● Operate on control flow graph of basic blocks – You can use a CFG of MIR or LIR ● Usually: – Perform some dataflow analysis to find candidates – Validate the correct of candidates using other testsIterative Dataflow Analysis ● Use bit vectors to represent the information – instructions, expressions, variables, etc. ● Set of dataflow equations ● Iterate until a fixed point is reached ● For each basic block, b: – IN[b] – information that flows into block – OUT[b] – information that flows out of block – What happens inside the blockExample: Reaching Defs ● Concept of definition and use – a = x+y – is a definition of a – is a use of x and y ● Given a program point p, a definition d reaches p – there exists a path from p to d where ● there is not a redefinition of the var of d – In other words, d is not killed before it reaches pExample: Reaching Defs ● Each basic block has – IN - set of definitions that reach beginning of block – OUT - set of definitions that reach end of block – GEN - set of definitions generated in block ● Be careful about redefinitions in block – KILL - set of definitions killed in block ● A statement does not kill itself!Example: Reaching Defs ● IN[b] = OUT[b1] U ... U OUT[bn] – where b1, ..., bn are predecessors of b in CFG ● OUT[b] = GEN[b] U (IN[b] - KILL[b]) – Transfer function! ● IN[entry] = 0…0 ● Forward analysis ● Confluence operator: U ● Transfer function of form: f(X) = A U (X – B) – A = GEN, B = KILLAnalysis Information Inside Basic Blocks ● One detail: – Given dataflow information at IN and OUT of node – Also need to compute information at each statement of basic block – Simple propagation algorithm usually works fine – Can be viewed as restricted case of dataflow analysis ● Generates gen[b] and kill[b] sets for each basic blocks for reaching defs ● Might have to specialize for each analysisTransformation Examples with Dataflow Analysis ● Global Constant Propagation and Folding – ~Reaching definitions ● Global Copy Propagation – Reaching definitions + More ● Loop Invariant Code Motion – Reaching definitions ● Liveness Analysis – Useful for register allocationConstant Propagation ● Constant propagation is the process ofsubstituting the values of known constants in expressions at compile time. int x = 14; int y = 7 - x / 2; return y * (28 / x + 2); ● Applying constant propagation once yields: int x = 14; int y = 7 - 14 / 2; return y * (28 / 14 + 2); ● Can apply again after folding! ● Works on your 3-address low IR.Useful Way to Store Reaching Defs ● Use-def and Def-use chains – Use-Def (UD) chain lists all definitions flowing to a use of a variable – Def-Use (DU) chain lists all uses which can be reached by a definition ● Ex: Global Constant Propagation – For each use of a variable, find all definitions – If all definitions of the variable are constant and same value, replace the use with the constantCopy Propagation ● copy propagation is the process of replacing the occurrences of targets of direct assignments with their values. ● A direct assignment is an instruction of the form x = y, which simply assigns the value of y to x. x = y; z = 3 + x ● Copy propagation would yield: x = y z = 3 + yCopy Propagation ● For s: x = y, we can substitute y for x in all places, u, where this definition of x is used. – s must be only def of x reaching u – On every path from s to u, there are no assignments to y. ● 1 and 2 can be checked with u/d chains but with additional