# Iterative algorithm for a forward data-flow problem

**Overview :**

The purpose of this article is to tell you about an iterative algorithm for forward data-flow problem. Before starting, you should know some terminology related to data flow analysis.

**Terminologies for Iterative algorithm :**

Here, we will discuss terminologies for iterative algorithm as follows.

Attention reader! Don’t stop learning now. Practice GATE exam well before the actual exam with the subject-wise and overall quizzes available in **GATE Test Series Course**.

Learn all **GATE CS concepts with Free Live Classes** on our youtube channel.

**Data flow analysis –**

It is defined as a technique in which set of values calculated at various points in a computer program for collecting information.

**Control Flow Graph (CFG) –**

It is used to determine those parts of a program to which a particular value assigned to a variable might propagate.

**Naive approach (Kildall’s method) –**

The easiest way to perform data-flow analysis of programs is to set up data-flow equations for each node of the control-flow graph and in this approach until the whole system stabilizes such that it reaches a fix point so, solve them by repeatedly calculating the output from the input locally at each node.

**An iterative algorithm –**

An iterative algorithm is the most common way to solve the data flow analysis equations. In this algorithm, we particularly have two states first one is in-state and the other one is out-state. The algorithm starts with an approximation of the in-state of each block and then computed by applying the transfer functions on the in-states. The in-states is updated by applying the join operations. The latter two steps are repeated until we reach the fix point: the situation in which the in-states do not change.

**The efficiency of the above algorithm –**

The efficiency of this algorithm for solving the data-flow equations is influenced by the order in which local nodes are visited, and also it depends on whether the data-flow equations are used for forwarding or backward data-flow analysis over the Control Flow Graph.

**Iteration orders for solving data flow equations :**

A few iteration orders for solving data-flow equations are discussed below as follows.

**Random order –**

In this iteration, order is not aware whether the data-flow equations solve a forward or backward data-flow problem. And hence, the performance is relatively poor compared to specialized iteration orders.

**Post order –**

This iteration order for backward data-flow problems. A node is visited after all its successor nodes have been visited, and implemented with the depth-first strategy.

**Reverse post order –**

This iteration order for forwarding data-flow problems. The node is visited before any of its successor nodes has been visited, except when the successor is reached by a back edge.

**Forward data analysis –**

Consider an arbitrary point ‘p’ In a forward analysis, we are reasoning about facts up to ‘p’, considering only the predecessors of the node at ‘p’. In a backward analysis, we are reasoning about facts from ‘p’ onward, considering only the successors.

**Example –**

line 1: if b==4 then line 2: a = 5; line 3: else line 4: a = 3; line 5: endif line 6: line 7: if a < 4 then ...// rest of the code

**Example descriptions :**

From the above example, we can observe that the reaching definition of variable at line 7 is the set of assignments a = 5 at line 2 and a = 3 at line 4.