Defining a Loop

Headers

Dominators

Natural Loops

Depth-First Order and Depth-First Spanning Trees

Finding Natural Loops Efficiently

We introduce one more definition - a backwards edge.

To find the loops of a program efficiently:
1. Compute a depth-first order (DFO). The backwards edges are those whose heads precede their tails in the DFO.

2. Compute Dominators. The back edges are the backwards edges whose heads dominate their tails.

3. For each back edge, compute the natural loop.