Lesson 15.3 — Dominance frontiers¶

Techniques: Cytron's bottom-up dominance frontiers, CHK's per-join runners, iterated dominance frontiers by worklist, DJ graphs and Sreedhar–Gao's linear-time DF⁺ · Pebble implements: Cytron (E8), CHK (E9), iterated DF worklist (E10); DJ-graph DF⁺ is checked through LLVM's IDFCalculator · Lab: Cytron vs CHK vs llvm::DominanceFrontier; worklist vs IDFCalculator · Prerequisites: Lesson 15.1 · Time: 4–5 hours

In the running example, suppose a variable x is assigned in C and in F. Where do the two definitions meet? C reaches H directly (C → H) and E through D; F reaches H through G and E through G → E. So E and H are the first blocks where "the value from C" and "some other value" can arrive on different incoming edges. They are C's and F's dominance frontier. And once E and H need a phi for x, those phis are new definitions: H's own frontier is B, so B needs one too. The set {B, E, H} is the iterated dominance frontier, exactly where minimal SSA (Ch 16) places phi nodes.

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
  classDef hl fill:#fde68a,stroke:#b45309;
  class B,E,H hl;

1. Problem and motivation¶

The problem. Given a CFG and its dominator tree, compute (a) \(\mathrm{DF}(X)\) for every block \(X\): the blocks just outside the region \(X\) dominates, where \(X\)'s dominance "ends", and (b) \(\mathrm{DF}^{+}(S)\) for a set of blocks \(S\). LLVM needs (b) for every promoted variable in mem2reg and for control dependence in adce (via the reverse CFG, Lesson 15.4); pebblec's SSA construction in Ch 16 calls your E10 on each variable's assignment blocks.

Cytron, Ferrante, Rosen, Wegman and Zadeck defined the dominance frontier and showed that phi nodes belong exactly in the iterated frontier of the assignment blocks; their 1991 paper gave both the frontier algorithm and the worklist for DF⁺ [CFRWZ91]. Frontier sets can be quadratic in total size even when phi placement is linear, which led Sreedhar and Gao to compute DF⁺ directly on a "DJ graph" without materializing frontiers [SG95]. Cooper, Harvey and Kennedy later gave the simplest frontier algorithm, walking "runners" from each predecessor of a join node [CHK01].

Cytron's bottom-up DF¶

Computing DF from its definition means, for every \(X\), looking at every node \(X\) dominates and every successor of those: quadratic even when the answer is small. Cytron et al. split \(\mathrm{DF}(X)\) into a local part contributed by \(X\)'s own successors and an up part inherited from \(X\)'s children in the dominator tree, and compute both in one bottom-up walk [CFRWZ91, §4]. LLVM's DominanceFrontier analysis implements it [LLVM-DFImpl].

CHK runners¶

Only join nodes (≥ 2 predecessors) can be in a frontier. CHK observe that \(Y \in \mathrm{DF}(X)\) exactly when \(X\) lies on the dominator-tree path from a predecessor of \(Y\) up to, but not including, \(\mathrm{idom}(Y)\) (Lemma 15.3.7). So for each join \(Y\) and each predecessor, walk a "runner" up the tree to \(\mathrm{idom}(Y)\), adding \(Y\) to every node passed [CHK01]. It needs nothing but the doms[] array of their dominator algorithm; GCC uses it.

Iterated DF by worklist¶

\(\mathrm{DF}^{+}(S)\) is a fixed point: \(\mathrm{DF}(S)\), then DF of the new nodes, and so on. Cytron et al. compute it with a worklist over the precomputed frontier sets [CFRWZ91, §5.1]. It is short and fast when frontiers are small, which they usually are; GCC's compute_idf is exactly this.

DJ graphs (Sreedhar–Gao)¶

When frontiers are large, precomputing them is the bottleneck. Sreedhar and Gao add the non-tree CFG edges ("J edges") to the dominator tree and show that \(\mathrm{DF}^{+}(S)\) can be read off by visiting each node at most once in order of decreasing tree depth [SG95, SGL96]. LLVM's IDFCalculator (used by mem2reg, adce, SSA updating) is this algorithm [LLVM-IDF].

2. Definitions and algorithms¶

\(G = (N, E, r)\) with dominator tree \(\mathcal{D}\); \(\mathrm{level}(x)\) is \(x\)'s depth in \(\mathcal{D}\) and \(\mathrm{children}(x)\) its \(\mathcal{D}\)-children. All nodes are reachable (unreachable nodes are in no frontier; their edges are ignored).

Definition 15.3.1 (Dominance frontier)

\[ \mathrm{DF}(X) \triangleq \{\, Y \in N \mid \exists P \in \mathrm{preds}(Y).\ X \mathrel{\mathrm{dom}} P \ \land\ \neg (X \mathrel{\mathrm{sdom}} Y) \,\}. \]

For a set, \(\mathrm{DF}(S) \triangleq \bigcup_{X \in S} \mathrm{DF}(X)\). A join node is a node with at least two predecessors.

Frontiers on the running example

\(\mathrm{DF}(C) = \{E, H\}\): \(C\) dominates the predecessor \(D\) of \(E\) and is itself a predecessor of \(H\), but strictly dominates neither. \(B \in \mathrm{DF}(B)\): \(B\) dominates its predecessor \(H\) and does not strictly dominate itself. \(E \notin \mathrm{DF}(B)\) although \(E\) is a join node below \(B\): \(B\) strictly dominates \(E\).

Definition 15.3.2 (Iterated dominance frontier)

\(\mathrm{DF}_1(S) = \mathrm{DF}(S)\), \(\mathrm{DF}_{i+1}(S) = \mathrm{DF}(S \cup \mathrm{DF}_i(S))\), and \(\mathrm{DF}^{+}(S) \triangleq \bigcup_i \mathrm{DF}_i(S)\). The sequence is increasing (by induction, since \(\mathrm{DF}\) of a larger set is larger) and bounded by \(N\), so it is eventually constant.

Definition 15.3.3 (Local and up frontiers)

\(\mathrm{DF}_{\mathrm{local}}(X) \triangleq \{\, Y \in \mathrm{succs}(X) \mid \mathrm{idom}(Y) \neq X \,\}\), and for \(Z\) with \(\mathrm{idom}(Z) = X\), \(\mathrm{DF}_{\mathrm{up}}(Z) \triangleq \{\, Y \in \mathrm{DF}(Z) \mid \mathrm{idom}(Y) \neq X \,\}\).

Lemma 15.3.4 (Strict dominance along an edge)

For an edge \(X \to Y\): \(X \mathrel{\mathrm{sdom}} Y \iff X = \mathrm{idom}(Y)\).

