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 until the whole system stabilizes, i.e. it
reaches a fixpoint. To guarantee termination 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 algorithm
The fixpoint of the dataflow equations can be calculated using the
round-robin iterative algorithm:
<math>\texttt{for}\ i\ \leftarrow\ 1\ \texttt{to}\ N<math>
<math>\mathit{initialize\ node}\ i<math>
<math>\texttt{while}\ (\mathit{sets\ are\ still\ changing})<math>
<math>\texttt{for}\ i\ \leftarrow\ 1\ \texttt{to}\ N<math>
<math>\mathit{recompute\ sets\ at\ node}\ i<math>
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.
Typically, the postorder iteration is implemented with the depth-first strategy.
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 natural name for reverse-postorder iteration would be "preorder iteration", but this
would be confusing with the mathematical definition of preorder.
