Lab 10.3 · One analysis three ways, one function on two engines¶

Chapter: 10 · The LLVM C++ API · Lessons: 10.4, 10.5, 10.7, 10.8 · Time: 4–6 hours · Tests: ./course test 10 (labels ch10)

Goal¶

This is the chapter's comparison lab, and it has two halves.

Three matching styles. Write the same small peephole analysis three times:
with raw isa/dyn_cast/cast and operand inspection (Lesson 10.4);
as an llvm::InstVisitor (Lesson 10.4);
with llvm::PatternMatch combinators (Lesson 10.5).

All three must report exactly the same findings on a hand-written corpus, on clang output at -O0 and -O2, and on 600 randomly generated functions. Then compare them on code size, readability and speed (ch10-apibench). 2. Two execution engines. Run the same IR function with the ExecutionEngine interpreter and with ORC LLJIT (Lesson 10.8). Both engines must agree with a C++ reference, and both must report errors as llvm::Error instead of crashing. Then measure where each one wins.

Patterns¶

Only instructions of scalar integer type are considered. Vectors, pointers and floating point never match, and neither does an icmp's own i1 result. Each instruction gets at most one kind. The rules are tried in this order, and the first match wins:

Kind	Rule (either operand order where it says "either")
`add-sub-cancel`	`add A, B` where one operand is an instruction `sub Y, X` and the other operand is that same `X` (either order)
`double`	`add X, X` (both operands the same value)
`mul-pow2`	`mul A, B` where one operand is a `ConstantInt` whose value is a power of two as an unsigned number (either order)
`not`	`xor A, B` where one operand is the all-ones `ConstantInt` (either order)
`neg`	`sub C, X` where `C` is the `ConstantInt` 0 (zero on the left only)
`smax`, `smin`, `umax`, `umin`	`select C, T, F` whose condition `C` is an `icmp P A, B` with `A ≠ B`: if `(T, F) = (A, B)` the kind comes from `P` (`sgt`/`sge` → `smax`, `slt`/`sle` → `smin`, `ugt`/`uge` → `umax`, `ult`/`ule` → `umin`; `eq`/`ne` → none); if `(T, F) = (B, A)` it comes from the swapped predicate; otherwise none. Also a call to the intrinsic `llvm.smax`/`llvm.smin`/`llvm.umax`/`llvm.umin` → that kind

Findings are reported by index, the 0-based position of the instruction in instructions(F) order (every instruction counts, terminators included). They are sorted by index.

Requirements¶

R1. findPatterns(F, Style::RawCasts) implements the table with isa/dyn_cast/cast, getOpcode() and operand inspection. It may use neither InstVisitor nor PatternMatch.h.
R2. findPatterns(F, Style::Visitor) implements it as a subclass of InstVisitor<…> whose visit* methods (e.g. visitAdd, visitSelectInst, visitIntrinsicInst) do the work.
R3. findPatterns(F, Style::PatternMatch) implements it with match(…) and PatternMatch combinators (m_c_Add, m_Deferred, m_Power2, m_Not, m_Neg, m_Select, m_ICmp, m_SMax, …).
R4. The three styles return identical vectors on every function (Finding has operator==).
R5. runInterpreter(IR, Fn, Args) parses the IR, checks the function, and calls it through EngineBuilder(...).setEngineKind(EngineKind::Interpreter) and runFunction. The interpreter aborts the whole process (report_fatal_error) on most intrinsics, so runInterpreter must return an Error for any module that declares an intrinsic, before executing anything.
R6. runLLJIT(IR, Fn, Args) does the same with orc::LLJITBuilder, ThreadSafeModule, lookup and a call through a function pointer. It supports 0 to 4 arguments, and intrinsics are fine.
R7 (errors). Both engines return an llvm::Error (never crash, never exit) for a parse error, a missing function, a function without a body, or a function whose type is not i64 (i64 × Args.size()).
R8 (resources). Every call creates and destroys its own context, module and engine. No leaks: the context must outlive the engine that uses it.

The contract¶

// labs/ch10-compare/include/apicmp/Compare.h  (provided; do not change)
namespace apicmp {
enum class Style { RawCasts, Visitor, PatternMatch };
struct Finding { unsigned Index; std::string Kind; /* operator== */ };
std::vector<Finding> findPatterns(llvm::Function &F, Style S);
llvm::Expected<int64_t> runInterpreter(llvm::StringRef IR, llvm::StringRef Fn, llvm::ArrayRef<int64_t> Args);
llvm::Expected<int64_t> runLLJIT(llvm::StringRef IR, llvm::StringRef Fn, llvm::ArrayRef<int64_t> Args);
}

Input formats¶

Textual LLVM IR. The corpus in inputs/ contains:

patterns.ll, hand-written, with index comments on every instruction;
kernels-O0.ll and kernels-O2.ll, generated from kernels.c by clang 23.1.2 (the command is in the C file);
exec.ll, the functions for the two engines. It contains no intrinsics, so the interpreter can run it.

Provided infrastructure¶

