Chapter 14 exercises¶

You'll implement a generic dataflow solver and its instances in pebble/lib/Analysis/Dataflow/ — the solver with five strategies (E1), SSA liveness (E2), reaching stores (E3), definite initialization (E4), an interval analysis with widening and narrowing (E6) — the pebble-uninit warning pass in pebble/lib/Passes/Dataflow/ (E5), and the comparison lab in labs/ch14-dataflow/. Run the tests after every step:

./course test 14                                   # builds, then runs every test labelled ch14
ctest --preset linux -L '^ch14$' -R DataflowSolver # a single suite while iterating (macos: --preset macos)

Before you start, every ch14 test fails with TODO(ch14): … (or, for E5, unknown pass name 'pebble-uninit'). That's expected: each message names the step below that fixes it.

Stuck? Work through the hints in order. The reference solution is in solutions/<same path>, but only look at it after you've passed the tests, or after an honest hour.

The contracts are four headers in pebble/include/pebble/Analysis/: Dataflow.h, Liveness.h, DataflowMemory.h, DataflowIntervals.h. Each header's file comment is part of the spec. pebble/lib/Analysis/Dataflow/Stub.cpp defines every contract function with one PEBBLE_TODO; replace or delete it as you go. The directory is yours: any *.cpp you add is compiled automatically.

E1 · A generic solver with five strategies¶

Contract: Solution solve(const Problem &P, Strategy S) and std::vector<unsigned> directionOrder(const Problem &P) in pebble/include/pebble/Analysis/Dataflow.h Tests: ch14.DataflowSolver.*

Write Kildall's algorithm (Lesson 14.2, Algorithm 14.2.10) once, for any monotone framework whose facts are opaque Fact values with a Join, a per-node Transfer, optional per-edge EdgeTransfer and optional Widen at WideningPoints, and run it in the five visiting orders of Lesson 14.4 (Algorithms 14.4.1 and 14.4.2). The equations, the visiting order and exactly what counts as a transfer evaluation and a pass are defined in the header's file comment; the tests compare your counts with the numbers in Lesson 14.4 §3, so follow those rules literally.

Requirements: - R1. solve returns the least solution of the header's equations (the MFP, Definition 14.2.9) for both directions, with In/Out in CFG orientation (for a backward problem, Out[n] is the join over successors and In[n] = Transfer(n, Out[n])). Every strategy returns the same In/Out when there is no widening (Theorem 14.4.4). Nodes unreachable from the boundary still get the least solution of their equations. - R2. Stats.TransferEvals and Stats.Passes follow the header exactly: round-robin sweeps count the final unchanged sweep; a worklist pop evaluates Transfer once; a dependent already pending is not added again. - R3. directionOrder is RPO in the analysis direction: DFS from each boundary node in listed order, then from every unreached node in index order; predecessors (backward) are ordered by source index. - R4. With Widen set, the joined value at a widening point is replaced by Widen(old, joined); the solver must terminate on the infinite-height interval problem of the tests in fewer than 20 evaluations. - R5. Complexity: $O(h \cdot e)$ joins and transfers for a lattice of height $h$ (Proposition 14.2.15); no recursion per node (random CFGs have hundreds of nodes, the lab's 10 000).

What the tests check: RunningExampleLiveness and RunningExampleReaching — the IN/OUT sets of Lesson 14.3 on the running example (as bit vectors); DirectionOrder — R3 on the running example and random graphs, both directions; RunningExampleCostsMatchLesson — the (evaluations, passes) of every strategy on the running example, e.g. liveness 18/3 with RPO round-robin, 24/4 in postorder, 9 FIFO, 8 LIFO, 8 priority; AllStrategiesAgreeOnRandomInstances — the five strategies agree on hundreds of random gen/kill problems; MFPEqualsMOPOnAcyclicDistributiveInstances — your MFP equals a brute-force MOP (Theorem 14.2.13); RoundRobinRPOWithinLoopConnectednessPlusTwo — passes ≤ $d(G) + 2$ and the bound is attained (Theorem 14.4.6); ConstantPropagationIsNotDistributive — an instance where MFP is strictly above MOP; WideningMakesAnInfiniteHeightLatticeTerminate — R4.

Hint 1 — where to start

