Dataflow analysis
Part of a series on 
Software development 

Core activities

Paradigms and models

Supporting disciplines 
Standards and bodies of knowledge 
Outlines 

Dataflow analysis is a technique for gathering information about the possible set of values calculated at various points in a computer program. A program's controlflow graph (CFG) is used to determine those parts of a program to which a particular value assigned to a variable might propagate. The information gathered is often used by compilers when optimizing a program. A canonical example of a dataflow analysis is reaching definitions.
A simple way to perform dataflow analysis of programs is to set up dataflow equations for each node of the controlflow graph and solve them by repeatedly calculating the output from the input locally at each node until the whole system stabilizes, i.e., it reaches a fixpoint. This general approach, also known as Kildall's method, was developed by Gary Kildall while teaching at the Naval Postgraduate School.^{[1]}^{[2]}^{[3]}^{[4]}
Basic principles
Dataflow analysis is the process of collecting information about the way the variables are defined and used in the program. It attempts to obtain particular information at each point in a procedure. Usually, it is enough to obtain this information at the boundaries of basic blocks, since from that it is easy to compute the information at points in the basic block. In forward flow analysis, the exit state of a block is a function of the block's entry state. This function is the composition of the effects of the statements in the block. The entry state of a block is a function of the exit states of its predecessors. This yields a set of dataflow equations:
For each block b:
 $out_{b}=trans_{b}(in_{b})$
 $in_{b}=join_{p\in pred_{b}}(out_{p})$
In this, $trans_{b}$ is the transfer function of the block $b$. It works on the entry state $in_{b}$, yielding the exit state $out_{b}$. The join operation $join$ combines the exit states of the predecessors $p\in pred_{b}$ of $b$, yielding the entry state of $b$.
After solving this set of equations, the entry and/or exit states of the blocks can be used to derive properties of the program at the block boundaries. The transfer function of each statement separately can be applied to get information at a point inside a basic block.
Each particular type of dataflow analysis has its own specific transfer function and join operation. Some dataflow problems require backward flow analysis. This follows the same plan, except that the transfer function is applied to the exit state yielding the entry state, and the join operation works on the entry states of the successors to yield the exit state.
The entry point (in forward flow) plays an important role: Since it has no predecessors, its entry state is well defined at the start of the analysis. For instance, the set of local variables with known values is empty. If the controlflow graph does not contain cycles (there were no explicit or implicit loops in the procedure) solving the equations is straightforward. The controlflow graph can then be topologically sorted; running in the order of this sort, the entry states can be computed at the start of each block, since all predecessors of that block have already been processed, so their exit states are available. If the controlflow graph does contain cycles, a more advanced algorithm is required.
An iterative algorithm
The most common way of solving the dataflow equations is by using an iterative algorithm. It starts with an approximation of the instate of each block. The outstates are then computed by applying the transfer functions on the instates. From these, the instates are updated by applying the join operations. The latter two steps are repeated until we reach the socalled fixpoint: the situation in which the instates (and the outstates in consequence) do not change.
A basic algorithm for solving dataflow equations is the roundrobin iterative algorithm:
 for i ← 1 to N
 initialize node i
 while (sets are still changing)
 for i ← 1 to N
 recompute sets at node i
 for i ← 1 to N
Convergence
To be usable, the iterative approach should actually reach a fixpoint. This can be guaranteed by imposing constraints on the combination of the value domain of the states, the transfer functions and the join operation.
The value domain should be a partial order with finite height (i.e., there are no infinite ascending chains $x_{1}$ < $x_{2}$ < ...). The combination of the transfer function and the join operation should be monotonic with respect to this partial order. Monotonicity ensures that on each iteration the value will either stay the same or will grow larger, while finite height ensures that it cannot grow indefinitely. Thus we will ultimately reach a situation where T(x) = x for all x, which is the fixpoint.
The work list approach
It is easy to improve on the algorithm above by noticing that the instate of a block will not change if the outstates of its predecessors don't change. Therefore, we introduce a work list: a list of blocks that still need to be processed. Whenever the outstate of a block changes, we add its successors to the work list. In each iteration, a block is removed from the work list. Its outstate is computed. If the outstate changed, the block's successors are added to the work list. For efficiency, a block should not be in the work list more than once.
The algorithm is started by putting informationgenerating blocks in the work list. It terminates when the work list is empty.
Ordering
The efficiency of iteratively solving dataflow equations is influenced by the order at which local nodes are visited.^{[5]} Furthermore, it depends on whether the dataflow equations are used for forward or backward dataflow analysis over the CFG. Intuitively, in a forward flow problem, it would be fastest if all predecessors of a block have been processed before the block itself, since then the iteration will use the latest information. In the absence of loops it is possible to order the blocks in such a way that the correct outstates are computed by processing each block only once.
In the following, a few iteration orders for solving dataflow equations are discussed (a related concept to iteration order of a CFG is tree traversal of a tree).
 Random order  This iteration order is not aware whether the dataflow equations solve a forward or backward dataflow problem. Therefore, the performance is relatively poor compared to specialized iteration orders.
 Postorder  This is a typical iteration order for backward dataflow problems. In postorder iteration, a node is visited after all its successor nodes have been visited. Typically, the postorder iteration is implemented with the depthfirst strategy.
 Reverse postorder  This is a typical iteration order for forward dataflow problems. In reversepostorder iteration, a node is visited before any of its successor nodes has been visited, except when the successor is reached by a back edge. (Note that reverse postorder is not the same as preorder.)
