Chapter 15 exercises

You implement Pebble's control-flow analyses: depth-first numbering, five dominator algorithms (CHK is the one the Pebble analyses use), dominance frontiers two ways, iterated frontiers, post-dominators, control dependence, natural loops, Havlak's loop forest and a reducibility test. The comparison lab (labs/ch15-dominance/SPEC.md) then times your algorithms against each other and against LLVM.

The contract

Everything the tests, the opt printers and the lab call is declared in one header, pebble/include/pebble/Analysis/Dominance.h: nine functions marked YOU plus the flag function implementsAlgorithm. Read that header first; each function's comment states its exact input and output.

Function	Exercise	What it returns
computeDFS(G)	E1	pre/post/RPO sequences and numbers, parents, LastDesc, edge kinds (DFSResult)
computeIdoms(G, D, A, Stats)	E2–E6	immediate dominators with algorithm A (IdomVector), plus pass/finger counts
implementsAlgorithm(A)	E5, E6	whether the optional algorithms are done (their tests are skipped until then)
computeDominanceFrontier(G, DT, A)	E8, E9	\(\mathrm{DF}(X)\) for every node, Cytron or CHK (NodeSets)
computeIteratedDF(DF, Defs)	E10	\(\mathrm{DF}^{+}(\mathit{Defs})\), sorted
computePostDominators(G, Roots)	E11	ipdom of every node, plus the virtual exit as node G.size()
computeControlDependence(G, PDT)	E12	\(\mathrm{CD}(Y)\) for every node
computeNaturalLoops(G, DT)	E13	the LoopInfo forest (LoopForest)
computeHavlakLoops(G, D)	E14	the CycleInfo forest for the same DFS
isReducibleT1T2(G, LimitSize)	E15	the T1/T2 verdict and the limit-graph size

Your code goes anywhere under pebble/lib/Analysis/Dominance/src/: every *.cpp there is compiled (read src/README.md). Design your own files, classes and helpers; delete src/Stub.cpp once you have replaced its functions. Provided (not exercises): the graph adapters DiGraph/FunctionCFG (Graph.h), the dominator tree class DomTree with \(O(1)\) queries (DomTree.h), LLVM's choice of post-dominator roots (findPostDomRoots), and the opt printer passes in pebble/lib/Passes/Dominance/Ch15Passes.cpp.

./course test 15                                  # builds, then runs every test labelled ch15
ctest --preset linux -L '^ch15$' -R CHK           # one suite while iterating (macos: --preset macos)
opt -load-pass-plugin=build/linux/lib/PebblePasses.so -passes='print<pebble-domtree>' \
    -disable-output tests/ch15/Inputs/running-example.ll

Before you start, every ch15 test fails with TODO(ch15): E<n>: …, except the tests of provided code (ch15.Graph.*, ch15.DomTree.*, ch15.PostDomRoots.*, ch15.RunningExample.LessonTablesMatchLLVM, ch15.DomAlgorithms.RequiredOnesAreImplemented) and the optional ★ suites, which are skipped. Each message names the step below that fixes it.

How the tests judge you. Every algorithm is compared with LLVM's own analysis (the oracle): DominatorTree, PostDominatorTree, DominanceFrontier, IDFCalculator, LoopInfo, CycleInfo, containsIrreducibleCFG. Each suite runs on the hand-written corpus in tests/ch15/Inputs/*.ll (irreducible CFGs, infinite loops, unreachable blocks, self loops, switches with duplicate targets, clang output for Duff's device and gotos) and on 1 650 random CFGs generated from a fixed seed. A failure prints the function and its CFG in the lessons' A -> B, C notation, so you can paste it into a drill or trace it by hand. Tests that are not about DFS use a reference DFS built with LLVM's iterators, and tests that need a dominator or post-dominator tree build it from LLVM's idoms, so each exercise can be solved independently of the others, except where the dependencies below say otherwise.

Dependencies. E11 calls a dominator algorithm on the reverse graph (use your E1 and E3). The RunningExample.Your* tests, DomTreeUpdates.*, the lit tests (the plugin runs everything, through buildDomTreeCHK and buildPostDomTree) and the lab need all required steps.

