Data-flow analysis

dataflow analysis

A simple way to perform dataflow analysis (DFA) of programs is to set up dataflow equations for each node of the Control_flow_graph (CFG) and solve them by repeatedly calculating the output from the input locally at each node untill the whole system stabilizes, i.e. it reaches a fixpoint. To guarantee terminiation it is required that the data flow equations form a fixed-point data-flow analysis, i.e. the local updates by the equations are Monotone.

An iterative algortihm

The fixpoint of the dataflow equations can be calculated using the round-robin iterative algorithm:
${\texttt {for}}\ i\ \leftarrow \ 1\ {\texttt {to}}\ N$
    ${\mathit {initialize\ node}}\ i$

${\texttt {while}}\ ({\mathit {sets\ are\ still\ changing}})$
    ${\texttt {for}}\ i\ \leftarrow \ 1\ {\texttt {to}}\ N$
        ${\mathit {recompute\ sets\ at\ node}}\ i$

The order matters

The efficiency of iteratively solving data-flow equations is influenced by the order at which local nodes are visited. For the above round-robin iterative algorithm it depends in which order nodes are selected from the set of nodes. Furthermore, it depends, whether the data-flow equations are used for forward or backward data-flow analysis over the CFG. In the following, a few iteration orders for solving data-flow equations are discussed.

random order This iteration order is not aware whether the DFA solves a forward or backward data-flow problem. Therefore, the performance is relatively poor compared to specialized iteration orders.

postorder This is a typical iteration order for forward data-flow problems. In postorder iteration a node is visited after all its successor nodes have been visited.

reverse-postorder This is a typical iteration order for backward data-flow problems. In reverse-postorder iteration a node is visited before all its successor nodes have been visited. A more natureal name for reverse-postorder iteration would be "preorder iteration", but this would be confusing with the mathematical definition of Preorder.