Lab 10.1 · Building IR with IRBuilder¶

Chapter: 10 · The LLVM C++ API · Lessons: 10.1, 10.2, 10.3, 10.8 · Time: 3–5 hours · Tests: ./course test 10 (labels ch10)

Goal¶

Write three functions that each construct a module in memory with llvm::IRBuilder, specified only by what the generated function computes. You decide the control-flow graph, where the phis go and how to name things. The tests verify each module, check its shape, JIT-compile it with ORC LLJIT and call it on hundreds of inputs against a C++ reference.

The point is the object model of Lessons 10.1–10.3. Which object owns which? When may a phi receive its back-edge operand? What is the insertion point when you call CreateXxx? What does the default folder do to constant operands?

Requirements¶

R1 (all builders). Each builder returns a new llvm::Module that lives in the context you are given, and the caller owns it. The module defines exactly one function, with external linkage and the name and signature from the contract, and it passes llvm::verifyModule. The arguments have the names given in the contract (%n, %coeffs, …); the tests match define lines by those names.
R2 (@fib). define i64 @fib(i64 %n) returns \(F(n) \bmod 2^{64}\), where \(F(0) = 0\), \(F(1) = 1\) and \(F(k) = F(k-1) + F(k-2)\). For \(n < 0\) it returns \(0\). It must be iterative: one loop whose state is carried in phi nodes, with no alloca and no call. It must handle \(n = 10^5\) without recursion.
R3 (@horner). define i64 @horner(ptr %coeffs, i64 %n, i64 %x) returns \(\sum_{i=0}^{n-1} c_i x^i \bmod 2^{64}\), where %coeffs points to \(n\) consecutive i64 values \(c_0, \dots, c_{n-1}\). For \(n \le 0\) it returns \(0\) and reads no memory. It must use Horner's rule, \((\dots((c_{n-1})x + c_{n-2})x + \dots)x + c_0\): the function contains exactly one mul instruction, inside a loop, and no alloca or call. Coefficients are read with a GEP and a load.
R4 (@dispatch). define i64 @dispatch(i32 %op, i64 %a, i64 %b) contains exactly one switch on %op with nine cases, 0 to 8. Case 0 is a + b, 1 is a - b, 2 is a * b, 3 is a & b, 4 is a | b and 5 is a ^ b (all wrapping). Case 6 is a << (b & 63) and case 7 is a >> (b & 63) (arithmetic). Case 8 is the signed minimum of a and b. Any other %op returns 0.
R5 (style). Use IRBuilder<> (the default ConstantFolder) or a builder with another folder of your choice. Do not write textual IR and parse it: the lab is about the C++ API.

The contract¶

// labs/ch10-irbuild/include/irbuild/Build.h  (provided; do not change)
namespace irbuild {
std::unique_ptr<llvm::Module> buildFib(llvm::LLVMContext &Ctx);
std::unique_ptr<llvm::Module> buildHorner(llvm::LLVMContext &Ctx);
std::unique_ptr<llvm::Module> buildDispatch(llvm::LLVMContext &Ctx);
}

Ownership. The returned unique_ptr<Module> owns the module. The module owns its functions, the functions own their blocks, and the blocks own their instructions (Lesson 10.1). The LLVMContext owns every type and constant you create, so it must outlive the module. The tests create the context, and after verification they move module and context together into an orc::ThreadSafeModule.

Input and output formats¶

There is no file input. The provided driver ch10-irbuild-dump fib|horner|dispatch (tools/DumpMain.cpp) prints your module as textual IR and exits with status 1 if it does not verify. The lit tests check that output with FileCheck. You can use it to look at your own IR:

build/<preset>/bin/ch10-irbuild-dump horner
build/<preset>/bin/ch10-irbuild-dump horner | opt -passes=verify -disable-output

Provided infrastructure¶