Build the predecessor lists once, then write directionOrder (an iterative DFS with an explicit stack of (node, next-edge-index) pairs). Every strategy needs it. Then write a single update(n) that recomputes one node from its neighbours and reports whether its output changed; the five strategies differ only in which n they call it on next.

Hint 2 — the key idea

Treat a backward problem as a forward one on the reverse graph: "inputs" are successors, "output" is In. Once update(n) is direction-agnostic, round-robin is "loop over the order until no update changes anything" and a worklist is "pop, update, push dependents if changed". The only thing that must not depend on the strategy is the fixed point, which Lemma 14.4.3 guarantees as long as you never skip a node whose inputs changed.

Hint 3 — a design sketch

State: std::vector<Fact> In, Out, a std::vector<char> Pending membership array next to a std::deque<unsigned> (FIFO/LIFO) or a std::set<unsigned> keyed by RPO rank (priority). Boundary nodes join BoundaryFact into their input on every update, not only the first. Common bugs the tests catch: counting a pass that was never run, seeding the LIFO stack in the wrong order (the first pop must be the first RPO node), and forgetting the edge function on one of the two directions.

Done when: ctest --preset linux -L '^ch14$' -R DataflowSolver passes.

E2 · Liveness of SSA values¶

Contract: LivenessResult computeLiveness(const llvm::Function &F) in pebble/include/pebble/Analysis/Liveness.h Tests: ch14.Liveness.*, tests/ch14/lit/liveness.test

Instantiate your E1 solver for liveness of SSA values (Lesson 14.3, Definition 14.3.9, Algorithm 14.3.7): one bit per argument and non-void instruction, backward, union. The header gives the equations and the two phi conventions: a phi's result is defined at the top of its block and is not live-in there; a phi's incoming value is used at the end of the incoming block, so it is live-out of that predecessor and nowhere else because of that use. Use EdgeTransfer (or an equivalent) for the phi uses. LivenessAnalysis (provided) wraps your function for the new pass manager; later chapters (SSA destruction, register allocation) reuse it.

Requirements: - E2-R1. Blocks has an entry for every block, reachable or not, with exactly the least solution of the header's equations; no duplicates in a set. - E2-R2. Constants, globals, blocks and metadata are never live; declarations give an empty result. - E2-R3. Bit-vector sets: $O((d + 2) \cdot n \cdot \lceil v / 64 \rceil)$ word operations for $v$ values (Proposition 14.3.22).

Output of the provided printer (the lit test compares it with goldens; sets are sorted by position in the function):

Pebble liveness for function 'count10'
  %entry: in = {} out = {}
  %while.cond: in = {} out = {%i.0}
  %while.body: in = {%i.0} out = {%add}
  %while.end: in = {%i.0} out = {}

What the tests check: RunningExample — the SSA form of the running example against the table in Lesson 14.3; CorpusMatchesPathOracle and RandomSSAFunctionsMatchPathOracle — every block of every corpus function and of random SSA functions (loops, several phis per block) against an independent oracle that searches paths from each use back to the definition; DeclarationsAreEmpty; liveness.test — the printer's exact output on running.ssa.ll and loops.ssa.ll.

Hint 1 — where to start

Number the values (arguments first, then instructions in order) and the blocks. For each block compute Defs(B) and UpwardExposed(B) with one forward walk over its non-phi instructions, and PhiUses(P → B) per edge from the phis of B.

Hint 2 — the key idea

With Transfer(B, X) = UpwardExposed(B) ∪ (X \ Defs(B)) and EdgeTransfer(B, S, X) = X ∪ PhiUses(B → S) the header's backward equations are exactly Liveness.h's. Phi results are in Defs(S), so they drop out of LiveIn(S) automatically.

Hint 3 — a design sketch

A small bit-set type over std::vector<uint64_t> (the Fact itself) with set, test, unionWith, subtract; a std::vector<const Value *> for decoding. The common bug: counting a phi's operand as a use in the phi's own block, which makes loop-carried values live around the whole loop header.

Done when: ch14.Liveness.* and ch14.lit :: liveness.test pass.

E3 · Reaching stores¶

Contract: ReachingStoresResult computeReachingStores(const llvm::Function &F) in pebble/include/pebble/Analysis/DataflowMemory.h Tests: ch14.MemoryDataflow.CorpusMatchesPathOracle, ch14.MemoryDataflow.RandomFunctionsMatchPathOracle, tests/ch14/lit/reaching-stores.test

