10.4 Dominators and Loops

Block A dominates block B if every path from the entry to B passes through A. This must-pass relation is the backbone of structural analysis on a CFG.

The entry dominates everything. Each block (except entry) has an immediate dominator, and those edges form the dominator tree.

Computing Dominance

A standard fixpoint formulation is:

Iterate to a fixpoint. The entry is dominated only by itself; every other block intersects the dominator sets of its predecessors.

Loops Are Back Edges

A natural loop appears when there is a back edge $n \to h$ where $h$ dominates $n$. Then $h$ is the loop header, and the body is every block that can reach $n$ without passing through $h$, plus $h$ itself.

This definition turns "loop" from a syntactic idea into a graph property, which is what optimizations need.

Why It Matters

Dominance places phi nodes, scopes loop-invariant code motion, and validates code hoisting. Get dominance right and a whole family of optimizations becomes safe.

The Dominator Tree

Immediate dominators form a tree: each block's parent is its closest strict dominator. The dominator tree is more than a curiosity; it is the data structure passes actually walk. Phi placement uses dominance frontiers derived from it, and code motion uses it to find the safe hoisting point.

Loop Anatomy

Once you have a natural loop, names matter: the header dominates the body, the back edge closes it, a preheader is an inserted block before the header for hoisting, and latches are blocks with the back edge. Optimizers target these precisely: invariant code moves into the preheader, induction variables are simplified in the body.

Nested and Irreducible Loops

Loops nest when one header dominates another. Most code is reducible, meaning loops have single headers and clean nesting. Hand-written gotos can create irreducible flow with multiple entries; compilers either transform it or fall back to weaker analysis. Knowing the difference explains why some control shapes optimize poorly.

Worked Insight

In the diamond plus a back edge from the merge to the header, dominance tells you instantly that the header is the loop entry and the body is everything it dominates up to the latch. No pattern matching on syntax required, just graph facts.