9/26/061CIS570 Lecture 5 Generalizing Data-flow Analysis 2Generalizing Data-flow Analysis Last Time– Introduction to data-flow analysis Today– Other types of data-flow analysis– Reaching definitions, available expressions, reaching constants– Abstracting data-flow analysisWhat’s common among the different analyses?CIS570 Lecture 5 Generalizing Data-flow Analysis 3 1 a = . . .; 2 b = . . .; 3 for (. . .) { 4 x = a + b; 5 . . . 6 }To determine whether it’s legal to move statement 4out of the loop, we need to ensure that there are noreaching definitions of a or b inside the loopReaching Definitions Definition– A definition (statement) d of a variable v reachesnode n if there is a path from d to n such that v isnot redefined along that path Uses of reaching definitions– Build use/def chains– Constant propagation– Loop invariant code motionv :=...dnReaching definitions of a and bx := 5dn f(x)Does this def of x reach n?Can we replace n with f(5)? ∉ def[v]9/26/062CIS570 Lecture 5 Generalizing Data-flow Analysis 4 Defining Gen and Kill for various statement types statement Gen[s] Kill[s] s: t = b op c s: t = M[b] s: M[a] = b s: if a op b goto Lstatement Gen[s] Kill[s]s: goto Ls: L:s: f(a,…)s: t=f(a, …)Computing Reaching Definitions Assumption– At most one definition per node– We can refer to definitions by their node “number” Gen[n]: Definitions that are generated by node n (at most one)Kill[n]: Definitions that are killed by node n {s} def[t] {s} def[t] {?} {} {} {}{} {}{} {} {} {}{s} def[t]CIS570 Lecture 5 Generalizing Data-flow Analysis 5Data-flow Equations for Reaching Definitions The in set– A definition reaches the beginning of a node if it reaches the end of any ofthe predecessors of that node The out set– A definition reaches the end of a node if (1) the node itself generates thedefinition or if (2) the definition reaches the beginning of the node and thenode does not kill it in[n] = ∪ out[p] out[n] = gen[n] ∪ (in[n] – kill[n]) p ∈ pred[n]ninpred[n]out outnoutGen(1)noutin(2)9/26/063CIS570 Lecture 5 Generalizing Data-flow Analysis 6Recall Liveness Analysis Data-flow equations for liveness in[n] = use[n] ∪ (out[n] – def[n]) out[n] = ∪ in[s]s ∈ succ[n] Gen: New information that’s added at a node Kill: Old information that’s removed at a node Can define almost any data-flow analysis in terms of Gen and Kill in[n] = gen[n] ∪ (out[n] – kill[n]) out[n] = ∪ in[s]s ∈ succ[n]A use of a variable generates livenessA def of a variable kills livenessLiveness equations in terms of Gen and KillCIS570 Lecture 5 Generalizing Data-flow Analysis 7 Backward data-flow analysis– Information at a node is based on what happens later in the flow graphi.e., in[] is defined in terms of out[] in[n] = gen[n] ∪ (out[n] – kill[n]) out[n] = ∪ in[s] Forward data-flow analysis– Information at a node is based on what happens earlier in the flow graphi.e., out[] is defined in terms of in[] in[n] = ∪ out[p] out[n] = gen[n] ∪ (in[n] – kill[n]) Some problems need both forward and backward analysis– e.g., Partial redundancy elimination (uncommon)Direction of Flowinoutns ∈ succ[n]p ∈ pred[n]livenessinoutnreachingdefinitions9/26/064CIS570 Lecture 5 Generalizing Data-flow Analysis 8 out[n] = ∪ in[s] in[n] = gen[n] ∪ (out[n] – kill[n]) in[n] = ∪ out[s] out[n] = gen[n] ∪ (in[n] – kill[n])=xnentryIs x def’d alongthis path?Use of xLive VariablesReaching Definitionsx= nentryDef of xIs x def’d alongthis path? Symmetry between reaching definitions and liveness– Swap in[] and out[] and swap the directions of the arcss ∈ succ[n]Data-flow Equations for Reaching Definitionsp ∈ pred[n]CIS570 Lecture 5 Generalizing Data-flow Analysis 9A Better Formulation of Reaching Definitions Problem– Reaching definitions gives you a set of definitions (nodes)– Doesn’t tell you what variable is defined– Expensive to find definitions of variable v Solution– Reformulate to include variablee.g., Use a set of (var, def) pairsx= ay= bnin[n] = {(x,a),(y,b),...}9/26/065CIS570 Lecture 5 Generalizing Data-flow Analysis 10Merging Flow Values Live variables and reaching definitions– Merge flow values via set union Why? When might this be inappropriate? out[n] = ∪ in[s] in[n] = gen[n] ∪ (out[n] – kill[n]) in[n] = ∪ out[s] out[n] = gen[n] ∪ (in[n] – kill[n])Live VariablesReaching Definitionss ∈ succ[n]p ∈ pred[n]CIS570 Lecture 5 Generalizing Data-flow Analysis 11Available Expressions Definition– An expression, x+y, is available at node n if every path from theentry node to n evaluates x+y, and there are no definitions of x or yafter the last evaluation...x+y......x+y......x+y...entrynx and y not definedalong blue edges9/26/066CIS570 Lecture 5 Generalizing Data-flow Analysis 12Available Expressions for CSE How is this information useful? Common Subexpression Elimination (CSE)– If an expression is available at a point where it is evaluated, it need not berecomputed Example3c := 4 * i2i := i + 1t := 4 * ib := t1i := jt := 4 * ia := t3c := t1i := ja := 4 * i2i := i + 1b := 4 * iCIS570 Lecture 5 Generalizing Data-flow Analysis 13Must vs. May Information May information– Identifies possibilities Must information– Implies a guaranteeMay Mustsafe overly large set overly small setdesired information small set large setGen add everything that add only facts that aremight be true guaranteed to be trueKill remove only facts that remove everything thatare guaranteed to be false might be falsemerge union intersectioninitial guess empty set universal setLiveness?Available expressions?9/26/067CIS570 Lecture 5 Generalizing Data-flow Analysis 14Reaching Definitions: Must or May Analysis? Consider constant propagationx = 5dn f(x)We need to know if d’might reach node nx = 4d’CIS570 Lecture 5 Generalizing Data-flow Analysis 15 Must or may Information? Direction? Flow values? Initial guess? Kill? Gen? Merge?Defining Available Expressions Analysis9/26/068CIS570 Lecture 5 Generalizing Data-flow Analysis 16Data-Flow Equationsin[n] = ∩ out[p]out[n] = gen[n] ∪ (in[n] – kill[n])Plug it in to our general DFA algorithmfor each node nin[n] = υ; out[n] = υrepeatfor each n in′[n] = in[n] out′[n] = out[n] in[n] = ∩ out[p] out[n] = gen[n] ∪ (in[n] – kill[n])until in′[n]=in[n] and out′[n]=out[n] for