File	What it gives you
`include/irbuild/Build.h`	the contract
`tools/DumpMain.cpp`	`ch10-irbuild-dump`: prints a module and runs the verifier
`src/Stub.cpp`	stubs that stop with `TODO(ch10)`; delete it once your own files define the three functions

What the tests check¶

Test	Checks
`ch10.IrBuild.FibStructure`	R1 (one definition named `@fib`, argument `%n`); R2: at least one `phi`, no `alloca`, no `call`
`ch10.IrBuild.FibValues`	JIT via `LLJIT`: `fib(n)` for \(n = -5 \dots 200\), `INT64_MIN`, \(10^5\), against a C++ reference with wrapping
`ch10.IrBuild.HornerStructure`	R1; R3: argument names, exactly one `mul`, no `alloca` or `call`, at least one `load`
`ch10.IrBuild.HornerValues`	edge cases (\(n = 0\), \(n < 0\), \(n = 1\), \(x = 0\), \(x = -1\)) and 500 random coefficient arrays (up to 11 coefficients, some \(x\) large enough to wrap)
`ch10.IrBuild.DispatchStructure`	R1; R4: `%op` is `i32`, exactly one `switch` on `%op` with 9 cases
`ch10.IrBuild.DispatchValues`	every op in \(\{-1, 0, \dots, 9, 1000\}\) on 121 edge-value pairs (0, ±1, 63, 64, 65, `INT64_MIN/MAX`, …) plus 2000 random triples
`tests/ch10/lit/irbuild-{fib,horner,dispatch}.test`	the printed module verifies (`opt -passes=verify`), and FileCheck finds the `define` line with the argument names, the phis, the GEP and load, the single `mul`, the nine `switch` cases; `--implicit-check-not` rejects any `alloca` or `call` where R2 and R3 forbid them

Milestones¶

buildDispatch: the easiest, because it has no loop. Run ctest --test-dir build/<preset> -R 'ch10.IrBuild.Dispatch'.
buildFib: a loop with three phis. Run ctest --test-dir build/<preset> -R 'ch10.IrBuild.Fib'.
buildHorner: a loop over memory. Run ctest --test-dir build/<preset> -R 'ch10.IrBuild.Horner'.
ctest --test-dir build/<preset> -R ch10.lit for the shapes.

Hints¶

Hint 1 — where to start

Draw the CFG first: which blocks exist, which edges, and which values flow along each edge. Then create all the blocks with BasicBlock::Create before you emit code into any of them, so you can branch forward. Lesson 10.3 §2 shows how the insertion point moves.

Hint 2 — the key idea

A phi's operands are (value, predecessor) pairs, and the back-edge value does not exist yet when you create the phi. Create the phi with CreatePHI(Ty, 2), build the loop body, and only then call addIncoming for both edges. The verifier checks that each phi has exactly one entry per predecessor (Ch 9), and a phi operand only has to dominate the end of its incoming edge's block, which is why the back-edge value may be defined later in the loop (Lesson 10.2, Theorem 10.2.13).

Hint 3 — a design sketch

@fib: blocks entry → {exit, loop}, loop → {loop, exit}, with phis i, a, b in loop and a result phi in exit. Keep the invariant \(a = F(i-1)\), \(b = F(i)\). @horner: iterate k from n down to 1 with an accumulator phi, load coeffs[k-1], and compute acc * x + c. @dispatch: CreateSwitch(op, default, 9), one block per case, all branching to a join block whose phi collects the nine results plus the default's 0. For case 8, CreateBinaryIntrinsic(Intrinsic::smin, …) or an icmp + select both work. The bug the tests catch most often is an off-by-one in @fib's exit condition (check \(n = 1\) and \(n = 2\)).

Stretch goals ★¶

Add buildFibRec (a recursive @fib), JIT both versions and time them. Then run opt -passes='default<O2>' on the recursive one and look at what LLVM does with the recursion.
Rebuild @dispatch with IRBuilder<InstSimplifyFolder> and constant %op values in a caller, and see which cases fold away.