THE DOMINATOR TREE what must run before you can get here
Node d dominates n if every path from entry to n passes through d. The immediate dominator idom(n) is the closest strict dominator, and the idom edges form a tree that says exactly what must have run before control can reach each block. It is the backbone of SSA form (φ-placement by dominance frontiers) and most modern optimisation.
THE TECHNIQUE intersect the predecessors, to a fixpoint
Dom(entry) = {entry}; for every other node, Dom(n) = {n} ∪ (∩ over predecessors p of Dom(p)) — iterate to a fixpoint. Then idom(n) is the single closest strict dominator. Below: a diamond CFG (0→1, 0→2, 1→3, 2→3, 3→4); the merge point 3 is dominated only by 0, not by 1 or 2. live demo
HISTORY & CREDIT the concept is from 1959
“Lengauer & Tarjan invented dominators” — they made them existfast (1979). The concept is Prosser’s (1959); the first algorithm is Lowry-Medlock (1969). cited
1959 · Reese Prosser defines dominance via a Boolean connectivity matrix — but gives no method to compute it. 1969 · Lowry & Medlock — the first actual algorithm (a fixpoint, ~O(n²e)), shipping in an IBM OS/360 compiler a decade before Lengauer-Tarjan. 1979 · Lengauer & Tarjan — DFS numbering + semidominators + link-eval with path compression: near-linear O(m·α(m,n)), not truly linear. 1988–2001 · Rosen-Wegman-Zadeck introduce SSA (1988); Cytron et al. place φ-nodes by dominance frontiers (1991); Cooper-Harvey-Kennedy (2001) revive the simple iterative idom[] method, often the fastest in practice.
Truly linear-time dominators came 20 years after Lengauer-Tarjan (Alstrup, Harel, Lauridsen & Thorup, 1999). Lengauer-Tarjan, 1979
RECOMMEND FOR I-13 Dom sets are bitmasks; intersect = AND
Each Dom set is one f64 bitmask; the predecessor intersection is bit-AND; the fixpoint is recursion:
$ i13 run dom.i13 # diamond 0->1,0->2, 1->3,2->3, 3->4
Dom(0)={0}=1 Dom(1)={0,1}=3 Dom(2)={0,2}=5 Dom(3)={0,3}=9 Dom(4)={0,3,4}=25
idom = [ -, 0, 0, 0, 3 ] (3 is dominated only by 0 -- not by 1 or 2, the two branches)
Recommend:nothing new — each Dom(n) is a bitmask; the update {n} ∪ ∩preds Dom(p) is bit-or of 1<<n with the bit-and of predecessors, iterated to a fixpoint (verified Dom(3)={0,3}, Dom(4)={0,3,4}; idom(3)=0, idom(4)=3). The merge point 3 escaping both branch-dominators is the whole point. Note: a CFG is a graph (adjacency), the corpus’s standing shape; dominance is the substrate SSA and its φ-placement stand on — the same lowering the 8/19 benchmark grades.