General requirements (every exercise):

• G1. Results follow the conventions at the top of Dominance.h: unreachable nodes are in no tree, frontier or loop (NoNode or empty); node sets are sorted and duplicate-free.
• G2. No recursion per node: the tests run DFS on a 200 000-node chain and the lab on 100 000-block graphs.
• G3. Complexity: E1, E8–E10, E12, E13 linear or output-sensitive as in the lessons' section 5; the lab's performance targets are in its spec.

Stuck? Work through the hints in order. The reference solution is in solutions/pebble/lib/Analysis/Dominance/src/ (one possible design among many), but only look at it after you've passed the tests, or after an honest hour.

---

E1 · Depth-first numbering and edge kinds

Contract: DFSResult computeDFS(const DiGraph &G) · Tests: ch15.DFS.*, and the lit test dfs-and-control-deps.ll through print<pebble-dfs>

Implement a depth-first search from G.entry() that tries successors in listed order (Lesson 15.5, Algorithm 15.5.2).

Requirements: - R1.1 Fill every field of DFSResult: the three sequences, the three number arrays, Parent, LastDesc and Kinds (one EdgeKind per successor, in successor order, Definition 15.5.1). - R1.2 Unreachable nodes get NoNode in every array and empty Kinds; the empty graph gives empty sequences. - R1.3 Iterative: DFS.DeepChainDoesNotOverflowTheStack runs it on a 200 000-node chain.

What the tests check: every field against a DFS built with LLVM's depth_first/post_order iterators; the RPO against ReversePostOrderTraversal; the retreating edges against llvm::FindFunctionBackedges; each edge kind against Definition 15.5.1.

Hint 1 — where to start

Keep an explicit stack of frames {node, index of the next successor to try} and an "on stack" flag per node. A node is entered when pushed (preorder) and finished when its frame has no successors left (postorder).

Hint 2 — the key idea

Classify an edge u → v at the moment you look at it: v unvisited → tree (and push v); v on the stack → back (retreating), including u = v; otherwise forward if pre(v) > pre(u), cross if not. When u finishes, every node numbered since u was entered is a descendant, so LastDesc[u] is simply the current preorder count minus one.

Hint 3 — a design sketch

One loop over the stack; read the top frame's node and successor index into locals before pushing a new frame (pushing may reallocate). The common bug the tests catch is RPO computed as the reverse of the preorder: RPO is the reverse of the postorder (compare ReversePostOrderTraversal in the failure message).

Done when: ch15.DFS.* pass.

---

E2 · Dominators by iterative dataflow

Contract: computeIdoms(G, D, DomAlgorithm::Iterative, Stats) · Tests: ch15.IterativeDominators.*, ch15.CHK.CountsPassesAndFingerSteps, ch15.RunningExample.YourDFSAndDominators

Compute \(\mathrm{Dom}(n)\) for every reachable node by round-robin iteration in RPO until a pass changes nothing, then derive immediate dominators from the sets (Lesson 15.1, Algorithm 15.1.11).

Requirements: - R2.1 Return LLVM's immediate dominators (NoNode for the entry and unreachable nodes). - R2.2 If Stats is non-null, Stats->Passes counts the passes including the final one that changes nothing: 2 on the running example, 3 on @chk_irreducible.

What the tests check: idoms against llvm::DominatorTree on the corpus and 860 random CFGs; the pass counts above.

Hint 1 — where to start

Use D's RPO as the iteration order. Represent ⊤ as a set of all reachable nodes; the entry's set is {entry}.

Hint 2 — the key idea

New set = ⊤ ∩ Dom(p) over reachable predecessors p, plus the node itself. Skip unreachable predecessors: they are not ⊤-like; including them would intersect with an empty set.

Hint 3 — a design sketch

A bit vector per node (llvm::BitVector works well). For the idoms, the strict dominators of n form a chain (Theorem 15.1.6), so the idom is the strict dominator whose own set is largest.

Done when: ch15.IterativeDominators.* pass.

---

E3 · Cooper–Harvey–Kennedy

Contract: computeIdoms(G, D, DomAlgorithm::CHK, Stats) · Tests: ch15.CHK.*, ch15.LabAgreement.*, ch15.DomTreeUpdates.*

