Data-flow Analysis - An Iterative Algorithm

An Iterative Algorithm

The most common way of solving the data-flow equations is by using an iterative algorithm. It starts with an approximation of the in-state of each block. The out-states are then computed by applying the transfer functions on the in-states. From these, the in-states are updated by applying the join operations. The latter two steps are repeated until we reach the so-called fixpoint: the situation in which the in-states (and the out-states in consequence) do not change.

A basic algorithm for solving data-flow equations is the round-robin iterative algorithm:

for i ← 1 to N

initialize node i

while (sets are still changing)

for i ← 1 to N

recompute sets at node i