Thomas A. Alspaugh
Data Flow

(Under Construction)

Control flow graph
A graph whose nodes are a program's statements and whose edges show how the program can move from statement to statement.
def
A def of variable x is an assignment of a value to a x.
use
A use of a value v of variable x is a use of v in a condition of a branch or loop, to compute a value that is assigned to a variable, or as output from the program. Every use u is associated with one or more defs d that could have assigned v to x, in which case u is said to be a use of d.
Data flow graph
A graph whose nodes are a program's statements, and whose edges connect each def d to every use u of d.
control flow

Figure 1. Control flow graph of m()

data flow

Figure 2. Control and data flow graph of m()

Here is an example program (that does nothing in particular) whose control flow and data flow graphs are shown in the figures. 

 1  int m(int x, int y) {
 2    while (x > 10) {
 3      x -= 10;  // x = x - 10;
 4      if (x == 10) {
 5        break;
 6      }
 7    }
 8    x = square(x);
 9    if (y < 20 && x%2 == 0) {
10      y += 20;  // y = y + 20;
11    }
12    else {
13      y -= 20;  // y = y - 20;
14    }
15    return 2*x + y;
16  }

Note that not all the lines of code in the example program are present in the graphs, only the lines that contain defs and/or uses. The line numbers for such lines are in bold in the program listing. Thus for example line 4 is included in the graph, since it contains a use of x; but lines 5, 6, and 6 are not because they contain neither defs nor uses.

Each node in the graph comprises one or more defs (its def set) and uses (its uses set), determined by the program code for that node. In addition, upstream defs flow into the node (the node's in set) from every control flow graph edge leading into the node, and may be used in the node's uses. The node's defs are said to kill all defs of the same variable flowing in, and the killed defs are the node's kill set. In the example, line 3 has a def of x, and so line 3 kills all defs of x that flow into it. Finally, defs flow out of the node (the node's out set) along every control flow graph edge leading out of the node. The out set consists of the node's in set plus its def set, minus its kill set: all the defs flowing in that it does not kill, plus its own defs.

For example, the value given to x in the def of line 1 may flow to the use of x in the condition in line 2, and thence to the rhs (right-hand side) expression of line 3, x -= 10 being shorthand for x = x - 10. However, line 3 is also a def of x, so it kills the value from the line 1 def and that def flows no further along this path. If the condition (x > 10) is false, then the loop isn't executed and the line 1 def propagates on to the use of x in the rhs of line 8. Because line 8 is also a def of x, it kills the line 1 def of x and that def flows no further along this path. There are no other paths from line 1, so this completes the flow of the def of x in line 1 to its uses. In all, this def has three uses (2, 3, 8).

Figure 2 confirms this and also shows that the use of x in line 2 is a possible use of two defs of x, the ones in lines 1 (if that def gives x a value of 10 or less) and in line 3 (if line 1 gives x a value 11 or greater).

flip bgunflip