Implement CHK exactly as in Lesson 15.1, Algorithm 15.1.12: passes over the RPO, Intersect walking two fingers up the partial tree by postorder number. This is the algorithm behind the pebble-domtree analysis that later chapters use.

Requirements: - R3.1 Return LLVM's immediate dominators. - R3.2 Fill Stats->Passes (as in E2) and Stats->FingerSteps (total finger moves inside Intersect, positive on the running example). - R3.3 The bichain of Proposition 15.1.31(c) with 40 nodes needs at least 39 passes (CHK.BichainNeedsOnePassPerNode): you must implement the round-robin algorithm, not a different one behind the same name.

What the tests check: idoms against LLVM on the corpus, 1 650 random CFGs and six 2 000–5 000-block CFGs; the pass counts; after random edits made through LLVM's DomTreeUpdater, your CHK from scratch equals LLVM's incrementally maintained tree.

Hint 1 — where to start

Use an idom array initialised to NoNode as the doms array: set the entry to itself while iterating and back to NoNode at the end. "Processed" then means "not NoNode", which also skips unreachable predecessors.

Hint 2 — the key idea

In Intersect, the finger with the smaller postorder number is deeper, so it moves up; loop until the fingers meet (Lemma 15.1.24(b)).

Hint 3 — a design sketch

Take the first processed predecessor as the starting candidate and fold the others in with Intersect. The tests catch two classic bugs: comparing preorder numbers with < (the wrong finger moves) and forgetting that the entry must temporarily be its own idom (the fingers never meet at the root).

Done when: ch15.CHK.* pass.

---

E4 · Lengauer–Tarjan, simple linking

Contract: computeIdoms(G, D, DomAlgorithm::LengauerTarjan) · Tests: ch15.LengauerTarjan.*, ch15.LabAgreement.*

Implement the four steps of Lesson 15.1, Algorithm 15.1.17 using D.Preorder as the DFS: semidominators with EVAL/LINK, buckets, implicit idoms, then the explicit pass.

Requirements: - R4.1 Return LLVM's immediate dominators. - R4.2 \(O(m \log n)\) (Proposition 15.1.30); no recursion in COMPRESS.

What the tests check: idoms against LLVM on the corpus, 1 650 random CFGs and the large lab CFGs.

Hint 1 — where to start

Rename nodes to preorder numbers 1..n (D.PreNum[x] + 1) and keep every array indexed by number, with 0 as the "no vertex" sentinel. You need: vertex, parent, semi, ancestor, label, dom, and a bucket per vertex.

Hint 2 — the key idea

EVAL(v) is v itself while v is unlinked (then its semi is its own number); after LINK it returns the vertex with the smallest semi on v's forest path, compressing the path. Drain bucket(parent(w)) right after LINK(parent(w), w).

Hint 3 — a design sketch

A bucket can be a singly linked list in two arrays (head per vertex, next per vertex). Write COMPRESS iteratively: collect the path, then update labels from the top down. The most common wrong answer the tests report is idom(w) = sdom(w) everywhere: step 4 (if dom[w] ≠ semi[w]: dom[w] ← dom[dom[w]], in increasing order) is missing.

Done when: ch15.LengauerTarjan.* pass.

---

E5 · Balanced linking

★ Optional. Contract: computeIdoms(G, D, DomAlgorithm::LengauerTarjanBalanced), then make implementsAlgorithm(LengauerTarjanBalanced) return true · Tests: ch15.LengauerTarjanBalanced.* (skipped until the flag is true)

Add the sophisticated LINK and EVAL from the paper's appendix (Lesson 15.1, Algorithm 15.1.17): size and child arrays, with semi[0] = label[0] = size[0] = 0.

Requirements: R5.1 Same idoms as E4. R5.2 \(O(m\,\alpha(m, n))\).

Hint 1 — where to start

Keep one code path for steps 2–4 and switch only EVAL and LINK on the variant.

Hint 2 — the key idea

In the balanced version, EVAL on a tree root returns label[v] (not v), and after COMPRESS it compares the labels of v and ancestor[v].

