Lab 21 · Tiling a toy ISA: macro expansion, maximal munch and optimal DP (★ BURG tables)¶

Goal¶

You build three instruction selectors for Tessera, a small RISC instruction set, over a tree IR: macro expansion (Lesson 21.1, Algorithm 21.1.6), maximal munch (Algorithm 21.1.8) and optimal tiling by dynamic programming (Lesson 21.2, Algorithms 21.2.3–21.2.4). A provided simulator runs your code and checks that it computes what the tree computes, and a comparison driver measures the three against each other. The optional part B (★, Lesson 21.3) is a BURG-style generator: it turns a tile grammar into BURS tables that a provided table-driven matcher runs without any cost arithmetic.

Part A is exercises E1–E3 and part B is E4 in chapters/21-instruction-selection/exercises.md.

Requirements¶

Part A, the function isel::select (contract below):

R1 (correct code). For every program, the listing computes the program: running it on the Tessera simulator leaves every temporary the program mentions and all of memory as the tree semantics does, for every initial state (the tests use 8 seeds). Each statement's code is emitted in program order.
R2 (macro expansion). Algo::Macro covers every node with the macro rule of its operator, exactly one rule per node:

operator	rule	operator	rule
`MOVE`	r1 (the destination `TEMP` is part of the rule)	`ADD`	r8
`STORE`	r2	`SUB`	r10
`TEMP`	r6 (no instruction)	`MUL`	r12
`CONST`	r7 (`li`)	`SHL`	r14
`MEM`	r17 (`ld … 0(…)`)

So the cost of a macro listing is fixed: the sum of these rules' costs over the nodes. - R3 (maximal munch). Algo::Munch works top-down: at each node, with the nonterminal the parent needs there (stmt at a root), it takes the matching rule with the largest pattern (most IR operator nodes, CONST and TEMP included), breaking ties by the lower rule number, and recurses into the pattern's nonterminal leaves. On the running example this is r5 at the root, then r16 and r9: shadd, addi, movm, cost 6. - R4 (optimal DP). Algo::DP returns a tiling of minimum total cost for each statement (any minimum-cost tiling is accepted). On the running example that is cost 5. - R5 (ordering). Consequently, for every program, cost(DP) ≤ cost(munch) ≤ cost(macro). (The second inequality holds for the Tessera grammar by Theorem 21.1.15; you do not have to do anything extra for it.) - R6 (complexity). DP runs in $O(n \cdot \lvert R \rvert)$ for a tree of $n$ nodes and $\lvert R \rvert$ rules (one pass up for labels, one pass down to emit). Munch and macro expansion are $O(n \cdot \lvert R \rvert)$ or better. No exponential enumeration of tilings. - R7 (determinism). The same program gives the same listing, byte for byte, every time (no iteration over pointer-keyed hash maps).

Part B (★), the function isel::burgGenerate:

R10 (tables). burgGenerate(G, MaxStates) returns the BURS automaton of $G$ in the text format of "BURS tables" below: states with, for each nonterminal of the grammar, the rule and the normalized cost difference (Definitions 21.3.2–21.3.3), a state for each leaf operator, and a transition for every operator and tuple of child states that some tree produces (Algorithm 21.3.4).
R11 (complete). Every tree over the grammar's operators that has a tiling labels without a missing leaf or trans entry, and the provided runtime then emits a minimum-cost tiling (Theorem 21.3.7).
R12 (grammars). Any rules file in the "Rules files" format: several nonterminals, chain rules, patterns of any depth (normalize them with helper nonterminals, Definition 21.3.1), terminal leaves in patterns. The tests use rules/tessera.rules and rules/tessera-chain.rules.
R13 (finiteness). If more than MaxStates states would be needed, return an error whose message contains not BURS-finite. rules/unbounded.rules is such a grammar (Proposition 21.3.8).

The contract¶

The tests call only these two functions. How you match patterns, label trees, represent tiles and emit code is yours: put all of it in src/ (every *.cpp there is compiled; src/Stub.cpp stops with TODO(ch21) until you replace it).

