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.

Java Click To expand
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.


JaVaScreenshot Previous    Next
Comments