Data-Flow AnalysisBack EndOptimization SafetyDead CodeSlide 5Slide 6Slide 7Low-Level IROptimizations and Control FlowControl Flow Graph (Revisited)Program PointsFlow of InformationLive Variable AnalysisComputing LivenessPart 1: Analyze InstructionsLiveness Across InstructionsExampleSlide 18Part 2: Analyze Control FlowControl FlowSystem of EquationsSolving the ProblemSlide 23Slide 24Slide 25Slide 26GeneralizationData-Flow AnalysisCS 671March 11, 20082CS 671 – Spring 2008Back EndInstruction selection•Mostly a local property•Build DAG of straight-line code, use pattern matching to identify instructionsOptimization and register allocation•Can be formulated as local problems•More effective as global passes–Larger scope increases knowledge, improves results–“Global”: typically means an entire procedure•Must take into account control flow3CS 671 – Spring 2008Optimization SafetySafety of code transformations often require verification of code properties•Information not obvious, explicit in the code•Requires systematic analysisExample: dead code elimination4CS 671 – Spring 2008Dead CodeExample:Conditions:•Computations whose value is never used•Obvious for straight-line code•What about control flow?x = y + 1;y = 2 * z;x = y + z;z = 1;z = x;Which statements can be safely removed?5CS 671 – Spring 2008Dead CodeWith control-flow:Which statements are dead code?•What if “c” is false?•Dead only on some paths through the codex = y + 1;y = 2 * z;if (c) x = y + z;z = 1;z = x;6CS 671 – Spring 2008Dead CodeWith more control-flow:Now which statements are dead code?while (p) { x = y + 1; y = 2 * z; if (c) x = y + z; z = 1;}z = x;7CS 671 – Spring 2008Dead CodeWith more control-flow:Statement “x = y+1” not deadWhat about “z = 1”?while (p) { x = y + 1; y = 2 * z; if (c) x = y + z; z = 1;}z = x;8CS 671 – Spring 2008Low-Level IRMost optimizations performed in low-level IR•Labels and jumps•No explicit loopsEven harder to seepossible pathslabel1:jumpifnot p label2x = y + 1y = 2 * zjumpifnot c label3x = y + zlabel3:z = 1jump label1label2:z = x9CS 671 – Spring 2008Optimizations and Control FlowRequired information•Not obvious from program–Dead code example: are there any possible paths that make use of the value?•Must verify conditions at compile-time•Must characterize all possible dynamic behaviorControl flow makes it hard to extract information•High-level: different kinds of control structures•Low-level: control-flow hard to inferNeed a unifying data structure10CS 671 – Spring 2008Control Flow Graph (Revisited)Control flow graph (CFG): a graph representation of the program•Includes both computation and control flow•Easy to check control flow properties•Provides a framework for global optimizations and other compiler passesNodes are basic blocks•Consecutive sequences of non-branching statementsEdges represent control flow•From jump to a label•Each block may have multiple incoming/outgoing edges11CS 671 – Spring 2008Program PointsIn between instructions•Before each instruction•After each instruction-x = y + 1-y = 2*z-if (c)--x = y + z--z = 1-May have multiple successors or predecessors12CS 671 – Spring 2008Flow of InformationQuestion 1: how does information flow across instructions?Question 2: how does information flow between predecessor and successor blocks?-x = y + 1-y = 2*z-if (c)--x = y + z--z = 1-13CS 671 – Spring 2008Live Variable AnalysisAt each program point: Which variables contain values computed earlier and needed laterFor instruction I:•in[I] : live variables at program point before I•out[I] : live variables at program point after IFor a basic block B:•in[B] : live variables at beginning of B•out[B] : live variables at end of BNote: in[I] = in[B] for first instruction of B out[I] = out[B] for last instruction of B14CS 671 – Spring 2008Computing LivenessAnswer question 1: for each instruction I, what is relation between in[I] and out[I]?Answer question 2: for each basic block B, with successors B1, …, Bn, what is relationship between out[B] and in[B1] … in[Bn]in[I]Iout[I]Bout[B]in[B1]B1in[Bn]Bn…15CS 671 – Spring 2008Part 1: Analyze InstructionsLive variables across instructionsExamples:Is there a general rule? Yes: knowing the variables live after I, we can compute variables live before Iin[I] = {y,z}x = y + zout[I] = {x,z}in[I] = {y,z,t}x = y + zout[I] = {x,t}in[I] = {x,t}x = x + 1out[I] = {x,t}16CS 671 – Spring 2008Liveness Across InstructionsHow is liveness determined?•All variables that I uses are live before I Called the uses of I•All variables live after I are also live before I, unless I writes to them Called the defs of IMathematically:in[I] = {y,z}x = 5out[I] = {x,y,z}in[I] = {b}a = b + 2in[I] = ( out[I] – def[I] )  use[I]17CS 671 – Spring 2008ExampleSingle basic block•Live1 = in[B] = in[I1]•Live2 = out[I1] = in[I2]•Live3 = out[I2] = in[I3]•Live4 = out[I3] = out[B]Relation between live sets•Live1 = (Live2 – {x})  {y}•Live2 = (Live3 – {y})  {z}•Live3 = (Live4 – {})  {d}Live1x = y+1Live2y = 2*zLive3if (d)Live418CS 671 – Spring 2008Flow of InformationEquation:Notice: information flows backwards•Need out[] sets to compute in[] sets•Propagate information upMany problems are forward Common sub-expressions, constant propagation, othersin[I] = ( out[I] – def[I] )  use[I]Live1x = y+1Live2y = 2*zLive3if (d)Live419CS 671 – Spring 2008Part 2: Analyze Control FlowQuestion 2: for each basic block B, with successors B1, …, Bn, what is relationship between out[B] and in[B1] … in[Bn]Examples:What’s the general rule?B{x,y,z}{x,z}B1{x,y}Bn…B{x,y}{x}B1{y}Bn…20CS 671 – Spring 2008Control FlowRule: A variable is live at end of block B if it is live at the beginning of any of the successors•Characterizes all possible executions•Conservative: some paths may not actually happenMathematically:Again: information flows backwardsAlso: information flows from any pathout[B] =  in[B’]B’  succ(B)21CS 671 – Spring 2008System of EquationsPut parts together:Defines a system of equations (or constraints)•Consider equation instances for each instruction and each basic block•What happens with loops?–Circular dependences in the constraints–Is that a problem?in[I] = ( out[I] – def[I] )  use[I]out[B] =  in[B’]B’  succ(B)Often called a system of Dataflow Equations22CS 671 – Spring