Chapter 11 exercises¶

You'll finish the C++ Pebble compiler. There are two halves.

Front half, E1–E4: lowerToPIR. Write it in pebble/lib/Lower/, with any file names and any number of files; every *.cpp there is compiled. It turns the typed AST into PIR. The contract is pebble/include/pebble/Lower/LowerToPIR.h, and the scheme is spec §15.
Back half, E5 and ★ E6: lowerPIRToLLVM. Write it in pebble/lib/CodeGen/PIRToLLVM.cpp. It turns PIR into LLVM IR that follows the runtime ABI. The contract is pebble/include/pebble/CodeGen/PIRToLLVM.h.

The provided driver (pebble/lib/Driver/) then emits an object file and links it with the runtime (Lesson 11.9), so pebblec prog.pbl -o prog && ./prog works. The comparison lab (labs/ch11-lowering/SPEC.md) compiles conditions and switches in competing ways and measures them.

./course test 11                                      # builds, then runs every test labelled ch11
ctest --preset linux -L '^ch11$' --output-on-failure  # the same through ctest (macos: --preset macos)
build/<preset>/bin/pebble-lit -v tests/ch11/lit/pir-checks.pbl     # one lit file, verbose
build/<preset>/bin/pebble-lit -v tests/ch11/e2e/trap-*.pbl         # some end-to-end programs
build/<preset>/bin/pebble-lit -Dlevels= tests/ch11/e2e             # front end + pir-run only (before E5)
build/<preset>/bin/pebblec --emit=pir prog.pbl        # look at your PIR
build/<preset>/bin/pebblec --emit=llvm prog.pbl       # look at your LLVM IR

Before you start. In a pure skeleton build, every ch11 test that starts from Pebble source stops at the first unfinished stage before yours, which is the lexer (TODO(ch01)). Build the front end from the solutions if yours isn't done:

cmake --preset linux -DPEBBLE_USE_SOLUTION=lexer,parser,names,types     # your lowering, your codegen
cmake --preset linux -DPEBBLE_USE_SOLUTION=lexer,parser,names,types,codegen   # E1–E4 with the reference back half
cmake --preset linux -DPEBBLE_USE_SOLUTION=lexer,parser,names,types,lower     # E5 with the reference front half

Then the tests fail with TODO(ch11): E1: lower the typed AST to PIR (lowerToPIR), TODO(ch11): E5: lower a PIR module to LLVM IR (lowerPIRToLLVM) and, for the lab, TODO(ch11): L1: …/L2: …. That's expected: each message names the exercise that fixes it. You can do the halves in either order. pebblec --from-pir x.pir tests E5 on hand-written PIR, and pir-run tests E1–E4 without any code generator.

Stuck? Work through the hints in order. The reference solutions are in solutions/pebble/lib/Lower/ and solutions/pebble/lib/CodeGen/PIRToLLVM.cpp, but only look at them after you've passed the tests, or after an honest hour.