Proof

(\(\Leftarrow\)) By definition. (\(\Rightarrow\)) Let \(d\) be another strict dominator of \(Y\). Every path \(r \leadsto X\) extended by \(X \to Y\) is a path to \(Y\), so it contains \(d\), and not as its last node (\(d \neq Y\)): \(d \mathrel{\mathrm{dom}} X\). So \(X\) is a strict dominator of \(Y\) dominated by all the others, i.e. \(\mathrm{idom}(Y)\) (Definition 15.1.5).

Theorem 15.3.5 (Local/up decomposition)

\(\mathrm{DF}(X) = \mathrm{DF}_{\mathrm{local}}(X) \cup \bigcup_{Z \in \mathrm{children}(X)} \mathrm{DF}_{\mathrm{up}}(Z)\).

Proof

First a fact: for a child \(Z\) of \(X\) and \(Y \in \mathrm{DF}(Z)\), \(X \mathrel{\mathrm{sdom}} Y \iff \mathrm{idom}(Y) = X\). (\(\Leftarrow\)) clear. (\(\Rightarrow\)) Take the witness predecessor \(P\) of \(Y\) with \(Z \mathrel{\mathrm{dom}} P\); \(\mathrm{idom}(Y)\) also dominates \(P\) (paths to \(P\) extend to \(Y\)), so both lie in \(\mathrm{Dom}(P)\), which is a root path of \(\mathcal{D}\) (Theorem 15.1.6(d)): they are comparable. If \(Z \mathrel{\mathrm{dom}} \mathrm{idom}(Y)\), then \(Z \mathrel{\mathrm{sdom}} Y\), contradicting \(Y \in \mathrm{DF}(Z)\). So \(\mathrm{idom}(Y)\) strictly dominates \(Z\), i.e. it is \(X\) or an ancestor of \(X\). Since \(X \mathrel{\mathrm{sdom}} Y\) puts \(X\) among \(Y\)'s strict dominators, of which \(\mathrm{idom}(Y)\) is the deepest, also \(X \mathrel{\mathrm{dom}} \mathrm{idom}(Y)\); by antisymmetry \(\mathrm{idom}(Y) = X\). (\(\subseteq\)) Let \(Y \in \mathrm{DF}(X)\) with witness \(P\). If \(P = X\): \(Y\) is a successor and \(\neg(X \mathrel{\mathrm{sdom}} Y)\), so \(\mathrm{idom}(Y) \neq X\) by Lemma 15.3.4: \(Y \in \mathrm{DF}_{\mathrm{local}}(X)\). If \(P \neq X\): \(X \mathrel{\mathrm{sdom}} P\), so \(P\) lies in the subtree of the child \(Z\) of \(X\) on the tree path to \(P\), and \(Z \mathrel{\mathrm{dom}} P\). \(Z\) does not strictly dominate \(Y\) (otherwise \(X \mathrel{\mathrm{dom}} Z \mathrel{\mathrm{sdom}} Y\) gives \(X \mathrel{\mathrm{sdom}} Y\), as \(X = Y\) would make \(Z\) a strict dominator of its own parent). So \(Y \in \mathrm{DF}(Z)\), and \(\mathrm{idom}(Y) \neq X\) because \(X\) does not strictly dominate \(Y\): \(Y \in \mathrm{DF}_{\mathrm{up}}(Z)\). (\(\supseteq\)) For \(Y \in \mathrm{DF}_{\mathrm{local}}(X)\) the witness is \(P = X\), and Lemma 15.3.4 turns \(\mathrm{idom}(Y) \neq X\) into \(\neg(X \mathrel{\mathrm{sdom}} Y)\). For \(Y \in \mathrm{DF}_{\mathrm{up}}(Z)\), the witness \(P\) of \(Y \in \mathrm{DF}(Z)\) satisfies \(X \mathrel{\mathrm{dom}} Z \mathrel{\mathrm{dom}} P\), and \(\mathrm{idom}(Y) \neq X\) means \(\neg(X \mathrel{\mathrm{sdom}} Y)\) by the fact above.

Cytron's bottom-up DF¶

