Lesson 15.2 — Incremental dominators

Techniques: edge insertion by depth-based search (DBS), edge deletion by subtree rebuild, batched updates with LLVM's DomTreeUpdater · Pebble implements: none of them in C++ (you use LLVM's DomTreeUpdater in the oracle tests and trace all three with the drill); Python oracles in tools/course/lib/cfa.py · Lab: ch15.DomTreeUpdates.* checks LLVM's incrementally maintained tree against your CHK after every batch of random edits · Prerequisites: Lesson 15.1 (dominator trees, Semi-NCA, NCA) · Time: 3–4 hours

A transformation such as jump threading or loop unswitching changes a handful of edges and then asks the dominator tree a question. Recomputing the tree for a 5 000-block function costs a millisecond; doing that after every one of ten thousand small edits is ten seconds. Take the running example (below) and add the edge A → E. Only two blocks change their immediate dominator: E, which can now be reached without B, and H, which can now be reached through E without B. Everything else, including E's own subtree F and G, keeps its idom. This lesson finds such changes without looking at the rest of the graph.

flowchart TD
  A([A]) --> B[B]
  B --> C[C]
  B --> E[E]
  C --> D[D]
  C --> H[H]
  D --> E
  E --> F[F]
  E --> H
  F --> G[G]
  G --> H
  G --> E
  H --> I[I]
  H --> B
  A -.->|inserted| E

1. Problem and motivation

