This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1CS553 Lecture Generalizing Data-flow Analysis 2Generalizing Data-flow Analysis Announcements– Read the data-flow analysis handout Today– Other types of data-flow analysis– Reaching definitions, available expressions, reaching constants– Abstracting data-flow analysisWhat’s common among the different analyses?CS553 Lecture 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]CS553 Lecture Generalizing Data-flow Analysis 4 Defining Gen and Kill for various statement types statement Gen[s] Kill[s] s: t = b op c {s} def[t] – {s} s: t = M[b] {s} def[t] – {s} s: M[a] = b {} {} s: if a op b goto L {} {}statement Gen[s] Kill[s]s: goto L {} {}s: L: {} {}s: f(a,…) {} {}s: t=f(a, …) {s} def[t] – {s}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 nCS553 Lecture Generalizing Data-flow Analysis 5A 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),...}2CS553 Lecture Generalizing Data-flow Analysis 6 1 a = . . .; 2 b = . . .; 3 ... 4 x = f(b);Recall Liveness Analysis Definition– A variable is live at a particular point in theprogram if its value at that point will be used inthe future (dead, otherwise). Uses of Liveness– Register allocation– Dead-code eliminationdnIf a is not live out of statement 1 thenstatement 1 is dead code.∉ def[v]...:= vCS553 Lecture Generalizing Data-flow Analysis 7Available 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 edgesCS553 Lecture Generalizing Data-flow Analysis 8Available 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 * iCS553 Lecture Generalizing Data-flow Analysis 9 guaranteed or possibleforward or backwardvariables, definitions, ...universal or empty setdue to semantics of stmt what is removed from setdue to semantics of stmt what is added to sethow sets from two control paths compose Must or may Information Direction Flow values Initial guess Kill Gen MergeAspects of Data-flow Analysis3CS553 Lecture Generalizing Data-flow Analysis 10Must vs. May Information Must information– Implies a guarantee May information– Identifies possibilitiesMay 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 true might be falsemerge union intersectioninitial guess empty set universal setLiveness?Available expressions?CS553 Lecture Generalizing Data-flow Analysis 11Reaching Definitions: Must or May Analysis? Consider constant propagationx = 5dnf(x)We need to know if d’might reach node nx = 4d’CS553 Lecture Generalizing Data-flow Analysis 12 Must Forward Sets of expressions Universal set Set of expressions killed by statement sSet of expressions evaluated by s Intersection Must or may Information? Direction? Flow values? Initial guess? Kill? Gen? Merge?Defining Available Expressions AnalysisCS553 Lecture Generalizing Data-flow Analysis 13Reaching Constants Goal– Compute value of each variable at each program point (if possible) Flow values– Set of (variable,constant) pairs Merge function– Intersection Data-flow equations– Effect of node n x = c– kill[n] = {(x,d)| ∀d}– gen[n] = {(x,c)}– Effect of node n x = y + z– kill[n] = {(x,c)| ∀c}– gen[n] = {(x,c) | c=valy+valz, (y, valy) ∈ in[n], (z, valz) ∈ in[n]}4CS553 Lecture Generalizing Data-flow Analysis 14Reality Check! Some definitions and uses are ambiguous– We can’t tell whether or what variable is involvede.g., *p = x; /* what variable are we assigning?! */– Unambiguous assignments are called strong updates– Ambiguous assignments are called weak updates Solutions– Be conservative– Sometimes we assume that it could be everythinge.g., Defining *p (generating reaching definitions)– Sometimes we assume that it is nothinge.g., Defining *p (killing reaching definitions)– Try to figure it out: alias/pointer analysis (more later)CS553 Lecture Generalizing Data-flow Analysis 15ConceptsData-flow analyses are distinguished by– Flow values (initial guess, type)– May/must– Direction– Gen– Kill– Merge Complication– Ambiguous references (strong/weak updates)CS553 Lecture Generalizing Data-flow Analysis 16Next Time Lecture– Lattice theoretic foundation for data-flow


View Full Document

CSU CS 553 - Study Guide

Download Study Guide
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Study Guide and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Study Guide 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?