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

## Lecture Outline

1. Review
2. Dominators
3. Depth-first ordering
4. Edges in a depth-first spanning tree
5. Reducible flow graphs
6. Natural loops

## 1. Review

1. Data-flow analysis frameworks
2. Iterative algorithm for general frameworks
3. Meaning of a data-flow solution
4. 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:
1. The node d is called the header and it is a single entry to the loop.
2. 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.