Reaching definitions (Lesson 14.3, Algorithm 14.3.3) for the memory of -O0 code: a store to a tracked alloca (isTrackedAlloca, provided: a local whose address never escapes) is a definition, and it kills every other store to the same alloca. Compute IN/OUT per block and, for every load of a tracked alloca, the stores that reach it — a use-def chain.

Requirements: - E3-R1. Blocks holds the least fixed point of the header's equations for every block (unreachable blocks too). gen[B] is the last store in B to each tracked alloca; kill[B] every other store to an alloca stored in B. - E3-R2. Loads[L] = the stores to L's alloca that reach L: those in IN[B] if no store to that alloca precedes L in B, else just the closest preceding one. An empty vector means no store reaches L. - E3-R3. Bit vectors over the stores; linear per pass.

Output of print<pebble-reaching-stores> (stores are named S0, S1, … in function order):

Pebble reaching stores for function 'sometimes'
  S0: store to %c.addr in %entry
  S1: store to %x in %if.then
  %entry: in = {} out = {S0}
  %if.then: in = {S0} out = {S0, S1}
  %if.end: in = {S0, S1} out = {S0, S1}
  %0 = load %c.addr in %entry: reached by {S0}
  %1 = load %x in %if.end: reached by {S1}

What the tests check: the result on every -O0 corpus function (tests/ch14/Inputs/*.O0.ll) and on 200 random functions with loops equals a brute-force oracle that enumerates paths; the printer's output on the corpus.

Hint 1 — where to start

Number the stores to tracked allocas, and group them by alloca. One forward walk per block gives gen and the set of allocas stored in the block; kill is the union of the groups of those allocas minus gen.

Hint 2 — the key idea

This is your E1 solver with Join = ∪, Init = {}, forward, Transfer = gen ∪ (X \ kill). The per-load answer needs a second, intra-block walk starting from IN[B], applying each store as you pass it (the transfer function one instruction at a time).

Hint 3 — a design sketch

DenseMap<const StoreInst *, unsigned> and a per-alloca bit mask of its stores; a "current reaching set" bit vector during the intra-block walk. The common bug: taking gen as all stores in the block (the first store to x is killed by the second).

Done when: the two MemoryDataflow.*PathOracle tests and reaching-stores.test pass.

E4 · Definite initialization¶

Contract: DefiniteInitResult computeDefiniteInit(const llvm::Function &F) in pebble/include/pebble/Analysis/DataflowMemory.h Tests: ch14.MemoryDataflow.*, tests/ch14/lit/definite-init.test

The must-analysis of Lesson 14.3 §2 (Definition 14.3.19, Algorithm 14.3.20): a tracked alloca is definitely initialized at a point if every path from the entry to it stores to the alloca. It is the same solver on the dual lattice: Join = ∩, Init = all tracked allocas (the top of the subset order, the least element of the join order), IN[entry] = {}.

Requirements: - E4-R1. Blocks holds the greatest fixed point (in ⊆) of the header's equations; blocks unreachable from the entry get the universe (the MFP convention; Lesson 14.3). - E4-R2. LoadIsInitialized[L] is true iff L's alloca is definitely initialized immediately before L (a store earlier in the same block counts). - E4-R3. Bit vectors over tracked allocas.

Output of print<pebble-definite-init>:

Pebble definite initialization for function 'sometimes'
  %entry: in = {} out = {%c.addr}
  %if.then: in = {%c.addr} out = {%c.addr, %x}
  %if.end: in = {%c.addr} out = {%c.addr}
  %0 = load %c.addr in %entry: initialized
  %1 = load %x in %if.end: maybe uninitialized

What the tests check: UninitCorpus — the verdicts on tests/ch14/Inputs/uninit.O0.ll (for example the load of y in never is uninitialized); the path oracle on the corpus and 200 random functions; TrackedAllocas (provided infrastructure); the printer's output.

Hint 1 — where to start

Reuse E3's alloca numbering; stored(B) is the set of allocas with a store in B.

Hint 2 — the key idea

In the solver, the entry is the boundary with BoundaryFact = {}, and Init is the universe; since the header's forward equation is IN = Init ⊔ BoundaryFact ⊔ … with ⊔ = ∩, the entry gets {} and every other block starts at the universe and only shrinks.

Hint 3 — a design sketch

The same bit-set type as E2/E3. The common bug: initializing every block to {} — then a loop header meets {} from its latch on the first visit and the analysis reports every variable used in a loop as maybe uninitialized.

Done when: ch14.MemoryDataflow.* and definite-init.test pass.

E5 · The `pebble-uninit` warning pass¶

Contract: a function pass registered as pebble-uninit in a new .cpp file of yours in pebble/lib/Passes/Dataflow/, with PEBBLE_FUNCTION_PASS("pebble-uninit", YourPass); from pebble/Passes/Registry.h (see that directory's README) Tests: tests/ch14/lit/uninit.c

Combine E4 and E3 into a warning in the style of Clang's -Wuninitialized / -Wsometimes-uninitialized (Lesson 14.3 §7, the real-world box compares all three): the must-analysis decides whether to warn, the may-analysis decides the wording.

Requirements: - E5-R1. For every load L of a tracked alloca with LoadIsInitialized[L] == false, print to llvm::errs() exactly one line, in instruction order:

<loc>: warning: variable '<name>' is uninitialized when used here [pebble-uninit]
<loc>: warning: variable '<name>' may be uninitialized when used here [pebble-uninit]

"is" when no store reaches L (ReachingStoresResult::Loads[L] empty), "may be" otherwise. - E5-R2. <loc> is file:line:col from the load's debug location when it has one, else <function>:%<block> (the block printed as an operand). <name> is the source variable's name from its #dbg_declare record (llvm::findDVRDeclares) when there is one, else the alloca's IR name. - E5-R3. The pass changes nothing (PreservedAnalyses::all()), skips declarations, and computes reaching stores only if some load needs a warning.

What the tests check: uninit.c compiles C with and without -g and FileChecks your warnings for never (is), sometimes and in_loop (may be), and both_paths, after_loop (none), with --implicit-check-not=warning so any extra warning fails; the same file shows Clang's own diagnostics next to yours.

Hint 1 — where to start

Copy the shape of any printer in Ch14Passes.cpp: a struct with run(Function &, FunctionAnalysisManager &) deriving from RequiredPassInfoMixin (so -O0's optnone does not skip it).

Hint 2 — the key idea

"Not definitely initialized" = some path has no store; "no store reaches" = no path has one. Both are properties of all paths, so neither analysis alone can make the three-way distinction; together they can (Algorithm 14.3.20).

Hint 3 — a design sketch

DILocation gives filename, line, column; LI.getParent()->printAsOperand(OS, false) prints %if.end. The common bug: using the store's location or the alloca's instead of the load's.

Done when: ch14.lit :: uninit.c passes.

E6 · Interval analysis with widening and narrowing¶

Contract: IntervalResult computeIntervals(const llvm::Function &F) in pebble/include/pebble/Analysis/DataflowIntervals.h Tests: ch14.Intervals.*, tests/ch14/lit/intervals.test, tests/ch14/lit/intervals-sound.c

An abstract interpreter of LLVM IR integers in the interval domain (Lesson 14.7, Algorithm 14.7.11): one environment per block entry, branch refinement and phi assignment on edges, widening at loop heads, then one descending phase with narrowing. The goldens are exact, so R2 and R3 fix the transfer functions and the iteration; anything they leave open is your choice only if it cannot change the result.

Requirements: - E6-R1 (domain). Tracked values: arguments and instructions of integer type with width $2 \le W \le 64$. An interval is a pair of signed $W$-bit bounds, $\mathrm{min}_W$ and $\mathrm{max}_W$ standing for $-\infty$ and $+\infty$; Lo > Hi is ⊥. Join is the convex hull; widening is the standard one (a bound that grew jumps to $\mathrm{min}_W$ / $\mathrm{max}_W$); narrowing replaces only infinite bounds (Definition 14.7.9). Compute bounds in 128-bit arithmetic. - E6-R2 (transfer). Operands: a ConstantInt is $[c, c]$ (sign-extended); a tracked value is its current interval; an untracked i1 is $[-1, 0]$; anything else is top. If an operand of a binary operator or cast is ⊥, the result is ⊥. Then:

Instruction	Result
`add`, `sub`, `mul`	the exact range $[l, h]$ of the operation on the operand intervals (for `mul`, min and max of the four corner products). With `nsw`: $[l, h] \cap [\mathrm{min}_W, \mathrm{max}_W]$ (overflow is poison; ⊥ if empty). Without `nsw`: $[l, h]$ if it fits in $W$ bits, else top
`sdiv x, [c, c]`	$c \ne 0$ and not ($c = -1$ and $x$ may be $\mathrm{min}_W$): hull of $x.lo / c$ and $x.hi / c$ (C truncating division); otherwise top
`srem x, [c, c]`, $c \ne 0$	with $m = \lvert c \rvert - 1$: $[0, \min(m, x.hi)]$ if $x.lo \ge 0$; $[\max(-m, x.lo), 0]$ if $x.hi \le 0$; else $[-m, m]$. Non-constant divisor: top
`and`	both operands $\ge 0$: $[0, \min(a.hi, b.hi)]$; else one operand a constant $c \ge 0$: $[0, c]$; else top
`ashr x, [c, c]`, $0 \le c < W$	$[x.lo \gg c, x.hi \gg c]$; otherwise top
`sext`	the operand's interval
`zext`	from `i1`: $[0, 1]$; operand $\ge 0$: unchanged; else $[0, 2^{W_{src}} - 1]$ if $W_{src} < W$, else top
`trunc`	the operand's interval if it fits in $W$ bits, else top
`select`	hull of the two value operands (the condition is ignored)
anything else (`load`, `call`, `or`, `xor`, `shl`, `lshr`, `udiv`, `urem`, `freeze`, …)	top

E6-R3 (algorithm). Exactly Algorithm 14.7.11:
order = RPO of the blocks reachable from the entry (DFS, successors in terminator order); blocks not in order stay unreachable. heads = targets of retreating edges (u → v with rank(v) ≤ rank(u)).
IN[entry] is reachable, with arguments at top and every other value ⊥; OUT[entry] = Transfer(entry, IN[entry]). Every other block starts unreachable.
Edge(p, b): if OUT[p] is unreachable, unreachable. If p ends in a conditional br with two different successors: a constant condition makes the other edge unreachable; an icmp on tracked integer operands refines both operands' intervals by the predicate (on the edge to successor 0) or by its inverse (successor 1) — eq meets them; ne removes a bound equal to the other side's constant; slt/sle/sgt/sge cut at the other side's bound (±1 for strict); ult/ule (and swapped ugt/uge) refine only when the right-hand side is $\ge 0$, to $[0, y.hi(-1)]$; if either becomes ⊥ the edge is unreachable. Then each phi of b takes its incoming value for p in that environment.
Sweep(phase), run once ascending and once descending: repeat, for each b in order except the entry: X = join of Edge(p, b) over all predecessors (unreachable is the identity). If b is a head: count the visit; for each phi of b — and for every tracked value once b has been visited more than 8 times in this phase — replace X[v] by IN[b][v] ∇ X[v] (ascending) or IN[b][v] Δ X[v] (descending); a head's reachability is old ∨ new ascending and new descending. If X ≠ IN[b]: IN[b] = X, OUT[b] = Transfer(b, X) (non-phi instructions in order, R2). Stop after a sweep with no change.
The result for an instruction is OUT[its block][v] (⊥ if the block is unreachable); for an argument, IN[entry].
E6-R4 (soundness). For every execution without poison, every value produced lies in its interval (Theorems 14.7.4 and 14.7.10).

Output of print<pebble-intervals> (values by block; bot for ⊥):

Pebble intervals for function 'count10'
  %while.cond:
    %i.0 = [0, 10]
  %while.body:
    %add = [1, 10]

What the tests check: CorpusIsSoundOnConcreteRuns and RandomFunctionsAreSoundOnConcreteRuns — every function of the corpus and 150 random SSA functions is run by an interpreter in the test on 40 inputs each, stopping at the first poison, and every produced value must lie in its interval; PrecisionOnKnownLoops — count10 gives %i.0 = [0, 10], the nested loops give %i.0 = [0, 8] and %j.0 = [0, 7], countdown gives [-2, 100], plus clamp, bucket (unsigned refinement) and modulo; intervals.test — the exact printer output (R2 + R3); intervals-sound.c — pebble-intervals-instrument inserts a check after every tracked definition, lli runs the program, and a deliberately shrunk variant must be caught.

Hint 1 — where to start

Get the domain operations (hull, meet, widen, narrow) and R2 right first, with the loop-free functions of the corpus (clamp, bucket, modulo); the soundness tests will already run on them. Then add the ascending sweep, then the descending one.

Hint 2 — the key idea

Widening only the phis of a head is enough for termination on reducible CFGs, because every value defined inside a loop is a function of the head's phis and of values defined outside the loop; widening the whole environment also widens values of enclosing loops that happen to be in it, and narrowing cannot always recover them (the nested test). The 8-visit fallback is what guarantees termination on irreducible random CFGs.

Hint 3 — a design sketch

An environment = (reachable flag, std::vector<Interval> indexed by value number); __int128 for bounds. Keep the refinement code in one function refine(pred, X, Y) and derive sgt/sge/ugt/uge by swapping. The common bugs: forgetting that add without nsw wraps (the random tests find it in a few seeds), treating an unreachable predecessor as top instead of the identity, and comparing environments with ⊥ intervals of different representations as different (which never terminates).

Done when: ch14.Intervals.*, intervals.test and intervals-sound.c pass.

Lab · Round-robin vs worklists vs sparse, and liveness in Datalog¶

Spec: labs/ch14-dataflow/SPEC.md · Your code: labs/ch14-dataflow/src/ (L1, C++) and labs/ch14-dataflow/datalog/ (L3, L4, Python) · Tests: ch14.SparseLiveness.*, ch14.datalog, ch14.lab.bench-smoke

Read the spec: it gives the requirements (L1 sparse liveness, L2 measurement, L3 a semi-naive Datalog engine, L4 liveness as Datalog rules), the contracts, the Datalog syntax and the exact meaning of its round and derivation counters, the driver formats, what the tests check and the milestones. Then compare your measurements with Lessons 14.4, 14.6 and 14.8, section 8.

★ Optional: an SCC-ordered (weak topological order) worklist as a sixth strategy; reaching definitions in Datalog; your liveness.dl in Soufflé.

Instruction	Result
`add`, `sub`, `mul`	the exact range \([l, h]\) of the operation on the operand intervals (for `mul`, min and max of the four corner products). With `nsw`: \([l, h] \cap [\mathrm{min}_W, \mathrm{max}_W]\) (overflow is poison; ⊥ if empty). Without `nsw`: \([l, h]\) if it fits in \(W\) bits, else top
`sdiv x, [c, c]`	\(c \ne 0\) and not (\(c = -1\) and \(x\) may be \(\mathrm{min}_W\)): hull of \(x.lo / c\) and \(x.hi / c\) (C truncating division); otherwise top
`srem x, [c, c]`, \(c \ne 0\)	with \(m = \lvert c \rvert - 1\): \([0, \min(m, x.hi)]\) if \(x.lo \ge 0\); \([\max(-m, x.lo), 0]\) if \(x.hi \le 0\); else \([-m, m]\). Non-constant divisor: top
`and`	both operands \(\ge 0\): \([0, \min(a.hi, b.hi)]\); else one operand a constant \(c \ge 0\): \([0, c]\); else top
`ashr x, [c, c]`, \(0 \le c < W\)	\([x.lo \gg c, x.hi \gg c]\); otherwise top
`sext`	the operand's interval
`zext`	from `i1`: \([0, 1]\); operand \(\ge 0\): unchanged; else \([0, 2^{W_{src}} - 1]\) if \(W_{src} < W\), else top
`trunc`	the operand's interval if it fits in \(W\) bits, else top
`select`	hull of the two value operands (the condition is ignored)
anything else (`load`, `call`, `or`, `xor`, `shl`, `lshr`, `udiv`, `urem`, `freeze`, …)	top

Chapter 14 exercises¶

E1 · A generic solver with five strategies¶

E2 · Liveness of SSA values¶

E3 · Reaching stores¶

E4 · Definite initialization¶

E5 · The pebble-uninit warning pass¶

E6 · Interval analysis with widening and narrowing¶

Lab · Round-robin vs worklists vs sparse, and liveness in Datalog¶

E5 · The `pebble-uninit` warning pass¶