Common rules for E1–E4. - C1. The PIR passes pir::verifyModule, and under pir-run it behaves exactly as the spec says: output, exit status and trap message with its location. pir-run is the oracle (docs/architecture.md §8). - C2. Every statement and terminator carries the @line:col of the Pebble construct that produced it. Trap locations come from these (spec §15, "Locations"). - C3. Follow spec §15's naming and ordering (locals, blocks, runtime externs on first use) if you want the lit tests' exact-match lines to pass. Any other verified lowering that behaves the same is also correct, and the e2e suite accepts it. - C4. Use the type of every expression from analyze() (Ch 6's side table, Expr::getType()); never re-infer types.

E1: Expressions and checks¶

Lessons: 11.1 (Algorithm 11.1.3), 11.4 (operands, Algorithm 11.4.4), 11.6 (checks as traps) Tests: tests/ch11/lit/pir-checks.pbl; e2e arith-*, trap-*, float-*, cast-*, exit-status*

Lower expressions to PIR rvalues and operands by syntax-directed translation, with every check of spec §8.3 made explicit.

Requirements: - E1-R1. Integer + - * and unary - emit the overflow predicate (saddo, ssubo, smulo), then assert !o, overflow, then the wrapping operation. &+ &- &* emit only the wrapping operation. - E1-R2. / and % check div_by_zero first, then overflow for MIN / -1 (and MIN % -1), then emit sdiv/srem. << and >> check ult b, 64 (shift). Comparisons, bitwise operators and float arithmetic have no checks. - E1-R3. Casts: int as float is sitofp, float as int is fptosi (saturating; NaN → 0), bool as int is zext. - E1-R4. Literals: a negated literal is a constant, so -9223372036854775808 works; an integer literal typed float is an f64 constant. - E1-R5. Operands are evaluated left to right, and each check comes right after its operands and before the operation (spec §8.2). Temporaries are fresh unnamed locals, one per operation (Lemma 11.1.4). - E1-R6. main's result is the exit status (exit-status*: the runtime keeps the low 8 bits).

What the tests check: pir-checks.pbl checks the exact predicate/assert/operation triples for +, -, *, unary -, /, % and shifts, their trap kinds and locations, and that &+ has no check. The trap-* programs check each trap's message, line:col and exit status 101 under pir-run and natively. arith-min-literal checks INT64_MIN.

Hint 1 — where to start

Start with a FunctionLowering class that owns a pir::Builder and a map from VarDecl * to pir::LocalId, and one method pir::Rvalue lowerRvalue(Expr *). Handle integer literals, variables and +, then make return 1 + 2; from main pass pir-run. pebblec --emit=pir shows what you produce, and pir-opt --verify-only tells you what is wrong with it.

Hint 2 — the key idea

Keep three functions: lowerRvalue(e), which gives the PIR rvalue of e; lowerOperand(e), which gives a constant, a place, or a fresh temporary holding lowerRvalue(e); and lowerPlace(e) (E3). A binary operation lowers both operands, sets the location, emits the checks, and returns the operation as an rvalue. The caller decides where the value goes, which saves a copy for x = a + b (destination-driven).

Hint 3 — a design sketch

A helper LocalId assignTemp(Type *, Rvalue) that creates an unnamed local and assigns to it covers most checks: o = assignTemp(bool, saddo a, b); B.assertFalse(o, overflow). The common bugs the tests catch: checking MIN / -1 before the zero test (the order is fixed by the spec), a trap location that points at the operand instead of the operator, and emitting neg for a negated literal (which overflows for MIN).

Done when: pir-checks.pbl and the arith-*, trap-*, float-*, cast-* and exit-status* programs pass (pebble-lit -v tests/ch11/lit/pir-checks.pbl tests/ch11/e2e/{arith,trap,float,cast,exit}-*.pbl).

E2: Statements and control flow¶

Lessons: 11.2 (Algorithm 11.2.2), 11.4 (loop shapes, Definition 11.4.6) Tests: tests/ch11/lit/pir-jumping-code.pbl, pir-for-loop.pbl, pir-zero-init.pbl; e2e control-*, shortcircuit-*, bool-logic, scope-shadowing

Lower let/var, assignment, if/else, while, for i in a..b, break, continue and return into PIR blocks. Compile every condition as jumping code.

Requirements: - E2-R1. Conditions of if and while go through lowerCond(e, t, f) (Algorithm 11.2.2). &&, || and ! only choose targets and create blocks; each comparison ends in one br. PIR has no and/or/not on bool from these operators. - E2-R2. A &&/|| used as a value (let b = x && y;) is jumping code into two blocks that assign true/false, then a join (Lesson 11.2 §3). - E2-R3. for i in a..b follows spec §15: the counter and a hidden end local are assigned once, the loop is top-tested (slt), the increment is unchecked, and continue targets a latch block created on first use. tests/ch11/lit/pir-for-loop.pbl is pir-spec §18's worked example and must match exactly. - E2-R4. var x: T; assigns the zero value of T (recursively for aggregates, E3). - E2-R5. No code after return, break or continue in the same block. Blocks that nothing can reach are not created (use a "dead" insertion state), and every live block ends in a terminator.

What the tests check: pir-jumping-code.pbl checks the targets and block structure of nested &&/||/! conditions, with an implicit check that no and/or/not appears. pir-for-loop.pbl checks the §18 example line by line. The shortcircuit-* programs check that the right operand's side effects (calls that print) happen only when they should, and control-* covers nested loops with break/continue and early returns.

Hint 1 — where to start

Implement if with a plain bool variable condition first (br c, then, else). Then add lowerCond for comparisons, then ! (swap targets), then && and || (one new block each). Test each with pebblec --emit=pir on a four-line program before you run the suite.

Hint 2 — the key idea

lowerCond(e1 && e2, t, f) creates a block m, lowers e1 to (m, f), switches to m, and lowers e2 to (t, f). There is no value and no join. A loop needs a map from the loop statement to its exit block and its continue target, so that break and continue know where to jump.

Hint 3 — a design sketch

Keep a bool Dead flag. It is set after a terminator and cleared when a new block starts. Statements lowered while Dead produce nothing. Create join and latch blocks lazily, only if some edge reaches them; otherwise the verifier finds a block with no terminator. The common bugs are a for loop whose end value is re-evaluated every iteration (it must be evaluated once, into the hidden local) and continue in a for loop skipping the increment.

Done when: the three lit files and the control-*, shortcircuit-*, bool-logic and scope-shadowing programs pass.

E3: Places, aggregates, calls and output¶

Lessons: 11.4 (Algorithm 11.4.4, Theorem 11.4.5), 11.5 (value semantics, Algorithm 11.5.2) Tests: e2e agg-*, ref-*, order-*, fn-*, str-*, extern-c, prog-*; pir-zero-init.pbl

Lower places (x, p.f, a[i], reference parameters), array and struct literals, calls with &/&mut arguments, and print/write with string interpolation.

Requirements: - E3-R1. lowerPlace(e) returns a PIR place with field, index and deref projections. a[i] evaluates a, then i, then the bounds check ult i, N. A constant index within 0..N needs no check. A reference parameter p is the place (*_p). - E3-R2. Evaluation order (Theorem 11.4.5). Operands are left to right. An operand that is a place is copied into a temporary if a later operand in the same list contains a call with a &mut argument (Definition 11.4.2). In d = e and d op= e, the destination's indices and checks come first, and they are stabilized if e may write. - E3-R3. Aggregates have value semantics: assignment copies, array and struct literals evaluate their elements left to right, [v; N] evaluates v once, and var x: T; zero-initializes recursively. - E3-R4. Calls: &place / &mut place arguments are assigned to a temporary of reference type, which is then passed. A call with an aggregate or unit result is still a PIR call statement (the code generator implements the ABI, E5). - E3-R5. print(v) / write(v) call pebble_print_int|float|bool|str, and print adds pebble_print_newline. An interpolated string evaluates all its values first, left to right, then prints the pieces in order. Text is truncated at the first NUL. Runtime externs are declared on first use, in order.

What the tests check: order-args, order-binary-call and order-assign-place detect a read that happens after a &mut call instead of before. ref-* checks &mut of elements, fields and parameters passed on. agg-* checks copies, literals, [v; N], zero-initialization, empty structs, large arrays and aggregate results. str-interp checks evaluation before printing. The prog-* programs (bank, Collatz, Newton's method, matrix multiplication, sieve) combine everything.

Hint 1 — where to start

Do places first: x and a[i] for local arrays, used as an assignment target and as an operand. Then struct fields, then reference parameters. order-* should be last, because it needs the materialization rule.

Hint 2 — the key idea

A place used as an operand is read when the instruction that uses it executes, not when you lowered it. That is correct unless something between the two can write the variable, and in Pebble only a call with a &mut argument can (Lemma 11.4.3). A pre-pass mayWrite(Expr *) over each operand list tells you when to copy.

Hint 3 — a design sketch

lowerOperands(list): compute mayWrite for each suffix, lower each operand, and copy it to a temporary if a later one may write and it isn't stable (a constant or a temporary). For assignment, lower the destination place, then replace any non-temporary index local in it by a copy if the right-hand side may write. Pebble has no user code between the copy and the use, so this is enough. Struct declarations may refer to each other: declare PIR struct types in dependency order.

Done when: every e2e program passes under pir-run (pebble-lit -Dlevels= tests/ch11/e2e).

E4: End-to-end programs¶

Lessons: all; 11.9 for the native half Tests: ch11.e2e (66 programs), ch11.lit, and the conformance suite (ctest -L conformance)

E4 is not new code: it is the point where your lowering meets the whole pipeline. Every program in tests/ch11/e2e/ must behave identically under pir-run and as a native executable at -O0, -O1 and -O2, and every LLVM module it produces must pass the verifier (opt -passes=verify).

Requirements: - E4-R1. All 66 programs pass with your lowering and your code generator (after E5), or with your lowering and the reference code generator (switch codegen). - E4-R2. The PIR you produce is canonical: pir-opt prints it back unchanged (the runner checks with pir-opt --verify-only). - E4-R3. Write two programs of your own in the same format (// EXPECT-STDOUT:, // EXPECT-TRAP: <message> @L:C, // EXPECT-STATUS:) for a construct you found hard, and add them to tests/ch11/e2e/.

What the tests check: for each program, (1) pebblec --emit=pir succeeds, (2) the PIR verifies, (3) pir-run shows the expected stdout, exit status and trap line, and (4) at each -O level the LLVM module verifies and the executable behaves the same. On failure the runner prints the command that failed.

Hint 1 — reading a failure

Run one program verbosely: pebble-lit -v tests/ch11/e2e/prog-bank.pbl. If pir-run already disagrees, the bug is in E1–E3. If only a native level fails, it is in E5, or it is undefined behavior that pir-run would have reported (status 70).

Hint 2 — differential debugging

pebblec --emit=pir x.pbl -o x.pir && pir-run x.pir, then pebblec --from-pir x.pir -O0 -o x && ./x. Compare the outputs, then bisect the program by deleting statements until the difference disappears (Chapter 12's ddmin does this automatically).

Hint 3 — only at -O2?

A difference that appears only at -O2 usually means your LLVM IR has undefined behavior that -O0 happens to hide: an add nsw where PIR's add wraps, a load of an uninitialized alloca, or a call LLVM recognizes as a library function (sqrt: see the nobuiltin rule of E5).

Done when: ctest --preset linux -R 'ch11\.(e2e|lit)$' passes.

E5: PIR to LLVM IR¶

Lessons: 11.1 (allocas + mem2reg, Algorithm 11.1.6), 11.3 (PIR switch → LLVM switch), 11.5 (Algorithm 11.5.2), 11.6 (trap blocks), 11.9 (runtime declarations) Tests: tests/ch11/lit/llvm-abi.pbl, llvm-traps.pbl, driver-modes.pbl; ch11.CodeGenTest.* (tests/pir/unit/CodeGenTest.cpp: every conformance PIR program behaves like pir-run at -O0 and -O2); all of ch11.e2e natively

Implement lowerPIRToLLVM (pebble/include/pebble/CodeGen/PIRToLLVM.h). The plan in the stub's comment is the order the tests exercise it.

Requirements: - E5-R1. Types and frames: map PIR types as the header says (bool is i1 in registers and i8 in memory). Create one alloca per local in the entry block and store the scalar parameters into theirs (Clang's strategy). mem2reg is LLVM's job (pebblec -O2, or the course pipeline once a chapter registers a promotion step), not yours. - E5-R2. Functions: PIR @main becomes define i64 @pebble_main(), other defined functions are internal, and extern fns are external declarations with zeroext on bool parameters. Calls to defined functions carry the call-site attribute nobuiltin. - E5-R3. Aggregates (Algorithm 11.5.2): an aggregate parameter is a ptr to a copy the caller makes; an aggregate result uses a leading ptr sret(<T>) noalias parameter and returns void. Aggregate assignment is a memcpy. - E5-R4. Operations: overflow predicates use llvm.s{add,sub,mul}.with.overflow, fptosi uses llvm.fptosi.sat, and the rest follow pebble/PIR/Operations.def. PIR switch becomes an LLVM switch. - E5-R5. assert and trap branch to a block that calls void @pebble_trap(i32 kind, ptr file, i32 line, i32 col) (declared noreturn nounwind cold) followed by unreachable, with the trap kind's runtime code and the statement's location. Runtime functions are declared on first use (Algorithm 11.9.2). - E5-R6. The module passes llvm::verifyModule, and the executable behaves like pir-run on the same PIR.

What the tests check: llvm-abi.pbl checks the function signatures (internal, sret, ptr parameters, zeroext, nobuiltin) and the caller's copies. llvm-traps.pbl checks the trap blocks, their arguments and noreturn, and the i8 round trip of bool. driver-modes.pbl checks --emit=pir|llvm|obj|exe, --from-pir and --from-llvm. CodeGenTest compiles every conformance PIR program and compares its behavior with pir-run.

Hint 1 — where to start

Create the functions first, all of them before any body, because calls may refer to functions defined later. Then do one function with scalar locals, assign, return and br, and run pebblec --from-pir on tests/conformance/lit/pir/fib.pir. Add operations one PIR opcode at a time.

Hint 2 — the key idea

One helper, Value *placeAddress(Place), gives a pointer for any PIR place: the local's alloca, then a GEP per field or index projection, and a load of the pointer for a deref. Operands are loads from placeAddress. Assignments are stores to it, or a memcpy for aggregates. Everything else is a switch over opcodes.

Hint 3 — a design sketch

For each PIR block, create an LLVM block up front and put the allocas in a separate entry block that branches to bb0. Then PIR block numbering never matters, and allocas stay in the entry block, where mem2reg requires them. The common bugs: storing an i1 into an i8 slot without zext, forgetting to copy an aggregate argument (the callee may modify it), and loading a bool from its i8 slot without a trunc to i1.

Done when: ctest --preset linux -L '^ch11$' -E 'Lab|SSAOnTheFly' --output-on-failure passes.

E6: On-the-fly SSA¶

Optional (★). Lesson: 11.1 (Algorithm 11.1.9, Theorems 11.1.10–11.1.11) Tests: tests/ch11/lit/ssa-braun.pbl, ch11.SSAOnTheFly.ShapeAndMinimality, ch11.SSAOnTheFly.ExecutablesBehaveLikeTheInterpreter

Implement CodeGenOptions::SSA = SSAConstruction::OnTheFly (pebblec --ssa=braun). Every scalar local whose address is never taken is an SSA value from the start. Braun et al.'s writeVariable/readVariable/sealBlock place the phis, and trivial phis are removed as you go, so no alloca, load or store is emitted for these locals. Until you implement it, return an Error whose message starts with unsupported:, and the ★ tests skip.

Requirements: - E6-R1. Only scalar locals that are never the root of a &/&mut place are promoted. Aggregates and address-taken locals keep their allocas. - E6-R2. A block is sealed when all its predecessors have been generated. Count each PIR block's predecessor edges up front and seal a block when its last incoming edge is emitted. - E6-R3. Trivial phis (Definition 11.1.8) are removed recursively, including phis that become trivial when another is removed. The result has no more phis than allocas + mem2reg produces for the same program (on Pebble's reducible CFGs both are minimal: Theorem 11.1.11, Proposition 11.1.12). - E6-R4. The executables behave exactly as with --ssa=allocas.

What the tests check: ssa-braun.pbl checks that a loop's two variables become header phis, that no scalar alloca remains, and that a copy-propagated constant appears directly. ShapeAndMinimality compiles every e2e program both ways and compares phi counts with mem2reg's. ExecutablesBehaveLikeTheInterpreter runs them.

Hint 1 — where to start

Implement readVariable for a sealed block with a single predecessor (just recurse) and for a local definition (a map from (local, block) to Value *). Get straight-line code and if without loops right before you touch sealing.

Hint 2 — the key idea

In an unsealed block (a loop header), readVariable creates an empty phi, records it as incomplete, and returns it. sealBlock fills the operands of every incomplete phi of the block by reading the variable in each predecessor, then tries to remove it as trivial. Braun et al.'s paper gives the full pseudocode in its Section 2 [BBH+13].

Hint 3 — a design sketch

Store definitions in DenseMap<std::pair<LocalId, BasicBlock *>, TrackingVH<Value>>, so that replacing a trivial phi updates every stored definition automatically. When you remove a phi, collect its phi users as WeakVH handles before replaceAllUsesWith, then try to remove those too; a user may be deleted during the recursion.

Done when: ctest --preset linux -R 'ch11\.(SSAOnTheFly|lit)' passes.

Lab: Short-circuit conditions and switch lowering¶

Lessons: 11.2, 11.3 · Spec: labs/ch11-lowering/SPEC.md · Tests: ch11.Lab.*, ch11.lab.measure-smoke*

L1. emitCondition: compile a condition as jumping code and as boolean values (SPEC R1–R2).
L2. emitSwitch: an LLVM switch, a jump table, a balanced binary search and bit tests (SPEC R3–R9).

Then measure both with ch11-lowerlab and explain the numbers (SPEC "Measurement"). The stubs are in labs/ch11-lowering/src/, and the contract is labs/ch11-lowering/include/lowerlab/Lowering.h.