# 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. 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.

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. This general approach was developed by Gary Kildall while teaching at the Naval Postgraduate School.

Data-flow analysis is the process of collecting information about the way the variables are used, defined 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 data-flow equations:

For each block b:

In this, ${\displaystyle trans_{b}}$ is the transfer function of the block ${\displaystyle b}$. It works on the entry state ${\displaystyle in_{b}}$, yielding the exit state ${\displaystyle out_{b}}$. The join operation ${\displaystyle join}$ combines the exit states of the predecessors ${\displaystyle p\in pred_{b}}$ of ${\displaystyle b}$, yielding the entry state of ${\displaystyle 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.

## Related Topics

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag msub invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag msub invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag msub invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mo invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag msub invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 388