Algorithm 15.3.6 (Cytron et al.'s frontiers)

Input: \(G\) and its dominator tree \(\mathcal{D}\).
Output: \(\mathrm{DF}(X)\) for every reachable \(X\).
Precondition: \(\mathcal{D}\) is the dominator tree of \(G\); nodes are visited children before parents.
Postcondition: DF[X] \(= \mathrm{DF}(X)\) (Definition 15.3.1).
Invariant: when \(X\) is processed, DF[Z] is final for every child \(Z\) of \(X\) (Theorem 15.3.15).

function CytronDF(G, D):
    for X in PostorderOfDominatorTree(D):          # children before parents
        DF[X] ← {}
        for Y in succs(X):                         # DF_local
            if idom(Y) ≠ X:
                DF[X] ← DF[X] ∪ {Y}
        for Z in children_D(X):                    # DF_up
            for Y in DF[Z]:
                if idom(Y) ≠ X:
                    DF[X] ← DF[X] ∪ {Y}
    return DF

function PostorderOfDominatorTree(D):
    return the nodes of D in postorder of a DFS from the root

You implement it as computeDominanceFrontier(G, DT, DFAlgorithm::Cytron) (E8).

CHK runners¶

Lemma 15.3.7 (Runner characterization)

\(Y \in \mathrm{DF}(X)\) iff some predecessor \(P\) of \(Y\) has \(X\) on the \(\mathcal{D}\)-path from \(P\) up to, but excluding, \(\mathrm{idom}(Y)\). In particular only join nodes are in frontiers.

Proof

(\(\Leftarrow\)) \(X\) is an ancestor-or-self of \(P\), so \(X \mathrel{\mathrm{dom}} P\); and \(\mathrm{idom}(Y)\) is a proper ancestor of \(X\). If \(X \mathrel{\mathrm{sdom}} Y\), then \(X\) would be among \(Y\)'s strict dominators, all of which are ancestors-or-self of \(\mathrm{idom}(Y)\) (Theorem 15.1.6(a)): impossible. (\(\Rightarrow\)) Let \(X \mathrel{\mathrm{dom}} P\) and \(\neg(X \mathrel{\mathrm{sdom}} Y)\). \(\mathrm{idom}(Y)\) also dominates \(P\), so both are ancestors of \(P\) and comparable. If \(X\) were an ancestor-or-self of \(\mathrm{idom}(Y)\) then \(X \mathrel{\mathrm{dom}} \mathrm{idom}(Y) \mathrel{\mathrm{sdom}} Y\), so \(X \mathrel{\mathrm{sdom}} Y\). Hence \(X\) lies strictly below \(\mathrm{idom}(Y)\) on \(P\)'s root path. Join nodes: if \(Y\) has a single predecessor \(P\), then \(P \mathrel{\mathrm{sdom}} Y\), so \(P = \mathrm{idom}(Y)\) and every path from \(P\) up to \(\mathrm{idom}(Y)\) is empty.

Algorithm 15.3.8 (CHK runners)

Input: \(G\) and \(\mathrm{idom}\) (the doms array of Algorithm 15.1.12).
Output: \(\mathrm{DF}(X)\) for every reachable \(X\).
Precondition: \(\mathrm{idom}\) is correct; only reachable predecessors are used.
Postcondition: DF[X] \(= \mathrm{DF}(X)\).
Invariant: after all runners of a join \(Y\) have run, \(Y \in\) DF[X] exactly for the \(X\) of Lemma 15.3.7.

function CHKFrontiers(G, idom):
    for X in N: DF[X] ← {}
    for Y in N:
        if Y has at least two reachable predecessors:
            for P in preds(Y), P reachable:
                runner ← P
                while runner ≠ idom(Y):
                    DF[runner] ← DF[runner] ∪ {Y}
                    runner ← idom(runner)
    return DF

The course solution stops a runner early when DF[runner] already has \(Y\): everything above it on the way to \(\mathrm{idom}(Y)\) was reached by an earlier runner for the same \(Y\) (GCC does the same with bitmap_set_bit returning false). You implement it as computeDominanceFrontier(G, DT, DFAlgorithm::CHK) (E9).

Iterated DF by worklist¶

Definition 15.3.9 (Join set)

For \(S \subseteq N\), \(J(S)\) is the set of nodes \(Y\) such that two non-empty paths \(X_1 \leadsto Y\) and \(X_2 \leadsto Y\) with \(X_1 \neq X_2 \in S\) exist that have no node in common except \(Y\). The iterated join \(J^{+}(S)\) is defined like \(\mathrm{DF}^{+}\) in Definition 15.3.2.

Theorem 15.3.10 (Iterated frontiers are the join sets; phi placement)

For every \(S \subseteq N\), \(J^{+}(S \cup \{r\}) = \mathrm{DF}^{+}(S \cup \{r\}) = \mathrm{DF}^{+}(S)\). Consequently minimal SSA places a phi for variable \(v\) exactly at \(\mathrm{DF}^{+}(S_v)\), where \(S_v\) is the set of blocks assigning \(v\) (the entry holds the implicit initial definition).

Proof sketch (full proof: [CFRWZ91, §5.1])

\(\mathrm{DF}(r) = \emptyset\): \(r\) strictly dominates every other node and has no predecessors, so the last equality follows from Definition 15.3.2. \(\mathrm{DF}(X) \subseteq J(\{X, r\})\) for \(X \neq r\) (in full): let \(P\) witness \(Y \in \mathrm{DF}(X)\). Take a path \(r \leadsto P\) and its suffix \(\pi_1\) after the last occurrence of \(X\), extended by \(P \to Y\). Every node \(u\) of \(\pi_1\) before \(Y\) is dominated by \(X\): a path \(r \leadsto u\) avoiding \(X\) followed by the rest of \(\pi_1\) would reach \(P\) avoiding \(X\). Let \(\pi_2 : r \leadsto Y\) be a path whose nodes before \(Y\) avoid \(X\): if \(Y \neq X\) it exists because \(X\) does not strictly, hence does not at all, dominate \(Y\); if \(Y = X\) take a simple path \(r \leadsto X\). No node of \(\pi_2\) before \(Y\) is dominated by \(X\) (its prefix would reach it avoiding \(X\)), so \(\pi_1\) and \(\pi_2\) share only \(Y\): \(Y \in J(\{X, r\})\). Iterating gives \(\mathrm{DF}^{+}(S \cup \{r\}) \subseteq J^{+}(S \cup \{r\})\). \(J(S) \subseteq \mathrm{DF}^{+}(S)\) is the key lemma of [CFRWZ91, §5.1]: a path from \(X\) to a node that \(X\) does not strictly dominate passes through \(\mathrm{DF}^{+}(\{X\})\); two paths from different definitions meeting first at \(Y\) therefore bring \(Y\) into the iterated frontier. Iterating both inclusions gives equality. A phi is needed at \(Y\) exactly when two different definitions of \(v\) (the entry counts as one) reach \(Y\) along paths that first meet there, which is \(J^{+}(S_v \cup \{r\})\).

Algorithm 15.3.11 (Iterated DF by worklist)

Input: the frontier sets DF, a set \(S\) of definition blocks.
Output: \(\mathrm{DF}^{+}(S)\).
Precondition: DF[X] \(= \mathrm{DF}(X)\) for every \(X\).
Postcondition: result \(= \mathrm{DF}^{+}(S)\) (Definition 15.3.2).
Invariant: result \(\subseteq \mathrm{DF}^{+}(S)\), and every node popped from the worklist has all of its frontier in result (Theorem 15.3.17).

function IteratedDF(DF, S):
    result ← {}
    everOnWorklist ← S
    worklist ← S                                   # FIFO
    while worklist not empty:
        X ← pop the front of worklist
        for Y in DF[X]:
            if Y ∉ result:
                result ← result ∪ {Y}              # a phi goes into Y
                if Y ∉ everOnWorklist:             # the phi is a new definition
                    everOnWorklist ← everOnWorklist ∪ {Y}
                    append Y to worklist
    return result

This is the phi-placement loop of [CFRWZ91, §5.1] simplified to one variable. You implement it as computeIteratedDF(DF, Defs) (E10).

DJ graphs (Sreedhar–Gao)¶

Definition 15.3.12 (DJ graph)

The DJ graph of \(G\) has the nodes \(N\), a D edge \(\mathrm{idom}(y) \to y\) for every \(y \neq r\), and a J edge \(x \to y\) for every CFG edge with \(x \neq \mathrm{idom}(y)\) (by Lemma 15.3.4, exactly the CFG edges whose source does not strictly dominate their target).

Lemma 15.3.13 (Frontiers on the DJ graph)

\(y \in \mathrm{DF}(x)\) iff some J edge \(z \to y\) has \(z\) in \(x\)'s subtree of \(\mathcal{D}\) and \(\mathrm{level}(y) \le \mathrm{level}(x)\).

Proof

(\(\Rightarrow\)) Let \(P\) witness \(y \in \mathrm{DF}(x)\). By Lemma 15.3.7, \(x\) lies strictly below \(\mathrm{idom}(y)\) on \(P\)'s root path; so \(P \ne \mathrm{idom}(y)\) (else \(x\) would be on an empty path) and \(P \to y\) is a J edge with \(P\) in \(x\)'s subtree, and \(\mathrm{level}(y) = \mathrm{level}(\mathrm{idom}(y)) + 1 \le \mathrm{level}(x)\). (\(\Leftarrow\)) \(x \mathrel{\mathrm{dom}} z\). If \(x \mathrel{\mathrm{sdom}} y\) then \(x\) would be a proper ancestor of \(y\) in \(\mathcal{D}\) and \(\mathrm{level}(x) < \mathrm{level}(y)\), contradicting the hypothesis; so \(z\) witnesses \(y \in \mathrm{DF}(x)\).

Algorithm 15.3.14 (Sreedhar–Gao DF⁺ on the DJ graph)

Input: \(G\), \(\mathcal{D}\) with levels and DFS-in numbers, a set \(S\).
Output: \(\mathrm{DF}^{+}(S)\), without computing any frontier set.
Precondition: \(\mathcal{D}\) is the dominator tree of \(G\).
Postcondition: result \(= \mathrm{DF}^{+}(S)\) (Theorem 15.3.18).
Invariant: when a root at level \(\ell\) is popped, every result node deeper than \(\ell\) has been found, and every subtree walked so far has reported all of its J edges into levels \(\le\) the level of the root it was walked from.

function SreedharGaoIDF(G, D, S):
    PQ ← max-priority queue on (level(x), dfsIn(x)), containing every x ∈ S
    walked ← S                                      # nodes whose subtree walk is done or queued
    inResult ← {}
    result ← []
    while PQ not empty:
        root ← pop the maximum of PQ                # deepest first
        stack ← [root]
        while stack not empty:
            x ← pop stack
            for y in succs(x):                      # J edges and D edges alike
                if level(y) > level(root): continue # D edges and deeper J edges: not in the frontier
                if y ∈ inResult: continue
                inResult ← inResult ∪ {y}
                append y to result
                if y ∉ S: insert y into PQ          # a phi at y is a new definition
            for c in children_D(x):
                if c ∉ walked:
                    walked ← walked ∪ {c}
                    push c on stack
    return result

A D edge \(x \to y\) has \(\mathrm{level}(y) = \mathrm{level}(x) + 1 > \mathrm{level}(\mathit{root})\) because \(x\) is in root's subtree, so the level test filters D edges automatically; LLVM does not distinguish the two edge kinds. This is the formulation of IDFCalculatorBase::calculate [LLVM-IDF]; the Python oracle is idf_sreedhar_gao.

3. Worked example¶

The running example; its dominator tree (Lesson 15.1) with levels:

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

Cytron's bottom-up DF on the running example¶

Postorder of the dominator tree: D C G F E I H B A. One row per node in that order:

step	X	DF_local(X)	DF_up of each child Z	DF(X)
1	D	{E} (idom(E) = B ≠ D)	—	{E}
2	C	{H} (C→D is a tree edge: idom(D) = C)	from D: {E} (idom(E) ≠ C)	{E,H}
3	G	{E,H}	—	{E,H}
4	F	{} (F→G: idom(G) = F)	from G: {E,H} (idom(E) = B ≠ F, idom(H) = B ≠ F)	{E,H}
5	E	{H} (E→F is a tree edge)	from F: {E,H} (idom(E) = B ≠ E, idom(H) = B ≠ E)	{E,H}
6	I	{}	—	{}
7	H	{B} (idom(B) = A ≠ H)	from I: {}	{B}
8	B	{} (B→C, B→E are tree edges)	from C: {} (idom(E) = idom(H) = B); from E: {} ; from H: {B} (idom(B) = A ≠ B)	{B}
9	A	{}	from B: {} (idom(B) = A)	{}

Row 8 is the one to study: E and H drop out because B is their idom (B strictly dominates them), but B itself survives in DF(B) because B does not strictly dominate itself: B is a loop header reached by its own latch H.

CHK runners on the running example¶

Join nodes: B (preds A, H), E (preds B, D, G), H (preds C, E, G). Each runner walks up the dominator tree to idom(join), exclusive:

join Y	idom(Y)	from pred	runner path (Y added to DF of each)
B	A	A	— (A = idom(B))
B	A	H	H, B
E	B	B	— (B = idom(E))
E	B	D	D, C
E	B	G	G, F, E
H	B	C	C
H	B	E	E
H	B	G	G, F, E

Collecting: DF(B) = {B}, DF(C) = {E,H}, DF(D) = {E}, DF(E) = {E,H}, DF(F) = {E,H}, DF(G) = {E,H}, DF(H) = {B}, others {}: the same sets as Cytron's. With the early stop (the course solution's version, and GCC's), the last runner for H, from G, stops at E: E already received H from the runner that started at E, so everything above E on the way to B has it too.

Iterated DF by worklist on the running example¶

x is assigned in S = {C, F}:

step	pop	DF(pop)	added to DF⁺	worklist after	DF⁺ so far
0	—	—	—	C F	{}
1	C	{E,H}	{E,H}	F E H	{E,H}
2	F	{E,H}	—	E H	{E,H}
3	E	{E,H}	—	H	{E,H}
4	H	{B}	{B}	B	{B,E,H}
5	B	{B}	—	(empty)	{B,E,H}

DF⁺({C, F}) = {B, E, H}: three phis, including one at the outer loop header B that neither C's nor F's own frontier mentions. Adding the entry block (for an initial value stored in A) changes nothing, since DF(A) = ∅ (Theorem 15.3.10); tests/ch15/lit/frontiers.ll checks that mem2reg puts its phis exactly in B, E and H.

DJ graphs (Sreedhar–Gao) on the running example¶

J edges (CFG edges x → y with x ≠ idom(y)): C→H, E→H, D→E, H→B, G→H, G→E. Levels: A=0, B=1, C=2, E=2, H=2, D=3, F=3, I=3, G=4. DFS-in numbers of the dominator tree break ties.

step	pop root (level)	subtree walked	J edges with level(y) ≤ level(root), y new	result so far	queue after (top first)
0	—	—	—	[]	F (3), C (2)
1	F (3)	F, G	G→H (2 ≤ 3), G→E (2 ≤ 3)	[H, E]	H (2), E (2), C (2)
2	H (2)	H, I	H→B (1 ≤ 2)	[H, E, B]	E (2), C (2), B (1)
3	E (2)	E (F already walked)	E→H: H already in result	[H, E, B]	C (2), B (1)
4	C (2)	C, D	C→H, D→E: already in result	[H, E, B]	B (1)
5	B (1)	B, H, E (C is in S, so it was marked from the start; H and E were walked as roots but never marked, so B's walk visits them again; their children I and F are marked)	H→B: B already in result	[H, E, B]	(empty)

Same answer, {B, E, H}. Only the definition blocks and nodes reached as dominator-tree children are marked walked; a node popped as a root (H, E) is not, so a later, shallower root can walk it once more (step 5). Each node is therefore walked at most twice, once as a root and once as a child, which keeps the bound linear. This is exactly what LLVM does: IDFCalculatorBase::calculate inserts the definition blocks and the children into VisitedWorklist, but not the roots it pops.

Try it

./course drill idf --seed 4 --difficulty medium --solution prints all three traces (Cytron, worklist, DJ graph) for a random CFG and assignment set; ./course drill dominators --difficulty medium --solution adds the CHK runners.

4. Invariants and correctness¶

Cytron's bottom-up DF¶

Theorem 15.3.15 (Correctness of Algorithm 15.3.6)

Algorithm 15.3.6 terminates and computes \(\mathrm{DF}(X)\) for every \(X\).

Proof

Invariant: the postorder of \(\mathcal{D}\) visits all children of \(X\) before \(X\), so when \(X\) is processed every DF[Z] for a child \(Z\) is final (by induction on the height of the subtree). The loop body then computes exactly the right-hand side of Theorem 15.3.5, with the filter \(\mathrm{idom}(Y) \neq X\) of Definition 15.3.3. Termination: one visit per node, one scan per successor edge and per element of each child's frontier.

When it breaks: processing in any order other than children-first; using CFG edges from unreachable predecessors (they are not dominated by anything and must be ignored).

CHK runners¶

Theorem 15.3.16 (Correctness of Algorithm 15.3.8)

Algorithm 15.3.8, with or without the early stop, computes \(\mathrm{DF}(X)\) for every \(X\).

Proof

By Lemma 15.3.7 the runners of join \(Y\) add \(Y\) to exactly the nodes \(X\) with \(Y \in \mathrm{DF}(X)\), and non-join nodes are in no frontier. Each runner climbs a finite tree path and reaches \(\mathrm{idom}(Y)\), because \(\mathrm{idom}(Y)\) is an ancestor of every predecessor. Early stop: if DF[runner] already holds \(Y\), an earlier runner for the same \(Y\) passed runner and continued up to \(\mathrm{idom}(Y)\) along the same tree path, so the rest of the walk would add nothing new.

When it breaks: a join node whose only reachable predecessor is idom(Y) (the others unreachable): count only reachable predecessors, as the course solution does.

Iterated DF by worklist¶

Theorem 15.3.17 (Correctness of Algorithm 15.3.11)

Algorithm 15.3.11 terminates and returns \(\mathrm{DF}^{+}(S)\); moreover \(\mathrm{DF}^{+}(S)\) is the least set \(R\) with \(\mathrm{DF}(S \cup R) \subseteq R\).

Proof

Least closed set: \(L = \mathrm{DF}^{+}(S)\) satisfies \(\mathrm{DF}(S \cup L) = L\) (the sequence of Definition 15.3.2 is constant from some \(i\) on). If \(\mathrm{DF}(S \cup R) \subseteq R\), then by induction \(\mathrm{DF}_i(S) \subseteq R\) for all \(i\), so \(L \subseteq R\). Termination: each node enters the worklist at most once (everOnWorklist). Soundness: by induction on the steps, every node added to result is in \(\mathrm{DF}(X)\) for a popped \(X \in S \cup\) result, hence in \(L\) (as \(L\) is closed). Completeness: at the end every node of \(S \cup\) result has been popped (it entered the worklist when it entered \(S\) or result), so \(\mathrm{DF}(S \cup \texttt{result}) \subseteq \texttt{result}\) and \(L \subseteq\) result by leastness.

When it breaks: forgetting that a phi is a definition (not re-queuing Y) gives \(\mathrm{DF}(S)\) instead of \(\mathrm{DF}^{+}(S)\): the missing B in the example.

DJ graphs (Sreedhar–Gao)¶

Theorem 15.3.18 (Correctness of Algorithm 15.3.14)

Algorithm 15.3.14 terminates, walks every node at most twice, and returns \(\mathrm{DF}^{+}(S)\).

Proof sketch (full proof: [SG95, §4])

Claim: after a root \(x\) is processed, \(\mathrm{DF}(x) \subseteq\) result. By Lemma 15.3.13, \(y \in \mathrm{DF}(x)\) iff some J edge \(z \to y\) has \(z\) in \(x\)'s subtree and \(\mathrm{level}(y) \le \mathrm{level}(x)\). Nodes of \(x\)'s subtree walked now report exactly such edges. A node of \(x\)'s subtree walked earlier was walked from a root \(x'\) popped earlier, so \(\mathrm{level}(x') \ge \mathrm{level}(x)\) (queue order), and \(x'\) lies inside \(x\)'s subtree (an ancestor of \(x\) would be shallower); that walk already reported every J edge with \(\mathrm{level}(y) \le \mathrm{level}(x')\), which includes those with \(\mathrm{level}(y) \le \mathrm{level}(x)\). Every element of \(S\) and of result becomes a root, so result \(\supseteq \mathrm{DF}^{+}(S)\) by Theorem 15.3.17's leastness; conversely every reported \(y\) is in DF of the root that found it, so result \(\subseteq \mathrm{DF}^{+}(S)\). Termination: each node is queued at most once (inResult), walked at most once as a popped root and at most once as a dominator-tree child (walked).

