**Unformatted text preview:**

1CIS570 Lecture 4 Introduction to Data-flow Analysis 2Introduction to Data-flow Analysis Last Time– Control flow analysis– BT discussion Today– Introduce iterative data-flow analysis– Liveness analysis– Introduce other useful conceptsCIS570 Lecture 4 Introduction to Data-flow Analysis 3Data-flow Analysis Idea– Data-flow analysis derives information about the dynamicbehavior of a program by only examining the static code 1 a := 0 2 L1: b := a + 1 3 c := c + b 4 a := b * 2 5 if a < 9 goto L1 6 return cExample– How many registers do we needfor the program on the right?– Easy bound: the number ofvariables used (3)– Better answer is found byconsidering the dynamicrequirements of the program2CIS570 Lecture 4 Introduction to Data-flow Analysis 4Liveness Analysis Definition– A variable is live at a particular point in the program if its value at thatpoint will be used in the future (dead, otherwise).∴ To compute liveness at a given point, we need to look into the future Motivation: Register Allocation– A program contains an unbounded number of variables– Must execute on a machine with a bounded number of registers– Two variables can use the same register if they are never in use at the sametime (i.e, never simultaneously live). ∴ Register allocation uses liveness informationCIS570 Lecture 4 Introduction to Data-flow Analysis 5Control Flow Graphs (CFGs) Simplification– For now, we will use CFG’s in which nodes represent programstatements rather than basic blocks Example 1 a := 0 2 L1: b := a + 1 3 c := c + b 4 a := b * 2 5 if a < 9 goto L1 6 return creturn ca = 0b = a + 1a<9126534a = b * 2c = c + bYesNo3CIS570 Lecture 4 Introduction to Data-flow Analysis 6Liveness by Example What is the live range of b?– Variable b is read in statement 4,so b is live on the (3 → 4) edge– Since statement 3 does not assigninto b, b is also live on the (2→3) edge– Statement 2 assigns b, so anyvalue of b on the (1→2) and (5→2) edges are not needed, so b isdead along these edges b’s live range is (2→3→4)return ca = 0b = a + 1a<9126534a = b * 2c = c + bYesNoCIS570 Lecture 4 Introduction to Data-flow Analysis 7Liveness by Example (cont) Live range of a– a is live from (1→2) and again from(4→5→2)– a is dead from (2→3→4) Live range of b– b is live from (2→3→4) Live range of c– c is live from(entry→1→2→3→4→5→2, 5→6)return ca = 0b = a + 1a<9126534a = b * 2c = c + bYesNo Variables a and b are never simultaneously live, so they can share a register4CIS570 Lecture 4 Introduction to Data-flow Analysis 8Terminology Flow Graph Terms– A CFG node has out-edges that lead to successor nodes and in-edges thatcome from predecessor nodes– pred[n] is the set of all predecessors of node nsucc[n] is the set of all successors of node n Examples– Out-edges of node 5:– succ[5] =– pred[5] =– pred[2] =(5→6) and (5→2){2,6}{1,5}{4}return ca = 0b = a + 1a<9126534a = b * 2c = c + bYesNoCIS570 Lecture 4 Introduction to Data-flow Analysis 9Uses and Defs Def (or definition)– An assignment of a value to a variable– def[v] = set of CFG nodes that define variable v– def[n] = set of variables that are defined at node n Use– A read of a variable’s value– use[v] = set of CFG nodes that use variable v– use[n] = set of variables that are used at node n More precise definition of liveness– A variable v is live on a CFG edge ifa = 0a < 9?∉ def[v]∈ use[v]v live (1) ∃ a directed path from that edge to a use of v (node in use[v]), and(2) that path does not go through any def of v (no nodes in def[v])5CIS570 Lecture 4 Introduction to Data-flow Analysis 10a := b * 25c := c + bThe Flow of Liveness Data-flow– Liveness of variables is a property that flowsthrough the edges of the CFG Direction of Flow– Liveness flows backwards through the CFG,because the behavior at future nodesdetermines liveness at a given node– Consider a– Consider b– Later, we’ll see other propertiesthat flow forwarda < 9?b := a + 1YesNo31a := 046return c2CIS570 Lecture 4 Introduction to Data-flow Analysis 11Liveness at Nodesedgesa = 0 Two More Definitions– A variable is live-out at a node if it is live on any of that node’s out-edges– A variable is live-in at a node if it is live on any of that node’s in-edges We have liveness on edges– How do we talk aboutliveness at nodes?just after computationjust before computationa := b * 25c := c + ba < 9?b := a + 1YesNo31a := 046return c2nlive-outout-edgesnlive-inin-edgesprogram points6CIS570 Lecture 4 Introduction to Data-flow Analysis 12 Data-flow equations in[n] = use[n] ∪ (out[n] – def[n]) out[n] = ∪ in[s]s ∈ succ[n](1)(3)(2) Rules for computing liveness (1) Generate liveness:If a variable is in use[n],it is live-in at node nnlive-inuse live-innlive-out (3) Push liveness across nodes:If a variable is live-out at node n and not in def[n] then the variable is also live-in at nlive-outnlive-inpred[n]live-outlive-out (2) Push liveness across edges:If a variable is live-in at a node n then it is live-out at all nodes in pred[n]Computing LivenessCIS570 Lecture 4 Introduction to Data-flow Analysis 13Solving the Data-flow Equations Algorithm This is iterative data-flow analysis (for liveness analysis)for each node n in CFGin[n] = ∅; out[n] = ∅repeatfor each node n in CFGin’[n] = in[n]out’[n] = out[n]in[n] = use[n] ∪ (out[n] – def[n])out[n] = ∪ in[s]until in’[n]=in[n] and out’[n]=out[n] for all ns ∈ succ[n]initialize solutionssolve data-flow equationstest for convergencesave current results7CIS570 Lecture 4 Introduction to Data-flow Analysis 14 3 bc c 5 a 2 a b 1 anode#use def in out in out in out in out in out in out in out 4 b a 6 c1st 2nd 3rd 4th 5th 6th 7thcaba abcaca bcbc bb aa acacac bcbc bb aac acaccac bcbc bb acac acc accac bcbc bbc acac acc accac bcbc bcbc acac acc accac bcbc bcbc acac acData-flow Equations for Livenessin[n] = use[n] ∪ (out[n] – def[n])out[n] = ∪ in[s]s ∈ succ[n]YesNo2b := a + 13c := c + b1a := 04a := b * 25a < 9?6return cExampleCIS570 Lecture 4 Introduction to Data-flow Analysis 15Improving PerformanceConsider the (3→4) edge in the graph:out[4] is used to compute in[4]in[4] is used to compute out[3] . . .So we should compute the sets in theorder: out[4], in[4], out[3], in[3], . .

View Full Document