Topic 10: Dataflow Analysis - cs.princeton.edu

1 1 Topic 10: Dataflow AnalysisCOS 320 Compiling TechniquesPrinceton University Spring 2016 Lennart BeringerAnalysis and Transformationanalysis spans multiple proceduressingle-procedure- Analysis : intra-proceduralDataflow Analysis MotivationDataflow Analysis MotivationAssuming only r5 is live-out at instruction AnalysisIterative Dataflow Analysis FrameworkDefinitionsIterative Dataflow Analysis FrameworkDefinitions for Liveness AnalysisDefinitions for Liveness AnalysisRemember generic equations:r1r2r3r1r1r1r2, r3r2r3------Smart ordering: visit nodes in reverse order of , r3r2r3------Smart ordering: visit nodes in reverse order of , r1r3, r1?r1r2r3r1r1r1r2, r3r2r3------Smart ordering: visit nodes in reverse order of , r1r3, r1r3, r2r3, r2r3, r2r3, r2r3, r1r3, r1r3?r1r2r3r1r1r1r2, r3r2r3------Smart ordering: visit nodes in reverse order of , r1r3, r1r3, r2r3, r2r3, r2r3, r2r3, r1r3, r1r3--r3r3, r1::Live Variable Application 1: Register AllocationInterference Graphr1r3?

2 R2 Interference Graphr1r3r2 Live Variable Application 2: Dead Code Eliminationof the formof the formLive Variable Application 2: Dead Code Eliminationof the formof the formThis may lead to further optimization opportunities, as uses of variables in s disappear. repeat all / some Analysis / optimization passes!Reaching Definition AnalysisReaching Definition Analysis (details on next slide)Reaching definitions: definition-ID each definition point a label ( definition ID ) each variable t with a set of labels:defs(t) = the labels d associated with a defof the effects of instruction forms on gen/killd: t b op c d: t M[b] d: t f(a_1, .., a_n)Statement sGen[s]Kill[s]d: t <-b op c{d}defs(t) {d}d: t <-M[b]{d}defs(t) {d}M[a] <-b{}{}if a relopb gotol1 else gotoL2{}{}GotoL{}{}L: {}{}f(a_1, .., a_n){}{}d: t <-f(a_1.)

3 , a_n){d}defs(t)-{d}Reaching Defs: Example4: c<-c+c2: c<-17: c <-05: gotoL11: a<-53: L1: if c > a gotoL26: L2: a <-c-adefs(a) = ?defs(c) = ?Reaching Defs: Example4: c<-c+c2: c<-17: c <-05: gotoL11: a<-53: L1: if c > a gotoL26: L2: a <-c-adefs(a) = {1, 6}defs(c) = {2, 4, 7}?Reaching Defs: Example4: c<-c+c2: c<-17: c <-05: gotoL11: a<-53: L1: if c > a gotoL26: L2: a <-c-a12467defs(a) = {1, 6}defs(c) = {2, 4, 7}?Reaching Defs: Example4: c<-c+c2: c<-17: c <-05: gotoL11: a<-53: L1: if c > a gotoL26: L2: a <-c-a12467defs(a)-{1}defs(a) = {1, 6}defs(c) = {2, 4, 7}defs(c)-{2}defs(c)-{7}defs(a)-{6}defs(c)-{4}64, 72, 712, 4 Reaching Defs: Example4: c<-c+c2: c<-17: c <-05: gotoL11: a<-53: L1: if c > a gotoL26: L2: a <-c-a1246764, 72, 712, 4 Direction: FORWARD, IN/OUT initially {}?Reaching Defs: Example4: c<-c+c2: c<-17: c <-05: gotoL11: a<-53: L1: if c > a gotoL26: L2: a <-c-a1246764, 72, 712, 4{ }{1}{1}{1, 2}Reaching Defs: Example4: c<-c+c2: c<-17: c <-05: gotoL11: a<-53: L1: if c > a gotoL26: L2: a <-c-a1246764, 72, 712, 4{ }{1}{1}{1, 2}{1,2}{1, 2}{1,2}{1, 4}Reaching Defs: Example4: c<-c+c2: c<-17: c <-05: gotoL11: a<-53: L1: if c > a gotoL26: L2: a <-c-a1246764, 72, 712, 4{ }{1}{1}{1, 2}{1}{1, 2}{1,2}{1, 4}{1,4}{1, 4}{1,2}{2,6}{2,6}{6,7}Reaching Defs: Example4: c<-c+c2: c<-17: c <-05: gotoL11: a<-53: L1: if c > a gotoL26: L2: a <-c-a1246764, 72, 712, 4{ }{1}{1}{1, 2}{1,2}{1, 2}{1,2}{1, 4}{1,4}{1, 4}{1,2}{2,6}{2,6}{6,7}{ }{1}{1}{1, 2}{1,2,4}{1, 2,4}{1,2,4}{1, 4}{1,4}{1, 4}{1,2,4}{2,4,6}{2,4,6}{6,7}No change10 Reaching Definition Application 1: Constant Propagationc5 Similarly.