// include/isel/Select.h
namespace isel {
enum class Algo { Macro, Munch, DP };
/// Selects Tessera instructions for every statement of P, in order, with algorithm A
/// over the Tessera grammar (R1-R7), and returns the listing in the "Assembly" format
/// (without the "cost" line: the driver appends it). Return an error only for a genuine
/// internal failure: every tree of the tree IR has a Tessera tiling.
std::expected<std::string, std::string> select(const tree::Program &P, Algo A);
}

// include/isel/Burg.h (part B)
namespace isel {
/// Builds the BURS tables of G (R10-R13). Fails with a message that contains
/// "not BURS-finite" when more than MaxStates states would be needed.
std::expected<std::string, std::string> burgGenerate(const grammar::Grammar &G, unsigned MaxStates);
}

The Tessera grammar is available as grammar::tessera() (the text of rules/tessera.rules); use it rather than hard-coding the patterns, so that your selectors are driven by the grammar as a generated selector would be.

Command-line contract¶

The provided drivers in tools/ (built into build/<preset>/bin/) wrap the contract:

ch21-isel [--algo=macro|munch|dp] FILE.tree      # listing + "cost N"; default dp
ch21-sim [--seeds=N] FILE.tree LISTING|-         # "ok: K instructions, cost C" or "error: ..."
ch21-burg gen RULES [--max-states=N]             # print the tables of RULES (part B)
ch21-burg run RULES TABLES FILE.tree             # select with the tables (provided runtime)
ch21-compare [--quick] [--n=N] [--seed=S]        # the measurement below

Formats¶

Tree IR¶

