Previous    Next

REDUCIBLE FLOW GRAPHS

A reducible flow graph is one in which the dictionary definition of loop corresponds more closely to the technical definition; but let us develop a more precise definition. Image 18.2a does not contain a loop; either node in the strongly connected component (2, 3) can be reached without going through the other.

Image 18.2: None of these contains a loop. Dotted lines indicate reduction of graph (c) by deleting edges and collapsing nodes.

Image 18.2c contains the same pattern of nodes 1, 2, 3; this becomes more clear if we repeatedly delete edges and collapse together pairs of nodes (x, y), where x is the only predecessor of y. That is: Delete 6 → 9, 5 → 4, collapse (7, 9), (3, 7), (7, 8), (5, 6), (1, 5), (1, 4); and we obtain Image 18.2a. An irreducible flow graph is one in which - after collapsing nodes and deleting edges - we can find a subgraph like Image 18.2a. A reducible flow graph is one that cannot be collapsed to contain such a subgraph. Without such subgraphs, then any cycle of nodes does have a unique header node. Common control-flow constructs such as if-then, if-then-else, while-do, repeat-until, for, and break (even multilevel break) can only generate reducible flow graphs. Thus, the control-flow graph for a MiniJava or Java function, or a C function without goto, will always be reducible. The following program corresponds to the flow graph in Image 18.1e, assuming MiniJava were augmented with repeat-until loops:

``` function isPrime(n: int) : int =
(i := 2;
repeat j := 2;
repeat if i*j=n
then return 0
else j := j+1
until j=n;
i := i+1
until i=n;
return 1)
```

In a functional language, loops are generally expressed using tail-recursive function calls. The isPrime program might be written as:

``` function isPrime(n: int) : int =
0 tryI(n,2)
function tryI(n: int, i: int) : int =
1 tryJ(n,i,2)
function tryJ(n: int, i: int, j: int) : int =
2 if i*j=n
3 then 0
4 else nextJ(n,i,j+1)
function nextJ(n: int, i: int, j: int) : int =
5 if j=n
then nextI(n,i+1)
else tryJ(n,i,j)
function nextI(n: int, i: int) : int =
6 if i=n
then 1
else tryI(n,i)
```

where the numbers 1-6 show the correspondence with the flow-graph nodes of Image 18.1f. Because the programmer can arrange these functions in arbitrary ways, flow graphs produced by the tail-call structure of functional programs are sometimes irreducible. Advantages of reducible flow graphs Many dataflow analyses (presented in ) can be done very efficiently on reducible flow graphs. Instead of using fixed-point iteration ("keep executing assignments until there are no changes"), we can determine an order for computing the assignments, and calculate in advance how many assignments will be necessary - that is, there will never be a need to check to see if anything changed.

However, for the remainder of this chapter we will assume that our controlflow graphs may be reducible or irreducible.

 JaVa Previous    Next