Exercise 8.P1 · Write PIR by hand

Chapter: 8 · The Design Space of IRs · Lesson: 8.7 (PIR) · Specification: docs/pir/pir-spec.md · Time: 1–2 hours · Tests: ./course test 8 (tests/ch08/lit/pir-multiples.test)

Goal

Before you generate PIR in Chapter 11, write it yourself. Translate the chapter's running example into PIR by hand, the way the Pebble front end will: checked arithmetic, || as control flow, typed locals. Then use the provided tools to verify it, run it, and lower it to LLVM IR.

The program, in Pebble-like pseudocode:

fn sum_multiples(n: int) -> int {
    var s = 0;
    var i = 1;
    while i <= n {
        if i % 3 == 0 || i % 5 == 0 { s = s + i; }
        i = i + 1;
    }
    return s;
}
fn main() -> int {
    print(sum_multiples(10));   // one number per line
    print(sum_multiples(999));
    return 0;
}

Requirements

• R1. labs/ch08-pir/multiples.pir is a PIR 1.0 module that parses and verifies: pir-opt --verify-only multiples.pir exits with status 0 (rules V1–V20, pir-spec §13).
• R2. pir-run multiples.pir prints exactly two lines, 33 and 233168, and exits with status 0. Print with the runtime functions @pebble_print_int and @pebble_print_newline (pir-spec §15), declared as externs.
• R3. It has the shape the Pebble front end produces: a function @sum_multiples with one i64 parameter and an i64 result that uses srem; every + of the source is a checked addition, saddo + assert !…, overflow + add (pir-spec §9.1); and @main has type fn() -> i64 and calls @sum_multiples.
• R4. The shared back end lowers it to LLVM IR that verifies: pebblec --from-pir --emit=llvm multiples.pir -o - | opt -passes=verify -disable-output.

Blocks must be numbered bb0, bb1, … in order of appearance and locals _0, _1, … with parameters first (pir-spec §3, "Numbering"). The reader tells you when they are not.

What the tests check

tests/ch08/lit/pir-multiples.test runs R1 (pir-opt --verify-only), R2 (pir-run output with FileCheck, no other output), R3 (FileCheck on the canonical form printed by pir-opt: fn @sum_multiples(_0: i64…) -> i64, then srem, saddo, assert !…, overflow, fn @main() -> i64, call @sum_multiples() and R4. Until you replace the provided multiples.pir, it prints TODO(ch08): P1: … and traps.

Hints

Hint 1 — where to start

Read pir-spec §6 (functions, locals, blocks) and §18 (a worked example with a loop and a checked +=), and copy the structure: declare all locals with let first, then write bb0.

Hint 2 — the key idea

|| is control flow, not an operator: test i % 3 == 0 and branch to the "add" block if true, otherwise test i % 5 == 0 and branch to the "add" block or past it. Draw the CFG first (Lesson 8.2): 7 blocks are enough for @sum_multiples.

Hint 3 — a design sketch

bb0: initialize s, i; goto bb1. bb1: c = sle i, n; br c, bb2, bb6. bb2: r = srem i, 3; z = eq r, 0; br z, bb4, bb3. bb3: the same with 5, br z, bb4, bb5. bb4: checked s = s + i; goto bb5. bb5: checked i = i + 1; goto bb1. bb6: return s. srem by a nonzero constant cannot trap, so it needs no check.