Initialization
The initial value of the instates is important to obtain correct and accurate results. If the results are used for compiler optimizations, they should provide conservative information, i.e. when applying the information, the program should not change semantics. The iteration of the fixpoint algorithm will take the values in the direction of the maximum element. Initializing all blocks with the maximum element is therefore not useful. At least one block starts in a state with a value less than the maximum. The details depend on the dataflow problem. If the minimum element represents totally conservative information, the results can be used safely even during the dataflow iteration. If it represents the most accurate information, fixpoint should be reached before the results can be applied.
Examples
The following are examples of properties of computer programs that can be calculated by dataflow analysis. Note that the properties calculated by dataflow analysis are typically only approximations of the real properties. This is because dataflow analysis operates on the syntactical structure of the CFG without simulating the exact control flow of the program. However, to be still useful in practice, a dataflow analysis algorithm is typically designed to calculate an upper respectively lower approximation of the real program properties.
Forward analysis
The reaching definition analysis calculates for each program point the set of definitions that may potentially reach this program point.
if b == 4 then a = 5; else a = 3; endif if a < 4 then ...  The reaching definition of variable 
Backward analysis
The live variable analysis calculates for each program point the variables that may be potentially read afterwards before their next write update. The result is typically used by dead code elimination to remove statements that assign to a variable whose value is not used afterwards.
The instate of a block is the set of variables that are live at the start of it. It initially contains all variables live (contained) in the block, before the transfer function is applied and the actual contained values are computed. The transfer function of a statement is applied by killing the variables that are written within this block (remove them from the set of live variables). The outstate of a block is the set of variables that are live at the end of the block and is computed by the union of the block's successors' instates.
Initial code:
b1: a = 3; b = 5; d = 4; x = 100; if a > b then b2: c = a + b; d = 2; b3: endif c = 4; return b * d + c;

Backward analysis:
// in: {} b1: a = 3; b = 5; d = 4; x = 100; //x is never being used later thus not in the out set {a,b,d} if a > b then // out: {a,b,d} //union of all (in) successors of b1 => b2: {a,b}, and b3:{b,d} // in: {a,b} b2: c = a + b; d = 2; // out: {b,d} // in: {b,d} b3: endif c = 4; return b * d + c; // out:{}

The instate of b3 only contains b and d, since c has been written. The outstate of b1 is the union of the instates of b2 and b3. The definition of c in b2 can be removed, since c is not live immediately after the statement.
Solving the dataflow equations starts with initializing all instates and outstates to the empty set. The work list is initialized by inserting the exit point (b3) in the work list (typical for backward flow). Its computed instate differs from the previous one, so its predecessors b1 and b2 are inserted and the process continues. The progress is summarized in the table below.
processing  outstate  old instate  new instate  work list 

