Previous Next |

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 |