Data-flow analysis

Data-flow analysis is a technique for gathering information about the possible set of values calculated at various points in a computer program. It forms the foundation for a wide variety of compiler optimizations and program verification techniques. A program's control-flow 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 data-flow analysis is reaching definitions. Other commonly used data-flow analyses include live variable analysis, available expressions, constant propagation, and very busy expressions, each serving a distinct purpose in compiler optimization passes. A simple way to perform data-flow analysis of programs is to set up data-flow equations for each node of the control-flow 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. The efficiency and precision of this process are significantly influenced by the design of the data-flow framework, including the direction of analysis (forward or backward), the domain of values, and the join operation used to merge information from multiple control paths. This general approach, also known as Kildall's method , was developed by Gary Kildall while teaching at the Naval Postgraduate School. 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 data-flow analysis has its own specific transfer function and join operation. Some data-flow 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 control-flow graph does not contain cycles (there were no explicit or implicit loops in the procedure) solving the equations is straightforward. The control-flow 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 control-flow graph does contain cycles, a more advanced algorithm is required. The value domain should be a partial order with finite height (i.e., there are no infinite ascending chains x_1 x_2 if b == 4 then a = 5; else a = 3; endif if a The reaching definition of variable at line 7 is the set of assignments at line 2 and at line 4. 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 in-state of b3 only contains b and d, since c has been written. The out-state of b1 is the union of the in-states of b2 and b3. The definition of c in b2 can be removed, since c is not live immediately after the statement. Solving the data-flow equations starts with initializing all in-states and out-states 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 in-state 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. Note that b1 was entered in the list before b2, which forced processing b1 twice (b1 was re-entered 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 out-states cannot shrink from one iteration to the next, although the out-state can be smaller than the in-state. This can be seen from the fact that after the first iteration the out-state can only change by a change of the in-state. Since the in-state starts as the empty set, it can only grow in further iterations. 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 data-flow values which can be represented as bit vectors are called bit vector problems, gen-kill problems, or locally separable problems. Such problems have generic polynomial-time solutions. In addition to the reaching definitions and live variables problems mentioned above, the following problems are instances of bitvector problems: Available expressions Very busy expressions Use-definition chains ==See also== Abstract interpretation Control flow analysis XLT86 ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1355882823 under CC BY-SA 4.0; modifications have been made.

Names in other languages