Dominator Tree, in depth: semidominators, Lengauer-Tarjan with path compression, dominance frontiers and SSA

Dominance from first principles

Take a directed graph with a designated root r (for a control-flow graph, the entry block). A node d dominates w if every path from r to w passes through d. Every node dominates itself and the root dominates everything reachable. d strictly dominates w if it dominates w and d differs from w. The immediate dominator idom(w) is the strict dominator of w that is closest to w: it is dominated by every other strict dominator of w.

The key structural fact is that the strict dominators of w form a chain. If d1 and d2 both dominate w, then one dominates the other. Take a simple path to w and say d2 comes last on it; its tail from d2 avoids d1, so any path reaching d2 without d1 would reach w without d1. So linking each node to its immediate dominator gives a tree rooted at r, and "d dominates w" becomes "d is an ancestor of w in this tree". With pre- and post-order numbers on the tree, that is an O(1) interval test, the same trick used for ancestor queries in the lowest common ancestor article.

In the graph in the figure, D can be reached through B or through C, so neither dominates it and its immediate dominator is A. E can only be reached from C, so idom(E) = C. The back edge from F to A adds paths, which can only remove dominators, so it changes none here.

Why the obvious algorithms are slow

The definition suggests two slow algorithms. Deleting each node d and searching from the root finds everything d dominates in O(n(n + m)) total; that is our test oracle. Iterating the data-flow equation Dom(w) = {w} union the intersection of Dom(p) over predecessors p with bit sets is quadratic in space as well as time.

Cooper, Harvey and Kennedy's 2001 iterative algorithm stores only idom pointers, visits blocks in reverse postorder and intersects two candidates by walking up the partial tree. It is short, usually converges in a few passes, and is what the strong bridges and articulation points article implements. Its worst case is quadratic, however, and graphs with long chains of nested joins hit it. Lengauer and Tarjan's 1979 algorithm gives a guarantee instead: O(m log n) with path compression alone, and O(m alpha(m, n)) when the forest is also linked by size, where alpha is the inverse Ackermann function.

Semidominators

Lengauer-Tarjan starts with a depth-first search from the root and numbers the nodes in preorder. Call these numbers dfnum, and write v < w to compare them. The DFS tree has a useful property that follows from the white-path theorem in the DFS edge classification article: any path from a smaller-numbered node to a larger-numbered one must pass through a common ancestor of the two in the tree. That restricts how bypass paths can look.

The semidominator of w, sdom(w), is the node v with the smallest dfnum such that there is a path from v to w whose interior nodes all have dfnum greater than w. Intuitively, it is the highest point in the DFS tree from which you can sneak down to w while touching only nodes that the DFS discovered after w. The tree parent of w always qualifies, so sdom(w) is a proper ancestor of w. Two theorems make it useful:

1. Computing sdom. sdom(w) is the minimum over all edges (v, w) of: v itself if v < w, otherwise sdom(u) for every u that is an ancestor of v in the DFS tree with u > w. Processing nodes in reverse preorder means every such u has already been finished.
2. From sdom to idom. Let u be the node with the smallest sdom on the tree path strictly below sdom(w) down to w inclusive. If sdom(u) = sdom(w) then idom(w) = sdom(w). Otherwise idom(w) = idom(u), which may not be known yet, so the algorithm records u and fixes it up in a final pass in preorder.

Both theorems need the same primitive: the minimum-sdom node on a tree path from some already-processed node up towards the root. That is what the eval/link forest provides.

Lengauer-Tarjan: the eval/link forest

The forest starts with every node as its own tree. When the main loop finishes w it links w under its DFS parent, so at any moment the forest contains exactly the processed nodes, hung from their tree parents. eval(v) returns the node with the smallest semidominator on the path from v up to, but not including, the root of v's forest tree, which is the first unprocessed ancestor. Path compression makes each node point straight at that root after a query and caches the path minimum in label, in the same spirit as the union-find article.

def lengauer_tarjan(succ, root):
    """succ: node -> list of successors. Returns idom for every reachable node."""
    order, parent, dfnum = [], {}, {}
    stack = [(root, None)]
    while stack:                          # iterative DFS, preorder numbers
        v, p = stack.pop()
        if v in dfnum:
            continue
        dfnum[v] = len(order); order.append(v); parent[v] = p
        for w in reversed(succ.get(v, ())):
            if w not in dfnum:
                stack.append((w, v))
    pred = {}
    for v in order:                       # predecessors among reachable nodes only
        for w in succ.get(v, ()):
            pred.setdefault(w, []).append(v)

    semi = {v: dfnum[v] for v in order}   # semidominator as a dfnum
    ancestor = {v: None for v in order}   # eval/link forest
    label = {v: v for v in order}         # min-semi node on the compressed path
    bucket = {v: [] for v in order}
    idom = {}

    def compress(v):                      # iterative path compression
        path = []
        while ancestor[ancestor[v]] is not None:
            path.append(v); v = ancestor[v]
        for u in reversed(path):
            a = ancestor[u]
            if semi[label[a]] < semi[label[u]]:
                label[u] = label[a]
            ancestor[u] = ancestor[a]

    def eval_(v):
        if ancestor[v] is None:
            return v
        compress(v)
        return label[v]

    for w in reversed(order[1:]):         # reverse preorder, root excluded
        for v in pred.get(w, ()):
            u = eval_(v)
            semi[w] = min(semi[w], semi[u])
        bucket[order[semi[w]]].append(w)
        p = parent[w]
        ancestor[w] = p                   # link(p, w)
        for v in bucket[p]:               # every v whose sdom is p
            u = eval_(v)
            idom[v] = u if semi[u] < semi[v] else p
        bucket[p].clear()
    for w in order[1:]:                   # deferred case, in preorder
        if idom[w] != order[semi[w]]:
            idom[w] = idom[idom[w]]
    idom[root] = root
    return idom

