WIXLIB

Dataflow analysisCS252r Spring 2011(Based on lecture notes by Jeff Foster)

Control flow graph A control flow graph is a representation of aprogram that makes certain analyses (includingdataflow analyses) easier A directed graph where Each node represents a statement Edges represent control flow Statements may be Assignments: x : y or x : y op z or x : op y Branches: goto L or if b then goto L etc. 2010 Stephen Chong, Harvard University2

Control-flow graph examplex : a y : a *while (ya : ax : a}b;b; a) { 1; bx : a b;y : a * b;y aa : a 1;x : a b 2010 Stephen Chong, Harvard University3

Variations on CFGs Usually don’t include declarations (e.g., int x;) inthe CFG But there’s usually something in the implementation May want a unique entry and exit node Won’t matter for the examples we give May group statements into basic blocks A sequence of instructions with no branches into orout of the block 2010 Stephen Chong, Harvard University4

Control-flow graph with basic blocksx : a y : a *while (ya : ax : a}b;b; a) { 1; b Can lead to more efficientimplementations More complicated toexplain, so for the meantimewe’ll use single statementblocks 2010 Stephen Chong, Harvard Universityx : a b;y : a * b;y aa : a 1;x : a b5

Graph example with entry and exitentryx : a y : a *while (ya : ax : a}b;b; a) { 1; b All nodes without a normalpredecessor should bepointed to by entry All nodes with a successorshould point to exit 2010 Stephen Chong, Harvard Universityx : a b;y : a * b;y aa : a 1;exitx : a b6

CFG vs AST CFGs are much simpler than ASTs Fewer forms, less redundancy, only simpleexpressions But AST is a more faithful representation CFGs introduce temporaries Lose block structure of program ASTs are Easier to report error other messages Easier to explain to programmer Easier to unparse to produce readable code 2010 Stephen Chong, Harvard University7

Dataflow analysis A framework for proving facts about programs Reasons about lots of little facts Little or no interaction between facts Works best on properties about how programcomputes Based on all paths through program Including infeasible paths Let’s consider some dataflow analyses 2010 Stephen Chong, Harvard University8

Available expressions An expression e is available at program point p if e is computed on every path to p,and the value of e has not changed since the last time e wascomputed on the paths to p Available expressions can be used to optimizecode If an expression is available, don’t need to recompute it(provided it is stored in a register somewhere) 2010 Stephen Chong, Harvard University9

Data flow facts Is expression e available? Facts “a b is available” “a * b is available” “a 1 is available”entryx : a b;y : a * b;y a For each programpoint, we willcompute which factshold. 2010 Stephen Chong, Harvard Universitya : a 1;exitx : a b10

Gen and Kill What is the effect of eachstatement on the facts?StmtGenKillentryx : a b;y : a * b;x : a ba by ay : a * ba*ba : a 1;y aa : a 1 2010 Stephen Chong, Harvard Universitya 1a ba*bexitx : a b11

Computing available expressionsentry {a b}x : a b;{a b}y : a * b;{a b, a*b}{a b, a*b}{a b}y a{a b}{a b, a*b}{a b, a*b}{a b}a : a 1; exitx : a b{a b} 2010 Stephen Chong, Harvard University12

Terminology A join point is a program point where two ormore branches meet Available expressions is a forward must analysis Forward Data flow from in to out Must At join points, only keep facts that hold on allpaths that are joined 2010 Stephen Chong, Harvard University13

Data flow equations Let s be a statement succs(s) { immediate successor stmts of s } preds(s) { immediate predecessor stmts of s } In(s) program point just before executing s Out(s) program point just after executing s In(s) s’ preds(s) Out(s’) Out(s) Gen(s) (In(S) - Kill(s)) 2010 Stephen Chong, Harvard University14

Liveness analysis A variable v is live at program point p if v will be used on some execution path originatingfrom p before v is overwritten Optimization If a variable is not live, no need to keep it in a register If variable is dead at assignment, can eliminateassignment 2010 Stephen Chong, Harvard University15

Data flow equations Available expressions is a forward must analysis Propagate facts in same direction as control flow Expression is available only if available on all paths Liveness is a backwards may analysis To know if a variable is live, we need to look at the futureuses of it. We propagate facts backwards, from Out to In Variable is live if it is used on some path Out(s) s’ succs(s) In(s’) In(s) Gen(s) (Out(S) - Kill(s)) 2010 Stephen Chong, Harvard University16

Gen and Kill What is the effect of eachstatement on the facts?StmtGenKillentryx : a b;y : a * b;x : a by : a * by aa : a 1 2010 Stephen Chong, Harvard Universitya, ba, bxya : a 1;a, yay aaexitx : a b17

Computing live variablesx : a b;x, y, a, bx, y, a, bx, y, a, by, a, by, a, by : a * b;y ax, a, bx, a, bx, y, ax, y, axxa : a 1;x : a b 2010 Stephen Chong, Harvard Universitya, by, a, bx, y, a,a b18

Very busy expressions An expression e is very busy at point p if On every path from p, expression e is evaluated beforethe value of e is changed Optimization Can hoist very busy expression computation What kind of problem? Forward or backward? May or must? 2010 Stephen Chong, Harvard University19

Reaching definitions A definition of a variable v is an assignment to v A definition of variable v reaches point p if There is no intervening assignment to v Also called def-use information What kind of problem? Forward or backward? May or must? 2010 Stephen Chong, Harvard University20

Space of data flow ive variablesAvailableexpressionsVery busyexpressions Most dataflow analyses can be categorized inthis way A few don’t fit, need bidrectional flow Lots of literature on data flow analyses 2010 Stephen Chong, Harvard University21

Data flow facts and lattices Typically, data flow facts form lattices E.g., available expressionsa b, a*b, a 1a*b, a 1 “top”a b, a*ba b, a 1a*ba 1a b 2010 Stephen Chong, Harvard University “bottom”22

Partial orders and lattices A partial order is a pair (P, ) such that is a relation over P ( P P) is reflexive, anti-symmetric, and transitive A partial order is a lattice if every two elements of P havea unique least upper bound and greatest lower bound. is the meet operator: x y is the greatest lower bound of x and y x y xand x y y if z x and z y then z x y is the join operator: x y is the least upper bound of x and y x x yand y x y if x z and y z then x y z A join semi-lattice (meet semi-lattice) has only the join (meet) operator defined 2010 Stephen Chong, Harvard University23

Complete lattices A partially ordered set is a complete lattice ifmeet and join are defined for all subsets (i.e., notjust for all pairs) A complete lattice always has a bottom elementand a top element A finite lattice always has a bottom element anda top element 2010 Stephen Chong, Harvard University24

Useful latticesS (2 , ) forms a lattice for any set S 2S is powerset of S, the set of all subsets of S. If (S, ) is a lattice, so is (S, ) i.e., can “flip” the lattice Lattice for constant propagation 1234. 2010 Stephen Chong, Harvard University25

Forward must data flow algorithmOut(s) for all statements sW : { all statements }repeat {Take s from W(worklist) In(s) : s′ pred(s) Out(s′)temp : Gen(s) (In(s) - Kill(s))if (temp ! Out(s)) {Out(s) : tempW : W succ(s)}} until W 2010 Stephen Chong, Harvard University26

Monotonicity A function f on a partial order is monotonic if if x y then f(x) f(y) Functions for computing In(s) and Out(s) aremonotonic In(s) : s′ pred(s) Out(s′) temp : Gen(s) (In(s) - Kill(s)) Putting them together: 2010 Stephen Chong, Harvard UniversityA function fs of In(s) s′ pred(s) Out(s′))temp : fs(27

Termination We know the algorithmterminates In each iteration, eitherW gets smaller, or Out(s)decreases for some s Since function is monotonic Lattice has only finiteheight, so for each s,Out(s) can decrease onlyfinitely often 2010 Stephen Chong, Harvard UniversityOut(s) for all statements sW : { all statements }repeat {Take s from WIn(s) : s′ pred(s)Out(s′)temp : Gen(s) (In(s) - Kill(s))if (temp ! Out(s)) {Out(s) : tempW : W succ(s)}} until W 28

Termination A descending chain in a lattice is a sequencex0 x1 . The height of a lattice is the length of the longestdescending chain in the lattice Then, dataflow must terminate in O(nk) time n # of statements in program k height of lattice assumes meet operation and transfer function takesO(1) time 2010 Stephen Chong, Harvard University29

Fixpoints Dataflow tradition: Start with Top, use meet To do this, we need a meet semilattice with top complete meet semilattice meets defined for any set finite height ensures termination Computes greatest fixpoint Denotational semantics tradition: Start withBottom, use join Computes least fixpoint 2010 Stephen Chong, Harvard University30

Forward must data flow algorithmOut(s) for all statements sW : { all statements }repeat {Take s from W(worklist) In(s) : s′ pred(s) Out(s′)temp : Gen(s) (In(s) - Kill(s))if (temp ! Out(s)) {Out(s) : tempW : W succ(s)}} until W 2010 Stephen Chong, Harvard University31

Forward data flow againOut(s) for all statements sW : { all statements }repeat {Take s from W temp : fs( s′ pred(s) Out(s′))if (temp ! Out(s)) {Out(s) : tempTransfer function forstatement sW : W succ(s)}} until W 2010 Stephen Chong, Harvard University32

Which lattice to use? Available expressions P sets of expressions Meet operation is set intersection is set of all expressions Reaching definitions P sets of definitions (assignment statements) Meet operation is set union is empty set Monotonic transfer function fs is defined based ongen and kill sets. 2010 Stephen Chong, Harvard University33

Distributive data flow problems If f is monotonic, then we havef(x y) f(x) f(y) If f is distributive then we havef(x y) f(x) f(y) 2010 Stephen Chong, Harvard University34

Benefit of distributivity Joins lose no informationfghk k(h(f( ) g( ))) k(h(f( )) h(g( ))) k(h(f( ))) k(h(g( )))) 2010 Stephen Chong, Harvard University35

