Lab 9 · Hand-written LLVM IR¶

Chapter: 9 · LLVM IR in Depth · Lessons: 9.1–9.7 · Time: 8–12 hours · Tests: ./course test 9 (label ch09, ctest ch09.lit)

Goal¶

You write LLVM IR by hand: nine small programs (E1–E9) and seven repairs of broken IR (F1–F7). Each program is one .ll file with functions of a fixed signature; a provided C driver calls them on thousands of inputs and compares every result with a C reference implementation. Writing IR without a front end in the way forces every decision the lessons describe: where the phis go and which edges they name (Lesson 9.3), which GEP indices reach a field and why struct indices are i32 constants (Lesson 9.4), how a variadic call and an overflow intrinsic are typed (Lesson 9.5), and which verifier rule a broken function violates.

Two tasks are comparisons of competing representations, measured below: the memory form vs the register (SSA) form of the same loop (E1), and typed GEPs vs the byte-offset getelementptr i8 form that LLVM 23 canonicalizes to (E9).

Requirements¶

Every task:

R0. The file is labs/ch09-ir/src/<name>.ll, opaque-pointer textual IR that opt -passes=verify accepts. It defines the functions listed with exactly the IR signature given (types, zeroext where shown). It may define other private helpers, globals and types. It has no target triple or target datalayout line (the tests compile for the host).
R1. Behavior matches the C reference in the driver on every input the driver tries, both when the file is compiled at -O0 and at -O2. At -O2 the optimizer takes your IR at its word, so IR that relies on undefined behavior or poison (Lesson 9.7) fails there even if it passes at -O0.
R2. The structural rules of the task hold (checked with FileCheck on opt -S of your file, so value names and formatting are yours to choose).

The programs¶

Task	File	IR signature(s)	Behavior	Structural rules
E1 loop with phi	`collatz.ll`	`i64 @collatz_steps(i64 %n)`, `i64 @collatz_steps_mem(i64 %n)`	number of Collatz steps from `n ≥ 1` to 1 (`n` even → `n/2`, odd → `3n+1`); both functions compute the same thing	`@collatz_steps`: no `alloca`/`load`/`store`, at least one `phi`. `@collatz_steps_mem`: uses `alloca`, has no `phi`; after `opt -passes=mem2reg` it has a `phi` and no `alloca`
E2 arrays via GEP	`arrays.ll`	`i64 @sum_i32(ptr %a, i64 %n)`, `i64 @argmax_i32(ptr %a, i64 %n)`, `void @reverse_i32(ptr %a, i64 %n)`	sum of `n` `i32`s sign-extended to `i64` (0 if `n ≤ 0`); index of the first maximum (−1 if `n ≤ 0`); reverse in place without touching `a[n]`	no `alloca`, `ptrtoint` or `inttoptr`; every function uses `getelementptr`; `@sum_i32` has a `phi`
E3 struct updates	`structs.ll`	identified type `%struct.Account = type { i64, i32, [3 x i64], double }`; `void @record(ptr %a, i64 %amount)`, `ptr @richest(ptr %v, i64 %n)`, `i64 @count_kind(ptr %v, i64 %n, i32 %kind)`	`record`: `history[2]←history[1]`, `history[1]←history[0]`, `history[0]←amount`, `balance += (double)amount`; `richest`: pointer to the first account with the largest balance (`null` if `n ≤ 0`); `count_kind`: how many have `kind == %kind`	the type line exactly as given; no `alloca`/`ptrtoint`/`inttoptr`; each function indexes with `getelementptr … %struct.Account`
E4 switch classifier	`classify.ll`	`i32 @classify_char(i8 %c)`	0 for `0`–`9`; 1 for `a`–`z`, `A`–`Z`, `_`; 2 for space, `\t`, `\n`, `\r`; 3 for any of `+-*/%=<>!&\|^~`; 4 for any of `()[]{},;:.`; 5 otherwise (all 256 bytes are tested)	no `alloca`; uses `switch i8`; the result reaches `ret` through a `phi i32`
E5 varargs printf	`printf.ll`	`void @print_record(i32 %id, float %score, i8 %grade, ptr %name)`, `void @print_sum(ptr %v, i64 %n)`	`print_record` prints `#<id> <grade as a char> <name>: <score with 2 decimals>` and a newline; `print_sum` prints `sum of <n> values = <sum>` and a newline (the `n` values are `i64`s)	declares `printf` as `i32 @printf(ptr, ...)`; calls it as `call i32 (ptr, ...) @printf(…)`; `print_record` converts the `float` with `fpext`
E6 overflow intrinsics	`checked.ll`	`zeroext i1 @checked_mul_add(i64 %a, i64 %b, i64 %c, ptr %out)`, `i32 @saturating_add_u8(i8 %a, i8 %b)`	returns 1 if `ab` or `ab+c` overflows (signed), else stores `ab+c` to `out` and returns 0 (`*out` untouched on overflow); `min(a+b, 255)` on unsigned bytes, zero-extended	no `alloca`; calls `llvm.smul.with.overflow.i64`, `llvm.sadd.with.overflow.i64` and `llvm.uadd.with.overflow.i8`
E7 error path without exceptions	`parse.ll`	`i32 @parse_u32(ptr %s, ptr %out)`	parse the NUL-terminated decimal string `s`: return 0 and store the value to `out`; 1 if `s` is empty; 2 if a byte is not `0`–`9`; 3 if the value does not fit in 32 bits (`out` untouched on every error)	no `alloca`, `invoke` or `landingpad`; uses `llvm.umul.with.overflow.i32`; exactly one `ret`, fed by a `phi i32` of the codes
E8 invoke	`invoke.ll`	`i64 @digit_or(i64 %c, i64 %dflt)`, `i64 @parse_digits_or(ptr %s, i64 %dflt)`	call the provided C++ function `i64 @ch09_parse_digit(i64)` (returns `c - '0'`, throws for a non-digit) through `invoke`: `digit_or` returns its result or `dflt` if it threw; `parse_digits_or` returns the decimal value of `s` (0 for `""`), or `dflt` as soon as a call throws	both functions have `personality ptr @__gxx_personality_v0`, `invoke i64 @ch09_parse_digit` and `landingpad { ptr, i32 }`; `parse_digits_or` loops with a `phi`. The driver also checks, through a counter in `thrower.cpp`, that you really called it
E9 GEP puzzles	`gep.ll`	see below	see below	no `ptrtoint`/`inttoptr`/`alloca` anywhere; the per-puzzle rules below

