Compilers and Translators:
Software Verification Tools
Lecture 8: Loops in Flow Graphs
September 27, 2007
- Depth-first ordering
- Edges in a depth-first spanning tree
- Reducible flow graphs
- Natural loops
- Data-flow analysis frameworks
- Iterative algorithm for general frameworks
- Meaning of a data-flow solution
- Framework for constant propagation
- 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.
3. Depth-First Ordering
- 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.
4. Reducible Flow Graphs
- 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
5. Natural Loops
- A natural loop in a flow graph is a set of nodes defined by a back
edge n → d with the properties:
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
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.
- 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