1CS553 Lecture Generalizing Data-flow Analysis 2Generalizing Data-flow Analysis Announcements– Project 2 writeup is available– Read Stephenson paper Last Time– Control-flow analysis Today– C-Breeze Introduction– Other types of data-flow analysis– Reaching definitions, available expressions, reaching constants– Abstracting data-flow analysisWhat’s common among the different analyses?– Introduce lattice-theoretic frameworksCS553 Lecture Generalizing Data-flow Analysis 3The C-Breeze Compiler Characteristics– A C source-to-source translator– Implemented in C++– Makes heavy use of templates and the Standard Template Library Organized as a set of phases– Parse an ANSI C program, producing an AST– Dismantle the C program into a LIR form– Emit C code as output– Can perform various analyses and transformations Can create new phases easily– Uses common design patterns: walkers and changers2CS553 Lecture Generalizing Data-flow Analysis 4C-Breeze StructureANSI Ccbzmyphase.olibc-breeze.aANSI C, call graph,assembly, statistics, etc.Output is determined by the phases that are invokedCS553 Lecture Generalizing Data-flow Analysis 5C-Breeze Terminology Phase– An organizational unit of work (analysis, transformation, or both) Translation unit– A file of a source program Walker– Uses visitor pattern to traversing the AST Changer– Uses visitor pattern for traversing and changing nodes in the AST3CS553 Lecture Generalizing Data-flow Analysis 6Walker Example (src/main/print_walker.*) void print_walker::at_basicblock(basicblockNode * the_bb, Order ord) { if (ord == Preorder) { indent(the_bb); _out << "basicblock: "; if (the_bb->decls().empty()) _out << "(no decls) "; if (the_bb->stmts().empty()) _out << "(no stmts) "; _out << endl; in(); } if (ord == Postorder) out(); } print_walker pw;unit_list_p u;// for each translation unit in the program...for (u=CBZ::Program.begin(); u!= CBZ::Program.end(); u++) // ... walk the AST using the CountAssg walker (*u)->walk (pw);CS553 Lecture Generalizing Data-flow Analysis 7Other C-Breeze Information No Symbol Table Alias Analysisint main(){ int a[10],b,c,d; a[3] = 4; b = 5+3; c = c+b + a[3]; return 0;}... a[3] = 4; __T2 = 8; b = 8; __T3 = c + 8; __T4 = __T3 + a[3]; c = __T4;...4CS553 Lecture Generalizing Data-flow Analysis 8Evaluating Compiler Infrastructures Efficiency– Execution time for parsing and transformation– Memory requirements– Speed of resulting code Front-ends and back-ends– Which ones are available and how robust? Intermediate Representation– How well defined is the IR-API? Pass Construction– How difficult is it to write analyses and transformations?– What basic analyses are available?– Debugging assistance?CS553 Lecture Generalizing Data-flow Analysis 9 1 a = . . .; 2 b = . . .; 3 for (. . .) { 4 x = a + b; 5 . . . 6 }To determine whether it’s legal to move statement4 out of the loop, we need to ensure that there areno reaching 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 := 5dnf(x)Does this def of x reach n?can we replace n with f(5)? ∉ def[v]5CS553 Lecture Generalizing Data-flow Analysis 10 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 11A 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= a y= bnin[n] = {(x,a),(y,b),...}6CS553 Lecture Generalizing Data-flow Analysis 12 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 13Available 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 edges7CS553 Lecture Generalizing Data-flow Analysis 14Available 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 15 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 Analysis8CS553 Lecture Generalizing Data-flow Analysis 16Must 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 17Reaching Definitions: Must or May Analysis? Consider constant propagationx = 5dnf(x)We