E9 puzzles. The driver (drivers/gep.c) declares, with the layouts it asserts at compile time:

struct Inner { int16_t tag; int32_t vals[4]; };                    // size 20, align 4
struct Outer { int8_t flag; struct Inner in[3]; int64_t total; };  // size 72, align 8

Function	Returns	Rule
`ptr @p1(ptr %o, i64 %i, i64 %j)`	`&o->in[i].vals[j]`	exactly one instruction before `ret`: a `getelementptr %struct.Outer` with indices `i64 0, i32 1, i64 %i, i32 1, i64 %j`
`ptr @p1_bytes(ptr %o, i64 %i, i64 %j)`	the same address	every `getelementptr` has source element type `i8` (integer arithmetic on the offsets is allowed)
`ptr @p2(ptr %o, i64 %k)`	`&o[k].total`	one `getelementptr %struct.Outer`
`ptr @p3(ptr %o)`	`&o[1].in[2].tag`	one `getelementptr %struct.Outer` with constant indices
`ptr @p3_bytes(ptr %o)`	the same address	one `getelementptr i8` with the constant byte offset (you compute it)
`ptr @p4(ptr %m, i64 %r, i64 %c)`	`&m[r][c]` for `int32_t m[][5]`	one `getelementptr [5 x i32]`
`ptr @p5(ptr %o, i64 %i)`	`&o->in[i] + 1` (one past element `i`)	any GEPs
`i64 @p6(ptr %o, i64 %i, i64 %j)`	`o[i].in[j].vals[j]`, loaded and sign-extended	one `getelementptr %struct.Outer` using `%j` twice, then the `load`

Your IR names the types %struct.Inner and %struct.Outer (any names work, but the tests look for %struct.Outer).

The repairs¶

