Editing Data-flow analysis (section)

=== Ordering ===
The efficiency of iteratively solving data-flow equations is influenced by the order at which local nodes are visited.<ref name="Cooper_2004"/> Furthermore, it depends on whether the data-flow equations are used for forward or backward data-flow analysis over the CFG. Intuitively, in a forward flow problem, it would be fastest if all predecessors of a block have been processed before the block itself, since then the iteration will use the latest information. In the absence of loops it is possible to order the blocks in such a way that the correct out-states are computed by processing each block only once.

In the following, a few iteration orders for solving data-flow equations are discussed 
(a related concept to iteration order of a [[control-flow graph|CFG]] is [[tree traversal]] of a
[[Tree (graph theory)|tree]]).

* '''Random order''' - This iteration order is not aware whether the data-flow equations solve 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 backward 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.
* '''[[depth-first search#Vertex orderings|Reverse postorder]]''' - This is a typical iteration order for forward data-flow problems. In '''reverse-postorder iteration''', a node is visited before any of its successor nodes has been visited, except when the successor is reached by a back edge. (Note that reverse postorder is not the same as [[depth-first search#Vertex orderings|preorder]].)