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.