A program is a sequence of statements, one S-expression each (newlines and spaces are free; # starts a comment to the end of the line):

# a[i] = p[3] with 8-byte words:  void store(long *a, long i, long *p) { a[i] = p[3]; }
(STORE (ADD (TEMP a) (SHL (TEMP i) (CONST 3)))
       (MEM (ADD (TEMP p) (CONST 24))))

Operators: (CONST n) a 64-bit integer, (TEMP name) a temporary named [a-z][a-z0-9_]* (not r followed by digits), (MEM e) the word at address $e$, (ADD e e), (SUB e e), (MUL e e), (SHL e e) on 64-bit two's-complement integers (wrapping; SHL uses the low 6 bits of the count), and at the root only (MOVE (TEMP x) e) (assign) or (STORE a e) (write $e$ at address $a$). include/isel/Tree.h has the parser, the printer and the reference semantics.

Semantics¶

A state is a map from temporaries to values plus a word memory indexed by 64-bit addresses (no alignment). Unwritten locations and temporaries have deterministic pseudo-random initial values that depend on a seed (tree::mem0 in Tree.h), so a wrong address or a wrong operand is detected. STORE a e evaluates $a$ and then $e$; trees have no side effects below the root, so the order in which you compute operands does not matter.

The Tessera ISA¶

Registers: r0 reads as 0 and cannot be written; r1, r2, … are an unbounded supply of virtual registers, each written before it is read; temporaries are registers named by their temporary's name (a, i, p). Costs:

instruction	meaning	cost	rule
`add rd, rs, rt` / `addi rd, rs, c`	rd ← rs + rt / rs + c	1	r8 / r9
`sub rd, rs, rt` / `subi rd, rs, c`	rd ← rs − rt / rs − c	1	r10 / r11
`mul rd, rs, rt`	rd ← rs · rt	3	r12
`madd rd, rs, rt, ru`	rd ← rs · rt + ru	3	r13
`sll rd, rs, rt` / `slli rd, rs, c`	rd ← rs ≪ rt / rs ≪ c	1	r14 / r15
`shadd rd, rs, rt, c`	rd ← rs + (rt ≪ c)	1	r16
`ld rd, c(rs)`	rd ← M[rs + c]	2	r17, r18, r19
`ldx rd, rs, rt`	rd ← M[rs + rt]	2	r20
`st rs, c(rt)`	M[rt + c] ← rs	2	r2, r3, r4
`movm (rs), (rt)`	M[rs] ← M[rt]	4	r5
`mv rd, rs`	rd ← rs	1	r1
`li rd, c`	rd ← c	1	r7

Rules files¶

rules/tessera.rules is the grammar of Table 21.1.1 in this format:

%start stmt
r3  stmt: STORE(ADD(reg, CONST), reg)   2  "st %2, %1(%0)"
r6  reg:  TEMP                          0  "=%0"
r16 reg:  ADD(reg, SHL(reg, CONST))     1  "shadd %d, %0, %1, %2"

Each rule is rN lhs: pattern cost "template". A pattern is an IR operator with sub-patterns or a lower-case nonterminal. In the template, %d is a fresh register for the rule's result and %k is the $k$-th leaf of the pattern from the left (0-based; a nonterminal leaf stands for the register or text its derivation produced, a CONST leaf for its value, a TEMP leaf for its name). A template =X emits nothing and makes X the rule's result (r6 makes a temporary's name the register). grammar::instantiate does the substitution; grammar::parseFile reads the file.

Assembly¶

One instruction per line, operands separated by commas, any indentation; # comments, blank lines and a final cost N line are ignored by the reader. The macro listing of the running example:

  li r1, 3
  sll r2, i, r1
  add r3, a, r2
  li r4, 24
  add r5, p, r4
  ld r6, 0(r5)
  st r6, 0(r3)
cost 9

BURS tables (part B)¶

burs 1
# any comment
state 0: reg=r7/1
state 1: reg=r6/0
...
leaf CONST 0
leaf TEMP 1
trans MEM 5 3
trans ADD 1 0 4

The first line is burs 1. state i: nt=rN/delta … defines state $i$ (numbered 0, 1, 2, … in order): for each nonterminal derivable at a node in that state, the rule at the root of its cheapest derivation and its normalized cost; nonterminals starting with _ (your helper nonterminals) may be listed and are never queried. leaf OP s gives the state of a CONST or TEMP leaf. trans OP s1 [s2] s gives the state of an operator node whose children are in states s1 (and s2). The provided runtime (include/isel/BurgRuntime.h) labels each node with one table lookup and reduces from %start.

Provided infrastructure¶

Not the learning objective; use it, do not reimplement it: the tree IR (Tree.h: parser, printer, semantics, random programs), the Tessera reader, cost table and simulator (Tessera.h, tessera::agrees), the rules-file reader and template instantiation (Grammar.h), the BURS runtime (BurgRuntime.h) and the four drivers.

What the tests check¶

Run ./course test 21 (or ctest --preset linux -L '^ch21$'; -L star adds part B). Every test goes through the contract and the simulator.

Test	What it asserts
`ch21.Algos/Selectors.SamplesExactCosts/{macro,munch,dp}`	on the five programs of `inputs/`, the listing is correct (R1) and has the cost in `tests/ch21/Inputs/samples.txt` (macro and munch costs are fixed by R2 and R3; DP's is the optimum)
`ch21.Algos/Selectors.CorpusExactCosts/*`	the same on 200 random programs (`tests/ch21/Inputs/corpus.txt`, generated by an independent Python implementation)
`ch21.Algos/Selectors.Deterministic/*`	R7
`ch21.Ordering.RandomProgramsCorrectAndOrdered`	300 more random programs: correct, macro cost equals the per-node count of R2, and DP ≤ munch ≤ macro (R5); DP must beat munch at least once
`ch21.Optimality.DPEqualsBruteForceOnSmallTrees`	at least 400 small trees: DP's cost equals the minimum over all tilings enumerated by brute force (R4)
`ch21.Optimality.RunningExampleHas18Tilings`	the running example has 18 tilings, the best costs 5, and DP finds 5
`ch21.lit` (`isel-running.test`, `isel-samples.test`, `sim-errors.test`)	the command line: macro gives 7 instructions of cost 9, munch contains `shadd` and `movm` at cost 6, DP reaches 5, and the simulator's error messages
`ch21.Grammars/Burs.`, `ch21.BursChains.`, `ch21.BursFiniteness.*`, `burg.test` (★, label `star`)	R10–R13: tables for both grammars (and for `tessera-chain.rules` plus a costlier `reg: CONST` rule that a chain rule must beat) label every test program and give optimal code; `unbounded.rules` is rejected with `not BURS-finite`
`ch21.lab.compare-smoke`	`ch21-compare --quick` runs to completion

Measurement¶

ch21-compare runs the three selectors on the 5 sample programs and 2000 random programs (seed 21) and prints total cost, instruction count, cost per IR node, time per program, and how often DP beats munch. Fill in the table and explain it with Theorem 21.1.15 and Theorem 21.2.7:

algo	cost	instrs	cost/node	µs/program
macro
munch
dp

The reference solution gives costs 70 866 / 53 935 / 53 632 over 71 197 nodes, with DP ahead of munch on 286 programs (14.3 %). Questions to answer in your notes: why does DP use more instructions than munch (38 202 vs 37 554) while costing less? Which Tessera rules make munch lose? How does the time per node grow with the number of rules?

Milestones¶

Matching (E1 prep). A function that tells whether a rule's pattern matches at a node and returns the operand nodes (Definition 21.1.3). Test it on the running example by hand.
E1: macro expansion. ctest --preset linux -R 'ch21.*macro' and ch21-isel --algo=macro inputs/running.tree | ch21-sim inputs/running.tree -.
E2: maximal munch. ctest --preset linux -R 'ch21.*munch'; compare your trace with ./course drill munch-tiling --solution.
E3: DP. ctest --preset linux -R 'ch21.*(dp|Ordering|Optimality)'; compare your labels with ./course drill dp-tiling --solution.
Measure with ch21-compare and fill in the table.
★ E4: BURG. Normal form first (Definition 21.3.1), then the worklist of Algorithm 21.3.4 on tessera.rules (19 states in the reference), then chain rules (tessera-chain.rules), then the state bound. ctest --preset linux -L star.

Hints¶

Hint 1: where to start

Write one recursive matcher over grammar::Pattern and tree::Node that returns the list of (node, nonterminal) operand pairs, or nothing. All three selectors use it: macro expansion calls it only with the macro rule, munch tries rules in a fixed order, and DP tries all rules at every node. Emission is the same for all three: a post-order walk over the chosen tiles that instantiates templates with the results of the operands.

Hint 2: the key idea

Munch decides top-down and never looks back; DP decides bottom-up and never commits early. For DP, keep for every node a small table from nonterminal to (cost, rule), fill it children first (Algorithm 21.2.3), and only then walk down from the root with the goal stmt, reading the rule to use from the table (Algorithm 21.2.4). The tables must not depend on the goal, which is why the walk down is a separate pass.

Hint 3: a design sketch

A Tile (rule, root node, operand list); a Labels map from node to an array indexed by nonterminal; an Emitter that owns the fresh-register counter and the output buffer, with emit(node, nonterminal) -> std::string returning the operand text. Common bugs the tests catch: counting nonterminals in the pattern size for munch (R3 counts operators only), forgetting that template operands are all leaves, including CONST and TEMP, and treating MOVE's destination TEMP as an operand to compute. For part B, key states by their canonical text (sorted nonterminal=rule/delta list) to find duplicates, and enumerate transitions over all tuples of existing states until no new state appears.

Stretch goals ★¶

Part B (E4) above.
Dynamic costs (Definition 21.2.10): add a rule reg: SHL(reg, CONST) that applies only to shift counts 1–3 with a cheaper cost, and make your DP evaluate the predicate per node.
DAG input: share identical subtrees (value numbering), then compare tree decomposition with duplicating the shared node, as in Lesson 21.4's examples D1 and D2.