Chapter 21 exercises

pebblec does not have its own instruction selector: it hands LLVM IR to LLVM's back end, which selects with SelectionDAG at -O1 and above (FastISel, or GlobalISel on AArch64, at -O0). So this chapter's exercises build the classic selectors yourself, on a toy ISA where every choice is visible, and then read LLVM's selectors at work:

• E1–E3 (the comparison lab labs/ch21-isel/SPEC.md, part A): macro expansion, maximal munch and optimal DP tiling for the Tessera ISA, checked by a simulator and by brute force, and measured against each other.
• E4 ★ (the same lab, part B): a BURG-style generator of BURS tables.
• E5 (labs/ch21-mir/SPEC.md): guided exploration of LLVM's selectors, frames and object files with llc, graded automatically.

The contract

Function or file	Exercise	What it is
isel::select(P, Algo::Macro) in labs/ch21-isel/include/isel/Select.h	E1	the macro-expansion listing of program P
isel::select(P, Algo::Munch)	E2	the maximal-munch listing
isel::select(P, Algo::DP)	E3	a minimum-cost listing
isel::burgGenerate(G, MaxStates) in include/isel/Burg.h	E4 ★	the BURS tables of grammar G as text
labs/ch21-mir/answers.yaml	E5	your 24 answers

Your code goes anywhere under labs/ch21-isel/src/ (every *.cpp there is compiled); src/Stub.cpp defines the two functions with PEBBLE_TODO until you replace them. Provided (not exercises): the tree IR, its semantics and random programs (Tree.h), the Tessera simulator and cost table (Tessera.h), the rules-file reader (Grammar.h), the BURS table runtime (BurgRuntime.h) and the command-line drivers ch21-isel, ch21-sim, ch21-burg, ch21-compare.

./course test 21                                   # builds, then runs every test labelled ch21
ctest --preset linux -L '^ch21$' -R munch          # one selector while iterating (macos: --preset macos)
ctest --preset linux -L star                       # the optional part B
build/linux/bin/ch21-isel --algo=munch labs/ch21-isel/inputs/running.tree \
  | build/linux/bin/ch21-sim labs/ch21-isel/inputs/running.tree -

Before you start, every ch21 test fails with TODO(ch21): E1-E3: …, TODO(ch21): E4 (optional): … or TODO(ch21): E5: …. Each message names the exercise that fixes it. Inside ch21.lit, the two files that check provided code (sim-errors.test and the llc facts in mir-facts.test) pass from the start.

Stuck? Work through the hints in order. The reference solutions are in solutions/labs/ch21-isel/src/ and solutions/labs/ch21-mir/answers.yaml; look only after passing the tests, or after an honest hour.

---

E1 — Macro expansion

Contract: isel::select(P, Algo::Macro) · Tests: ch21.Algos/Selectors.*/macro, ch21.Ordering.*, isel-running.test, isel-samples.test · Lesson: 21.1, Algorithm 21.1.6

Cover every node of every statement with its operator's macro rule (SPEC R2), emitting code children first. This is how baseline compilers such as Winch and Sparkplug work, and it gives the reference point for the other two selectors.

Requirements: SPEC R1, R2, R7. The macro cost of a program is the sum of its nodes' macro-rule costs (the tests recompute it independently).

What the tests check: exact costs on the five sample programs (running.tree costs 9 with 7 instructions) and on 200 random programs, correctness on the simulator, determinism.

Hint 1 — where to start

Write the pattern matcher first (SPEC milestone 1); macro expansion only ever calls it with one rule per operator.

Hint 2 — the key idea

A rule's result is text: a fresh register rN for %d, or the operand itself for a template =X. Emit the operands first and substitute their results into the template.

Hint 3 — a design sketch

An emitter object with a register counter and an output buffer, and one function emit(node, rule) -> result text. The MOVE destination is not an operand to compute: it is the pattern's TEMP leaf.

Done when: the macro tests pass.

---

E2 — Maximal munch

Contract: isel::select(P, Algo::Munch) · Tests: ch21.Algos/Selectors.*/munch, ch21.Ordering.*, isel-running.test · Lesson: 21.1, Algorithm 21.1.8

Top-down, take the largest matching pattern for the goal nonterminal, ties to the lower rule number (SPEC R3), and recurse into its operand nodes.

Requirements: SPEC R1, R3, R5 (munch ≤ macro), R7.

What the tests check: exact costs (so your tie-breaking must follow R3), shadd and movm on the running example at cost 6, correctness and determinism.

Hint 1 — where to start

Sort the rules once by (pattern size descending, rule number ascending); munch then takes the first rule in that order that matches with the right left-hand side.

Hint 2 — the key idea

