Skip to content

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

Chapter: 15 · Control-Flow Analysis: Dominance & Loops · Lessons: 15.1 (algorithms, section 5 complexity, section 8 comparison), 15.6 (the ★ measurement) · Time: 2–3 hours after E1–E4 · Tests: ./course test 15 (labels ch15, lab)

Goal

Measure the dominator algorithms of Lesson 15.1 against each other and against LLVM's DominatorTree on the same inputs: random CFGs of 1 000 to 100 000 blocks and three families built to hurt particular algorithms (ladder, comb, bichain). You implement the algorithms (exercises E1–E4, optionally E5 and E6) behind the chapter's contract; the lab driver ch15-dombench is provided, checks every result against LLVM, and prints one table row per input. Your job is to run it, fill in the table below, and explain each row with the lesson's complexity results.

Requirements

  • R1. computeDFS and computeIdoms with DomAlgorithm::Iterative, CHK and LengauerTarjan return LLVM's immediate dominators on every lab input (the driver exits with status 1 and names the algorithm and input on any disagreement).
  • R2. No recursion per node: the largest input has 100 000 blocks and a DFS depth close to that.
  • R3. Complexity as in Lesson 15.1, section 5: CHK \(O((d + 2) \cdot m \cdot h)\), Lengauer–Tarjan \(O(m \log n)\) (simple linking), Semi-NCA \(O(n^2)\) worst case. Performance target on the reference container (4 cores, LLVM 23.1.2, RelWithDebInfo): the full run finishes in about a minute, and your Lengauer–Tarjan on the 100 000-block random CFG takes under 100 ms.
  • R4. DomStats::Passes for CHK is filled (the table's CHK passes column).
  • R5 ★. With E5/E6 done and implementsAlgorithm returning true for them, the lt-bal and semi-nca columns appear.

The contract

There is no lab-specific code to write: the lab calls the chapter contract, pebble/include/pebble/Analysis/Dominance.h, which you implement in pebble/lib/Analysis/Dominance/src/ (spec: exercises.md, E1–E6). The functions it uses:

// pebble/include/pebble/Analysis/Dominance.h (excerpt; the full header documents every field)
namespace pebble::cfa {
DFSResult computeDFS(const DiGraph &G);
IdomVector computeIdoms(const DiGraph &G, const DFSResult &D, DomAlgorithm A,
                        DomStats *Stats = nullptr);
bool implementsAlgorithm(DomAlgorithm A);
}

Input and output formats

usage: ch15-dombench [--quick] [--seed N] [--reps N]
  • --quick: small inputs only, one repetition (the ctest smoke run ch15.lab.bench-smoke).
  • --seed N: seed of the random-CFG generator (default fixed, so runs are reproducible).
  • --reps N: repetitions per measurement; the table shows the median.

For each input the driver builds an llvm::Function with that CFG, converts it with FunctionCFG::build, and times each algorithm (DFS included for yours; DominatorTree::recalculate for LLVM). Output is a Markdown table, then a verdict line:

| shape | blocks | edges | CHK passes | iterative | chk | lt | lt-bal | semi-nca | llvm |
|---|---:|---:|---:|---:|---:|---:|---:|---:|---:|
| random | 200 | 279 | 3 | 0.06 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 |
...
all algorithms agree with llvm::DominatorTree

Times are milliseconds; - means not run (the iterative algorithm only up to 4 000 blocks because of its \(n^2\) bits; the optional columns until implementsAlgorithm says so).

Provided infrastructure

File What it gives you
bench/DomBench.cpp the driver: graph families, timing, the LLVM cross-check
pebble/include/pebble/Analysis/Graph.h DiGraph, FunctionCFG (graph adapters)
pebble/include/pebble/Analysis/DomTree.h the dominator tree with \(O(1)\) queries

The families (Lesson 15.1, Proposition 15.1.31): random — local spanning tree, forward edges, a few back edges, some irreducible; ladder — \(a_i \to a_{i+1}\), \(a_i \to b_i\), \(b_i \to b_{i+1}\) with the \(a\)-chain explored first; comb — a chain whose every node also jumps to one join node; bichain — an irreducible chain entered at both ends.

What the tests check

Test Checks
ch15.lab.bench-smoke ch15-dombench --quick exits 0: every algorithm agrees with LLVM on the small inputs
ch15.LabAgreement.LargeRandomCFGs CHK, Lengauer–Tarjan (and the ★ algorithms when implemented) equal LLVM's idoms on six random CFGs of 2 000–5 000 blocks
ch15.CHK.BichainNeedsOnePassPerNode your CHK really iterates: the 40-node bichain needs at least 39 passes
ch15.CHK.*, ch15.LengauerTarjan.*, … correctness of each algorithm (exercises E2–E6)

Milestones

  1. E1 and E3 pass (ctest --preset linux -L '^ch15$' -R 'DFS|CHK').
  2. E4 passes; ch15.LabAgreement.* and ch15.lab.bench-smoke pass (ctest --preset linux -L lab).
  3. Run the measurement and fill in the table:
cmake --build build/linux --target ch15-dombench
build/linux/bin/ch15-dombench --reps 5
Input CHK passes chk (ms) lt (ms) semi-nca (ms) llvm (ms)
random, 100 000 blocks
ladder, 20 000 blocks
comb, 20 000 blocks
bichain, 1 000 blocks
  1. For each family, write down which algorithm degrades and why, citing the mechanism of Proposition 15.1.31 (which loop walks how far), and compare with the reference numbers in Lesson 15.1, section 8.

Hints

Hint 1 — where to start

Get correctness first with --quick; the driver's error message names the algorithm and the input. Then run the full table once before optimizing anything.

Hint 2 — the key idea

Each family targets one loop: the ladder makes every Intersect (and Semi-NCA's climb) walk the whole \(a\)-chain; the comb makes one node fold in \(n\) predecessors one by one; the bichain makes information travel one node per pass. If your numbers do not show the predicted growth (4× the blocks, 16× the time for the quadratic cases), your algorithm is not the one the lesson describes.

Hint 3 — a design sketch

If Lengauer–Tarjan is slow on the 100 000-block input, look for per-call allocations inside EVAL (reuse one path buffer) and for maps where dense arrays indexed by preorder number would do. If CHK's pass count on random graphs is 2 when the lesson says 4–5, check that your iteration order is RPO: some random graphs are irreducible.

Stretch goals ★

  • Implement E5 and E6 and compare lt with lt-bal (the lesson and LLVM's comment above SemiNCAInfo::eval predict no practical gain).
  • How often is real C code irreducible? Compile every C file you have and count the verdicts of your T1/T2 test (E15):
for f in $(find /usr -name '*.c' 2>/dev/null); do
  clang -S -emit-llvm -O0 -Xclang -disable-O0-optnone -w -o - "$f" 2>/dev/null |
    opt -load-pass-plugin=build/linux/lib/PebblePasses.so \
        -passes='print<pebble-reducibility>' -disable-output 2>&1
done | grep -c ': irreducible'

Compare with Lesson 15.6, section 5, and look at one irreducible function with print<pebble-loops;havlak> and print<cycles>.