The problem. Given a CFG \(G\), its dominator tree \(\mathcal{D}\), and a batch of edge insertions and deletions that turn \(G\) into \(G'\), compute the dominator tree \(\mathcal{D}'\) of \(G'\) in time proportional to the part of \(\mathcal{D}\) that changes, not to the size of \(G\). In LLVM, every transformation that edits the CFG while other passes hold a DominatorTree must keep it valid; pebblec's optimization pipeline (Ch 17, Ch 18) relies on LLVM's updater for exactly this reason.

Incremental dominators were first studied for reducible flowgraphs by Ramalingam and Reps [RR94] and for general graphs by Sreedhar, Gao and Lee [SGL97], who updated the DJ graph (Lesson 15.3) locally. Both were complex and rarely faster than recomputation in practice. Alstrup and Lauridsen [AL96] and later Georgiadis, Italiano, Laura and Santaroni [GILS16] simplified insertion to a search guided by tree depths and handled deletion by rebuilding one subtree with Semi-NCA. The 2016 experimental study showed these simple algorithms beat recomputation on real CFGs; LLVM adopted them in 2017, replacing hand-written, error-prone per-transform updates [Kud17].

DBS edge insertion

Inserting \(u \to v\) can only make dominators shallower: a new path may avoid some old dominator of \(v\) (Lemma 15.2.9). The question is which nodes are affected and what their new idom is. The answer [RR94, AL96, GILS16] is strikingly clean: all affected nodes get the same new idom, \(\mathrm{NCA}(u, v)\) in the old tree, and they can be found by a depth-guided search from \(v\) (Lemma 15.2.3). LLVM runs it in SemiNCAInfo::InsertReachable [LLVM-GDTC].

Subtree-rebuild deletion

Deleting \(u \to v\) can only make dominators deeper, and possibly make part of the graph unreachable. There is no equally simple characterization of the affected set, so [GILS16] finds a small subtree that contains all changes (Lemma 15.2.5) and rebuilds just that subtree with Semi-NCA (Lesson 15.1). LLVM's DeleteReachable and DeleteUnreachable implement it.

Batched updates (DomTreeUpdater)

Real transformations change several edges at once, sometimes insert an edge and delete it again, and sometimes change so much that recomputation is cheaper. LLVM's DomTreeUpdater (and the GraphDiff-based batch updater underneath) collects updates, cancels opposite pairs, and then applies them one at a time against snapshots of the CFG, or recomputes from scratch past a size-dependent threshold [LLVM-DTU]. It is an engineering technique rather than a paper, but every LLVM transform that touches the CFG uses it.

2. Definitions and algorithms

Definition 15.2.1 (Update, depth, affected node)

Let \(\mathcal{D}\) be the dominator tree of \(G\) (Theorem 15.1.6), \(\mathrm{depth}(x)\) the level of \(x\) in \(\mathcal{D}\) (root 0), and \(\mathrm{NCA}(a, b)\) the nearest common ancestor in \(\mathcal{D}\). An update is an edge insertion \(G' = G + (u, v)\) or deletion \(G' = G - (u, v)\), and \(\mathcal{D}'\), \(\mathrm{idom}'\) refer to \(G'\). A node \(w\) is affected if \(\mathrm{idom}'(w) \neq \mathrm{idom}(w)\) (including becoming or ceasing to be reachable).

Definition 15.2.2 (Proper support)

After deleting \((u, v)\), the node \(v\) has proper support if some remaining reachable predecessor \(p\) of \(v\) has \(\mathrm{NCA}(v, p) \neq v\), i.e. \(p\) is not in \(v\)'s own subtree of \(\mathcal{D}\) [GILS16, p. 3].

Lemma 15.2.3 (Insertion)

Insert \((u, v)\) with \(u\) reachable, and let \(z = \mathrm{NCA}(u, v)\). A node \(w\) is affected iff \(\mathrm{depth}(z) + 1 < \mathrm{depth}(w)\) and there is a path \(v \leadsto w\) in \(G'\) all of whose nodes \(x\) satisfy \(\mathrm{depth}(x) \ge \mathrm{depth}(w)\). Every affected \(w\) has \(\mathrm{idom}'(w) = z\).

Proof sketch (full proof: [GILS16, §2, Lemma 2.5]; also [RR94, AL96])

Only shallower: by Lemma 15.2.9 below, \(\mathrm{Dom}'(w) \subseteq \mathrm{Dom}(w)\). \(z\) still dominates the affected nodes: a new path to \(w\) uses \((u, v)\), so it passes through \(u\), which \(z\) dominates; and \(w\) lies below \(z\) (the search from \(v\) never climbs above depth \(\mathrm{depth}(z) + 1\)). Nothing strictly between \(z\) and \(w\) survives: the path \(r \leadsto u \to v \leadsto w\) with the \(v \leadsto w\) part at depths \(\ge \mathrm{depth}(w)\) avoids every old dominator of \(w\) whose depth is in \((\mathrm{depth}(z), \mathrm{depth}(w))\), because such a dominator is neither on \(r \leadsto u\) (it is not an ancestor of \(u\) below \(z\)) nor deep enough to be on the \(v \leadsto w\) part. So \(\mathrm{idom}'(w) = z\). Converse: if every path from \(v\) to \(w\) passes a node shallower than \(w\), that node (or one of its old dominators) still separates \(w\) from the new edge, and \(\mathrm{idom}(w)\) is unchanged.

DBS edge insertion

Algorithm 15.2.4 (Depth-based search insertion)

• Input: \(\mathcal{D}\) with depths, \(G' = G + (u, v)\).
• Output: \(\mathcal{D}'\).
• Precondition: \(u\) and \(v\) are reachable in \(G\). (If \(v\) was unreachable, LLVM's InsertUnreachable first runs Semi-NCA on the newly reachable part and then inserts each edge from it into the old tree as a reachable insertion.)
• Postcondition: every affected node of Lemma 15.2.3 has idom \(z\); no other idom changed.
• Invariant: when \(t\) is popped from bucket, no path from \(v\) to \(t\) through not-too-shallow nodes has a larger minimum depth than \(\mathrm{depth}(t)\) (Theorem 15.2.10).

function InsertReachable(D, G′, u, v):
    z ← NCA_D(u, v)
    if depth(z) + 1 ≥ depth(v): return D        # nothing can be affected
    affected ← []
    visited ← {v}
    bucket ← max-priority queue on depth, containing v
    while bucket not empty:
        t ← pop the deepest node of bucket
        append t to affected
        level ← depth(t)
        explore ← [t]                            # nodes reachable at this level
        while explore not empty:
            x ← pop explore
            for s in succs_G′(x):
                if depth(s) ≤ depth(z) + 1: continue      # too shallow: unaffected, blocks paths
                if s ∈ visited: continue
                add s to visited
                if depth(s) > level:
                    push s on explore             # deeper: not affected, but may lead to affected nodes
                else:
                    insert s into bucket          # depth(s) ≤ level: affected
    for w in affected:
        idom(w) ← z                               # and fix depths of w's subtree
    return D

The bucket queue pops deeper nodes first so that each node is first reached along a path whose minimum depth is as large as possible (a widest-path search): that is the path Lemma 15.2.3 asks for. The course oracle is insert_edge_dbs in tools/course/lib/cfa.py.

Subtree-rebuild deletion

Lemma 15.2.5 (Deletion is local)

Delete \((u, v)\) with \(v\) still reachable, and let \(z = \mathrm{NCA}(u, v)\). Only nodes in the subtree of \(z\) in \(\mathcal{D}\) can be affected, and \(z\) still dominates all of them.

Proof (the lemma is [GILS16, Lemma 2.6], cited as such in SemiNCAInfo::DeleteReachable)

Since \(v\) stays reachable, so does every node: a path through \((u, v)\) can be rerouted through a surviving path to \(v\). If \(z = v\) the edge closes a cycle through \(v\) and no simple path uses it, so nothing changes (Theorem 15.2.11, first case). Otherwise let \(w\) be affected. By Lemma 15.2.9 some \(d \in \mathrm{Dom}'(w) \setminus \mathrm{Dom}(w)\) exists: a simple path \(P : r \leadsto w\) of \(G\) avoids \(d\), and every such path uses \((u, v)\). \(P\) visits \(z\) before \(u\) (as \(z \mathrel{\mathrm{dom}} u\)), so \(P = r \leadsto z \leadsto u \to v \leadsto w\), and neither its prefix \(r \leadsto z\) nor its suffix \(v \leadsto w\) uses \((u, v)\). Every path \(r \leadsto v\) of \(G'\) contains \(d\) (otherwise, followed by the suffix, it would reach \(w\) avoiding \(d\)), and contains \(z\) (\(z \in \mathrm{Dom}(v) \subseteq \mathrm{Dom}'(v)\)). Take a simple such path \(T\). Replacing its part up to \(z\) by the prefix of \(P\) (which avoids \(d\)) gives another path \(r \leadsto v\) of \(G'\), which must contain \(d\); so \(d\) occurs on \(T\) after \(z\). Now suppose \(z\) does not dominate \(w\) in \(G\): some path \(Q : r \leadsto w\) avoids \(z\). It never visits \(u\) (every path to \(u\) passes \(z\)), so it is a path of \(G'\) and contains \(d\). Then \(Q\) up to \(d\), followed by \(T\) from \(d\) to \(v\), is a path \(r \leadsto v\) of \(G'\) avoiding \(z\) (\(T\) is simple and \(z\) precedes \(d\) on it), contradicting \(z \in \mathrm{Dom}'(v)\). Hence \(z \mathrel{\mathrm{dom}} w\), and \(w \neq z\) because a path to \(z\) ends before it could use \((u, v)\), so \(\mathrm{Dom}'(z) = \mathrm{Dom}(z)\). Finally \(z\) still dominates \(w\) in \(G'\) by Lemma 15.2.9.

Lemma 15.2.6 (When the target becomes unreachable)

If \(\mathrm{idom}(v) = u\) and \(v\) has no proper support after deleting \((u, v)\), then \(v\) is unreachable in \(G'\).

Proof

Every remaining reachable predecessor \(p\) of \(v\) satisfies \(\mathrm{NCA}(v, p) = v\), i.e. \(v \mathrel{\mathrm{dom}} p\) in \(G\). Suppose some path \(r \leadsto v\) exists in \(G'\); take a shortest one, \(r \leadsto p \to v\). Its prefix \(r \leadsto p\) does not contain \(v\) (shortest), is a path of \(G\) (it does not use the deleted edge, whose target is \(v\)), and reaches \(p\), contradicting \(v \mathrel{\mathrm{dom}} p\) in \(G\).

Algorithm 15.2.7 (Subtree-rebuild deletion)

• Input: \(\mathcal{D}\), \(G' = G - (u, v)\).
• Output: \(\mathcal{D}'\).
• Precondition: \(\mathcal{D}\) is the dominator tree of \(G\), and the CFG has already been changed (the updater reads \(G'\)).
• Postcondition: \(\mathcal{D}'\) is the dominator tree of \(G'\); unreachable nodes are removed.
• Invariant: nodes outside the rebuilt subtree keep their idom (Lemma 15.2.5); inside it, Semi-NCA runs on a flowgraph rooted at the subtree's root.

function DeleteEdge(D, G′, u, v):
    if u not in D or v not in D: return D         # already unreachable
    z ← NCA_D(u, v)
    if z = v: return D                            # v dominates u: the edge was a back edge
    if idom(v) ≠ u or HasProperSupport(D, G′, v):
        DeleteReachable(D, G′, u, v)
    else:
        DeleteUnreachable(D, G′, v)               # Lemma 15.2.6
    return D

function HasProperSupport(D, G′, v):
    for p in preds_G′(v):
        if p in D and NCA_D(v, p) ≠ v: return true
    return false

function DeleteReachable(D, G′, u, v):
    z ← NCA_D(u, v)
    if z is the root: recompute D from scratch; return
    k ← depth(z)
    S ← nodes found by a DFS from z in G′ that only descends into nodes x with depth(x) > k
    run Semi-NCA on the subgraph of G′ induced by S, rooted at z     # Lesson 15.1
    reattach the resulting tree below idom(z)

function DeleteUnreachable(D, G′, v):
    k ← depth(v)
    DFS from v in G′ descending only into nodes deeper than k;
        every node reached at depth ≤ k is collected into Affected
    top ← v
    for a in Affected:
        c ← NCA_D(a, v)
        if c ≠ a and depth(c) < depth(top): top ← c
    if top is the root: recompute D from scratch; return
    erase every node of the DFS (v's subtree) from D                  # now unreachable
    if top = v: return
    rebuild the D-subtree of top as in DeleteReachable (DFS from top below depth(top), Semi-NCA, reattach)

DeleteUnreachable must rebuild above \(v\) when the vanished subtree had edges into other nodes (Affected): those nodes may have depended on paths through it. The course oracle is delete_edge_dbs in tools/course/lib/cfa.py (it recomputes in the unreachable case).

Batched updates (DomTreeUpdater)

Algorithm 15.2.8 (Batched, legalized updates)

• Input: a stream of {Insert|Delete, From, To} updates submitted after the IR has been changed, a strategy (Eager or Lazy), and the tree.
• Output: a valid tree whenever it is queried.
• Precondition: the updates describe the IR changes exactly and in order; each edge's operations alternate (insert, delete, insert, …) so the net count per edge is \(-1\), \(0\) or \(+1\).
• Postcondition: after Flush, the tree is the dominator tree of the current CFG.
• Invariant: between flushes, the tree is the dominator tree of the CFG as it was at the last flush, and pending lists exactly the changes since then (Theorem 15.2.13).

function ApplyUpdates(DTU, updates):                 # DomTreeUpdater::applyUpdates
    if DTU.strategy = Eager:
        BatchApply(DTU.tree, updates)
    else:
        append updates to DTU.pending                # Lazy: nothing happens yet

function Flush(DTU):                                 # also run by getDomTree()
    BatchApply(DTU.tree, DTU.pending)
    DTU.pending ← []
    delete the blocks queued for deletion

function BatchApply(D, updates):                     # SemiNCAInfo::ApplyUpdates
    legal ← Legalize(updates)
    if legal is empty: return
    if |legal| = 1: InsertEdge or DeleteEdge on the current CFG; return
    n ← number of nodes in D
    if (n ≤ 100 and |legal| > n) or (n > 100 and |legal| > n / 40):
        recompute D from scratch; return
    for each update in legal:                        # against CFG snapshots (GraphDiff)
        view the CFG as it was just before this update
        InsertEdge or DeleteEdge accordingly

function Legalize(updates):                          # cfg::LegalizeUpdates
    count[(a, b)] ← (number of inserts) − (number of deletes) of each edge
    return one Insert for every count = +1 and one Delete for every count = −1

InsertEdge dispatches to InsertReachable (Algorithm 15.2.4) or, when To was unreachable, InsertUnreachable; DeleteEdge is Algorithm 15.2.7. This mirrors GenericDomTreeUpdater::applyUpdates/flush [LLVM-DTU], cfg::LegalizeUpdates [LLVM-CFGUpdate] and SemiNCAInfo::ApplyUpdates [LLVM-GDTC] (LLVM 23.1.2).

3. Worked example

All three techniques on the running example. The old tree and depths (from Lesson 15.1):

A (0)
└── B (1)
    ├── C (2)
    │   └── D (3)
    ├── E (2)
    │   └── F (3)
    │       └── G (4)
    └── H (2)
        └── I (3)

DBS edge insertion: insert A → E

z = NCA(A, E) = A, depth 0; depth(E) = 2 > 0 + 1, so the search runs from E. "Too shallow" means depth ≤ depth(z) + 1 = 1.

step	pop (affected)	level	successors scanned	bucket after
1	E	2	E→F (depth 3 > 2: explore, not affected); E→H (depth 2 ≤ 2: affected, to bucket); F→G (depth 4: explore); G→H (visited); G→E (visited)	H
2	H	2	H→I (depth 3: explore, not affected); H→B (depth 1: too shallow)	(empty)

Affected = {E, H}; both get idom = A. F, G and I were visited but not affected: they stay below E and H. Recomputing from scratch gives the same tree.

A second insertion, D → G, shows the early cut-off: z = NCA(D, G) = B (depth 1), depth(G) = 4 > 2. Pop G: G→H (depth 2 ≤ 2, too shallow), G→E (too shallow). Affected = {G}, new idom(G) = B.

Try it

./course drill dom-update --seed 3 --difficulty easy --solution prints this table for a random insertion.

Subtree-rebuild deletion: delete B → E, then F → G

Delete B → E. z = NCA(B, E) = B ≠ E. idom(E) = B = u, so check proper support: E's remaining predecessors are D and G, and NCA(E, D) = B ≠ E, so D supports E: E stays reachable → DeleteReachable.

step	action	state
1	z = NCA(B, E) = B, depth 1; idom(B) = A exists, so no full recomputation	rebuild the subtree of B
2	DFS from B descending only into depth > 1	S = {B, C, D, H, I, E, F, G} (visit order B C D E F G H I)
3	Semi-NCA on G′ restricted to S, rooted at B (edge B→E gone)	idom: C=B, D=C, E=D, F=E, G=F, H=C, I=H
4	reattach below idom(B) = A	E: B → D, H: B → C

H changes too: with B → E gone, every path to E runs through C and D, so every path to H (via C, E or G) runs through C.

Delete F → G. z = NCA(F, G) = F ≠ G; idom(G) = F = u and G has no other predecessor, so no proper support → DeleteUnreachable(G) (Lemma 15.2.6).

step	action	state
1	DFS from G, descending only into depth > 4	visits G; G→H (depth 2) and G→E (depth 2) go to Affected = [H, E]
2	NCA(H, G) = B ≠ H, depth 1 < 4 → top = B; NCA(E, G) = E = E, ignored	top = B
3	top is not the root; erase the DFS nodes	G removed from the tree
4	rebuild the subtree of B (DFS below depth 1, Semi-NCA, reattach under A)	idoms unchanged: H = B (preds C, E), E = B

The rebuild in step 4 changes nothing here, but it must run: H's old idom could have relied on a path through G.

Batched updates: a lazy DomTreeUpdater

A transformation redirects C's branch from H to I, and along the way temporarily adds and removes an edge A → E. With the Lazy strategy it submits, in order: {Delete, C, H}, {Insert, A, E}, {Insert, C, I}, {Delete, A, E}, and then asks for the tree.

step	event	pending	tree
1	applyUpdates(Delete C→H)	[−C→H]	old (stale)
2	applyUpdates(Insert A→E)	[−C→H, +A→E]	old (stale)
3	applyUpdates(Insert C→I)	[−C→H, +A→E, +C→I]	old (stale)
4	applyUpdates(Delete A→E)	[−C→H, +A→E, +C→I, −A→E]	old (stale)
5	getDomTree() → flush → Legalize	A→E counts +1 −1 = 0 and is dropped; legal = [−C→H, +C→I]
6	2 updates, 9 nodes ≤ 100, 2 ≤ 9: apply incrementally
7	DeleteEdge(C, H): idom(H) = B ≠ C → DeleteReachable, rebuild subtree of NCA(C, H) = B	pending []	H: B → E
8	InsertEdge(C, I): after step 7, H hangs below E (depth 3) and I below H (depth 4); z = NCA(C, I) = B, and depth(I) = 4 > depth(B) + 1 = 2, so DBS runs: pop I (affected), I has no successors		I: H → B

Final tree: idom = {B: A, C: B, D: C, E: B, F: E, G: F, H: E, I: B}, the same as recomputation on the edited CFG. With the Eager strategy, steps 1–4 would each update the tree at once, and the A → E insertion and deletion would both have been processed for nothing.

4. Invariants and correctness

Lemma 15.2.9 (Monotonicity of updates)

For every node \(w\) reachable in both \(G\) and \(G'\): inserting an edge gives \(\mathrm{Dom}'(w) \subseteq \mathrm{Dom}(w)\); deleting an edge gives \(\mathrm{Dom}'(w) \supseteq \mathrm{Dom}(w)\).

Proof

Insertion only adds paths \(r \leadsto w\) and deletion only removes them. A node on every path of a larger family is on every path of any non-empty subfamily; \(w\) reachable in both graphs keeps the families non-empty.

DBS edge insertion

Theorem 15.2.10 (Correctness of DBS insertion)

Algorithm 15.2.4 visits every node at most once and marks affected exactly the nodes of Lemma 15.2.3; after it, \(\mathcal{D} = \mathcal{D}'\).

Proof sketch (full proof: [GILS16, §3])

Termination: every node enters visited at most once and is scanned once. Soundness: the search visits exactly the nodes deeper than \(\mathrm{depth}(z) + 1\) that are reachable from \(v\) through such nodes. Because bucket always yields the deepest pending node and explore only follows nodes deeper than the current level, a node \(s\) is placed in bucket precisely when the best path found to it has minimum depth \(\mathrm{depth}(s)\), which is the condition of Lemma 15.2.3; nodes reached only through shallower bottlenecks go to explore from a shallower level and are not marked. Result: Lemma 15.2.3 gives \(\mathrm{idom}'(w) = z\) for the marked nodes and no change for the others.

When it breaks: if \(u\) is unreachable, the NCA is undefined; the precondition is essential (LLVM routes this case to InsertUnreachable).

Subtree-rebuild deletion

Theorem 15.2.11 (Correctness of subtree-rebuild deletion)

Algorithm 15.2.7 returns the dominator tree of \(G'\).

Proof

Back edge (\(z = v\)): \(v\) dominates \(u\), so every path through the edge \((u, v)\) visits \(v\) before \(u\) and again after it: it is not simple. Dominance depends only on simple paths (Definition 15.1.1), so deleting the edge changes nothing. Reachable case: by Lemma 15.2.5 only nodes below \(z\) change, and \(z\) keeps dominating them. Every path \(r \leadsto w\) of \(G'\) to a node \(w\) of \(z\)'s old subtree contains \(z\), and after its last \(z\) it stays inside the subtree: a node \(y\) outside the subtree is not dominated by \(z\) (its dominators did not change), so a path \(r \leadsto y\) avoiding \(z\) followed by the rest of the path would reach \(w\) avoiding \(z\). So the DFS from \(z\) restricted to nodes deeper than \(z\) collects exactly the subtree's nodes, dominance among them is dominance in the flowgraph they induce rooted at \(z\), Semi-NCA on it (Theorem 15.1.28) gives the new idoms, and reattaching below \(\mathrm{idom}(z)\) restores the rest. Unreachable case (sketch; [GILS16, Lemma 2.7], cited by SemiNCAInfo::DeleteUnreachable): by Lemma 15.2.6, \(v\) and every node reachable only through it disappear. A surviving node \(a\) that had an edge from the vanished part may lose paths; it is affected at most up to \(\mathrm{NCA}(a, v)\), so rebuilding the subtree of the shallowest such NCA (top) is a reachable-case rebuild. If top is the root, recomputation is the rebuild. Termination: one DFS and one Semi-NCA run.

When it breaks: calling the updater before changing the IR: DeleteEdge reads the current successors (LLVM asserts in debug builds that the edge is really gone).

Batched updates (DomTreeUpdater)

Lemma 15.2.12 (Legalize keeps the net effect)

If the submitted updates transform \(G_0\) into \(G_k\) and each edge's operations alternate, then Legalize returns a set of updates that transforms \(G_0\) into \(G_k\), each edge at most once.

Proof

Edges are independent: the final presence of an edge depends only on its own operations. With alternating operations, the net count is \(+1\) exactly when the edge was absent in \(G_0\) and present in \(G_k\), \(-1\) in the opposite case, and \(0\) when its presence is unchanged. Emitting one Insert for \(+1\), one Delete for \(-1\) and nothing for \(0\) reproduces \(G_k\) from \(G_0\).

Theorem 15.2.13 (Correctness of batched updates)

After Flush, the tree is the dominator tree of the current CFG.

Proof

By Lemma 15.2.12 the legalized list \(U_1, \dots, U_j\) turns the CFG of the last flush into the current CFG. If it is recomputed, done. Otherwise the updates are applied in order, and \(U_i\) is applied against the snapshot "current CFG with \(U_{i+1}, \dots, U_j\) undone", which is exactly the graph after \(U_1, \dots, U_i\) (the GraphDiff "PreViewCFG"). So each call meets the precondition of Algorithm 15.2.4 or 15.2.7 (tree of the graph before the update, graph already changed), and by Theorems 15.2.10 and 15.2.11 and induction on \(i\) the tree is right after each one. Termination: a finite list.

When it breaks: submitting an update twice or out of order for the same edge (the counts become ±2 and LegalizeUpdates asserts "Unbalanced operations!"); querying the raw DominatorTree instead of DTU.getDomTree() while updates are pending.

5. Complexity

\(n\) = nodes, \(m\) = edges, \(k\) = number of updates in a batch, \(\lvert S \rvert\) = nodes of the rebuilt subtree, \(m_S\) = edges among them.

Technique	Time (worst)	Time (typical)	Space	Notes
DBS insertion	\(O(m \log n)\) with a binary heap (LLVM uses std::priority_queue); \(O(n + m)\) with a bucket queue indexed by depth [GILS16]	a handful of nodes	\(O(n)\)	\(O(1)\) when \(\mathrm{depth}(z) + 1 \ge \mathrm{depth}(v)\)
Subtree-rebuild deletion	\(O(m_S + \lvert S \rvert \log \lvert S \rvert)\) (Semi-NCA's cost on \(S\); \(O(\lvert S \rvert^2)\) in the Semi-NCA worst case)	the subtree of a nearby NCA	\(O(\lvert S \rvert)\)	the whole tree when \(z\) is the root
Batched updates	\(\min(k \cdot \text{per-update cost},\ \text{full recomputation})\)	\(k\) per-update costs	\(O(k)\) pending	recompute when \(k > n\) (\(n \le 100\)) or \(k > n/40\)

Proposition 15.2.14 (Cost of one update)

DBS insertion costs \(O((n_V + m_V) \log n)\) where \(n_V, m_V\) are the nodes and edges it visits; subtree-rebuild deletion costs one restricted DFS plus one Semi-NCA run on the rebuilt subtree.

Proof

Each visited node is pushed once onto explore or bucket and each of its outgoing edges scanned once; bucket operations cost \(O(\log n)\) with a binary heap (O(1) with an array of buckets indexed by depth, since depths are integers below \(n\)). Deletion does exactly one DFS restricted to \(S\) (\(O(\lvert S \rvert + m_S)\)) and one Semi-NCA on the same subgraph (Proposition 15.1.30).

Pathological input: deleting an edge \(u \to v\) where \(\mathrm{NCA}(u, v)\) is the entry: for example deleting B → E in a variant of the running example where B is the entry. DeleteReachable then rebuilds the whole tree, and a sequence of such deletions costs \(k\) full recomputations. The same happens for insertions whose NCA is shallow and whose \(v\) has a huge deep subtree reachable at depth \(\ge \mathrm{depth}(v)\): DBS visits the whole subtree.

At scale: Georgiadis et al. measured the dynamic algorithms on CFGs of real programs and found DBS and the SNCA-based deletion outperforming static recomputation by large factors per update [GILS16]; LLVM's n/40 recomputation threshold was tuned "with an acceptable performance on some real-world inputs" (comment in SemiNCAInfo::ApplyUpdates, LLVM 23.1.2) [LLVM-GDTC].

6. Variants and refinements

DBS edge insertion

• Ramalingam–Reps [RR94]: the original incremental algorithm, for reducible flowgraphs; it also updates in O(affected) — trade-off: restricted to reducible CFGs, more complex bookkeeping.
• Sreedhar–Gao–Lee [SGL97]: updates the DJ graph and dominator tree together, using the dominance frontier to find affected nodes — trade-off: keeps DF up to date for free, but needs DF and is much more code.
• Alstrup–Lauridsen [AL96]: the depth-based insertion in its original form — trade-off: same idea; GILS16 add the practical bucket queue.

Subtree-rebuild deletion

• Full recomputation on every deletion — trade-off: trivially correct, \(O(m)\) each time; what LLVM did before 2017, and still does when the NCA is the root.
• Dynamic SNCA with "pre-DFS" information [GILS16]: keep DFS numbers between updates to avoid rerunning the DFS — trade-off: faster deletions, but insertions must maintain the DFS tree.
• Post-dominator trees: deletion can create a new root (an infinite loop appears); LLVM's DeleteUnreachable adds a root and calls InsertReachable from the virtual exit instead (Lesson 15.4) — trade-off: roots must be re-minimized afterwards (UpdateRootsAfterUpdate).

Batched updates

• Eager vs Lazy (DomTreeUpdater::UpdateStrategy): Eager applies each update immediately — trade-off: the tree is always valid but cancelled pairs cost work twice; Lazy batches — trade-off: cheaper, but the tree is stale until flushed.
• Direct DT.applyUpdates(...) without a DomTreeUpdater — trade-off: no deleted-block bookkeeping, no post-dominator tree; used by utilities that own the tree (loop rotation, [LLVM-LoopRotate]).
• MemorySSAUpdater, LoopInfo updates follow the same batching style — trade-off: each analysis needs its own update logic; LLVM transforms pass a DTU, an MSSAU and LoopInfo together.

7. In real compilers

DBS edge insertion

LLVM

llvm/include/llvm/Support/GenericDomTreeConstruction.h — SemiNCAInfo::InsertEdge dispatches to InsertReachable (the DBS above, with the comment "Based on Lemma 2.5 from [2]" and the "widest path problem" remark) and InsertUnreachable/ComputeUnreachableDominators for newly reachable regions; UpdateInsertion re-parents the affected nodes (LLVM 23.1.2) [LLVM-GDTC].

• GCC 15 gcc/dominance.cc — iterate_fix_dominators cites Ramalingam–Reps and Sreedhar–Gao–Lee but, for the small block sets GCC's passes produce, recomputes the dominators of the affected blocks with CHK (Lesson 15.1) [GCC-Dominance].
• Cranelift, Go, rustc do not update dominator trees incrementally; they recompute after CFG changes (their pipelines run few CFG-changing passes between queries).

Loop rotation inserts edges into a live dominator tree

Reproduce (clang 23.1.2, opt 23.1.2; loop(...) runs loop-simplify and LCSSA first, as the new pass manager always does for loop passes):

cat > count.c <<'EOF'
int count(int *a, int n) {
  int c = 0;
  for (int i = 0; i < n; i++)
    if (a[i] > 0)
      c++;
  return c;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm count.c -o count.ll
opt -passes='sroa,print<domtree>,loop(loop-rotate),print<domtree>' \
    -debug-pass-manager -disable-output count.ll 2>&1 |
  grep -E 'DominatorTreeAnalysis|Running pass: (Loop|Dom)|^  +\['

Output (complete, filtered by the grep):

Running analysis: DominatorTreeAnalysis on count
Running pass: DominatorTreePrinterPass on count (17 instructions)
  [1] %entry {0,7} [0]
    [2] %for.cond {1,7} [1]
      [3] %for.body {2,6} [2]
        [4] %if.then {3,4} [3]
        [4] %if.end {4,6} [3]
          [5] %for.inc {5,6} [4]
      [3] %for.end {6,7} [2]
Running pass: LoopSimplifyPass on count (17 instructions)
Running pass: LoopRotatePass on loop %for.cond in function count
Running pass: DominatorTreePrinterPass on count (21 instructions)
  [1] %entry {4294967295,4294967295} [0]
    [2] %for.body.lr.ph {4294967295,4294967295} [1]
      [3] %for.body {4294967295,4294967295} [2]
        [4] %if.then {4294967295,4294967295} [3]
        [4] %if.end {4294967295,4294967295} [3]
          [5] %for.inc {4294967295,4294967295} [4]
            [6] %for.cond.for.end_crit_edge {4294967295,4294967295} [5]
    [2] %for.end {4294967295,4294967295} [1]

What to notice: DominatorTreeAnalysis runs once; the second tree is the first one updated. Rotation submits {Insert, entry, for.end}, {Insert, entry, for.body}, {Delete, entry, for.cond} to DT->applyUpdates (LoopRotate::rotateLoop [LLVM-LoopRotate]). The inserted edge entry → for.end re-parents for.end from for.cond to \(\mathrm{NCA}(\texttt{entry}, \texttt{for.end}) = \texttt{entry}\): every affected node gets the NCA, as Lemma 15.2.3 says. The blocks with lr.ph and crit_edge in their names come from later edge splits, which update the tree locally too. The {4294967295,…} pairs show that the DFS numbers of Corollary 15.1.7 are invalid after updates until a query recomputes them.

Subtree-rebuild deletion

LLVM

Same file — SemiNCAInfo::DeleteEdge, HasProperSupport ("as defined on the page 3 and later explained on the page 7 of [2]"), DeleteReachable (lemma 2.6) and DeleteUnreachable, each ending in runSemiNCA plus reattachExistingSubtree, or in CalculateFromScratch when the subtree to rebuild is rooted at the entry [LLVM-GDTC].

• GCC 15 again uses iterate_fix_dominators/recompute_dominator on the affected blocks rather than a subtree rebuild [GCC-Dominance].

SCCP deletes an infeasible edge; the dominators get deeper

Reproduce (clang 23.1.2, opt 23.1.2):

cat > dead.c <<'EOF'
int d(int a) {
  int k = 0;
  if (k)
    a = a + 1;
  else
    a = a - 1;
  return a * 2;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm dead.c -o dead.ll
opt -passes='sroa,print<domtree>,sccp,print<domtree>' \
    -debug-pass-manager -disable-output dead.ll 2>&1 |
  grep -E 'DominatorTreeAnalysis|Running pass: (SCCP|Dom)|^  +\['

Output (complete, filtered by the grep):

Running analysis: DominatorTreeAnalysis on d
Running pass: DominatorTreePrinterPass on d (9 instructions)
  [1] %entry {0,4} [0]
    [2] %if.then {1,2} [1]
    [2] %if.end {2,3} [1]
    [2] %if.else {3,4} [1]
Running pass: SCCPPass on d (9 instructions)
Running pass: DominatorTreePrinterPass on d (5 instructions)
  [1] %entry {4294967295,4294967295} [0]
    [2] %if.else {4294967295,4294967295} [1]
      [3] %if.end {4294967295,4294967295} [2]

What to notice: SCCP proves if (k) false, deletes the edge entry → if.then through a lazy DomTreeUpdater (SCCPSolver::removeNonFeasibleEdges [LLVM-SCCP]) and erases the dead block. if.then had idom entry and no other predecessor, so it has no proper support and the unreachable case runs (Lemma 15.2.6). Its successor if.end loses paths and its idom moves down, from entry to if.else (Lemma 15.2.9: deletion only adds dominators). Here the NCA that bounds the rebuild is the entry itself, so DeleteUnreachable takes its "root reached, rebuild the whole tree" exit: on a four-block function that is the cheapest correct answer, and the pass manager still never re-runs DominatorTreeAnalysis.

Batched updates

LLVM

llvm/include/llvm/Analysis/GenericDomTreeUpdater.h — GenericDomTreeUpdater::applyUpdates, applyUpdatesPermissive, flush, getDomTree, and the Eager/Lazy UpdateStrategy [LLVM-DTU]; llvm/lib/Analysis/DomTreeUpdater.cpp instantiates it; llvm/include/llvm/Support/CFGUpdate.h — cfg::LegalizeUpdates [LLVM-CFGUpdate]; SemiNCAInfo::ApplyUpdates holds the recomputation threshold (LLVM 23.1.2):

// excerpt from SemiNCAInfo::ApplyUpdates, GenericDomTreeConstruction.h
} else if (BUI.NumLegalized > DT.DomTreeNodes.size() / 40)

• MLIR keeps no incremental dominance: mlir/lib/IR/Dominance.cpp — DominanceInfoBase::invalidate(Region *) drops a region's tree and getDominanceInfo recalculates it on the next query (MLIR regions are usually small).

Jump threading: many edits, one lazy flush

Reproduce (clang 23.1.2, opt 23.1.2):

cat > thread.c <<'EOF'
int t(int a, int b) {
  int x;
  if (a > 0)
    x = 1;
  else
    x = 0;
  if (x)
    b = b * 3;
  return b;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm thread.c -o thread.ll
opt -passes='sroa,print<domtree>,jump-threading,print<domtree>' \
    -debug-pass-manager -disable-output thread.ll 2>&1 |
  grep -E 'DominatorTreeAnalysis|Running pass: (Jump|Dom)|^  +\['

Output (complete, filtered by the grep):

Running analysis: DominatorTreeAnalysis on t
Running pass: DominatorTreePrinterPass on t (11 instructions)
  [1] %entry {0,6} [0]
    [2] %if.then {1,2} [1]
    [2] %if.end {2,5} [1]
      [3] %if.then1 {3,4} [2]
      [3] %if.end2 {4,5} [2]
    [2] %if.else {5,6} [1]
Running pass: JumpThreadingPass on t (11 instructions)
Running pass: DominatorTreePrinterPass on t (6 instructions)
  [1] %entry {4294967295,4294967295} [0]
    [2] %if.then1 {4294967295,4294967295} [1]
    [2] %if.end2 {4294967295,4294967295} [1]

What to notice: jump threading sees that the second if (x) is decided by the first branch, threads each incoming edge straight to its target, and deletes the blocks in between: several insertions and deletions, queued in a DomTreeUpdater created with UpdateStrategy::Lazy and flushed before the pass returns [LLVM-JumpThreading]. The pass manager keeps the cached tree (no second Running analysis: DominatorTreeAnalysis), and the flushed tree is correct for the new three-block CFG: Theorem 15.2.13.

Find where LLVM does it. Open llvm/include/llvm/Support/GenericDomTreeConstruction.h (LLVM 23.1.2) and find the static function that handles an inserted edge whose endpoints were both already in the tree. Question: what is its name? (Quiz llvm-where-insert.) Then find the constant 40 in ApplyUpdates: for a 2 000-node tree, from how many legalized updates on does LLVM recompute from scratch? (Answer: more than 2000 / 40 = 50, so 51.)

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
DBS edge insertion	exact; only affected nodes change	O(m) worst per insertion, usually a few nodes	the affected set, all re-parented to one NCA	~60 lines	LLVM InsertReachable
Subtree-rebuild deletion	exact	Semi-NCA on the subtree of NCA(u, v); whole tree if that is the root	rebuilt subtree	~80 lines + support test	LLVM DeleteReachable/DeleteUnreachable
Batched updates (DomTreeUpdater)	exact once flushed	lazy: one flush per batch; recompute when updates > n/40 (n > 100)	tree valid only after flush()	API discipline	every CFG-changing LLVM transform

Choose DBS insertion when edges are added one at a time between queries and the tree is large: it touches only the affected region, often nothing at all. Choose subtree-rebuild deletion when deletions are local (the NCA of the edge is deep); for deletions near the entry, recomputation is just as good. Choose batched lazy updates when a transform makes many edits before the next query, or might undo its own edits; choose Eager when interleaved queries need a valid tree after each edit.

The oracle tests ch15.DomTreeUpdates.EagerMatchesRecomputation and ...LazyMatchesRecomputation apply 8 random edits to each of 250 random functions through DomTreeUpdater and compare the result with your CHK after every few edits; LLVM's own DT.verify(VerificationLevel::Full) is checked too.

9. Assessment

Technique	Quiz ids (solutions/quizzes/ch15.yaml)	Drill	Flashcard tag	Exercises
DBS insertion	dbs-insert-affected, incremental-lemmas, llvm-where-insert	./course drill dom-update --difficulty easy	dbs-insert	— (oracle tests DomTreeUpdates.* use LLVM's implementation)
Subtree-rebuild deletion	dbs-delete-idoms, incremental-lemmas	./course drill dom-update --difficulty medium	dbs-delete	—
Batched updates	incremental-lemmas, llvm-where-insert	no drill: batching is an API policy, not a computation to practise; the quiz and the flashcards cover it	domtree-updater	—

Updating the tree before the IR

DomTreeUpdater::applyUpdates requires the CFG to already be in its new state ("It is required for the state of the LLVM IR to be updated before submitting the updates"): the updater inspects successors to validate deletions and to compute snapshots. Submitting first and editing later corrupts the tree silently in release builds.

References

See the chapter references.