4 Copy propagation,replace egr1 = r2; r3 r1 + 5with r3 r2 + 5 But often register allocation canalready coalesce r1 and Definition Application 2: Constant Folding15 Common Subexpression EliminationCSEC ommon Subexpression Eliminationr1 CSEC ommon Subexpression Eliminationr1r1 CSECopy = x op yr2= x op yr3= x op yx:=66no defsof registers used by e here!eemust be computed at least once on any pathe available here!Generally, many expressions are available at any program pointDefinitionsentryr1 = x op yr2= x op yr3= x op yx:=66no defsof registers used by e here!eemust be computed at least once on any pathe available here!(iestatements generate/kill availability)Generally, many expressions are available at any program pointDefinitionsentryr1 = x op yr2= x op yr3= x op yx:=66no defsof registers used by e here!eemust be computed at least once on any pathe available here!

5 (iestatements generate/kill availability)Generally, many expressions are available at any program point Statement M[r2] = e-generates no expression (we doavailability in register here)-kills any M[ .. ] expression, ieloadsIterative Dataflow Analysis Framework (forward)Statement sGen(s)Kill(s)t b op c{b op c} exp(t)expressions containing tOK?Iterative Dataflow Analysis Framework (forward)Statement sGen(s)Kill(s)t b op c{b op c} kill(s)exp(t)t M[b]{M[b]} kill(s) exp(t)M[a] b{} fetches if a ropb gotoL1 else gotoL2{}{}GotoL{}{}L:{}{}f(a1,..,an)??t f(a1, .., an)??expressions containing texpressions of the form M[ _ ]to deal with t = b or t = cIterative Dataflow Analysis Framework (forward)Statement sGen(s)Kill(s)t b op c{b op c} kill(s)exp(t)t M[b]{M[b]} kill(s) exp(t)M[a] b{} fetches if a ropb gotoL1 else gotoL2{}{}GotoL{}{}L:{}{}f(a1.)

6 ,an){} fetches t f(a1, .., an){}exp(t) fetches expressions containing texpressions of the form M[ _ ] to deal with t = b or t = cAvailable Expression Analysis only expressions that are out-available at allpredecessors of n are in-available at n fact that sets shrinktriggers initialization of all sets to U(set of all expressions), except for IN[entry] = {}Step 1: fill in Kill[n]Node nGen[n]Kill[n]123456789 Universe Uof expressions: M[r5], M[A], M[B], r1+r2, r1+ 12, r3+r1 fetches exp(r1)exp(r2)exp(r3)exp(r5)no singleton registers (r4 etc)no Boolean exprs(r3>r2)Step 2: fill in Gen[n]Node nGen[n]Kill[n]1r1+r2, r1+ 12, r3+r1 2r1+r23r3+r14-5-6r1+r2, r1+ 12, r3+r1 7-8M[r5]9M[r5], M[A],M[B]Universe Uof expressions: M[r5], M[A], M[B], r1+r2, r1+ 12, r3+r1 fetches exp(r1)exp(r2)exp(r3)exp(r5)no singleton registers (r4 etc)no Boolean exprs(r3>r2)ExampleNode nGen[n]Kill[n]1M[A]r1+r2, r1+ 12, r3+r1 2M[B]r1+r23r1+r2r3+r14r3+r1-5--6-r1+r2, r1+ 12, r3+r1 7r1+r2-8r1+r2M[r5]9-M[r5], M[A],M[B]Universe Uof expressions: M[r5], M[A], M[B], r1+r2, r1+ 12, r3+r1 fetches exp(r1)exp(r2)exp(r3)exp(r5)no singleton registers (r4 etc)no Boolean exprs(r3>r2)Example: hash expressionsnGen[n]Kill[n]1M[A]r1+r2, r1+ 12, r3+r1 2M[B]r1+r23r1+r2r3+r14r3+r1-5--6-r1+r2, r1+ 12, r3+r1 7r1+r2-8r1+r2M[r5]9-M[r5], M[A],M[B]nGen[n]Kill[n]151, 2, 3 26131343-5--6-1, 2, 371-8149-4,5, 6r1+r21r1+122r3+r13M[r5]4M[A]5M[B]6 Step 3: DF iterationFORWARDU= {1.}