File	What it gives you
`include/apicmp/Compare.h`	the contract
`inputs/*.ll`, `inputs/kernels.c`	the corpus
`bench/Bench.cpp`	`ch10-apibench [--quick]`: times each style over the corpus, and the two engines on `exec.ll`; exits 1 if styles or engines disagree
`src/Stub.cpp`	stubs that stop with `TODO(ch10)`

What the tests check¶

Test	Checks
`ch10.Compare.Corpus`	each style on every function of `patterns.ll`, `kernels-O0.ll`, `kernels-O2.ll` equals `tests/ch10/Inputs/compare-expected.txt` (hand-checked against the index comments)
`ch10.Compare.Planted`	600 random straight-line functions (i32 or i64) built with `IRBuilder<NoFolder>`, with every pattern planted in both operand orders plus near misses (non-powers of two, `-2` instead of `-1`, `sub X, 0`, `eq` compares, arms that are not the compared values, adds of the minuend); each style must equal the generator's own classification. The first failure prints the function
`ch10.Compare.EnginesInterpreter`, `…EnginesLLJIT`	`fib`, `fibrec`, `gcd` (100 argument pairs including `INT64_MAX` and `INT64_MIN + 1`), `collatz`, `clamp`, `cubic` (4 arguments) from `exec.ll` against C++ references
`ch10.Compare.EnginesErrors`	R5 and R7: parse error, missing function, wrong arity, wrong type (both engines); an `llvm.abs` module is refused by the interpreter and runs under LLJIT
`ch10.lab.bench-smoke`	`ch10-apibench --quick` runs and all styles and engines agree

Measurement¶

Run build/<preset>/bin/ch10-apibench (Release build) and fill in:

	raw casts	InstVisitor	PatternMatch
lines of code (yours)
time for 2000 rounds (ms)

call	Interpreter (ms)	LLJIT (ms)
`fib(1000000)`
`fibrec(24)`
`collatz(837799)`

The reference solution on the course machine (LLVM 23.1.2, Release, x86-64) measured 2.3 / 2.9 / 11.5 ms for the three styles. For the engines it measured fib(1000000) at 412.8 ms interpreted vs 13.3 ms JIT, fibrec(24) at 109.8 vs 12.1 ms, and collatz(837799) at 0.7 vs 12.0 ms. The interpreter wins when the run is shorter than the ~12 ms it takes to compile. Lesson 10.8 §5 (Proposition 10.8.12) discusses the crossover, and Lesson 10.5 §5 explains why PatternMatch was slowest here.

Milestones¶

RawCasts on patterns.ll: ctest --test-dir build/<preset> -R ch10.Compare.Corpus (the other styles still fail).
Visitor and PatternMatch: the corpus test passes, then ch10.Compare.Planted.
runLLJIT, then runInterpreter: ctest --test-dir build/<preset> -R ch10.Compare.Engines.
Measurement: ch10-apibench.

Hints¶

Hint 1 — where to start

Write one classifier classify(Instruction &) -> optional<const char *> per style and a shared loop that numbers instructions(F) and collects findings. Put the kind names and the predicate → kind mapping in one shared header, so the styles cannot disagree on spelling. CmpInst::getSwappedPredicate gives the predicate for swapped operands.

Hint 2 — the key idea

InstVisitor dispatches statically on the opcode: visitAdd(BinaryOperator &), visitSelectInst, and visitIntrinsicInst for intrinsic calls. You only write the operand checks. In PatternMatch, m_c_Add(m_Sub(m_Value(Y), m_Value(X)), m_Deferred(X)) states add-sub-cancel in one line: m_Deferred compares with the X bound earlier in the same attempt, and the commutative matcher retries with the operands swapped. In LLVM 23, m_SMax matches only the llvm.smax intrinsic, not the select form, so the select form needs m_Select(m_ICmp(Pred, …), …).

Hint 3 — a design sketch

Engines: parse with parseAssemblyString, check the signature, then (interpreter) EngineBuilder(std::move(M)).setEngineKind(EngineKind::Interpreter).setErrorStr(&S).create() and runFunction(F, {GenericValue…}), reading IntVal. Include llvm/ExecutionEngine/Interpreter.h so the interpreter is linked in. For LLJIT: InitializeNativeTarget() and InitializeNativeTargetAsmPrinter() once, LLJITBuilder().create(), addIRModule(ThreadSafeModule(std::move(M), std::move(Ctx))), lookup(Fn), then toPtr<int64_t (*)(int64_t, …)>() switched on the arity. The bugs the tests catch most often: destroying the LLVMContext before the interpreter that owns a module in it; calling *Expected without checking it; treating -2 as all-ones; matching sub X, 0 as neg; forgetting that mul i8 %x, -128 is mul-pow2 (128 = 2^7 unsigned).

Stretch goals ★¶

Add a fourth style: a table of declarative rules (a vector of {kind, pattern-lambda}) and compare it with the hand-ordered if chain (Lesson 10.5 §6, the DSL approach).
Run exec.ll under MCJIT (EngineKind::JIT) too, and under LLLazyJIT, and add them to the timing table.