Three details matter. The bucket of p is drained right after w is linked, because then every node whose semidominator is p has its whole path below p in the forest. The final loop runs in preorder so idom(idom(w)) is already final when w reads it. And compress is iterative: the recursive form in the paper overflows the stack on a 200,000-node chain.

Worked example: tracing the algorithm

Run the code on the figure's graph. The DFS visits entry, A, B, D, F, exit, C, E, giving dfnums 0 to 7. The main loop then works backwards from E:

F is the instructive row. Its tree parent is D, and D alone would give sdom(F) = D. But the edge from E reaches F, and E was discovered after F, so the path A, C, E, F has interior nodes numbered above F. The eval query finds it without exploring any paths: the forest already holds E linked under C, and C's semidominator is A. F, D and B wait in A's bucket until B is linked under A; then each has a minimum-sdom node on its path whose sdom equals A, so all three get idom A, matching the tree in the figure. Fuzzing the code against the brute-force oracle and against Cooper-Harvey-Kennedy on 3,000 random graphs with up to 14 nodes, including unreachable nodes and self-loops, produced identical idom maps.

Dominance frontiers and SSA

The dominance frontier of d is the set of nodes where d's dominance ends: blocks w such that d dominates a predecessor of w but does not strictly dominate w. Cytron and colleagues showed in 1991 that when a variable is assigned in a set of blocks, the phi functions for SSA form belong exactly at the iterated dominance frontier of that set. The tree makes frontiers cheap: for each join point, walk up from each predecessor until you reach the join point's immediate dominator.

def dominance_frontiers(succ, idom):
    pred = {}
    for v in idom:
        for w in succ.get(v, ()):
            if w in idom:
                pred.setdefault(w, []).append(v)
    df = {v: set() for v in idom}
    for b, ps in pred.items():
        if len(ps) < 2:                   # only join points can be in a frontier
            continue
        for p in ps:
            runner = p
            while runner != idom[b]:
                df[runner].add(b)
                runner = idom[runner]
    return df

On the example this gives DF(B) = {D}, DF(C) = {D, F}, DF(D) = {F}, DF(E) = {F} and DF(F) = DF(A) = {A}. If a variable x is assigned in B and E, the frontier of {B, E} is {D, F}; adding those blocks and iterating adds A, the loop header. So x needs phi functions at D, F and A, and nowhere else.

Other uses of the tree

• Natural loops. An edge t to h is a back edge of a natural loop when h dominates t. F to A qualifies, and the loop body is every node that reaches F without passing A. A retreating edge whose target does not dominate its source means the graph is irreducible.
• Post-dominators and control dependence. Run the same algorithm on the reversed graph, rooted at a virtual exit that every return block and infinite loop feeds. Post-dominance frontiers give control dependence for slicing and dead-code elimination.
• Heap retained size. Treat objects as nodes, references as edges and a virtual root above the GC roots. An object's retained size is the size of its dominator subtree, as heap-dump analysers report it; the Java heap tuning article shows where that number shows up in practice.

Operational guidance

Compilers care about constant factors and incremental updates. LLVM's GenericDomTreeConstruction.h documents that it builds trees with the Semi-NCA algorithm from Georgiadis's 2005 dissertation, which reuses Lengauer-Tarjan's semidominator phase but replaces the idom phase with nearest-common-ancestor walks. The header notes a quadratic worst case but usually slightly faster runs than simple Lengauer-Tarjan, and the code supports incremental edge insertions and deletions.

Measured on CPython 3.13: a 200,000-node chain took 0.60 s with Lengauer-Tarjan and 0.35 s with Cooper-Harvey-Kennedy, which converges in one pass there. A random graph with 100,000 nodes and about 400,000 edges took 1.43 s and 4.92 s respectively. These are rough interpreter numbers, not compiled-code ratios.

Failure modes

• Unreachable nodes. They have no dominators. Code that indexes arrays by node and assumes every node got a dfnum reads garbage. Build predecessor lists only from reachable nodes, as the code does, and return no entry for the rest.
• Wrong final-pass order. Running the deferred fix-up in reverse preorder reads idoms that have not been fixed yet. The oracle catches this within a few hundred random graphs.
• Multiple exits for post-dominators. Without a virtual exit, blocks that only reach one of several returns get no post-dominator, and infinite loops never reach an exit at all.
• Stale trees. A pass that edits the CFG and keeps the old tree places phis and hoists code incorrectly. Update incrementally or rebuild.
• Recursion depth. Recursive DFS and compression overflow on long chains.

Trade-offs

What to do next

1. Write the delete-and-search oracle first and keep it in your test suite.
2. Implement Lengauer-Tarjan as above with iterative DFS and compression, and fuzz it against the oracle on a few thousand random graphs that include unreachable nodes, self-loops and duplicate edges.
3. Add the pre/post-order numbering on the tree so dominance queries are O(1).
4. Add dominance frontiers and check them by hand on a diamond and a loop.
5. For post-dominators, add a virtual exit and run the same code on the reversed graph.
6. Benchmark against Cooper-Harvey-Kennedy on your own graphs; if the graph changes often, look at Semi-NCA-style incremental updates.