Chapter 20 exercises¶

You'll implement four interprocedural passes as opt plugin passes in pebble/lib/Passes/IPO/ — a call-graph printer with LLVM's SCC order (print<pebble-callgraph>), a bottom-up inliner with three heuristics (pebble-inline), attribute inference over SCCs (pebble-funcattrs) and tail-recursion elimination with ★ accumulators (pebble-tre) — and the two parts of the comparison lab: CHA vs RTA (★ XTA) call graphs checked against a dynamic oracle in labs/ch20-callgraph/, and your three inlining heuristics measured on a benchmark corpus in labs/ch20-inline/. Run the tests after every step:

./course test 20                                              # builds, then runs every test labelled ch20
ctest --preset linux -L '^ch20$' -R ch20.lit                  # the pass tests only (macos preset on a Mac)
build/<preset>/bin/pebble-lit -v tests/ch20/lit/inline-cost.ll # one lit file, verbose

Before you start, every ch20 test fails. The pass tests fail with unknown pass name 'pebble-inline' (and the other three names), because no pass is registered yet; the lab tests stop with TODO(ch20): …. That's expected.

How to write a pass. Put each pass in any .cpp file under pebble/lib/Passes/IPO/ (read its README.md), as a new-pass-manager pass (Ch 12): E1–E3 are module passes (run(Module &, ModuleAnalysisManager &)), because they walk the whole call graph; E4 is a function pass. Register each next to its definition with pebble/Passes/Registry.h:

PEBBLE_MODULE_PASS("print<pebble-callgraph>", YourPrinter);
PEBBLE_MODULE_PASS("pebble-funcattrs", YourAttrs);
PEBBLE_FUNCTION_PASS("pebble-tre", YourTRE);
// a pass with parameters (E2) registers a parser in a PEBBLE_REGISTER_PASSES block:
//   R.modulePass<YourInliner>("pebble-inline", parseYourParams);