Hint 3 — a design sketch

Transcribe the while loop of LINK literally, including the two assignments of s := ancestor(s) := child(s) and the final swap(s, child[v]) when size[v] < 2 · size[w]. Compare your size/child columns with the lesson's balanced-linking table.

Done when: the balanced suites pass, and ch15-dombench shows an lt-bal column.

---

E6 · Semi-NCA

★ Optional. Contract: computeIdoms(G, D, DomAlgorithm::SemiNCA), then make implementsAlgorithm(SemiNCA) return true · Tests: ch15.SemiNCA.* (skipped until the flag is true)

Compute semidominators as in E4 (no buckets), then set idom(w) in increasing preorder by climbing from parent(w) while the number is larger than semi(w) (Lesson 15.1, Algorithm 15.1.19). This is what LLVM runs.

Requirements: R6.1 Same idoms as E4.

Hint 1 — where to start

Initialise idom[w] = parent[w] for every w; phase 1 is E4's loop without buckets.

Hint 2 — the key idea

Because you process w in increasing number, every idom[x] with x < w is final, and the ancestors of w all have smaller numbers (Theorem 15.1.28).

Hint 3 — a design sketch

Phase 2 is three lines. The ladder rows of the lab table show its quadratic worst case.

Done when: the Semi-NCA suites pass.

---

E7 · Read the provided dominator tree

No code: DomTree (pebble/include/pebble/Analysis/DomTree.h, implementation in pebble/lib/Analysis/Dominance/provided/DomTree.cpp) is provided, and ch15.DomTree.* passes before you start. Read DomTree::build and DomTree::dominates and answer for yourself:

1. Why does build use one shared counter for the entry and exit numbers, and why is the \(O(1)\) test in dominates correct (Corollary 15.1.7)?
2. What do dominates(A, B) and properlyDominates(A, B) return when B is unreachable, and why does LLVM choose that (Lesson 15.1, second pitfall)?
3. Compare nearestCommonDominator with DominatorTreeBase::findNearestCommonDominator in llvm/include/llvm/Support/GenericDomTree.h (LLVM 23.1.2).

---

E8 · Dominance frontiers (Cytron)

Contract: computeDominanceFrontier(G, DT, DFAlgorithm::Cytron) · Tests: ch15.CytronDF.*, lit frontiers.ll (print<pebble-domfrontier>)

Bottom-up over the dominator tree: \(\mathrm{DF}_{\mathrm{local}}\) from successors, \(\mathrm{DF}_{\mathrm{up}}\) from the children's frontiers (Lesson 15.3, Algorithm 15.3.6).

Requirements: R8.1 One set per node, equal to llvm::DominanceFrontier's, sorted and duplicate-free. R8.2 \(O(m + \lvert \mathrm{DF} \rvert)\).