b3  {}  {}  {b,d}  (b1,b2) 
b1  {b,d}  {}  {}  (b2) 
b2  {b,d}  {}  {a,b}  (b1) 
b1  {a,b,d}  {}  {}  () 
Note that b1 was entered in the list before b2, which forced processing b1 twice (b1 was reentered as predecessor of b2). Inserting b2 before b1 would have allowed earlier completion.
Initializing with the empty set is an optimistic initialization: all variables start out as dead. Note that the outstates cannot shrink from one iteration to the next, although the outstate can be smaller than the instate. This can be seen from the fact that after the first iteration the outstate can only change by a change of the instate. Since the instate starts as the empty set, it can only grow in further iterations.
Other approaches
In 2002, Markus Mohnen described a new method of dataflow analysis that does not require the explicit construction of a dataflow graph,^{[6]} instead relying on abstract interpretation of the program and keeping a working set of program counters. At each conditional branch, both targets are added to the working set. Each path is followed for as many instructions as possible (until end of program or until it has looped with no changes), and then removed from the set and the next program counter retrieved.
A combination of control flow analysis and data flow analysis has shown to be useful and complementary in identifying cohesive source code regions implementing functionalities of a system (e.g., features, requirements or use cases).^{[7]}
Special classes of problems
There are a variety of special classes of dataflow problems which have efficient or general solutions.
Bit vector problems
The examples above are problems in which the dataflow value is a set, e.g. the set of reaching definitions (Using a bit for a definition position in the program), or the set of live variables. These sets can be represented efficiently as bit vectors, in which each bit represents set membership of one particular element. Using this representation, the join and transfer functions can be implemented as bitwise logical operations. The join operation is typically union or intersection, implemented by bitwise logical or and logical and. The transfer function for each block can be decomposed in socalled gen and kill sets.
As an example, in livevariable analysis, the join operation is union. The kill set is the set of variables that are written in a block, whereas the gen set is the set of variables that are read without being written first. The dataflow equations become
 $out_{b}=\bigcup _{s\in succ_{b}}in_{s}$
 $in_{b}=(out_{b}kill_{b})\cup gen_{b}$
In logical operations, this reads as
out(b) = 0 for s in succ(b) out(b) = out(b) or in(s) in(b) = (out(b) and not kill(b)) or gen(b)
Dataflow problems which have sets of dataflow values which can be represented as bit vectors are called bit vector problems, genkill problems, or locally separable problems.^{[8]} Such problems have generic polynomialtime solutions.^{[9]}
In addition to the reaching definitions and live variables problems mentioned above, the following problems are instances of bitvector problems:^{[9]}
 Available expressions
 Very busy expressions
 Usedefinition chains
IFDS problems
Interprocedural, finite, distributive, subset problems or IFDS problems are another class of problem with a generic polynomialtime solution.^{[8]}^{[10]} Solutions to these problems provide contextsensitive and flowsensitive dataflow analyses.
There are several implementations of IFDSbased dataflow analyses for popular programming languages, e.g. in the Soot^{[11]} and WALA^{[12]} frameworks for Java analysis.
Every bitvector problem is also an IFDS problem, but there are several significant IFDS problems that are not bitvector problems, including trulylive variables and possiblyuninitialized variables.
Sensitivities
Dataflow analysis is typically pathinsensitive, though it is possible to define dataflow equations that yield a pathsensitive analysis.
 A flowsensitive analysis takes into account the order of statements in a program. For example, a flowinsensitive pointer alias analysis may determine "variables x and y may refer to the same location", while a flowsensitive analysis may determine "after statement 20, variables x and y may refer to the same location".
 A pathsensitive analysis computes different pieces of analysis information dependent on the predicates at conditional branch instructions. For instance, if a branch contains a condition
x>0
, then on the fallthrough path, the analysis would assume thatx<=0
and on the target of the branch it would assume that indeedx>0
holds.  A contextsensitive analysis is an interprocedural analysis that considers the calling context when analyzing the target of a function call. In particular, using context information one can jump back to the original call site, whereas without that information, the analysis information has to be propagated back to all possible call sites, potentially losing precision.
List of dataflow analyses
 Reaching definitions
 Liveness analysis
 Definite assignment analysis
 Available expression
 Constant propagation
See also
References
 ^ Kildall, Gary Arlen (May 1972). Global expression optimization during compilation (Ph.D. dissertation). Seattle, Washington, USA: University of Washington, Computer Science Group. Thesis No. 20506, Technical Report No. 720602.
 ^ Kildall, Gary Arlen (19731001). "A Unified Approach to Global Program Optimization" (PDF). Proceedings of the 1st Annual ACM SIGACTSIGPLAN Symposium on Principles of Programming Languages (POPL). POPL '73. Boston, Massachusetts, USA: 194–206. doi:10.1145/512927.512945. hdl:10945/42162. S2CID 10219496. Archived (PDF) from the original on 20170629. Retrieved 20061120. ([1])
 ^ Rüthing, Oliver; Knoop, Jens; Steffen, Bernhard (20030731) [1999]. "Optimization: Detecting Equalities of Variables, Combining Efficiency with Precision". In Cortesi, Agostino; Filé, Gilberto (eds.). Static Analysis: 6th International Symposium, SAS'99, Venice, Italy, September 22–24, 1999, Proceedings. Lecture Notes in Computer Science. Vol. 1694 (illustrated ed.). Springer. pp. 232–247 [233]. ISBN 9783540664598. ISSN 03029743.
 ^ Huitt, Robert; Eubanks, Gordon; Rolander, Thomas "Tom" Alan; Laws, David; Michel, Howard E.; Halla, Brian; Wharton, John Harrison; Berg, Brian; Su, Weilian; Kildall, Scott; Kampe, Bill (20140425). Laws, David (ed.). "Legacy of Gary Kildall: The CP/M IEEE Milestone Dedication" (PDF) (video transscription). Pacific Grove, California, USA: Computer History Museum. CHM Reference number: X7170.2014. Retrieved 20200119.