When it breaks: popping in any order other than decreasing level (a shallow root would walk and mark a subtree before a deeper root needed it).

5. Complexity¶

\(n\) = nodes, \(m\) = edges, \(\lvert \mathrm{DF} \rvert = \sum_X \lvert \mathrm{DF}(X) \rvert\), \(\lvert S \rvert\) = assignment blocks.

Technique	Time (worst)	Time (typical)	Space	Notes
Cytron DF	\(O(m + \lvert \mathrm{DF} \rvert)\)	linear	\(O(\lvert \mathrm{DF} \rvert)\)	output-sensitive
CHK runners	\(O(m + \lvert \mathrm{DF} \rvert)\)	linear, fewest instructions	\(O(\lvert \mathrm{DF} \rvert)\)	only join nodes do work
Iterated DF worklist	\(O(\lvert \mathrm{DF} \rvert)\) per query (after DF)	tiny	\(O(n)\)	plus the cost of DF
DJ graph / Sreedhar–Gao	\(O(n + m)\) per query (\(O(n \log n + m)\) with a heap, as in LLVM)	linear	\(O(n)\)	no DF sets needed

Proposition 15.3.19 (Output-sensitive bounds)

Algorithms 15.3.6 and 15.3.8 run in \(O(m + \lvert \mathrm{DF} \rvert)\); Algorithm 15.3.11 in \(O(n + \lvert \mathrm{DF} \rvert)\); Algorithm 15.3.14 in \(O(n + m)\) plus the priority-queue cost.