What the tests check: every set against LLVM on the corpus and 1 650 random CFGs (the tree is built from LLVM's idoms).

Hint 1 — where to start

Produce a postorder of the dominator tree with an explicit stack over DT.children(v).

Hint 2 — the key idea

Both parts use the same test: keep Y unless DT.idom(Y) == X (Theorem 15.3.5).

Hint 3 — a design sketch

Collect into a vector, then sort and deduplicate. If the test reports a missing X ∈ DF(X), you filtered with "X dominates Y" instead of "X strictly dominates Y" (a loop header is in its own frontier).

Done when: ch15.CytronDF.* pass.

---

E9 · Dominance frontiers (CHK runners)

Contract: computeDominanceFrontier(G, DT, DFAlgorithm::CHK) · Tests: ch15.CHKDF.*, lit frontiers.ll (print<pebble-domfrontier;chk>)

For each join node B (≥ 2 reachable predecessors), walk a runner from each reachable predecessor up to idom(B), adding B to every node passed (Lesson 15.3, Algorithm 15.3.8).

Requirements: R9.1 As R8.1. R9.2 Stop a runner as soon as it reaches a node that already has B.

Hint 1 — where to start

Process B in increasing node id; then every frontier list grows in sorted order automatically.

Hint 2 — the key idea

If the runner's frontier already ends with B, an earlier runner for the same B covered this node and everything above it: stop (Theorem 15.3.16).

Hint 3 — a design sketch

Count only reachable predecessors when deciding whether B is a join node; unreachable.ll's @dead_into_loop catches the difference.

Done when: ch15.CHKDF.* pass.

---

E10 · Iterated dominance frontier

Contract: computeIteratedDF(DF, Defs) · Tests: ch15.IteratedDF.*, lit frontiers.ll (print<pebble-idf>)

The worklist of Lesson 15.3, Algorithm 15.3.11.

Requirements: R10.1 Return \(\mathrm{DF}^{+}(\mathit{Defs})\) sorted. R10.2 Ignore out-of-range and duplicate definitions.

What the tests check: 18 definition sets per function against llvm::ForwardIDFCalculator (frontiers come from LLVM, so only E10 is exercised).

Hint 1 — where to start

Two flags per node: "in the result" and "ever on the worklist". Seed the worklist with the definitions.

Hint 2 — the key idea

A node that enters DF⁺ is a new definition (a phi), so it must be processed too, unless it was already on the worklist.

Hint 3 — a design sketch

If the test reports exactly DF(S) instead of DF⁺(S), you never re-queued the newly added nodes.

Done when: ch15.IteratedDF.* pass.

---

E11 · Post-dominators

Contract: IdomVector computePostDominators(G, Roots) · Tests: ch15.PostDominators.*, lit postdomtree.ll (print<pebble-postdomtree>)

Build the reverse graph with one extra node, the virtual exit \(\hat{x}\) = G.size(), as its entry and an edge to every root (given; findPostDomRoots is provided and matches LLVM), and run a dominator algorithm on it (Lesson 15.4, Algorithm 15.4.8).

Requirements: - R11.1 The result has G.size() + 1 entries; Result[G.size()] == NoNode; every other entry is LLVM's immediate post-dominator, with the virtual exit written as G.size(). - R11.2 Use the given roots, in order, for the edges out of the virtual exit.

What the tests check: the size and the root entry; every ipdom against llvm::PostDominatorTree (whose virtual root is a null block) on the corpus, including infinite-loops.ll, and 1 650 random CFGs.

Hint 1 — where to start

DiGraph R(N + 1, N); add N → root first (in Roots order), then V → U for every predecessor U of V.

Hint 2 — the key idea

Nothing new: post-dominators are dominators of R (Proposition 15.4.3). Your E1 and E3 do the work.

Hint 3 — a design sketch

If only the infinite-loop functions fail, you built the virtual exit's edges from "nodes without successors" instead of the given roots.

Done when: ch15.PostDominators.* pass.

---

E12 · Control dependence

Contract: computeControlDependence(G, PDT) · Tests: ch15.ControlDependence.*, lit dfs-and-control-deps.ll (print<pebble-control-deps>)

For every edge A → B whose target does not strictly post-dominate A, walk the post-dominator tree from B up to (excluding) ipdom(A), adding A to each node's set (Lesson 15.4, Algorithm 15.4.10). PDT is the post-dominator tree over G.size() + 1 nodes (root = the virtual exit).

Requirements: R12.1 Result[Y] \(= \mathrm{CD}(Y)\) (Definition 15.4.4), sorted; G.size() entries. R12.2 Self loops: A → A makes A control dependent on itself.

What the tests check: every set against the definition evaluated with LLVM's post-dominator tree (the PDT you receive is built from LLVM's ipdoms, so only E12 is exercised).

Hint 1 — where to start

PDT.dominates(B, A) is "B post-dominates A", and PDT.idom(x) is ipdom(x).

Hint 2 — the key idea

A self loop A → A must not be skipped: A is control dependent on itself. Skip only when B != A and B post-dominates A.

Hint 3 — a design sketch

Stop the walk also at NoNode and at the virtual exit; sort and deduplicate each set at the end.

Done when: ch15.ControlDependence.* pass.

---

E13 · Natural loops

Contract: computeNaturalLoops(G, DT) · Tests: ch15.NaturalLoops.*, lit loops.ll (print<pebble-loops>), lit loop-forms.ll

