1CS553 Lecture Program Optimizations using Data-Flow Analysis 2Program Optimizations using Data-Flow Analysis Last time– Lattice theoretic framework for data-flow analysis Today– Dead-code elimination– Copy propagation– Constant propagation– Common sub-expression elimination (CSE)CS553 Lecture Program Optimizations using Data-Flow Analysis 3Dead Code Elimination Remove statements that define only one variable and the variable beingdefined is not in the live out set. Algorithmdo {1) generate a FlowGraph from the list of instructions2) perform liveness3) for each node in FlowGraph if the defs set contains only one temporaryif the temporary being defined is not in the live out setremove the node from the FlowGraph4) generate a list of instructions from the modified FlowGraph} while (changes);CS553 Lecture Program Optimizations using Data-Flow Analysis 4Dead code elimination with the MiniJava compiler 1) Method in FlowGraph for removing a node that attaches predecessors withsuccessors. 2) Modify Targets class so that we can query getFallThrough() and get a label forconstructing a new list of Assem.Instr. 3) Method to trace through a FlowGraph to generate an Assem.Instr list. 4) DataFlowSet interface (will be provided) 5) DataFlowProblem interface (will be provided) 6) DataFlowSolver class where the constructor takes a DataFlowProblem as inputand solves it with IDFA. 7) Reimplement Liveness using the data-flow framework (an implementation forLiveDataFlowSet will be provided)CS553 Lecture Program Optimizations using Data-Flow Analysis 5Copy Propagation Propagate the results of a move statement. Algorithmdo {1) generate a FlowGraph from the list of instructions2) perform reaching definitions3) for each node in FlowGraph for each useif the use is reached by a def in a move statementchange the use to the rhs in the move statement4) generate a list of instructions from the modified FlowGraph} while (changes);2CS553 Lecture Program Optimizations using Data-Flow Analysis 6Copy propagation with the MiniJava compilerAssume the DataFlowSolver has already been written.– The ReachDefs class should implement the DataFlowProblem interface.– Implement a ReachDefsDataFlowSet class with reaching def statements pairedwith the temporary they define.– Implement a CopyProp class.CS553 Lecture Program Optimizations using Data-Flow Analysis 7Constant Propagation using Reaching Definitions Propagate the results of a CONSTANT move statement. Algorithmdo {1) generate a FlowGraph from the list of instructions2) perform reaching definitions3) for each node in FlowGraph for each useif the use is reached by a def in a constant move statementchange the use to the rhs in the move statement4) generate a list of instructions from the modified FlowGraph} while (changes);CS553 Lecture Program Optimizations using Data-Flow Analysis 8Constant Propagation with the MiniJava compilerAssume the DataFlowSolver has already been written.– Subclass Assem.Instr with a CONSTMOVE instruction type.– The ReachDefs class should implement the DataFlowProblem interface.– Implement a ReachDefsDataFlowSet class with reaching def statements pairedwith the temporary they define.– Implement a ConstPropReachDef class.CS553 Lecture Program Optimizations using Data-Flow Analysis 9Constant Propagation Goal– Discover constant variables and expressions and propagate them forwardthrough the program Uses– Evaluate expressions at compile time instead of run time– Eliminate dead code (e.g. , debugging code)– Improve efficacy of other optimizations (e.g., value numbering andsoftware pipelining)3CS553 Lecture Program Optimizations using Data-Flow Analysis 10RoadmapSimple ConstantsKildall [1973]1Sparse Simple ConstantsReif and Lewis [1977]faster2MoreconstantsSparse ConditionalConstantsWegman & Zadeck [1991]faster4MoreconstantsConditional ConstantsWegbreit [1975]3CS553 Lecture Program Optimizations using Data-Flow Analysis 11Kinds of Constants Simple constants Kildall [1973]– Constant for all paths through a program Conditional constants Wegbreit [1975]– Constant for actual paths through a program (when only one direction of aconditional is taken)j?4j := 32 j := 53c := 1...if c=11true falseCS553 Lecture Program Optimizations using Data-Flow Analysis 12 2v×c ∩ {(x,c) ∀c} {(x,c)} if (y,cy)∈In & (z,cz)∈In, {(x,cy ⊕ cz)}Data-Flow Analysis for Simple Constant Propagation Simple constant propagation: analysis is “reaching constants”– D:– ⊓:– F:– Kill(x←. . .) = – Gen(x←c) = – Gen(x←y⊕z) = – . . .CS553 Lecture Program Optimizations using Data-Flow Analysis 13 Reaching constants for simple constant propagation– D:– ⊓:– F:– Fx←c(In) = – Fx←y⊕z(In) = – . . . c ⊓ ⊤ = c c ⊓ ⊥ = ⊥ c ⊓ d = ⊥ if c ≠ d c ⊓ d = c if c = d{All constants} ∪ {⊤,⊥} Data-Flow Analysis for Simple Constant Propagation (cont) c if cy=Iny & cz=Inz, then cy ⊕ cz, else ⊤or ⊥¨⊥0 1 2 3-3 -2 -1 . . .. . .Using tuples of lattices4CS553 Lecture Program Optimizations using Data-Flow Analysis 14Initialization for Reaching Constants Pessimistic– Each variable is initially set to 󲰥in data-flow analysis– Forces merges at loop headers to go to 󲰥conservatively Optimistic– Each variable is initially set to ⊤in data-flow analysis– Each variable is set to 󲰥at the entry node in the flow graph.– What assumption is being made when optimistic reaching constants isperformed?CS553 Lecture Program Optimizations using Data-Flow Analysis 15Simple Constants with the MiniJava compilerAssume the DataFlowSolver has already been written.– Subclass Assem.Instr with a CONSTMOVE instruction type.– Subclass Assem.Instr with a BINOPMOVE instruction type that can be queriedfor the operator type, each operand, and the temporary being defined.– The SimpleConstants class should implement the DataFlowProblem interface.– In the transfer function, BINOPMOVE instructions may be replaced withCONSTMOVE instructions.– Can we replace operands to a BINOPMOVE instruction with a constant?– The SimpleConstants class should take a reference to a list of Assem.Instrs asinput and as a side-effect modify that list.CS553 Lecture Program Optimizations using Data-Flow Analysis 16Common Subexpression Elimination Idea– Find common subexpressions whose range spans the same basic blocksand eliminate unnecessary re-evaluations– Leverage available