Try a pass with opt -load-pass-plugin=build/linux/lib/PebblePasses.so -passes='pebble-inline<cost;remarks>' -S input.ll. To make inputs from C: clang-23 -O1 -Xclang -disable-llvm-passes -fno-discard-value-names -S -emit-llvm f.c -o - | opt -passes=sroa -S -o f.ll (unoptimized IR with SSA values; -O1 keeps the functions eligible for optimization, unlike -O0's optnone).

Common to E1–E4 (registry.test, equivalence.test): - All four names appear in opt -passes='print<pebble-passes>' with chapter ch20 and the right pass kind. - The passes keep the module valid and preserve behavior: equivalence.test compiles tests/ch20/lit/Inputs/equiv.c (recursion, accumulators, floating point, indirect calls, a hash loop), runs it under lli before and after each pass, each inlining heuristic, and pipelines mixing all four with LLVM passes, and diffs the output. - A pass returns PreservedAnalyses::all() when it changed nothing.

Stuck? Work through the hints in order. The reference solutions are in solutions/pebble/lib/Passes/IPO/. Only look at them after you've passed the tests, or after an honest hour.

E1: print¶

Contract: a module pass registered as print<pebble-callgraph> that prints to standard output and changes nothing. Tests: tests/ch20/lit/callgraph-format.ll, callgraph-vs-llvm.test (in ch20.lit)

Build the call graph of a module as LLVM's CallGraph does and print it with its strongly connected components in the order LLVM's scc_iterator visits them — the bottom-up order every pass of this chapter walks (Lesson 20.2, Algorithm 20.2.3 and Definition 20.2.4). You design the graph representation and the traversal; do not use llvm::CallGraph or scc_iterator themselves (the test compares against them).

Requirements:

R1. Nodes and edges. One node per function of the module. A defined function has one outgoing edge per call instruction (CallBase), in instruction order, duplicates kept: to the called function if the callee is known, otherwise to the calls-external node (indirect call). A declaration has one edge to the calls-external node, unless it is marked nocallback. The calls-external node has no successors.
R2. Roots. The external calling node has an edge to every function with non-local linkage and to every function whose address is taken (Function::hasAddressTaken, ignoring callback and assume-like uses), in module order. Traversal starts there only: an internal function no root reaches does not appear in the SCC list.
R3. SCC order. Run Tarjan's algorithm from the external calling node, visiting successors in edge order; print the SCCs in completion order (callees first), each SCC's members in the order they are popped from Tarjan's stack. Leave out the two external nodes.
R4. Recursive SCCs. An SCC is recursive if it has at least two members or its single member has an edge to itself.
R5. Output format (exact; --strict-whitespace --match-full-lines):

pebble-callgraph: module '<module identifier>'
edges:
  <f> -> <callee>, <callee>, <indirect>     one line per DEFINED function, module order
  <g> -> (none)                             a defined function without calls
sccs (bottom-up):
  #1: <member> <member>  [recursive]        two spaces before [recursive]
  #2: <member>

Callee names are the functions' names; an indirect call prints <indirect>. Declarations have no edges: line but do appear in sccs. - R6. Complexity. \(O(F + C)\) for \(F\) functions and \(C\) call sites; iterative, so a 10⁵-deep call chain does not overflow the stack.

What the tests check:

Test	Asserts
`callgraph-format.ll`	the exact output on a module with a mutual recursion, a self-loop, an indirect call, an address-taken internal function, a declaration and an unreachable internal function
`callgraph-vs-llvm.test`	your SCC list equals `opt -passes=print-callgraph-sccs` (external nodes removed), SCC by SCC and member by member, on two C programs, the format test's module and 300 random modules with internal, address-taken and declared functions and indirect calls

Hint 1 — where to start

Print the edges: section first; it is a loop over functions and instructions. Then run opt -passes=print-callgraph-sccs -disable-output on the same file and read the order you must reproduce.

Hint 2 — the key idea

The order is fully determined by three choices LLVM makes: the root's successor order (module order of external or address-taken functions), the successor order inside a node (call-site order), and Tarjan's pop order. Unreachable internal functions are simply never visited. A declaration's edge to the calls-external node never creates a cycle, so it only matters for R1.

Hint 3 — a design sketch

A map from Function * to a vector of callees (null for calls-external), a root vector, and an explicit DFS stack of (node, next-successor index) frames with the usual index, lowlink and on-stack set. When a frame is finished, propagate its lowlink to the parent frame; when lowlink == index, pop an SCC. The common bug the random test catches: updating the parent's lowlink from a successor's index instead of its lowlink after the successor's frame completes.

Done when: callgraph-format.ll and callgraph-vs-llvm.test pass.

E2: pebble-inline¶

Contract: a module pass registered as pebble-inline with the parameters size, cost (the default), profile=FILE, threshold=N and remarks, separated by ; — for example -passes='pebble-inline<cost;threshold=300;remarks>'. Unknown parameters are a pipeline parse error. Tests: inline-cost.ll, inline-size.ll, inline-profile.ll, inline-order.ll, equivalence.test (in ch20.lit); lab part B (ch20.lab)

Implement the bottom-up inliner of Lesson 20.3 (Algorithm 20.3.9) with three heuristics. You write the decisions; LLVM's InlineFunction(CB, IFI) does the mechanics (cloning, argument substitution, return merging).

Requirements:

R1. Order. Process functions in the SCC order of E1, extended to every function (visit functions no root reaches after the root, in module order). For each function, the candidates are the direct calls to defined functions it has when its turn comes (take a snapshot before inlining); calls created by inlining are not reconsidered.
R2. Never inline: a call inside the caller's own SCC (recursive); a callee with noinline or optnone, or a call site marked noinline (noinline); a callee that may be replaced at link time (isInterposable(): weak, linkonce; not viable: interposable definition); a caller and callee whose function attributes are incompatible (AttributeFuncs::areInlineCompatible, not viable: incompatible function attributes); a vararg callee, a call whose type differs from the callee's, or a callee isInlineViable rejects (not viable: …). A callee with alwaysinline is always inlined (alwaysinline).
R3. size: inline iff the callee has at most \(N\) counted instructions (Definition 20.3.6 without any simplification: phi, ret, unconditional br, debug and lifetime intrinsics are free; everything else counts), \(N = 12\) unless threshold=N.
R4. cost: the course cost model (Definitions 20.3.6–20.3.8): cost \(= 5 \times\) (counted instructions of the callee reachable after folding branches and instructions whose operands are constant at this call site) \(- (5 \times \text{arguments} + 5 + 25)\), minus 15000 if the callee is internal and this is its only use; threshold \(T = 225\) (or threshold=N), at least 325 for an inlinehint callee, \(+50\%\) (\(T + \lfloor T/2 \rfloor\)) if exactly one block of the callee is reachable; inline iff cost \(< \max(1, T)\).
R5. profile=FILE: the cost model with call-site hotness from a Ch 12 pebble-bbcount dump (lines count function:block; blocks without a name are function:#index). A call site whose block ran at least a tenth as often as the most frequent block (\(10 \cdot n \ge \max\), \(n > 0\)) is hot: \(T = 3000\). One whose block never ran is cold: \(T = \min(T, 45)\) and no bonuses at all (neither the single-block nor the last-call bonus). A missing file is a fatal usage error pebble-inline: cannot read profile '<FILE>'.
R6. Cleanup. After the walk, delete internal functions left without uses.
R7. Remarks (with remarks, on standard error, one line per candidate in processing order):

pebble-inline: inline <callee> into <caller>: cost=<C> threshold=<T>[ (hot)| (cold)]
pebble-inline: keep call to <callee> into <caller>: cost=<C> threshold=<T>[ (hot)| (cold)]
pebble-inline: inline <callee> into <caller>: size=<S> limit=<N>
pebble-inline: keep call to <callee> into <caller>: recursive | noinline | not viable: <reason>

What the tests check:

Test	Asserts
`inline-cost.ll`	exact costs and thresholds (remarks) for: constant-argument folding, the last-call bonus, the 225 boundary (`cost=225` is kept; `threshold=226` inlines it), `inlinehint`, the single-block bonus, `noinline`, `alwaysinline`, a self-recursive callee (`not viable: recursive call`) and a self-call (`recursive`); the IR after inlining
`inline-size.ll`	the size rule, `threshold=13`, free instructions
`inline-profile.ll`	hot, cold and neither call sites against the static model; the hot boundary (\(10 \cdot n = \max\) is hot); the missing-file error
`inline-order.ll`	bottom-up order and the snapshot rule
`inline-interposable.ll`	`weak`/`linkonce` callees are never inlined (even `alwaysinline`), `linkonce_odr` ones may be; incompatible function attributes are kept
`inline-scc.ll`	calls between two mutually recursive functions are kept (`recursive`) in both heuristics
`equivalence.test`	`lli` output unchanged for every heuristic and a huge threshold

Hint 1 — where to start

Do the size heuristic with remarks first, on inline-size.ll: it needs only the order of E1 (reuse your SCC code) and a count. Then write the cost model as a separate function (call site) → (cost, reachable blocks) and check it against ./course drill inline-decision, which prints every step.

Hint 2 — the key idea

Cost analysis is a simulation of the callee at this call site: map each argument to the constant it receives (if any), walk the blocks reachable from the entry, fold an instruction when all its operands are known constants (ConstantFoldInstOperands, ConstantFoldCompareInstOperands), and follow only the known successor of a conditional branch or switch on a constant. Folded instructions are free; so are instructions in blocks you never reach.

Hint 3 — a design sketch

A per-call-site analysis with a map Value * → Constant *, a worklist of reachable blocks, a counter; a Profile with a StringMap<uint64_t> and the maximum; the driver loops over SCCs, snapshots (CallBase *, profile key) pairs for each caller before touching it (inlining invalidates the block names you would compute later), decides, calls InlineFunction, and emits the remark. The common bug inline-order.ll catches: iterating over the caller's instructions while inlining into it.

Done when: the six inline-*.ll tests and equivalence.test pass; then run lab part B.

E3: pebble-funcattrs¶

Contract: a module pass registered as pebble-funcattrs. Tests: funcattrs.ll, funcattrs-vs-llvm.test, equivalence.test (in ch20.lit)

Infer memory effects and norecurse bottom-up over the SCCs of the call graph (Lesson 20.6, Algorithm 20.6.5; soundness is Theorem 20.6.6).

Requirements:

R1. Memory effects. For each SCC (order of E2 R1), compute the join over its members of each instruction's effect in the lattice none < read < write: loads and stores whose underlying object (getUnderlyingObject) is an alloca are local (no effect); other simple loads read, other simple stores write; volatile and atomic accesses write; a call has the effect of its call site / callee attributes (doesNotAccessMemory, onlyReadsMemory, else write), except calls to members of the same SCC, which are skipped (the optimistic assumption of the fixed point); lifetime and assume-like intrinsics are free; any other instruction that may write writes, that may read reads. Result none → memory(none) on every member; read → memory(read); never weaken an attribute that is already there (intersect).
R2. norecurse. A single-function SCC without a self-call gets norecurse if every call in it is direct, to a function that already has norecurse, or to a declaration marked nocallback.
R3. Never annotate an SCC that contains a declaration, an optnone function or a function that may be replaced at link time (!hasExactDefinition(), e.g. weak, linkonce); callers then see such a function as unknown.
R4. Complexity. One pass over the module after the SCCs: \(O(F + I)\).

What the tests check:

Test	Asserts
`funcattrs.ll`	pure, reading, writing, local-only, calling, recursive, volatile/atomic, indirect, declaration, `optnone` and `weak` cases get exactly the attributes above
`funcattrs-vs-llvm.test`	on three C programs and the feature corpus, every attribute you add is also inferred by LLVM's `function-attrs` (soundness), and you infer at least 40 memory attributes and 26 `norecurse` (a pass that infers nothing is sound but fails)

Hint 1 — where to start

Reuse the SCC order of E1 with every function visited. Do memory effects for single-function SCCs without calls first, then calls, then cycles.

Hint 2 — the key idea

Because callees are finished before callers, a call's effect is just the attribute you (or clang) already put on the callee; inside a cycle there is nothing yet, so assume the best and take the join of what the members do outside the cycle — Theorem 20.6.6 shows why this optimistic start is sound. ./course drill funcattrs-fixpoint traces the same computation.

Hint 3 — a design sketch

A function localEffect(F, SCC) returning a small enum, a loop over SCCs that first checks R3, joins, then writes F->setMemoryEffects(F->getMemoryEffects() & New). For norecurse, check the SCC size, the self-call and each callee. The common bug funcattrs-vs-llvm.test catches: treating a store through a pointer argument as local.

Done when: funcattrs.ll and funcattrs-vs-llvm.test pass.

E4: pebble-tre¶

Contract: a function pass registered as pebble-tre. Tests: tre.ll, tre-negative.ll, equivalence.test (in ch20.lit)

Turn self-recursive tail calls into a loop (Lesson 20.8, Algorithm 20.8.4; correctness is Theorem 20.8.5), ★ with an accumulator for calls followed by one associative and commutative operation.

Requirements:

R1. Eligibility. The function is not varargs, has no dynamic alloca (non-constant size) and no alloca whose address escapes (used other than as the address of a load or store, through GEPs and casts), no byval/inalloca/preallocated parameter (the call's private copy would become the caller's object), and no musttail call (it must stay right before its ret). A candidate call is a direct self-call without notail/musttail.
R2. Tail position. The call is followed by ret of its result (or ret void), or by an unconditional branch to a block that holds only a phi of the call's result and a ret of that phi (the shape clang without optimization + sroa produces).
R3. Loop. Create a new entry block that branches to the old entry, renamed tailrecurse; give it one phi per argument (named <arg>.tr), replace the arguments' uses by the phis, move constant-size allocas into the new entry, and replace each eligible call and its return by a branch to tailrecurse that feeds the call's arguments to the phis. Drop the tail marker from remaining calls that could now see the frame (not required by the tests).
R4. ★ Accumulator. Also accept a call whose result has exactly one use: add, mul, and, or, xor (or fadd/fmul with reassoc and nsz) with an operand that does not depend on the call, whose result is returned (directly or through the shared return block). Introduce accumulator.tr (starts at the identity; accumulator.next = operation of the accumulator and the other operand), make every remaining return return accumulator.ret.tr = operation of the accumulator and the returned value, and drop nsw/nuw/exact flags on the operations you reorder.
R5. Must not transform: calls not in tail position, sub/sdiv and non-reassociable floating point, escaping locals, side effects between the call and the return, notail, dynamic allocas, byval parameters, functions containing a musttail call, calls to other functions.

What the tests check:

Test	Asserts
`tre.ll`	Euclid (plain), the shared-return-block shape, `fact` with a `mul` accumulator (both operand orders), a non-identity base case, `fadd reassoc nsz`, a `void` tail call, static allocas moved to the new entry; exact block, phi and value names
`tre-negative.ll`	every function of R5 keeps its recursive call (including a `byval` parameter and a function with a `musttail` call); the result verifies
`equivalence.test`	`lli` output unchanged, alone and in pipelines

Hint 1 — where to start

Handle the plain ret (call) shape without accumulators first (Euclid). Write the IR you want by hand, then produce it.

Hint 2 — the key idea

All eligible calls of a function share one loop header and one set of phis: create the header lazily on the first elimination. With an accumulator, what a return must produce is "the accumulated operation applied to what the original return produced", which is why every remaining return (the base cases) changes, not only the eliminated one. Read the accumulator's other operand from the instruction at elimination time: the arguments have been replaced by phis by then.

Hint 3 — a design sketch

First collect candidates (call, its return or shared return block, the optional accumulator instruction); if the function is ineligible or there are none, return. Then build the header, the argument phis and — if some candidate has an accumulator — the accumulator phi; eliminate each candidate; finally rewrite the returns. After isStaticAlloca stops being true (the allocas are no longer in the entry block), test for a constant array size instead.

Done when: tre.ll, tre-negative.ll and equivalence.test pass.

Lab A · CHA vs RTA (★ XTA) call graphs¶

Spec: labs/ch20-callgraph/SPEC.md · Your code: labs/ch20-callgraph/src/ (any files you like) · Tests: ch20.lab (cg-*.test)

Implement class hierarchy analysis and rapid type analysis (Lesson 20.1, Algorithms 20.1.5 and 20.1.6) for a small class-based language whose parser is provided, then check them against a Python oracle, a brute-force dynamic call graph (soundness) and each other (the precision chain, Theorem 20.1.14). Measure call edges and reachable bodies on the lesson's inputs and compare with Lesson 20.1 §8.

★ Optional: XTA (Algorithm 20.1.8); its test runs only when you switch it on.

Lab B · Three inlining heuristics¶

Spec: labs/ch20-inline/SPEC.md · Your code: your E2 pass · Tests: ch20.lab (inline-lab.test)

Run your pebble-inline in its three modes over seven C benchmarks with the provided driver, check that every program's output is unchanged, and measure inlined sites, code size, executed instructions and executed calls. The spec states the orderings the test requires; compare your table with Lesson 20.3 §3 and explain every difference in one sentence per benchmark.