COMS W4117
Compilers and Translators:
Software Verification Tools
Lecture 8: Loops in Flow Graphs
September 27, 2007
Lecture Outline
- Review
- Dominators
- Depth-first ordering
- Edges in a depth-first spanning tree
- Reducible flow graphs
- Natural loops
- Reading
1. Review
- Data-flow analysis frameworks
- Iterative algorithm for general frameworks
- Meaning of a data-flow solution
- Framework for constant propagation
2. Dominators
- 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
cycle-free path.
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:
- 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.
6. Reading
aho@cs.columbia.edu