Each file in labs/ch09-ir/broken/ is invalid: opt -passes=verify (or, for F7, the parser) rejects it with the message quoted at the top of the file. Copy it to src/ under the same name, repair it, and keep its function's name, signature and specified behavior. The header comment of each file states the behavior; the driver is drivers/fix.c, compiled with -DFIX=<k>.

Task	File	Function	The rule it breaks (Lesson 9.3 §2)	Extra rule for your repair
F1	`fix1-dominance.ll`	`i64 @abs_diff(i64, i64)`	a use not dominated by its definition	a `phi i64`, no `alloca`
F2	`fix2-phi-preds.ll`	`i64 @clamp(i64, i64, i64)`	phi entries ≠ predecessors	a `phi i64`, no `alloca`
F3	`fix3-phi-order.ll`	`i64 @fib(i64)`	phis not grouped at the top of the block	a `phi i64`, no `alloca`
F4	`fix4-entry.ll`	`i64 @sum_squares(i64)`	the entry block has predecessors	a `phi i64`, no `alloca`
F5	`fix5-self-ref.ll`	`i64 @count_bits(i64)`	a non-phi instruction uses its own value	a `phi i64`; no `alloca`, no `llvm.ctpop`
F6	`fix6-intrinsic.ll`	`i64 @add_or_saturate(i64, i64)`	an intrinsic declared with the wrong type	keeps `llvm.sadd.with.overflow.i64`, correctly declared; no `llvm.sadd.sat`
F7	`fix7-types.ll`	`i32 @is_pow2(i64)`	type errors the parser reports (two of them)	uses an `icmp`

The contract¶

