Data-flow analysis

icon
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, is the transfer function of the block . It works on the entry state , yielding the exit state . The join operation combines the exit states of the predecessors of , yielding the entry state of .

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.

This page was last edited on 16 February 2018, at 02:38.
Reference: https://en.wikipedia.org/wiki/Flow_analysis under CC BY-SA license.

Related Topics


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Recently Viewed