Skip to content

Chapter 10 exercises

This chapter's implementation work is three standalone labs in labs/ch10-*. Each one ships a specification (SPEC.md) and the smallest possible test contract, and you design everything else. Run the tests after every step:

./course test 10                                   # builds, then runs every test labelled ch10
ctest --test-dir build/<preset> -L ch10 -R IrBuild  # one lab's suite while iterating

Before you start, every ch10 test fails with TODO(ch10): …. That's expected: each message names the lab and the requirement that fixes it.

Stuck? Work through the hints in each spec in order. The reference solutions are in solutions/labs/ch10-*/src/, but only look at them after you've passed the tests, or after an honest hour.

L1 · Build IR with IRBuilder

Contract: buildFib, buildHorner and buildDispatch in labs/ch10-irbuild/include/irbuild/Build.h (stubbed in labs/ch10-irbuild/src/Stub.cpp; your code goes anywhere under labs/ch10-irbuild/src/) Spec: labs/ch10-irbuild/SPEC.md Tests: ch10.IrBuild.*, tests/ch10/lit/irbuild-*.test

Build three functions in memory, specified only by what they compute: an iterative Fibonacci with phi-carried loop state, a Horner polynomial evaluator reading coefficients through a GEP, and a switch-based dispatcher. The tests verify each module, check its shape and JIT-compile it with ORC LLJIT against a C++ reference on hundreds of inputs. Lessons: 10.1, 10.2, 10.3.

Hint 1 — where to start

Draw each CFG on paper first, then create every block before emitting into any of them. buildDispatch has no loop, so start there.

Hint 2 — the key idea

A phi's back-edge value does not exist when you create the phi: create it with CreatePHI(Ty, 2), build the loop body, then addIncoming both edges (Lesson 10.2, Theorem 10.2.13).

Done when: ctest -L ch10 -R 'IrBuild|irbuild' passes.

L2 · An IR inspection and rewriting tool

Contract: the ch10-tool --stats|--def-use|--rewrite-pow2 <file.ll> command line, entered through irtool::run in labs/ch10-irtool/include/irtool/Tool.h Spec: labs/ch10-irtool/SPEC.md (exact output formats) Tests: ch10.IrTool.ExitCodes, tests/ch10/lit/tool-*

Parse and verify IR with proper error reporting, walk the ownership tree for statistics, print def-use chains in a canonical order (not use-list order), and rewrite multiplications, unsigned divisions and remainders by powers of two into shifts and masks, while iterating, keeping flags right and preserving meaning under lli. Lessons: 10.1, 10.2, 10.4, 10.7.

Hint 1 — where to start

Get R1 (usage and error exit codes) and --stats working first; they exercise parsing, verifying and walking Module → Function → BasicBlock → Instruction.

Hint 2 — the key idea

For the rewrite, create the replacement before the old instruction (iterator position), takeName, RAUW, erase, all inside make_early_inc_range(instructions(F)) (Theorem 10.1.14).

Done when: ctest -L ch10 -R 'IrTool|ch10.lit' passes.

L3 · Comparison lab: one analysis three ways, one function on two engines

Contract: findPatterns(F, Style), runInterpreter, runLLJIT in labs/ch10-compare/include/apicmp/Compare.h Spec: labs/ch10-compare/SPEC.md Tests: ch10.Compare.*, ch10.lab.bench-smoke

Write the same peephole analysis (nine pattern kinds) with raw casts, as an InstVisitor and with PatternMatch, and make all three agree on a corpus and on 600 random functions. Then run the same IR function through the ExecutionEngine interpreter and ORC LLJIT, with errors reported as llvm::Error. Finally measure with ch10-apibench and fill in the table in the spec. Lessons: 10.4, 10.5, 10.7, 10.8.

Hint 1 — where to start

Write the raw-cast style against inputs/patterns.ll, whose comments give every instruction's index and expected kind.

Hint 2 — the key idea

In LLVM 23, m_SMax matches only the intrinsic, and m_c_Add(m_Sub(m_Value(Y), m_Value(X)), m_Deferred(X)) states add-sub-cancel in one line. The interpreter aborts on intrinsics, so refuse them first.

Done when: ctest -L ch10 -R Compare and ch10.lab.bench-smoke pass. Then compare your measurements with Lesson 10.5 §5 and Lesson 10.8 §5.

★ Optional: add a declarative rule-table style (Lesson 10.5 §6), and time MCJIT and LLLazyJIT too.