7 , 6}InOutIn[n]Out[n]{}UUUUUUUUUUUUUUUUU::: ExampleFORWARDU= {1, .., 6}InOutIn[n]Out[n]{}U{}5UU55,6UU5, 61, 5, 6UU1, 5, 61, 3, 5, 6UU1, 3, 5, 61, 3, 5, 6UU1, 3, 5, 65, 6UU5, 61, 5, 6UU1, 5, 61, 5, 6UU1, 5, 61 ExampleIn[n]Out[n]{}555, 65, 61, 5, 61, 5, 61, 3, 5, 61, 3, 5, 61, 3, 5, 61, 3, 5, 65, 65, 61, 5, 61, 5, 61, 5, 61, 5, 61M[A]M[A], M[B]r1+r2, M[A], M[B]r1+r2, r3+r1, M[A], M[B]r1+r2, r3+r1, M[A], M[B]M[A], M[B]r1+r2, M[A], M[B]r1+r2, M[A], M[B]r1+r2r1+r2, M[A], M[B]r1+r21r1+122r3+r13M[r5]4M[A]5M[B]6 Common Subexpression Elimination (CSE)Note that the same w is used for all occurrences of x op y:s1: v = x op y s2: u= x op y s: t= x op y s1 : w= x op y v= ws2 : w= x op yu=ws: t= wCan be seen as further Analysis : reaching expressions CSE Exampleww; r3 = w; r4 = wwCopy PropagationCopy Propagationr4 = r99 + r1M[r99] = r4 SetsBasic Block Level AnalysisdefsusesBasic Block Level AnalysisBasic Block Level AnalysisIN[pn]=OUT[pn]=Reducible Flow Graphs RevisitedNot a backedge destdoes not dominate srcreducibleirreducibleReducible Flow Graphs Structured ProgramsSubgraph H of CFG, and nodes u H, v H such that all edges into H go to u, all edges out of H go to vReaching Definitions for Structured ProgramspnlrRemember:Conservative ApproximationsLimitation of Dataflow AnalysisOther example: There are more sophisticated program analyses that can (conservatively) approximate the ranges/sets of possible values fit into a general framework of transfer functions and inference by iterated updates until a fixed point is reached.

8 Abstract interpretation are very useful for eliminating dead branches, showing thatarray accesses are always within range,..But eventually, they run into the same theoretical limitationsImplementation of data flow info (sets of variables, expressions, labels, ..) linked lists, maybe ordered by variable name suitable for sparse analyses (typically, only few variables are live at a program point .. ) bit-vectors of length N, if set is of size < 2^N union, intersection implemented by bit-wise OR/AND suitable for dense up iterations: worklist algorithms instead of traversing all nodes in each iteration, just revisit those nodes for which IN/OUT might change FORWARD: after visiting a node, if OUT[n] was modified, ensure that all successors of n are in the queue (insert if necessary) BACKWARD: similarly, add predecessors of n if IN[n] has changed3.

9 Single-information-at-a-time versus exhaustive information: is the (costly-to-compute) expression e available here versus give me all available expressions, at all program points Use-defchains, def-use chains many optimizations exploit def-use relationship avoid recalculation by introducing a data structureUse-defchain: for each use of a variable store the set of reaching definitionsDef-use chain: for each definition d of a variable store all its uses Generalization: static single-assignment (SSA) form see future = ..x = ..y = .. = .. = .. = .. , i3xi5i1, i3yi6i5 VarDefUsesxi1i2, i4, i5xi3i4, i5yi5I6