The contract is the set of function signatures above, plus the C drivers in labs/ch09-ir/drivers/ (read them: each one's reference implementation is the specification of the behavior). Nothing else is provided: no stubs, no helper IR. Design the control flow, the value names and any helper functions yourself.

Provided	What it gives you
`drivers/driver.h`	the shared test harness: a deterministic pseudo-random generator and `CH09_EXPECT_EQ`, which prints `FAIL <call>: got <x>, expected <y>`
`drivers/<task>.c`, `drivers/fix.c`	one driver per task: declarations of your functions, the C reference, the inputs
`drivers/thrower.cpp`	`ch09_parse_digit` for E8 (C++; the test links with the C++ runtime)
`broken/fix*.ll`	the inputs of F1–F7

Input and output formats¶

Each driver prints nothing but failures and one summary line:

FAIL collatz_steps(27): got 110, expected 111
FAILED: 1 of 4022 cases

or, when everything matches, ok: <n> cases (exit status 0). A driver that gets no result for 30 seconds (usually a loop in your IR that never exits) prints FAIL timeout: … and exits 1. E5 is the exception: its driver only calls your functions, and the test compares the printed lines exactly:

#7 A Ada: 91.50
#-3 C Grace Hopper: 2.71
#2147483647 F : -1.00
sum of 0 values = 0
sum of 3 values = 6
sum of 5 values = 4000000001

What the tests check¶

One lit test per task, in tests/ch09/lit/ (e1-collatz.test … e9-gep.test, f1-dominance.test … f7-types.test). Each runs, in order:

Step	Command (abridged)	Checks
1	`%ch09-need <file>`	the file exists; otherwise `TODO(ch09): <task>: …`
2	`opt -passes=verify -disable-output src/<file>`	R0: the file parses and verifies
3	`opt -S src/<file> \\| FileCheck --check-prefix=IR`	R2: the structural rules of the table
4	`clang -O0 src/<file> drivers/<task>.c -o t && ./t \\| FileCheck --check-prefix=OUT`	R1 at `-O0`: `ok: … cases`, no `FAIL`
5	the same at `-O2`	R1 at `-O2`

E1 adds opt -passes=mem2reg on your file (the memory form must become a phi). F1–F7 also check that the provided broken input still fails with the quoted message, so the spec and the files cannot drift apart. E8 compiles the driver as C, thrower.cpp as C++, and links with clang --driver-mode=g++.

Milestones¶

E1, E2 (Lessons 9.1–9.4): values, phis, a loop over memory. build/<preset>/bin/pebble-lit -v tests/ch09/lit/e1-collatz.test tests/ch09/lit/e2-arrays.test
F1–F5 (Lesson 9.3): read the verifier message, name the rule (Definitions 9.3.2–9.3.4), repair. … tests/ch09/lit/f*.test
E3, E9 (Lesson 9.4): struct layout and GEP. Compute the E9 offsets by hand with Algorithm 9.4.4 before you run the test; then check with ./course drill gep-offset.
E4, E7 (Lesson 9.3): switch, a single exit fed by a phi.
E5, E6, F6, F7, E8 (Lesson 9.5): calls, varargs, intrinsics, invoke.
Measurement (below), then compare with Lesson 9.4 §8.

Measurement: memory form vs register form, typed GEP vs `i8` GEP¶

For each pair, measure the machine code size (bytes, from llvm-nm -S) with and without the IR optimizer:

llc -O0 -mtriple=x86_64-unknown-linux-gnu -filetype=obj labs/ch09-ir/src/collatz.ll -o c0.o && llvm-nm -S c0.o
llc -O2 -mtriple=x86_64-unknown-linux-gnu -filetype=obj labs/ch09-ir/src/collatz.ll -o c2.o && llvm-nm -S c2.o
opt -O2 labs/ch09-ir/src/collatz.ll | llc -O2 -mtriple=x86_64-unknown-linux-gnu -filetype=obj -o co.o && llvm-nm -S co.o
opt -passes=instcombine -S labs/ch09-ir/src/gep.ll    # which of your GEPs change form?

Function	`llc -O0`	`llc -O2`	`opt -O2` then `llc -O2`
`collatz_steps` (register form)
`collatz_steps_mem` (memory form)

llc alone runs no IR-level optimization, so the memory form keeps its loads and stores. (Reference solution: 83 vs 110 bytes at llc -O0, 43 vs 77 at llc -O2.) Explain the last column with Lesson 9.4's discussion of mem2reg, and explain what instcombine did to @p1 and @p1_bytes with Lesson 9.4, Section 6.

Hints¶

Hint 1 — where to start

Write the C version first, then compile it with clang -S -emit-llvm -O0 -Xclang -disable-O0-optnone -fno-discard-value-names and read what clang produces. Do not copy it: it is in memory form, and most tasks forbid alloca. Instead, list the variables that change inside each loop; each becomes a phi in the loop header with one entry per predecessor.

Hint 2 — the key idea

For loops: an entry test, a header with one phi per loop-carried variable, the body, and an exit block whose phis pick the result per incoming edge (Lesson 9.3, Algorithm 9.3.6). For GEP: the first index steps over whole objects of the source element type; every later index steps into the current aggregate: an i32 constant field number for a struct, any integer for an array (Definition 9.4.3). For F-tasks: the message names the violated rule; the fix is almost always "introduce a phi" or "introduce a block".

Hint 3 — a design sketch

E7: one block per check (entry for the empty string, a loop header that loads the byte, a check block, mul, add), each failing check branching to a single exit block whose phi i32 lists one code per predecessor. E8: invoke needs a personality; the landing pad is landingpad { ptr, i32 } catch ptr null, followed by __cxa_begin_catch/__cxa_end_catch to finish the catch. E5: a variadic call spells the callee's type, call i32 (ptr, ...) @printf(…), and you apply C's default argument promotions yourself (float → double, i8 → i32). The most common bug the tests catch: a phi that forgets one predecessor edge (F2 in your own code).

Stretch goals ★¶

Write i64 @sum_ints(i32 %count, ...), a variadic function of your own, with llvm.va_start/llvm.va_end and the va_arg instruction. The va_list object is target specific (24 bytes on x86-64 Linux, 8 on AArch64 macOS, 32 on AArch64 Linux): allocate [32 x i8], align 16 and let the target decide. Compare with what clang emits for the same C function, which does not use va_arg at all on x86-64.
Rewrite E4 with a lookup table (a private constant [256 x i8] and one GEP + load) and compare the code llc -O2 emits for the two versions.
Add !range and !noundef metadata to the loads in E2 where they are true, and use opt -passes=instcombine to find an instruction they let LLVM delete (Lesson 9.6).