Proof

Cytron: each successor edge is examined once in \(\mathrm{DF}_{\mathrm{local}}\), and each element of a child's frontier once in \(\mathrm{DF}_{\mathrm{up}}\); the child frontiers sum to at most \(\lvert \mathrm{DF} \rvert\) (each is a frontier). CHK with early stop: every runner step adds a new element to some DF[X] or stops, so steps \(\le \lvert \mathrm{DF} \rvert +{}\) (one stop per predecessor edge). Worklist: each node is popped at most once and its frontier scanned once. Sreedhar–Gao: each node is walked at most twice (once as a root, once as a child) and its out-edges are scanned each time; each node enters the queue at most once.

Pathological input: nested repeat-until loops. With \(k\) nested loops — \(R \to H_1\), \(H_i \to H_{i+1}\) (\(i < k\)), \(H_k \to T_k\), \(T_i \to H_i\), \(T_i \to T_{i-1}\) (\(i > 1\)), \(T_1 \to X\) — the idoms are \(H_{i+1} \mapsto H_i\), \(T_k \mapsto H_k\), \(T_{i-1} \mapsto T_i\), so the subtree of \(H_i\) or of \(T_i\) contains the tails \(T_1, \dots, T_i\), whose J edges \(T_j \to H_j\) lead to the levels of \(H_1, \dots, H_i\). By Lemma 15.3.13, \(\mathrm{DF}(H_i) = \mathrm{DF}(T_i) = \{H_1, \dots, H_i\}\), so \(\lvert \mathrm{DF} \rvert = k(k+1) = \Theta(n^2)\) for \(n = 2k + 2\) nodes (the course oracles report 20 entries for \(k = 4\) and 1 056 for \(k = 32\)), while \(\mathrm{DF}^{+}\) of any single block has at most \(k\) elements. Cytron and CHK must write every one of those entries; Sreedhar–Gao never builds them.

