Chapter 9 exercises¶
In this chapter you write LLVM IR by hand. There is no C++: every task is one .ll file in labs/ch09-ir/src/, checked by the verifier, by FileCheck rules on its structure, and by a C driver that runs it on thousands of inputs at -O0 and -O2. The full specification, with the exact signatures, the structural rules and what each test checks, is labs/ch09-ir/SPEC.md; this page orders the tasks, ties each to its lesson and gives graded hints.
./course test 9 # all ch09 tests (one lit suite, ctest ch09.lit)
build/<preset>/bin/pebble-lit -v tests/ch09/lit/e1-collatz.test # one task while you work on it
Before you start, every test stops with TODO(ch09): <task>: …: the file does not exist yet. That is expected; the message names the task.
Stuck? Compile the C reference in the driver with clang -S -emit-llvm -O1 and read (don't copy) what clang does. The reference solutions are in solutions/labs/ch09-ir/src/; look only after the tests pass or after an honest hour.
E1 · A loop with phis, and the same loop in memory form¶
Contract: i64 @collatz_steps(i64 %n) and i64 @collatz_steps_mem(i64 %n) in labs/ch09-ir/src/collatz.ll · Test: tests/ch09/lit/e1-collatz.test · Lessons: 9.1, 9.3 (Algorithm 9.3.6), 9.4 (Proposition 9.4.12)
Count Collatz steps twice: once as SSA values with phis and no memory, once with alloca/load/store and no phis. The test also runs mem2reg on your memory form and requires a phi to appear, so the two versions are the two ends of SSA construction.
Hint 1 — where to start
List the loop-carried variables (n and the step count). Each becomes one phi in the loop header with an entry per predecessor edge.
Hint 2 — the key idea
n = 1 must return 0 without entering the loop: test in entry and give the exit block a phi with one entry from entry and one from the loop.
Hint 3 — a design sketch
Blocks entry, loop, exit; in loop, compute both successors of n and pick with select (no inner branches needed). For the memory form, one alloca per variable in entry, and blocks cond, body, even, odd, latch, exit. The common bug: %n.next defined in the body but used in the header without going through the phi ("Instruction does not dominate all uses!", F1's message).
E2 · Arrays through GEP¶
Contract: @sum_i32, @argmax_i32, @reverse_i32 in labs/ch09-ir/src/arrays.ll · Test: e2-arrays.test · Lesson: 9.4 (Definition 9.4.3)
Hint 1 — where to start
getelementptr inbounds i32, ptr %a, i64 %i is &a[i]: one index, scaled by 4.
Hint 2 — the key idea
argmax returns the first maximum: update only on a strictly greater element (icmp sgt), and keep the best value in a phi so you don't reload it. reverse needs two indices moving towards each other.
Hint 3 — a design sketch
Each function: an entry test for n ≤ 0, one loop block with phis for the index and the accumulator(s), an exit block whose phi picks the result per edge. The common bug: sext vs zext of the loaded i32.
E3 · Struct updates¶
Contract: %struct.Account = type { i64, i32, [3 x i64], double }, @record, @richest, @count_kind in labs/ch09-ir/src/structs.ll · Test: e3-structs.test · Lessons: 9.2, 9.4 (Algorithm 9.4.2)
Hint 1 — where to start
Lay out the struct first (Algorithm 9.4.2): id@0, kind@8, history@16, balance@40, size 48. The driver's _Static_asserts check the same numbers in C.
Hint 2 — the key idea
getelementptr %struct.Account, ptr %a, i64 0, i32 2, i64 1 is &a->history[1]; the leading i64 0 means "the struct %a points to" (the GEP FAQ's favorite question). For an array of accounts, the first index is the element number.
Hint 3 — a design sketch
record: three GEPs to the history slots, two loads, three stores, then sitofp and fadd for the balance. richest: keep the best pointer in a phi; compare balances with fcmp ogt (strict, so the first maximum wins).
E4 · A switch-based classifier¶
Contract: i32 @classify_char(i8 %c) in labs/ch09-ir/src/classify.ll · Test: e4-classify.test (all 256 bytes) · Lesson: 9.3 (Definition 9.3.1)
Hint 1 — where to start
One switch i8 with one case per listed byte; the default handles everything else.
Hint 2 — the key idea
Letters are two ranges: in the default block, or i8 %c, 32 maps A–Z onto a–z, and one unsigned comparison of %lower - 97 with 26 tests both ranges.
E5 · Calling printf¶
Contract: @print_record, @print_sum in labs/ch09-ir/src/printf.ll · Test: e5-printf.test (exact output lines) · Lesson: 9.5 (Definition 9.5.2)
Hint 1 — where to start
Declare i32 @printf(ptr, ...), put the format strings in private unnamed_addr constant [N x i8] c"…\00" globals (count the bytes, including \0A and the terminating \00), and call call i32 (ptr, ...) @printf(…).
Hint 2 — the key idea
You are the C front end: apply the default argument promotions yourself. A float goes as double (fpext), a char as i32 (sext).
E6 · Overflow intrinsics¶
Contract: zeroext i1 @checked_mul_add(i64, i64, i64, ptr), i32 @saturating_add_u8(i8, i8) in labs/ch09-ir/src/checked.ll · Test: e6-checked.test · Lessons: 9.5, 9.7
Hint 1 — where to start
llvm.smul.with.overflow.i64 returns { i64, i1 }; take it apart with extractvalue.
Hint 2 — the key idea
The C prototype returns _Bool, and the C caller assumes the return register holds 0 or 1: that is what zeroext on the return value promises (Lesson 9.5, ABI attributes).
E7 · An error path without exceptions¶
Contract: i32 @parse_u32(ptr %s, ptr %out) in labs/ch09-ir/src/parse.ll · Test: e7-parse.test · Lessons: 9.3, 9.5
Hint 1 — where to start
Draw the CFG first: one block per check, all failures branching to one exit block.
Hint 2 — the key idea
The exit block's phi i32 has one entry per incoming edge, and each entry is the error code of that edge; the success path stores to *out and then branches there with code 0 (Definition 9.3.4, W4).
Hint 3 — a design sketch
entry (empty string?) → loop (load byte, end?) → check (digit?) → mul (umul.with.overflow by 10) → add (uadd.with.overflow) → digit (increment) → back to loop; ok stores and joins exit. The common bug: forgetting that sub i8 %c, 48 wraps for bytes below '0', which is exactly why one unsigned comparison with 10 suffices.
E8 · invoke and a landing pad¶
Contract: @digit_or, @parse_digits_or in labs/ch09-ir/src/invoke.ll, calling the provided C++ i64 @ch09_parse_digit(i64) · Test: e8-invoke.test · Lesson: 9.3 (the invoke box)
Hint 1 — where to start
Compile a small C++ try { … } catch (...) { … } with clang++ -S -emit-llvm -O1 and find the invoke, the landingpad and the personality.
Hint 2 — the key idea
catch ptr null catches everything; after the landing pad, call __cxa_begin_catch on the exception pointer (field 0 of the landing pad's { ptr, i32 }) and then __cxa_end_catch, which ends the catch and frees the exception.
E9 · The GEP puzzles¶
Contract: @p1, @p1_bytes, @p2, @p3, @p3_bytes, @p4, @p5, @p6 in labs/ch09-ir/src/gep.ll · Test: e9-gep.test · Lesson: 9.4 (Algorithm 9.4.4, Theorem 9.4.5, Algorithm 9.4.9)
Compute every offset by hand before running the test; then check with ./course drill gep-offset.
Hint 1 — where to start
Lay out %struct.Inner (size 20) and %struct.Outer (in@4, total@64, size 72) with Algorithm 9.4.2.
Hint 2 — the key idea
Struct indices are i32 constants; array indices may be variables. p1_bytes is Algorithm 9.4.9's output: constant parts as one getelementptr i8 with the summed offset, variable parts as multiplications (or shifts) of the index.
F1–F7 · Fix the broken IR¶
Inputs: labs/ch09-ir/broken/fix1-dominance.ll … fix7-types.ll · Your files: the same names in labs/ch09-ir/src/ · Tests: tests/ch09/lit/f1-dominance.test … f7-types.test · Lessons: 9.3 (Definition 9.3.4, Algorithm 9.3.7), 9.5 (F6)
Each input fails opt -passes=verify (F7: the parser) with the message quoted at its top. Copy it, name the violated rule (W1–W7), repair it, and keep its specified behavior. Practice first with ./course drill ir-validity.
Hint — the repairs, in one line each (open only after trying)
F1: a value that depends on the path needs a phi. F2: a phi needs an entry for every predecessor edge. F3: phis first. F4: a loop header cannot be the entry block; add a new entry. F5: a loop-carried value is a phi, never %x = add %x, …. F6: read the intrinsic's signature in the LangRef. F7: conditions are i1, and every ret returns the function's type.
Measurement¶
Fill in the table in SPEC.md (code size of your two E1 functions at llc -O0, llc -O2 and after opt -O2; what instcombine does to your E9 GEPs) and compare with Lesson 9.4 §8.
★ Optional: the stretch goals in the spec: a variadic function of your own with va_arg, a lookup-table version of E4, and !range metadata on E2's loads.