Models of Programs

MODELS OF PROGRAMS:

Data Flow Graphs:

A data flow graph is a model of a program with no conditionals. In a high-level programming language, a code segment with no conditionals—more precisely, with only one entry and exit point is known as a basic block. Figure 2.14 shows a simple basic block. As the C code is executed, we would enter this basic block at the beginning and execute all the statements.

w = a+b; 

x = a-c; 

y = x+d; 

x = a+c; 

z = y+e;

Fig 2.14 A basic block in C.

w = a+b; 

x = a-c; 

y = x1+d; 

x2= a+c; 

z = y+e;

Fig 2.14 The basic block in single-assignment form.

Before we are able to draw the data flow graph for this code we need to modify it slightly. There are two assignments to the variable x—it appears twice on the left side of an assignment. We need to rewrite the code in single-assignment form, in which a variable appears only once on the left side.

Since our specification is C code, we assume that the statements are executed sequentially, so that any use of a variable refers to its latest assigned value. In this case, x is not reused in this block (presumably it is used elsewhere), so we just have to eliminate the multiple assignment to x. The result is shown in Figure 2.14, where we have used the names x1 and x2 to distinguish the separate uses of x.

The single-assignment form is important because it allows us to identify a unique location in the code where each named location is computed. As an introduction to the data flow graph, we use two types of nodes in the graph round nodes denote operators and square nodes represent values.

The value nodes may be either inputs to the basic block, such as a and b, or variables assigned to within the block, such as w and x1.

The data flow graph for our single-assignment code is shown in Figure 2.15.The single-assignment form means that the data flow graph is acyclic—if we assigned to x multiple times, then the second assignment would form a cycle in the graph including x and the operators used to compute x.