Back edges are T → H with H dominating T (T reachable). Merge back edges per header, collect each body with a reverse walk that stops at the header, then nest by containment (Lesson 15.5, Algorithm 15.5.7).

Requirements: - R13.1 One LoopForest::Loop per header with Blocks and Latches sorted; the set of (latch, header) pairs equals LoopInfo's back edges. - R13.2 Parent, Children, Depth (outermost = 1) and Innermost agree with LoopInfo; Children and Parent are consistent.

What the tests check: headers, blocks, latches, parents, depths and the innermost loop of every block against llvm::LoopInfo on the corpus and 1 650 random CFGs.

Hint 1 — where to start

A std::map from header to latches keeps the output deterministic; a bit vector per loop makes containment tests O(1).

Hint 2 — the key idea

The parent of a loop is the smallest other loop that contains its header (Theorem 15.5.5(b)).

Hint 3 — a design sketch

Skip unreachable predecessors in the reverse walk (DT.contains(P)): @dead_into_loop has a dead block that branches into a loop body, and LoopInfo does not count it.

Done when: ch15.NaturalLoops.* pass.

---

E14 · Havlak's loop nesting forest

Contract: computeHavlakLoops(G, D) · Tests: ch15.Havlak.*, lit loops.ll (print<pebble-loops;havlak>)

Implement Lesson 15.5, Algorithm 15.5.9 with union-find over the given DFS. Mark loops with an entry from outside the header's DFS subtree as Irreducible.

Requirements: - R14.1 On the DFS that CycleInfo uses, the loops (headers, blocks, parents, depths, irreducible flags) equal CycleInfo's. - R14.2 On the lessons' DFS, some loop is irreducible iff containsIrreducibleCFG says so; on reducible CFGs the forest equals LoopInfo's (latches included).

What the tests check: R14.1 on every corpus and random function, running your code on a copy of the graph with reversed successor lists (that is CycleInfo's DFS, not a bug in the test); R14.2 on the same functions.

Hint 1 — where to start

Precompute the back predecessors (v with D.isAncestor(w, v)) and the other predecessors of every node once; ignore unreachable predecessors.

Hint 2 — the key idea

Process w in reverse preorder. Find(y) gives the header of the outermost loop already collapsed around y; if that is not in w's subtree, the loop is irreducible and y is appended to w's non-back predecessors so that w's enclosing loop sees it.

Hint 3 — a design sketch

Record the header of every collapsed node; afterwards the parent of w's loop is the loop of w's header, and a node's innermost loop is its own loop if it is a header, otherwise the loop of its header.

Done when: ch15.Havlak.* pass.

---

E15 · Reducibility by T1/T2

Contract: bool isReducibleT1T2(G, LimitSize) · Tests: ch15.Reducibility.*, lit loops.ll (print<pebble-reducibility>)

Apply T1 and T2 to the reachable part until neither applies; report the limit-graph size (Lesson 15.6, Algorithm 15.6.6).

Requirements: R15.1 Reducible iff !containsIrreducibleCFG. R15.2 *LimitSize is the number of limit-graph nodes: 1 iff reducible, 3 for the two-entry loop S -> B, C; B -> C; C -> B, 5 for @running_irreducible.

Hint 1 — where to start

Ordered successor and predecessor sets per node make merges easy; start from the reachable nodes of a DFS (your E1 is fine).

Hint 2 — the key idea

Use a worklist: after merging V into M, re-queue M (it may now have a self loop) and V's successors (their predecessor sets changed).

Hint 3 — a design sketch

Never apply T2 to the entry. The limit-graph sizes in R15.2 are the tests' fixed points.

Done when: ch15.Reducibility.* pass. At this point ./course test 15 should be all green (★ suites skipped unless you did E5/E6).

---

Lab · CHK vs Lengauer–Tarjan vs Semi-NCA vs LLVM

Spec: labs/ch15-dominance/SPEC.md · Tests: ch15.LabAgreement.*, ch15.lab.bench-smoke

The lab times your computeIdoms on large random CFGs and three adversarial families, checks every result against LLVM, and asks you to explain which algorithm degrades where. The spec has the commands, the table to fill in and a ★ measurement of how often real C code is irreducible.