At scale: Cytron et al. measured frontier sizes on real Fortran programs and found them roughly linear in program size [CFRWZ91, §8]; the quadratic case needs deep nests of loops sharing exits, which real code rarely has but machine-generated code (and fuzzers) can. LLVM chose the DJ-graph algorithm for mem2reg, which runs on every function in every pipeline, to be immune to it.

Cytron's bottom-up DF¶

Iterative bottom-up with an explicit worklist (LLVM's DominanceFrontierBase::analyze uses a DFCalculateWorkObject stack instead of recursion) [LLVM-DFImpl] — trade-off: no stack overflow, more code.
Bit-vector frontiers — trade-off: \(O(n^2)\) bits but very fast unions; GCC stores frontiers as bitmaps.
Post-dominance frontiers by running it on the reverse CFG (Lesson 15.4) — trade-off: none; that is how control dependence is computed.

CHK runners¶

Early stop when the runner's DF already contains Y (GCC, the course solution) — trade-off: none; avoids re-walking shared tree paths.
Frontiers of only some nodes (walk runners, but record only nodes in a set of interest) — trade-off: cheaper when you only need DF of the assignment blocks.

Iterated DF by worklist¶

Pruned SSA: intersect with the blocks where the variable is live-in (LLVM's IDFCalculator::setLiveInBlocks) [CCF91] — trade-off: needs liveness, removes dead phis.
Merge sets (Das & Ramakrishna) [DR05]: precompute \(M(X) = \mathrm{DF}^{+}(\{X\})\) once with a DJ-graph-based iteration, then \(\mathrm{DF}^{+}(S) = \bigcup M(X)\) — trade-off: fast for many queries, quadratic space.

DJ graphs (Sreedhar–Gao)¶

Linear-time loop detection on DJ graphs [SGL96] — trade-off: the same structure finds loops and irreducible regions (Lesson 15.5).
Incremental DJ-graph updates [SGL97] — trade-off: keeps DF⁺ queries cheap under CFG changes, much more code.
Heap vs bucket queue: LLVM uses std::priority_queue keyed by (level, DFS-in) for determinism — trade-off: \(O(n \log n)\) instead of \(O(n)\), but stable output order.

7. In real compilers¶

Cytron's bottom-up DF¶

LLVM

llvm/include/llvm/Analysis/DominanceFrontierImpl.h — DominanceFrontierBase<BlockT, IsPostDom>::analyze: DF_local over CFG children, then DF_up from dominator-tree children, with a work stack instead of recursion; exposed as DominanceFrontierAnalysis and print<domfrontier> (llvm/lib/Analysis/DominanceFrontier.cpp, LLVM 23.1.2) [LLVM-DFImpl]. Few passes still use it; mem2reg switched to IDFCalculator.

Pebble your computeDominanceFrontier(…, DFAlgorithm::Cytron) (E8), printed by print<pebble-domfrontier>.

Cytron frontiers of the running example, from C

Reproduce (clang 23.1.2, opt 23.1.2; running.c is the running example written with gotos, as in Lesson 15.1, section 7; simplifycfg fuses G into F):

cat > running.c <<'EOF'
void work(int);
void running(int *c) {
B:  if (c[0]) goto C; goto E;
C:  if (c[1]) goto D; goto H;
D:  work(4); goto E;
E:  if (c[2]) goto F; goto H;
F:  work(6); goto G;
G:  if (c[3]) goto H; goto E;
H:  if (c[4]) goto I; goto B;
I:  return;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm running.c -o running.ll
opt -passes='simplifycfg,print<domfrontier>' -disable-output running.ll 2>&1 | LC_ALL=C sort

Output (complete):

  DomFrontier for BB %B is:  %B
  DomFrontier for BB %C is:  %H %E
  DomFrontier for BB %D is:  %E
  DomFrontier for BB %E is:  %H %E
  DomFrontier for BB %F is:  %H %E
  DomFrontier for BB %H is:  %B
  DomFrontier for BB %I is: 
  DomFrontier for BB %entry is: 
DominanceFrontier for function: running

What to notice: the sets are the lesson's (with F standing for F+G): \(\mathrm{DF}(C) = \{E, H\}\), \(\mathrm{DF}(D) = \{E\}\), the loop headers in their own frontiers (\(B \in \mathrm{DF}(B)\), \(E \in \mathrm{DF}(E)\)), and \(\mathrm{DF}(\texttt{entry}) = \emptyset\) (Theorem 15.3.10's "adding \(r\) changes nothing"). DominanceFrontierBase::analyze builds them exactly as Algorithm 15.3.6: DF_local from the successors, DF_up from the tree children, children first. The printer walks a DenseMap keyed by block pointers, so its line order changes from run to run; the sort (with LC_ALL=C, so macOS and Linux collate alike) makes the output reproducible. The order within a line is stable: each frontier is a SetVector.

CHK runners¶

GCC 15 gcc/cfganal.cc — compute_dominance_frontiers: the runner loop over the predecessors of every block with EDGE_COUNT (b->preds) >= 2, stopping as soon as bitmap_set_bit reports the bit was already set; the comment explains that "the number of nodes touched by this algorithm is equal to the size of the dominance frontiers" [GCC-Cfganal].
Go 1.25 does not build frontiers at all (see the DJ-graph entry below).
Pebble your computeDominanceFrontier(…, DFAlgorithm::CHK) (E9), print<pebble-domfrontier;chk>.

GCC places phis at join nodes found by runners

Reproduce (gcc-14 = GCC 14.2.0, Ubuntu build 14.2.0-4ubuntu2~24.04.1, the newest GCC in the course container; the source pointers above are to the gcc-15 branch; any Linux):

cat > phis.c <<'EOF'
int h(int n, int c) {
  int x = 0;
  for (int i = 0; i < n; i++) {
    if (c)
      x = i;
    else
      x = x + 1;
  }
  return x;
}
EOF
gcc-14 -O1 -fdump-tree-ssa=phis.ssa -c phis.c -o /dev/null
sed -n '/^int h/,$p' phis.ssa

Output (complete from the function header on):

int h (int n, int c)
{
  int i;
  int x;
  int _7;

  <bb 2> :
  x_4 = 0;
  i_5 = 0;
  goto <bb 7>; [INV]

  <bb 3> :
  if (c_9(D) != 0)
    goto <bb 4>; [INV]
  else
    goto <bb 5>; [INV]

  <bb 4> :
  x_11 = i_3;
  goto <bb 6>; [INV]

  <bb 5> :
  x_10 = x_2 + 1;

  <bb 6> :
  # x_1 = PHI <x_11(4), x_10(5)>
  i_12 = i_3 + 1;

  <bb 7> :
  # x_2 = PHI <x_4(2), x_1(6)>
  # i_3 = PHI <i_5(2), i_12(6)>
  if (i_3 < n_6(D))
    goto <bb 3>; [INV]
  else
    goto <bb 8>; [INV]

  <bb 8> :
  _7 = x_2;
  return _7;

}

What to notice: GCC's into-SSA pass computes all frontiers with the runner loop of compute_dominance_frontiers and then places phis. Only the join blocks <bb 6> (preds 4 and 5, the two arms of if (c)) and <bb 7> (the loop header, preds 2 and 6) receive PHI nodes: non-join blocks are in no frontier (Lemma 15.3.7). The runners from 4 and 5 stop at \(\mathrm{idom}(6) = 3\), putting 6 into \(\mathrm{DF}(4)\) and \(\mathrm{DF}(5)\); i, assigned only in 2 and 6, gets a phi only in 7.

Iterated DF by worklist¶

GCC 15 gcc/cfganal.cc — compute_idf: the worklist of CFRWZ91 over bitmaps; gcc/tree-into-ssa.cc — insert_phi_nodes calls it for every variable [GCC-Cfganal].
Pebble your computeIteratedDF (E10), used by Ch 16's pebble-mem2reg.

GCC's DF⁺ for x assigned in C and F: phis at B, E, H

Reproduce (gcc-14 = GCC 14.2.0, Ubuntu build 14.2.0-4ubuntu2~24.04.1):

cat > defs.c <<'EOF'
void work(int);
int running(int *c) {
  int x = 0;
B:  if (c[0]) goto C; goto E;
C:  x = 1; if (c[1]) goto D; goto H;
D:  work(4); goto E;
E:  if (c[2]) goto F; goto H;
F:  x = x + 6; goto G;
G:  if (c[3]) goto H; goto E;
H:  if (c[4]) goto I; goto B;
I:  return x;
}
EOF
gcc-14 -O1 -fdump-tree-ssa-details=defs.ssa -c defs.c -o /dev/null
grep -E '^creating PHI' defs.ssa
grep -E '^[A-I]:$|^  <bb [0-9]+> :$|x_[0-9]+ = ' defs.ssa

Output (complete, filtered by the two greps):

creating PHI node in block #3 for x
creating PHI node in block #8 for x
creating PHI node in block #13 for x
creating PHI node in block #3 for .MEM
creating PHI node in block #8 for .MEM
creating PHI node in block #13 for .MEM
  <bb 2> :
  x_16 = 0;
  <bb 3> :
  # x_10 = PHI <x_16(2), x_12(15)>
B:
  <bb 4> :
  x_19 = 1;
  <bb 5> :
  <bb 6> :
  <bb 7> :
  <bb 8> :
  # x_11 = PHI <x_10(5), x_19(6), x_21(12)>
E:
  <bb 9> :
  x_21 = x_11 + 6;
  <bb 10> :
  <bb 11> :
  <bb 12> :
  <bb 13> :
  # x_12 = PHI <x_19(7), x_11(10), x_21(11)>
H:
  <bb 14> :
  <bb 15> :

What to notice: defs.c is the running example with x assigned in the entry, in C and in F. GCC's insert_phi_nodes asks compute_idf for \(\mathrm{DF}^{+}(\{\text{entry}, C, F\})\) and creates phis in blocks 3, 8 and 13, which are the blocks labelled B, E and H: exactly the worked example's \(\{B, E, H\}\). The phi at 3 (B) comes only from the iterated step: B is in the frontier of H, which is in the frontier of C and F (Algorithm 15.3.11). The .MEM phis are GCC's virtual SSA name for memory, defined by the calls to work in D and F.

DJ graphs (Sreedhar–Gao)¶

LLVM

llvm/include/llvm/Support/GenericIteratedDominanceFrontier.h — IDFCalculatorBase::calculate: a std::priority_queue of dominator-tree nodes keyed by (level, DFS-in number), a subtree walk with VisitedWorklist, and the SuccLevel > RootLevel filter; llvm/include/llvm/Analysis/IteratedDominanceFrontier.h — ForwardIDFCalculator/ReverseIDFCalculator [LLVM-IDF]. Users: PromoteMem2Reg::run in llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp (with setLiveInBlocks for pruned SSA) [LLVM-Mem2Reg] and ADCE (LLVM 23.1.2).

Go 1.25 src/cmd/compile/internal/ssagen/phi.go — phiState.insertVarPhis: "For large functions, we use Sreedhar & Gao"; a blockHeap priority queue ordered by dominator-tree level, exactly the loop above. Functions below smallBlocks = 500 use Braun et al.'s on-the-fly construction instead (Ch 16) [Go-Phi].
Cranelift and V8 avoid frontiers entirely by building SSA on the fly (Braun et al.), as Ch 16 explains.

LLVM's mem2reg (IDFCalculator) on the same program

Reproduce (clang 23.1.2, opt 23.1.2):

cat > defs.c <<'EOF'
void work(int);
int running(int *c) {
  int x = 0;
B:  if (c[0]) goto C; goto E;
C:  x = 1; if (c[1]) goto D; goto H;
D:  work(4); goto E;
E:  if (c[2]) goto F; goto H;
F:  x = x + 6; goto G;
G:  if (c[3]) goto H; goto E;
H:  if (c[4]) goto I; goto B;
I:  return x;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm defs.c -o defs.ll
opt -passes=mem2reg -S defs.ll | grep -E '^[A-I]:|= phi'

Output (complete, filtered by the grep):

B:                                                ; preds = %if.end16, %entry
  %x.0 = phi i32 [ 0, %entry ], [ %x.2, %if.end16 ]
C:                                                ; preds = %if.then
D:                                                ; preds = %if.then3
E:                                                ; preds = %if.end12, %D, %if.end
  %x.1 = phi i32 [ 1, %D ], [ %add, %if.end12 ], [ %x.0, %if.end ]
F:                                                ; preds = %if.then7
G:                                                ; preds = %F
H:                                                ; preds = %if.then11, %if.end8, %if.end4
  %x.2 = phi i32 [ %add, %if.then11 ], [ %x.1, %if.end8 ], [ 1, %if.end4 ]
I:                                                ; preds = %if.then15

What to notice: LLVM computes the same \(\mathrm{DF}^{+} = \{B, E, H\}\) without any frontier set: IDFCalculatorBase::calculate pops the defining blocks deepest-first and walks their dominator subtrees, each node at most twice (Algorithm 15.3.14). Each phi has one operand per predecessor, including clang's empty if.then*/if.end* blocks that carry the gotos. mem2reg also passes the live-in blocks (pruned SSA, [CCF91]); here x is live into all three, so nothing is pruned.

Find where LLVM does it. Open llvm/include/llvm/Support/GenericIteratedDominanceFrontier.h (LLVM 23.1.2) and read IDFCalculatorBase::calculate. Question: the priority queue orders dominator-tree nodes by a pair; which tree property is the first component of that pair? (Quiz llvm-where-idf.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Cytron DF	all DF sets	O(n + Σ\|DF\|) but Θ(n²) output on nested repeat-until loops · fast	explicit sets for every node	~30 lines	LLVM `DominanceFrontier`, classic SSA
CHK runners	all DF sets	same bound; touches only join nodes · fastest in practice	same sets	~15 lines	GCC `compute_dominance_frontiers`
Iterated DF worklist	DF⁺ of any set	O(Σ\|DF\|) after DF · needs all DF sets	phi blocks	~15 lines	GCC `compute_idf`, Cytron SSA
DJ graph / Sreedhar–Gao	DF⁺ without DF sets	O(n + m) per query · no quadratic DF	phi blocks, deterministic order	~50 lines	LLVM `IDFCalculator` (mem2reg, ADCE), Go (≥ 500 blocks)

Choose Cytron's DF when you need every frontier explicitly and already walk the dominator tree bottom-up (or want the proof-friendly formulation). Choose CHK runners when you want the least code and the fastest frontier computation on normal CFGs. Choose the worklist DF⁺ when you have frontiers anyway and place phis for a few variables. Choose Sreedhar–Gao when you place phis for many variables in large or machine-generated functions: it is linear per query with no quadratic intermediate.

The oracle tests compare Cytron and CHK with llvm::DominanceFrontier on the corpus and 1 650 random CFGs, and your worklist DF⁺ with ForwardIDFCalculator on 18 definition sets per function (ch15.CytronDF.*, ch15.CHKDF.*, ch15.IteratedDF.*).

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch15.yaml`)	Drill	Flashcard tag	Exercises
Cytron DF	`df-sets`, `frontier-theorems`	`./course drill idf --difficulty medium`	`cytron-df`	E8
CHK runners	`df-sets`, `df-runner`, `frontier-theorems`	`./course drill dominators --difficulty medium`	`chk-df`	E9
Iterated DF worklist	`idf-phis`, `llvm-where-idf`	`./course drill idf`	`idf-worklist`	E10
DJ graph / Sreedhar–Gao	`idf-phis`, `llvm-where-idf`	`./course drill idf --solution` (DJ-graph cross-check)	`dj-graph`	— (checked through `IDFCalculator`)

DF(X) is not \"the join points after X\"

DF(X) is where X's dominance ends. A join node that X strictly dominates (E and H relative to B) is not in DF(B), and a node can be in its own frontier (B ∈ DF(B)). Test yourself on the loop header: its frontier contains itself whenever it dominates its latch.

References¶

See the chapter references.

Lesson 15.3 — Dominance frontiers¶

1. Problem and motivation¶

Cytron's bottom-up DF¶

CHK runners¶

Iterated DF by worklist¶

DJ graphs (Sreedhar–Gao)¶

2. Definitions and algorithms¶

Cytron's bottom-up DF¶

CHK runners¶

Iterated DF by worklist¶

DJ graphs (Sreedhar–Gao)¶

3. Worked example¶

Cytron's bottom-up DF on the running example¶

CHK runners on the running example¶

Iterated DF by worklist on the running example¶

DJ graphs (Sreedhar–Gao) on the running example¶

4. Invariants and correctness¶

Cytron's bottom-up DF¶

CHK runners¶

Iterated DF by worklist¶

DJ graphs (Sreedhar–Gao)¶

5. Complexity¶

6. Variants and refinements¶

Cytron's bottom-up DF¶

CHK runners¶

Iterated DF by worklist¶

DJ graphs (Sreedhar–Gao)¶

7. In real compilers¶

Cytron's bottom-up DF¶

CHK runners¶

Iterated DF by worklist¶

DJ graphs (Sreedhar–Gao)¶

8. Comparison¶

9. Assessment¶

References¶