COMS W4117
Compilers and Translators:
Software Verification Tools
Lecture 8: Loops in Flow Graphs
September 27, 2007

Lecture Outline

In a flow graph, a node d is a dominator of a node n if every path from ENTRY to n goes through d.
A dominator tree is a convenient way to represent dominator information. In a dominator tree, ENTRY is the root, and each node dominates only its descendants in the tree.
We can find the dominators of each node in a flow graph using an iterative data-flow analysis framework. See Alg. 9.38, p. 658.

We can perform a depth-first search to produce a depth-first ordering of the nodes of a flow graph.
Recall the definitions of preorder and postorder traversals of trees.
See Alg. 9.41, pp. 660-662 for depth-first search algorithm.
The depth-first search identifies three kinds of edges in a flow graph: advancing, retreating, and cross edges.
Note that u → v is a retreating edge if and only dfn[u] &ge dfn[v], where dfn[u] is the depth-first number of node u.

A back edge is a retreating edge whose head dominates its tail.
A flow graph is reducible if all its retreating edges in any DFST are also back edges.
Structured programming always produces programs with reducible flow graphs.
Canonical nonreducible flow graph: the "ice-cream cone".
The depth of a flow graph is the largest number of retreating edges on any cycle-free path.

A natural loop in a flow graph is a set of nodes defined by a back edge n → d with the properties:

The node d is called the header and it is a single entry to the loop.
The loop consists of d plus all the nodes in the flow graph that can read n without going through d.

Given a flow graph with a back edge n → d we can construct the natural loop of this back edge by performing a depth-first search on the reverse flow graph starting with node n. See Alg. 9.46, pp. 665-666.
In a reducible flow graph, we can associated a natural loop with each retreating edge.
If two loops have distinct headers, then they are either disjoint or one is nested within the other. Natural loops allow us to easily find the innermost loops in a reducible flow graph.
If two natural loops have the same header, we can merge the two loops into a single loop.