Dominator Trees and the Cooper-Harvey-Kennedy Iterative Method

In a control-flow graph with a designated entry vertex, a vertex d dominates a vertex n when every path from entry to n passes through d. Dominance is the formal statement of “this code always runs before that code”, and it is the basis for placing computations where they execute unconditionally: loop-invariant code motion, static single assignment construction, and the detection of unreachable blocks all reduce to it.

The dominator relation is a partial order with a tree embedded in it. Every vertex has a unique immediate dominator — the closest strict dominator — and the edges from each vertex to its immediate dominator form a tree rooted at the entry. That tree, not the full dominator sets, is what compilers actually build, and it holds the same information in O(n) space instead of O(n²).

Why the tree exists

Two facts give the tree. First, the dominators of a vertex are totally ordered by dominance: if d₁ and d₂ both dominate n, then one dominates the other. The proof is short — take a simple path from the entry to n, and suppose d₁ appears on it before d₂. If some other path reached d₂ without passing d₁, then following that path and rejoining the first one at d₂ would yield a walk from the entry to n that avoids d₁, contradicting that d₁ dominates n; so every path to d₂ passes through d₁, and d₁ dominates d₂. Second, the entry dominates every reachable vertex, so the dominator set of any reachable vertex is nonempty; ordering that chain from the entry down to n, the last element before n is the immediate dominator.

Taken together, the immediate-dominator function is well defined for every reachable vertex except the entry, and following it upward terminates at the entry. The result is a tree, and the full dominator set of n is exactly the path from the entry to n in that tree.

Unreachable vertices break the definition: no path from entry exists, so the universal quantification over paths is vacuous and every vertex dominates them. Implementations exclude them from the analysis, typically by running a reachability pass first — which is just a traversal from the entry marking the blocks that participate.

The dataflow equations

The dominator sets satisfy a forward dataflow system. For the entry, Dom(entry) = {entry}. For every other reachable vertex n with predecessors p₁..p_k,

Dom(n) = {n} ∪ (Dom(p₁) ∩ Dom(p₂) ∩ … ∩ Dom(p_k))

The intersection is the key: a vertex dominates n only if it dominates every predecessor, because any path to n arrives through one of them. The equation is monotone and the lattice of subsets is finite, so iterating from a conservative initial state converges to the greatest fixpoint below the initial assignment. Initializing every non-entry vertex to “all vertices” and iterating downward reaches the correct answer; initializing to the empty set does not, because the iteration would have to grow sets and the intersection operator drives them down.

The naive iteration represents each Dom(n) as a bitset of n bits. The fixpoint may require O(n) passes in the worst case, each pass touching every edge and intersecting bitsets of n/64 words, so the worst case is O(n²·m/64) word operations, and the memory is O(n²) bits. For a function with ten thousand blocks that is 12.5 MB of bitsets and a great many passes. Both figures are why the bitset formulation is taught but not used.

Intersecting the tree instead of the sets

The Cooper-Harvey-Kennedy algorithm keeps only the immediate dominator of each vertex and computes the intersection of predecessor dominator sets implicitly, by walking up the tree.

To intersect the dominators of two vertices a and b, walk both upward toward the entry, always advancing the one with the higher reverse post-order number, until they meet. The meeting vertex is the deepest common dominator, which is exactly the intersection’s maximum element, and for the purposes of the equation that maximum is all that matters: the intersection of the dominator sets is the tree path from the entry to that meeting vertex, so storing the meeting vertex suffices to represent it.

def compute_idom(preds, entry, rpo):
    # rpo: vertices in reverse post-order, entry first; rank[v] is its position
    rank = {v: i for i, v in enumerate(rpo)}
    idom = {v: None for v in rpo}
    idom[entry] = entry

    def intersect(a, b):
        while a != b:
            while rank[a] > rank[b]:
                a = idom[a]
            while rank[b] > rank[a]:
                b = idom[b]
        return a

    changed = True
    while changed:
        changed = False
        for v in rpo[1:]:
            new = None
            for p in preds[v]:
                if idom[p] is None:
                    continue          # predecessor not yet processed
                new = p if new is None else intersect(new, p)
            if new is not None and idom[v] != new:
                idom[v] = new
                changed = True
    return idom

Two details make it work in practice. The iteration proceeds in reverse post-order, which is the depth-first finish order reversed and is close to a topological order of the reducible graph, so information flows forward through most of the graph in a single pass. And the walk terminates at the entry because idom[entry] = entry, which makes the intersection of a vertex with the entry return the entry rather than looping.

The convergence behaviour is the point of the method. On the control-flow graphs compilers produce, the loop converges in a small number of passes, and each pass is O(m) tree walks of bounded length. The worst case is still quadratic in principle, but the practical behaviour is why the iterative method is widely used in compilers despite the near-linear bound of the Lengauer-Tarjan method.

Reverse post-order is not optional

Reverse post-order gives the iteration its direction. In post-order, a vertex is numbered after all its descendants; reversing puts ancestors first, and in a reducible flow graph — one whose only retreating edges are loop backedges — reverse post-order is a topological order of the graph with backedges removed. Every forward edge then points from a lower rank to a higher one, so a single pass propagates dominance down the graph.

Numbering by discovery order instead, or by arbitrary index, loses that property and can force the iteration to run for a number of passes proportional to the loop nesting depth. The difference is not asymptotic in the worst case, but it is the difference between two passes and dozens on real code.

The rank array also replaces the comparison by position in the list. Storing the reverse post-order position per vertex makes each step of intersect a single integer comparison and a lookup, which is the difference between a hash lookup per step and an array access.

What the tree is used for

Once built, the dominator tree answers several questions in constant or logarithmic time.

A vertex d dominates n exactly when d is an ancestor of n in the tree, which is a test on the entry and exit times of a depth-first numbering of the tree — the same interval containment argument that applies to any DFS forest, applied to a tree that was itself computed by a traversal.

A loop’s header dominates every vertex in the loop body, and the set of vertices dominated by the header that can reach the backedge is the natural loop. Loop identification, and therefore the placement of preheaders and the rotation of loops, reads directly off the tree.

Static single assignment construction needs dominance frontiers: for each vertex, the set of vertices where its dominance stops. The frontier of a vertex d is computable from the tree and the predecessor lists by a local rule — a vertex is in the frontier of d if d dominates a predecessor of it but does not strictly dominate the vertex itself. Building all frontiers walks the dominator tree upward from every vertex with more than one predecessor; its cost is linear in the number of edges plus the total size of the frontiers, and the result drives the placement of phi functions.

Limits and failure modes

The analysis assumes a single entry. Multiple entry points — computed gotos into a function, exception handlers reachable from outside, or the artificial entry blocks created by some intermediate representations — must be merged into a synthetic entry, or the analysis must be run per entry, and the choice changes the answers. Merging is standard but changes the graph’s semantics for the purposes of optimization, since it claims paths exist that cannot be taken.

Irreducible flow graphs, produced by aggressive goto-based code or by hand-written assembly, have loops with multiple entry points. The iterative algorithm still converges and still produces a correct tree; it simply takes more passes, because reverse post-order no longer approximates a topological order. The Lengauer-Tarjan method’s bound does not depend on reducibility, which is one reason it remains the reference algorithm in the literature.

Finally, the tree describes static dominance, not execution frequency. A block that dominates another may run only when an earlier condition is true, and the dominator tree says nothing about that. Profile-guided decisions need the frequencies that instrumentation supplies, and dominance is only the structural precondition for moving code at all.