Chapter 8 · Exercises¶
Every exercise is specified in full in its SPEC (requirements, formats, tests, milestones). This page is the index, with a short statement of each task and graded hints. Run the tests with ./course test 8. In the skeleton build every Chapter 8 test fails with TODO(ch08) until you implement the contract. The provided-tool tests (ch08.Machines.HandWritten, run-machines.test) pass from the start.
| # | Task | Spec | Contract | Lessons |
|---|---|---|---|---|
| L1 | Lower Tiny to stack bytecode, TAC, ANF and block-argument SSA, and measure them | labs/ch08-forms/SPEC.md | irforms::lower in labs/ch08-forms/include/irforms/Lower.h |
8.1, 8.4, 8.6 |
| L2 | Leaders, blocks, CFG, DFS orders, back and critical edges; split critical edges | labs/ch08-cfg/SPEC.md | cfglab::analyze, cfglab::splitCriticalEdges in labs/ch08-cfg/include/cfglab/CFG.h |
8.2 |
| P1 | Write the running example in PIR by hand | labs/ch08-pir/SPEC.md | the file labs/ch08-pir/multiples.pir |
8.7 |
| X1 | ★ Local value numbering on the lab's TAC | below | none (untested) | 8.3 |
L1 · One program, four IRs¶
Write irforms::lower(const tiny::Program &, Form) so that the provided interpreters return the reference evaluator's value for every program, the SSA passes the validator (rules S0–S4), and the ANF is well scoped. Then run ch08-compare and fill in the measurement table of the SPEC.
Hint 1 — where to start
TAC first (Algorithm 8.1.4), then stack (Algorithm 8.1.7). Both are one recursive walk over the tree with a name supply for temporaries and labels. Check each with ch08-lower --form=tac labs/ch08-forms/inputs/euler1.tiny | ch08-run --form=tac -.
Hint 2 — the key idea for SSA and ANF
An environment from source variables to atoms replaces copies. Joins get fresh parameters for every variable (Algorithm 8.4.7). ANF is the same traversal with meta-level continuations (Algorithm 8.6.5): if puts the rest of the statements into a join point, while becomes a loop point.
Hint 3 — a design sketch
See the SPEC's Hint 3: one small emitter per form; gen(expr, env) -> atom; stmts(list, env) -> env (SSA) or stmts(list, index, env, K) -> lines (ANF). Test the &&/|| join and a while inside an if early; the random tests contain both.
L2 · Basic blocks, CFG and orders¶
Write cfglab::analyze (leaders, blocks, successors, preorder, postorder, RPO, back edges, critical edges, in the exact output format of the SPEC) and cfglab::splitCriticalEdges.
Hint 1 — where to start
A label-to-index map, then the three leader rules in one pass (Algorithm 8.2.3). A block's successors depend only on its last instruction.
Hint 2 — the key idea
Iterative DFS with an explicit stack of (block, next successor) and an on-stack flag (Algorithm 8.2.8). For splitting, compute the critical edges once, on the original CFG, and treat a branch's taken and fall-through edges separately (Algorithm 8.2.6).
Hint 3 — a design sketch
See the SPEC's Hint 3. Remember that a branch to its own fall-through is a single edge, and that unreachable blocks still count as predecessors.
P1 · PIR by hand¶
Write labs/ch08-pir/multiples.pir: @sum_multiples(i64) -> i64 with checked additions and || as control flow, and a @main that prints the sums up to 10 and 999.
Hint 1 — where to start
Copy the structure of pir-spec §18's worked example: let declarations, then bb0. Keep the reader's error messages open: they name the rule and the line.
Hint 2 — the key idea
Draw the CFG before writing: the || needs two test blocks that share one "then" block.
Hint 3 — a design sketch
Seven blocks, in the SPEC's Hint 3. Check with pir-opt --verify-only, pir-run, then pebblec --from-pir --emit=llvm -O2 to see LLVM remove your checks.
X1 · Local value numbering on the lab TAC¶
★ Optional, untested. Extend your L1 TAC output with a pass that runs local value numbering (Algorithm 8.3.5) on each basic block of your listing (use your L2 blocks) and replaces each redundant instruction by a copy from a holder. Measure the static size and the executed steps before and after with ch08-run --form=tac --stats, on straight.tiny (three redundant instructions, Lesson 8.3 §3) and on the random programs.
Hint 1 — where to start
Only straight-line code inside a block is in scope. Reset the table at every leader.
Hint 2 — the key idea
The kill rule: when a variable is reassigned, remove it from the holders of its old value number (Lesson 8.3's pitfall). A key whose value has no holder left must be recomputed.
Hint 3 — a design sketch
map<Key, int> table; map<string, int> varVN; map<int, set<string>> holders; with Key = (op, vn1, vn2) and the operands sorted for add, mul, eq, ne. Compare your results with ./course drill value-numbering --solution on a few seeds.