[…] Eubanks: […] Gary […] was an inventor, he was inventive, he did things. His Ph.D. thesis proved that global flow analysis converges. […] This is a fundamental idea in computer science. […] I took a […] summer course once from a guy named Dhamdhere […] they talked about optimization for like a week and then they put a slide up and said, "Kildall's Method," this is the real story. […] that's something that no one ever thinks about. […]
[2][3] (33 pages)  ^ Cooper, Keith D.; Harvey, Timothy J.; Kennedy, Ken (20040326) [November 2002]. "Iterative DataFlow Analysis, Revisited" (PDF). PLDI 2003. ACM. TR04432. Retrieved 20170701.^{[permanent dead link]}
 ^ Mohnen, Markus (2002). A GraphFree Approach to DataFlow Analysis. Lecture Notes in Computer Science. Vol. 2304. pp. 185–213. doi:10.1007/3540459375_6. ISBN 9783540433699.
 ^ Kuang, Hongyu; Mäder, Patrick; Hu, Hao; Ghabi, Achraf; Huang, LiGuo; Lü, Jian; Egyed, Alexander (20151101). "Can method data dependencies support the assessment of traceability between requirements and source code?". Journal of Software: Evolution and Process. 27 (11): 838–866. doi:10.1002/smr.1736. ISSN 20477481. S2CID 39846438.
 ^ ^{a} ^{b} Reps, Thomas; Horwitz, Susan; Sagiv, Mooly (1995). "Precise interprocedural dataflow analysis via graph reachability". Proceedings of the 22nd ACM SIGPLANSIGACT Symposium on Principles of Programming Languages  POPL '95. New York, New York, USA: ACM Press: 1, 49–61. doi:10.1145/199448.199462. ISBN 0897916921. S2CID 5955667.
 ^ ^{a} ^{b} Knoop, Jens; Steffen, Bernhard; Vollmer, Jürgen (19960501). "Parallelism for free: efficient and optimal bitvector analyses for parallel programs". ACM Transactions on Programming Languages and Systems. 18 (3): 268–299. doi:10.1145/229542.229545. ISSN 01640925. S2CID 14123780.
 ^ Naeem, Nomair A.; Lhoták, Ondřej; Rodriguez, Jonathan (2010), "Practical Extensions to the IFDS Algorithm", Compiler Construction, Lecture Notes in Computer Science, vol. 6011, Berlin / Heidelberg, Germany: Springer Verlag, pp. 124–144, doi:10.1007/9783642119705_8, ISBN 9783642119699
 ^ Bodden, Eric (2012). "Interprocedural dataflow analysis with IFDS/IDE and Soot". Proceedings of the ACM SIGPLAN International Workshop on State of the Art in Java Program Analysis  SOAP '12. New York, New York, USA: ACM Press: 3–8. doi:10.1145/2259051.2259052. ISBN 9781450314909. S2CID 3020481.
 ^ Rapoport, Marianna; Lhoták, Ondřej; Tip, Frank (2015). Precise Data Flow Analysis in the Presence of Correlated Method Calls. International Static Analysis Symposium. Lecture Notes in Computer Science. Vol. 9291. Berlin / Heidelberg, Germany: Springer Verlag. pp. 54–71. doi:10.1007/9783662482889_4. ISBN 9783662482872.
Further reading
 Cooper, Keith D.; Torczon, Linda (2003) [20020101]. Engineering a Compiler. Morgan Kaufmann. ISBN 9781558606982.
 Muchnick, Steven Stanley (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers. ISBN 9781558603202.
 Hecht, Matthew S. (19770503). Flow Analysis of Computer Programs. Programming Languages Series. Vol. 5. Elsevier NorthHolland Inc. ISBN 9780444002105.
 Khedker, Uday P.; Sanyal, Amitabha; Karkare, Bageshri (2009). Data Flow Analysis: Theory and Practice. CRC Press (Taylor and Francis Group).
 Nielson, Flemming; Nielson, Hanne Riis; Hankin, Chris (2005). Principles of Program Analysis. Springer Science+Business Media.