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.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