Accuracy of data flow analysis Ideally we would like to compute the meet over allpaths (MOP) solution: Let fs be the transfer function for statement s If p is a path s1, ,sn, let fp fsn;.fs1 Let paths(s) be the set of paths from the entry to s MOP(s) p paths(s) fp( ) If the transfer functions are distributive, then solvingusing the data flow equations in the standard wayproduces the MOP solution 2010 Stephen Chong, Harvard University36

What problems are distributive? Analyses of how the program computes E.g., Live variables Available expressions Reaching definitions Very busy expressions All Gen/Kill problems are distributive 2010 Stephen Chong, Harvard University37

Non-distributive example Constant propagation 1234.x : 2;x : 1;y : 1;y : 2; z : x y In general, analysis of what the program computes isnot distributive Thm: MOP for In(s) will always be iterative dataflowsolution 2010 Stephen Chong, Harvard University38

Practical implementation Data flow facts are assertions that are true orfalse at a program point Can represent set of facts as bit vector Fact i represented by bit i Intersection bitwise and, union bitwise or, etc “Only” a constant factor speedup But very useful in practice 2010 Stephen Chong, Harvard University39

Basic blocks A basic block is a sequence of statements suchthat No branches to any statement except the first No statement in the block branches except the last In practical data flow implementations Compute Gen/Kill for each basic block Compose transfer functions Store only In/Out for each basic block Typical basic block is about 5 statements 2010 Stephen Chong, Harvard University40