Munch never reconsiders: the rule chosen at a node fixes the goals of its operand nodes. Compare your choices with ./course drill munch-tiling --solution.

Hint 3 — a design sketch

choose(node, goal) -> rule plus the E1 emitter. The size counts operator nodes only (Pattern::size); counting nonterminals too breaks the tie-breaking and the corpus costs.

Done when: the munch tests pass.

---

E3 — Optimal tiling by dynamic programming

Contract: isel::select(P, Algo::DP) · Tests: ch21.Algos/Selectors.*/dp, ch21.Ordering.*, ch21.Optimality.* · Lessons: 21.2, Algorithms 21.2.3–21.2.4

Label every node bottom-up with the least cost of deriving it from each nonterminal and the rule that achieves it, then reduce top-down from stmt.

Requirements: SPEC R1, R4, R5, R6, R7.

What the tests check: DP's cost equals brute force on at least 400 small trees and the corpus optimum on 200 programs; DP ≤ munch on 300 random programs and strictly better at least once; the running example costs 5.

Hint 1 — where to start

Do the label table of the running example by hand first (Lesson 21.2 §3, or ./course drill dp-tiling --solution), then code it.

Hint 2 — the key idea

The cost of a rule at a node is its own cost plus the labels of its operand nodes for the nonterminals the pattern asks for (Definition 21.2.1). The Tessera grammar has no chain rules, so no closure step is needed; tessera-chain.rules in E4 has them.

Hint 3 — a design sketch

A map from node to a small array of (cost, rule) per nonterminal; label(node) children first; reduce(node, goal) reads the rule and recurses into the operands with the pattern's nonterminals. Use "strictly less" when comparing costs so that ties go to the first rule tried: that keeps R7.

Done when: ./course test 21 shows all part A tests passing; then run ch21-compare and fill in the SPEC's measurement table.

---

E4 — A BURG-style table generator

★ Optional. Contract: isel::burgGenerate(G, MaxStates) · Tests: ch21.Grammars/Burs.*, ch21.BursChains.*, ch21.BursFiniteness.*, burg.test (label star) · Lesson: 21.3, Algorithm 21.3.4, Theorem 21.3.7, Proposition 21.3.8

Generate the BURS automaton of a rules file: normalize the grammar, build δ-states from the leaves up with a worklist, and print states, leaf states and transitions in the SPEC's "BURS tables" format. The provided runtime labels trees by table lookup and must then select optimal code.

Requirements: SPEC R10–R13.

What the tests check: tables for tessera.rules and tessera-chain.rules that select code of optimal cost for every sample and corpus program (at most 200 states); determinism; unbounded.rules rejected with not BURS-finite.

Hint 1 — where to start

Normal form (Definition 21.3.1): give every inner pattern node a helper nonterminal with a cost-0 base rule. Then states are cost vectors over all nonterminals, normalized by their minimum.

Hint 2 — the key idea

A state is identified by its normalized costs and its rules. Transitions only need the child states that exist, so iterate: for every operator, every tuple of existing states, compute the target state; add new states to the worklist until nothing changes (Algorithm 21.3.4). Bound the number of states to detect non-finiteness (R13).

Hint 3 — a design sketch

A canonical string of a state as the key of a map from state to number; one function transition(op, childStates) -> optional<State> that applies base rules and then chain closure; print only the grammar's own nonterminals (helpers may be printed with a leading _). The reference finds 19 states for tessera.rules.

Done when: ctest --preset linux -L star passes.

---

E5 — Guided MIR exploration

Contract: labs/ch21-mir/answers.yaml · Tests: ch21.lit (mir-answers.test) · Lessons: 21.5, 21.6, 21.9, 21.10

Follow the tasks of labs/ch21-mir/SPEC.md: nine tasks, 24 questions, each answered from llc, llvm-mc, llvm-objdump or llvm-readelf output. Tasks 1, 2, 5 and 6 are SelectionDAG and legalization; 3, 4 and 8 GlobalISel and FastISel; 7 prologue/epilogue insertion; 9 relocations and relaxation.

Requirements: SPEC R1–R3.

What the tests check: check.py grades all 24 answers against the hashed questions.yaml; mir-facts.test checks separately that the llc output still contains the facts the answers rest on.

Hint 1 — where to start

Run each task's commands and save the output to a file; search it for the opcode or field the question names.

Hint 2 — the key idea

Compare two outputs rather than reading one: before and after a pass (-stop-before/-stop-after), x86-64 and AArch64, SelectionDAG and GlobalISel. The difference is the answer.

Hint 3 — when an answer is marked wrong

Check the exact spelling (MIR opcodes are case-sensitive), strip % and $ from registers, and write sets as YAML lists. python3 labs/ch21-mir/check.py prints feedback per question.

Done when: check.py prints all 24 answers correct.