Lesson 21.1 — Tree tiling I: macro expansion, maximal munch and peephole combining¶

Techniques: macro expansion, maximal munch, peephole combining (Davidson–Fraser) · Lab: labs/ch21-isel E1 (macro) and E2 (munch) · Prerequisites: Lesson 8.3 (trees and DAGs), Ch 9 (LLVM IR) · Time: 4–6 hours

Take the C statement a[i] = p[3]; with 8-byte longs. After lowering, its address arithmetic is explicit, and one natural IR is a tree:

(STORE (ADD (TEMP a) (SHL (TEMP i) (CONST 3)))      # address a + (i << 3)
       (MEM (ADD (TEMP p) (CONST 24))))              # value  M[p + 24]

The target machine does not execute trees. It executes instructions, and one instruction usually does several tree operations at once: x86-64 stores this value with movq %rax, (%rdi,%rsi,8), which performs the STORE, the ADD and the SHL in one instruction. Instruction selection chooses which instructions compute the tree. This lesson covers the three oldest ways to do it: translate every node on its own (macro expansion), grab the biggest instruction that fits at each node from the top (maximal munch), or translate naively and then fuse adjacent instructions (peephole combining). On the toy ISA of this chapter they produce code of cost 9, 6 and 5 for the tree above. Lesson 21.2 proves that 5 is the minimum.

1. Problem and motivation¶

An instruction selector runs after the middle end and before register allocation. In LLVM it is the pass that turns LLVM IR into machine instructions (MIR) with virtual registers: SelectionDAG (Lesson 21.5), GlobalISel or FastISel (Lesson 21.6). Its input is a program in a machine-independent IR. Its output is a sequence of target instructions that computes the same thing and costs as little as possible, where cost means cycles, bytes or some mix. The problem is hard for two reasons. First, the mapping is many-to-many: one IR operation may need several instructions (a 128-bit add on a 64-bit machine), and one instruction may implement several IR operations (the x86 addressing mode above). Second, choices interact: using one big instruction here can rule out a better one next door.

The course studies instruction selection as tree tiling. You describe every instruction by the tree fragment (the pattern) it computes, and a selection is a way of covering the IR tree with non-overlapping patterns (Definition 21.1.4). Pebble does not select instructions itself, since LLVM does that for it. The comparison lab labs/ch21-isel has you build three selectors for a toy RISC ISA, Tessera, and measure them against each other.

Macro expansion¶

The oldest selectors, in compilers of the 1950s and 1960s and in the "template" code generators that followed, expanded each IR operation into a fixed instruction sequence, like a macro processor expanding a macro call. Blindell's survey calls this family macro expansion and traces it through early compilers and the retargetable template generators of the 1970s [Bli16, Ch. 2]. It is still the right tool when compile time matters more than code quality. WebAssembly baseline compilers such as Wasmtime's Winch and V8's Liftoff, and V8's Sparkplug for JavaScript bytecode, all expand one operation at a time (§7). Macro expansion cannot use complex instructions or addressing modes, because it never looks at more than one node.

Maximal munch¶

Once instruction sets had addressing modes and multi-operation instructions, compilers needed selectors that look at several nodes at a time. Cattell's work on deriving code generators from machine descriptions described a greedy top-down strategy that at each node takes the instruction covering the most of the tree [Cat80], and the name maximal munch stuck. Appel's textbook made the formulation used here standard: munch the root with the largest matching tile, then munch the subtrees that remain [Appel, §9.1]. Munch is fast and simple and never misses a larger instruction when one fits. §4 shows exactly how good that makes it (Theorem 21.1.13) and where it falls short of the optimum (Proposition 21.1.14).

Peephole combining¶

Instead of choosing big instructions directly, you can generate naive code and then combine adjacent instructions whose joint effect is a single instruction of the machine. McKeeman introduced peephole optimization as a small window slid over the generated code [McK65]. Davidson and Fraser made it retargetable: every instruction is a register-transfer list (RTL), the combiner substitutes the RTL of a producer into its consumer, and it keeps the result whenever the machine description recognizes it as a single instruction [DF80, DF84]. With that in place, selection is "macro-expand, then combine". GCC's combine pass is a direct descendant: its header comment calls it "essentially the 'combiner' phase of the U. of Arizona Portable Optimizer" [GCC-Combine].

2. Definitions and algorithms¶

Definition 21.1.1 (Tree IR)

Let $\Sigma$ be a finite ranked alphabet of operators, each $o \in \Sigma$ with an arity $\mathrm{ar}(o) \in \mathbb{N}$. A tree is $o(t_1, \dots, t_k)$ with $k = \mathrm{ar}(o)$ and subtrees $t_i$; leaves ($k = 0$) may carry an attribute (a constant, a temporary's name). The nodes of $t$ are $V(t)$, with $n = \lvert V(t) \rvert$; $t_v$ is the subtree rooted at $v$. The lab's IR has $\Sigma = \{\mathsf{CONST}/0, \mathsf{TEMP}/0, \mathsf{MEM}/1, \mathsf{ADD}/2, \mathsf{SUB}/2, \mathsf{MUL}/2, \mathsf{SHL}/2, \mathsf{MOVE}/2, \mathsf{STORE}/2\}$. A statement is a tree whose root is $\mathsf{MOVE}$ or $\mathsf{STORE}$ and whose other nodes are expression operators. A program is a sequence of statements. Its semantics is the usual one on 64-bit wrapping integers and a word memory (SPEC, "Semantics").

Definition 21.1.2 (Tile grammar)

A tile grammar is $G = (N, \Sigma, R, S, c)$: a finite set $N$ of nonterminals (disjoint from $\Sigma$), a start nonterminal $S \in N$, a finite set $R$ of rules $r = A \to \pi$ with $A \in N$ and pattern $\pi$ a tree over $\Sigma \cup N$ in which nonterminals occur only as leaves, and a cost $c : R \to \mathbb{N}$. A rule whose pattern is a single nonterminal ($A \to B$) is a chain rule. The size $\lvert \pi \rvert$ counts the operator nodes of $\pi$, not its nonterminal leaves. Each rule also carries an instruction template that is emitted when the rule is used.

Definition 21.1.3 (Match)

A pattern $\pi$ matches tree $t$ at node $v$ if there is a map $h$ from the nodes of $\pi$ to $V(t)$ with $h(\mathrm{root}(\pi)) = v$ that preserves operators (an operator node of $\pi$ with label $o$ and children $p_1..p_k$ maps to a node of $t$ labelled $o$ whose children are $h(p_1)..h(p_k)$). Nonterminal leaves of $\pi$ may map to any node. The images of the nonterminal leaves, in left-to-right order, are the operand nodes $\mathrm{ops}(\pi, v)$. The images of the operator nodes form the tile $\mathrm{cov}(\pi, v)$, the set of nodes the rule covers.

Definition 21.1.4 (Derivation, tiling, cost)

An $A$-derivation of $t_v$ is a rule $r = A \to \pi$ that matches at $v$, together with, for every nonterminal leaf $B$ of $\pi$ mapped to operand node $u$, a $B$-derivation of $t_u$. (For a chain rule $A \to B$ it is a $B$-derivation of $t_v$ itself.) Its cost is the sum of $c(r)$ over all rule applications in it. A tiling of a statement $t$ is an $S$-derivation of $t$ at its root. An optimum tiling has minimum cost among all tilings of $t$. We write $\mathrm{OPT}(t)$ for that cost.

A tiling of the running example

The rules of Table 21.1.1 below give an $S$-derivation of the running example with three tiles: r2 $\mathsf{stmt} \to \mathsf{STORE}(\mathsf{reg}, \mathsf{reg})$ at the root, r16 $\mathsf{reg} \to \mathsf{ADD}(\mathsf{reg}, \mathsf{SHL}(\mathsf{reg}, \mathsf{CONST}))$ covering $\{\mathsf{ADD}, \mathsf{SHL}, \mathsf{CONST}\ 3\}$, and r18 $\mathsf{reg} \to \mathsf{MEM}(\mathsf{ADD}(\mathsf{reg}, \mathsf{CONST}))$ covering the load and its address. The three TEMP leaves are covered by r6 (cost 0). The cost is $2 + 1 + 2 = 5$.

Table 21.1.1 — Tessera as a tile grammar (labs/ch21-isel/rules/tessera.rules). Costs are cycles: memory costs 2, a multiply 3, and the memory-to-memory movm 4. %d is a fresh destination register and %0, %1, … are the pattern's leaves from left to right.

rule	derives	pattern	cost	instruction
r1	stmt	`MOVE(TEMP, reg)`	1	`mv %0, %1`
r2	stmt	`STORE(reg, reg)`	2	`st %1, 0(%0)`
r3	stmt	`STORE(ADD(reg, CONST), reg)`	2	`st %2, %1(%0)`
r4	stmt	`STORE(CONST, reg)`	2	`st %1, %0(r0)`
r5	stmt	`STORE(reg, MEM(reg))`	4	`movm (%0), (%1)`
r6	reg	`TEMP`	0	none: the value is the temporary itself
r7	reg	`CONST`	1	`li %d, %0`
r8	reg	`ADD(reg, reg)`	1	`add %d, %0, %1`
r9	reg	`ADD(reg, CONST)`	1	`addi %d, %0, %1`
r10	reg	`SUB(reg, reg)`	1	`sub %d, %0, %1`
r11	reg	`SUB(reg, CONST)`	1	`subi %d, %0, %1`
r12	reg	`MUL(reg, reg)`	3	`mul %d, %0, %1`
r13	reg	`ADD(MUL(reg, reg), reg)`	3	`madd %d, %0, %1, %2`
r14	reg	`SHL(reg, reg)`	1	`sll %d, %0, %1`
r15	reg	`SHL(reg, CONST)`	1	`slli %d, %0, %1`
r16	reg	`ADD(reg, SHL(reg, CONST))`	1	`shadd %d, %0, %1, %2`
r17	reg	`MEM(reg)`	2	`ld %d, 0(%0)`
r18	reg	`MEM(ADD(reg, CONST))`	2	`ld %d, %1(%0)`
r19	reg	`MEM(CONST)`	2	`ld %d, %0(r0)`
r20	reg	`MEM(ADD(reg, reg))`	2	`ldx %d, %0, %1`

Register r0 always reads 0. Real ISAs limit immediates (12 bits on AArch64 add, 32 on x86-64). Tessera does not, so no rule needs a predicate on its constant. Lesson 21.2 shows how lburg and iburg add such predicates as dynamic costs.

Definition 21.1.5 (Macro rules; munch-safe grammar)

A macro rule for operator $o$ and nonterminal $A$ is a rule $A \to o(B_1, \dots, B_k)$ whose pattern has exactly one operator node. The exception is a leaf that the IR form itself forces to be a terminal, such as the destination $\mathsf{TEMP}$ of $\mathsf{MOVE}$. A macro table $M$ picks one macro rule for every operator. A grammar is munch-safe if it has no chain rules and, for every nonterminal $B$ that occurs as a pattern leaf and every operator $o$ that can label a node in such a position, there is a macro rule $B \to o(\dots)$ whose leaves are again nonterminals of that kind. The root goal $S$ also needs a macro rule for every statement operator.

Tessera's macro table

$M = \{\mathsf{MOVE} \mapsto \text{r1}, \mathsf{STORE} \mapsto \text{r2}, \mathsf{TEMP} \mapsto \text{r6}, \mathsf{CONST} \mapsto \text{r7}, \mathsf{ADD} \mapsto \text{r8}, \mathsf{SUB} \mapsto \text{r10}, \mathsf{MUL} \mapsto \text{r12}, \mathsf{SHL} \mapsto \text{r14}, \mathsf{MEM} \mapsto \text{r17}\}$. The only leaf nonterminal is $\mathsf{reg}$, and every expression operator has a macro rule for it, so Tessera is munch-safe.

Macro expansion¶

Algorithm 21.1.6 (Macro expansion)

Input: a statement tree $t$; a tile grammar $G$ with a macro table $M$.
Output: an instruction sequence and the register holding each node's value.
Precondition: $M(o)$ is defined for every operator in $t$.
Postcondition: the emitted code is the derivation that uses $M(\mathrm{op}(v))$ at every node $v$ (Proposition 21.1.7). Its cost is $\sum_{v} c(M(\mathrm{op}(v)))$, not counting forced terminal leaves.
Invariant: when Expand(v) returns, the code emitted so far computes the value of $t_v$ into the returned operand, and it has not changed any temporary or memory location read by a subtree still to be expanded.

function MacroExpand(t):
    Expand(root(t))

function Expand(v):                        # returns the operand text holding t_v's value
    r ← M(op(v))
    operands ← []
    for each leaf ℓ of pattern(r), left to right:
        u ← the node of t that ℓ maps to at v
        if ℓ is a nonterminal: operands.append(Expand(u))       # children first
        else:                  operands.append(Attribute(u))    # CONST value or TEMP name
    return Emit(r, operands)

function Emit(r, operands):                # instantiate r's template
    if template(r) starts with "=":        # no instruction (e.g. r6 reg: TEMP)
        return Substitute(template(r)[1:], operands, none)
    d ← none
    if template(r) mentions %d: d ← FreshRegister()
    append Substitute(template(r), operands, d) to the output
    return d

function Substitute(s, operands, d):
    replace %d by d and every %k by operands[k] in s; return s

function FreshRegister(): counter ← counter + 1; return "r" + counter

Proposition 21.1.7 (Macro expansion is correct and linear)

If every template implements its rule's pattern (the instruction computes the pattern's value from its operands, and a statement template performs the statement's effect) and writes only its fresh destination (statement templates: only the stored location or the moved temporary), then Algorithm 21.1.6 emits code that computes $t$. It runs in time $\Theta(n)$ and emits exactly one template per operator node of $t$.

Proof

By induction on the height of $t_v$ we show the invariant for Expand(v). Leaf: $r$ is r6 (no code, the operand is the temporary) or r7 (li into a fresh register). Either way the returned operand holds the leaf's value and nothing else changed. Inner node: the recursive calls, left to right, return operands holding the children's values (induction hypothesis). Each call writes only fresh registers, so it does not disturb a value returned earlier. The template of $M(o)$ then computes $o$ of those values into a fresh register (hypothesis on templates). At the root, the statement template performs the store or move. The expression operators are pure, so evaluating the children before the statement's own effect agrees with the tree semantics. The IR has no side effects inside an expression (Definition 21.1.1). Cost and time: every node is visited once, and each visit does $O(\mathrm{ar}(o) + \lvert \text{template} \rvert)$ work, which is $O(1)$ for a fixed grammar.

Maximal munch¶

Algorithm 21.1.8 (Maximal munch)

Input: a statement tree $t$; a munch-safe tile grammar $G$ (Definition 21.1.5).
Output: a tiling of $t$ and its code.
Precondition: $G$ has no chain rules and is munch-safe.
Postcondition: the tiling is a valid $S$-derivation (Theorem 21.1.13), and at every tile root the chosen rule has maximum size among the rules for that goal matching there.
Invariant: Munch(v, A) is only called with a pair such that some $A$-rule matches at $v$. On return, the emitted code computes $t_v$'s value (or its effect for $A = S$).

function MaximalMunch(t):
    Munch(root(t), S)

function Munch(v, A):
    best ← none
    for each rule r = A → π in G, in rule-number order:
        if Matches(π, v) and (best = none or |π| > |pattern(best)|):
            best ← r                                   # ties keep the lower number
    if best = none: fail "no rule derives A at v"      # impossible if G is munch-safe
    operands ← []
    for each leaf ℓ of pattern(best), left to right:
        u ← the node ℓ maps to at v
        if ℓ is a nonterminal B: operands.append(Munch(u, B))
        else:                    operands.append(Attribute(u))
    return Emit(best, operands)                        # as in Algorithm 21.1.6

function Matches(π, v):
    if π is a nonterminal: return true
    if label(π) ≠ op(v): return false
    return Matches(child_i(π), child_i(v)) for all i

The tiles are chosen top-down (root first) and the code is emitted bottom-up (children first), which is the order Appel uses [Appel, §9.1].

Definition 21.1.9 (Optimum vs optimal tilings, after Appel)

Let two tiles be adjacent when one's root is an operand node of the other. A tiling is optimal (or locally optimal) if no two adjacent tiles can be replaced by a single rule whose tile is their union and whose cost is lower than the sum of theirs. It is optimum if no tiling of $t$ at all is cheaper [Appel, §9.1].

Peephole combining¶

Definition 21.1.10 (Register transfers, links, combinable pairs)

Write each instruction $i$ as a register transfer $d_i \leftarrow e_i$ (or $M[a_i] \leftarrow e_i$ for a store), where $e_i$ is an expression tree over registers, constants and $\mathsf{MEM}$. A link $i \to j$ exists when $j$ reads the register $d_i$, $i$ is the last definition of $d_i$ before $j$, and $j$ is the only reader of $d_i$ (it is dead after $j$). The combination $j[i]$ replaces every use of $d_i$ in $e_j$ by $e_i$. A recognizer $\mathrm{Recog}$ maps a transfer to the cheapest single machine instruction that implements it, or $\bot$. For Tessera, $\mathrm{Recog}$ matches the transfer against the patterns of Table 21.1.1.

Algorithm 21.1.11 (Peephole combining, after Davidson–Fraser)

Input: a straight-line instruction sequence $I_1, \dots, I_m$ (for example, macro-expanded code), a recognizer and a cost function.
Output: an equivalent sequence with no more instructions and no higher cost.
Precondition: every $I_j$ is recognized. Links are computed as in Definition 21.1.10.
Postcondition: no link $i \to j$ has a recognized combination $j[i]$ that costs at most $c(i) + c(j)$ (a local fixed point), and the program's behavior is unchanged. Accepting ties is GCC's rule too: combine_validate_cost rejects a combination only if it costs more [GCC-Combine], since a tie still saves one instruction.
Invariant: the current sequence is equivalent to the input (Theorem 21.1.16), and every successful step removes one instruction.

function Combine(I):
    changed ← true
    while changed:
        changed ← false
        for i in I, in order:
            j ← LinkTarget(I, i)                 # the unique reader of d_i, or none
            if j = none: continue
            if some instruction strictly between i and j writes a register or memory
               location that e_i reads: continue          # value would change
            if i reads memory and some instruction strictly between i and j writes memory:
               continue
            k ← Recog(j[i])
            if k ≠ ⊥ and cost(k) ≤ cost(i) + cost(j):     # not worse, one instruction fewer
                replace j by k; delete i
                changed ← true

function LinkTarget(I, i):
    readers ← the instructions after i that read d_i before d_i is redefined
    if |readers| = 1 and d_i is not live after that reader: return the reader
    return none

3. Worked example¶

The running example has 10 nodes. Nodes are named in postorder, and labs/ch21-isel/inputs/running.tree holds the same tree.

flowchart TD
  n10["n10: STORE"] --> n5["n5: ADD"]
  n10 --> n9["n9: MEM"]
  n5 --> n1["n1: TEMP a"]
  n5 --> n4["n4: SHL"]
  n4 --> n2["n2: TEMP i"]
  n4 --> n3["n3: CONST 3"]
  n9 --> n8["n8: ADD"]
  n8 --> n6["n6: TEMP p"]
  n8 --> n7["n7: CONST 24"]

Macro expansion¶

Expand visits the nodes in postorder. One row per call:

step	node	macro rule	emitted	returns	cost so far
1	n1 `TEMP a`	r6	—	`a`	0
2	n2 `TEMP i`	r6	—	`i`	0
3	n3 `CONST 3`	r7	`li r1, 3`	`r1`	1
4	n4 `SHL`	r14	`sll r2, i, r1`	`r2`	2
5	n5 `ADD`	r8	`add r3, a, r2`	`r3`	3
6	n6 `TEMP p`	r6	—	`p`	3
7	n7 `CONST 24`	r7	`li r4, 24`	`r4`	4
8	n8 `ADD`	r8	`add r5, p, r4`	`r5`	5
9	n9 `MEM`	r17	`ld r6, 0(r5)`	`r6`	7
10	n10 `STORE`	r2	`st r6, 0(r3)`	—	9

Seven instructions, cost 9. The code has an instruction for every operator and ignores shadd, ld 24(p) and every other multi-node instruction.

Maximal munch¶

Munch picks tiles top-down. At each call, every rule for the goal that matches is listed with its size, and the largest wins (ties go to the lower rule number). This table is produced by the drill oracle (tools/course/lib/tiling.py, munch(..., trace)):

step	node	goal	matching rules (size)	chosen
1	n10 `STORE`	stmt	r2 (1), r5 (2)	r5 `movm`
2	n5 `ADD`	reg	r8 (1), r16 (3)	r16 `shadd`
3	n1 `TEMP a`	reg	r6 (1)	r6
4	n2 `TEMP i`	reg	r6 (1)	r6
5	n8 `ADD` (the operand of r5's `MEM`)	reg	r8 (1), r9 (2)	r9 `addi`
6	n6 `TEMP p`	reg	r6 (1)	r6

Step 1: r3 needs STORE(ADD(reg, CONST), reg), but n5's right child is a SHL, so r3 fails, and r4 fails too. Of r2 and r5, r5 covers two nodes (STORE and MEM) and wins.
Step 5: r5 covered n9 MEM, so munch never looks at the load rules r17–r20. The address n8 must end up in a register, and r9 addi is the largest reg rule there.

The code is emitted children first:

shadd r1, a, i, 3
addi  r2, p, 24
movm  (r1), (r2)
cost 6

Munch's code is three instructions of cost 6, but the optimum is 5 (the tiling in the example after Definition 21.1.4): shadd r1, a, i, 3; ld r2, 24(p); st r2, 0(r1). Munch's biggest tile at the root, movm, swallowed the MEM, and with it the chance to fold +24 into the load's addressing mode.

Peephole combining¶

Start from the macro-expanded code and apply Algorithm 21.1.11 in order. Each row is one attempt $i \to j$:

#	producer $i$	consumer $j$	combined transfer $j[i]$	recognized as	cost before → after
1	`li r1, 3`	`sll r2, i, r1`	$r2 \leftarrow i \ll 3$	`slli r2, i, 3` (r15)	2 → 1
2	`slli r2, i, 3`	`add r3, a, r2`	$r3 \leftarrow a + (i \ll 3)$	`shadd r3, a, i, 3` (r16)	2 → 1
3	`shadd r3, a, i, 3`	`st r6, 0(r3)`	$M[a + (i \ll 3)] \leftarrow r6$	⊥ (no scaled store)	kept
4	`li r4, 24`	`add r5, p, r4`	$r5 \leftarrow p + 24$	`addi r5, p, 24` (r9)	2 → 1
5	`addi r5, p, 24`	`ld r6, 0(r5)`	$r6 \leftarrow M[p + 24]$	`ld r6, 24(p)` (r18)	3 → 2
6	`ld r6, 24(p)`	`st r6, 0(r3)`	$M[r3] \leftarrow M[p + 24]$	⊥ (`movm` has no offset)	kept
7	second pass: no link changes				fixed point

The result is shadd r3, a, i, 3; ld r6, 24(p); st r6, 0(r3), of cost 5, which is optimum here. That depends on the order: if the combiner had tried ld r6, 0(r5) into the store before step 5, it would have formed movm (r3), (r5) (cost 4 ≤ 2 + 2, one instruction fewer, so it is accepted). Step 5 would then have nothing left to fold +24 into, and the result would be munch's cost 6. §6 comes back to this order dependence.

Try it

./course drill munch-tiling --seed 3 --difficulty hard --solution traces munch on a tree where it loses to the optimum, in this table format. Build your own selectors in labs/ch21-isel and check them with build/<preset>/bin/ch21-isel --algo=munch labs/ch21-isel/inputs/running.tree.

4. Invariants and correctness¶

Macro expansion¶

Proposition 21.1.7 and its proof above cover correctness. The precondition matters: remove r17 from Tessera, and a MEM whose address is not of the form ADD(reg, CONST) has no macro rule, so Algorithm 21.1.6 stops even though other rules exist.

Maximal munch¶

Lemma 21.1.12 (The tiles of a chain-free derivation partition the tree)

Let $D$ be an $A$-derivation of $t_v$ in a grammar without chain rules. Then the tiles $\mathrm{cov}(\pi_r, u)$ of the rule applications of $D$ are pairwise disjoint, and their union is $V(t_v)$ minus the forced terminal leaves (Definition 21.1.5) that belong to their parent's tile.

Proof

By induction on the height of $t_v$. The rule $r$ applied at $v$ covers $\mathrm{cov}(\pi_r, v)$, which contains $v$. Every node of $t_v$ outside that tile lies in exactly one subtree $t_u$ with $u \in \mathrm{ops}(\pi_r, v)$, because patterns are trees and their nonterminal leaves map to the roots of disjoint subtrees. By the induction hypothesis, the sub-derivations at these $u$ partition their subtrees. There are no chain rules, so no two rule applications sit at the same node. The union of these disjoint sets is $V(t_v)$.

Theorem 21.1.13 (Maximal munch terminates, is valid, and leaves no combinable pair)

Let $G$ be munch-safe. For every statement $t$, Algorithm 21.1.8 terminates after one call per tile and returns a tiling of $t$. Moreover, no two adjacent tiles of this tiling can be replaced by a single rule whose tile is their union, whatever that rule costs. In particular the tiling is optimal in the sense of Definition 21.1.9.

Proof

Termination and validity. Each recursive call Munch(u, B) is on an operand node $u$ of the chosen pattern, a proper descendant of $v$ (patterns have at least one operator node because there are no chain rules). So the recursion depth is at most the height of $t$, and each call chooses one tile. The call never fails: $B$ occurs as a pattern leaf and $u$ is labelled by some operator $o$, so munch-safety gives a macro rule $B \to o(\dots)$, which matches at $u$. The set of candidates is therefore non-empty. The chosen rules and their recursive derivations form an $S$-derivation by Definition 21.1.4.

No combinable pair. Suppose tile $T_1$ (rule $r_1 = A \to \pi_1$, rooted at $v$) and an adjacent tile $T_2$ (rule $r_2 = B \to \pi_2$, rooted at an operand node $u$ of $\pi_1$) could be replaced by a rule $r = A \to \pi$ whose tile at $v$ is $T_1 \cup T_2$. Then $\pi$ matches at $v$, derives the same goal $A$, and has size $\lvert \pi \rvert = \lvert T_1 \rvert + \lvert T_2 \rvert > \lvert \pi_1 \rvert$ (by Lemma 21.1.12 the tiles are disjoint, and $\lvert T_2 \rvert \ge 1$). But at $v$ munch chose $r_1$ as a rule of maximum size among the matching $A$-rules, so no matching $A$-rule is larger. Contradiction.

Proposition 21.1.14 (Maximal munch is not optimum)

There is a munch-safe grammar and a tree on which maximal munch's tiling costs strictly more than $\mathrm{OPT}(t)$. For Tessera and the running example, munch costs 6 and the optimum is 5.

Proof

§3 computes munch's tiling (r5, r16, r9 and r6 three times, cost $4 + 1 + 1 = 6$) and exhibits a tiling of cost 5 (r2, r16, r18). A tiling of cost below 5 does not exist: Lesson 21.2 enumerates all 18 tilings of this tree (Theorem 21.2.7 computes the minimum), and tools/course/tests/test_ch21.py checks the count and the minimum by brute force.

The failure is global. Munch's tiling is optimal (no pair can merge), yet the optimum uses a smaller root tile (r2 instead of r5) so that a larger tile fits below it (r18 instead of r9). A strategy that looks at one node at a time cannot weigh these two decisions together.

Theorem 21.1.15 (Cost ordering: optimum ≤ munch ≤ macro)

Let $G$ be munch-safe with macro table $M$, and suppose $G$ satisfies subsumption: for every rule $r = A \to \pi$ and every node $v$ where it matches, $c(r) \le \sum_{x \in \mathrm{cov}(\pi, v)} c(M(\mathrm{op}(x)))$, where the sum skips forced terminal leaves. Then for every statement $t$, $\mathrm{OPT}(t) \le \mathrm{cost}(\mathrm{munch}(t)) \le \mathrm{cost}(\mathrm{macro}(t))$.

Proof

The first inequality holds because munch returns a tiling (Theorem 21.1.13) and $\mathrm{OPT}$ is the minimum over all tilings. For the second, let $T_1, \dots, T_q$ be munch's tiles with rules $r_1, \dots, r_q$. By Lemma 21.1.12 they partition the non-forced nodes of $t$, and macro expansion charges exactly $c(M(\mathrm{op}(x)))$ for each such node $x$ (Proposition 21.1.7). Hence $\mathrm{cost}(\mathrm{munch}) = \sum_j c(r_j) \le \sum_j \sum_{x \in T_j} c(M(\mathrm{op}(x))) = \mathrm{cost}(\mathrm{macro})$.

Tessera satisfies subsumption

Check every multi-node rule against the sum of its macro costs: r3 $2 \le 2 + 1 + 1$; r4 $2 \le 2 + 1$; r5 $4 \le 2 + 2$; r9 and r11 $1 \le 1 + 1$; r13 $3 \le 1 + 3$; r15 $1 \le 1 + 1$; r16 $1 \le 1 + 1 + 1$; r18 $2 \le 2 + 1 + 1$; r19 and r20 $2 \le 2 + 1$. The lab's tests check $\mathrm{DP} \le \mathrm{munch} \le \mathrm{macro}$ on 300 random programs (SPEC R5).

Which precondition breaks munch. Munch-safety is essential. Take the grammar with rules reg: TEMP, reg: CONST, reg: ADD(reg, reg), reg: MEM(reg) and reg: MEM(ADD(reg, x)), plus the single rule x: TEMP. On MEM(ADD(TEMP a, CONST 5)), munch picks the size-2 rule at the MEM, then asks for an x at CONST 5 and gets stuck. A tiling exists (MEM(reg) over ADD(reg, reg)), but finding it needs backtracking. The grammar breaks munch-safety because x occurs as a leaf but has no rule for CONST. Without subsumption, Theorem 21.1.15's second inequality fails too. Raise r16 shadd to cost 10 and munch still picks it (it looks at sizes, not costs), paying 10 where macro expansion pays 3.

Peephole combining¶

Theorem 21.1.16 (Combining preserves behavior and terminates)

If $\mathrm{Recog}(e)$ returns only instructions that implement $e$ exactly, then every step of Algorithm 21.1.11 turns a sequence into an equivalent one. The algorithm terminates after at most $m - 1$ successful combinations and $O(m^2)$ attempts.

Proof

Equivalence. Before the step, $j$ computes $e_j$ with $d_i$ holding the value $e_i$ had at $i$. The side conditions of the algorithm guarantee that no instruction between $i$ and $j$ changes a register or (for loads) memory that $e_i$ reads. So $e_i$ evaluated at $j$'s position equals the value of $d_i$ there, and $j[i]$ computes the same value as $j$. The instruction $i$ can then be deleted: its only effect was writing $d_i$, which has no other reader and is dead after $j$ (Definition 21.1.10). Termination. Each successful step removes one instruction, so there are at most $m - 1$ of them. Each pass of the while loop either succeeds at least once or ends the loop, and a pass makes at most $m$ attempts, so the total is $O(m \cdot m)$.

The algorithm reaches a local fixed point, not the optimum. Its result depends on the order of attempts (§3 shows one order that reaches cost 5 and one that reaches 6), and it can only merge along single-use links. That is why GCC's combiner also tries triples and quadruples [GCC-Combine].

5. Complexity¶

Variables: $n$ nodes in the tree, $R$ rules, $p$ the maximum pattern size, $R_o$ the rules whose pattern root is operator $o$, $m$ instructions in the combiner's input, and $w$ the cost of one call to the recognizer.

Technique	Worst-case time	Typical time	Space	Justification
Macro expansion	$\Theta(n)$	$\Theta(n)$	$O(h)$ recursion ($h$ = tree height)	one template per node (Proposition 21.1.7)
Maximal munch	$O(n \cdot R \cdot p)$	$O(n \cdot \max_o R_o \cdot p)$ with rules indexed by root operator	$O(h)$	at most $n$ calls (one per tile), each tries $R$ rules at $O(p)$ per match
Peephole combining	$O(m^2 w)$	$O(m w)$ (one or two passes)	$O(m)$ links	Theorem 21.1.16

Munch visits fewer nodes than there are. Each call handles one tile and skips all the nodes that tile covers, so the number of calls equals the number of tiles, which is at most $n$.

A pathological family for munch's time. Besides the macro rule $\mathsf{reg} \to \mathsf{ADD}(\mathsf{reg}, \mathsf{reg})$, let the grammar have rules $\mathsf{reg} \to \mathsf{ADD}^{j}(\mathsf{CONST}, \mathsf{reg}, \dots, \mathsf{reg})$ for $j = 2..R$, each a left spine of $j$ ADD nodes whose leftmost leaf is a CONST. On a left spine of $n$ ADDs ending in a TEMP, the $j$-th rule walks $\Theta(j)$ nodes down the spine before it fails at the leaf, which is an ADD (or the TEMP), never a CONST. Only the macro rule matches, so munch makes one call per ADD ($n$ calls, tiles of size 1), and each call spends $\sum_{j \le R} \Theta(j) = \Theta(R^2)$ on failed matches. With $p = R$ that is $\Theta(nR^2) = \Theta(nRp)$ for the nodes at depth at least $R$: the $O(nRp)$ bound is tight.

A pathological family for munch's quality. Munch's cost can exceed the optimum by any factor if the grammar ignores subsumption. Give r5 movm cost $K$. Munch still takes it on every STORE(reg, MEM(reg)), so a program of $s$ such statements costs munch at least $sK$ while the optimum is at most $4s$ (ld + st). The ratio grows as $K/4$. Under subsumption, munch is never worse than macro expansion (Theorem 21.1.15).

Real-world scale. On 2005 programs (the lab's 5 samples plus 2000 random ones, 71197 tree nodes), the reference solution's totals are 70866 (macro), 53935 (munch) and 53632 (DP, the optimum). Munch is within 0.6 % of optimal in total, DP beats it on 14.3 % of the programs, and the selectors take 14, 36 and 59 µs per program. Reproduce with build/<preset>/bin/ch21-compare on a solution build (SPEC, "Measurement").

Macro expansion¶

Value-stack expansion (Winch, Liftoff, Sparkplug): the expander keeps a compile-time model of the operand stack. Constants and locals stay symbolic until an instruction needs them, so i32.const 3; i32.shl becomes shll $3, %eax without a separate li (see §7). This gives slightly better code at no algorithmic cost.
Expand then combine [DF84]: pair the naive expander with a peephole combiner (below). This is how GCC works: RTL expansion followed by combine.
Tree-walk code generation with attributes [EaC3, Ch. 11]: a syntax-directed walk that chooses among a few templates by inspecting children (for example, an immediate operand). It sits between macro expansion and tiling.

Maximal munch¶

Priority instead of size. LLVM's DAG selector orders patterns by a complexity score (3 per node, plus extras) that a target can raise with AddedComplexity, and Cranelift's ISLE uses explicit rule priorities (Lesson 21.7). Both are munch with a tunable order. The trade-off is more control and more ways to write a wrong order.
LR-parsing code generators (Graham–Glanville [GG78]): linearize the tree in prefix order and parse it with an LR parser built from the patterns, so every reduction emits an instruction. This is fast and table-driven. Shift-reduce conflicts are resolved in favor of the longest match, which is maximal munch again, and the grammar's ambiguity makes the tables fragile [Muchnick, §6.2].
Bottom-up greedy. Match at the leaves first and grow tiles upwards. This is simpler for DAGs but can miss big tiles that start at the root.

Peephole combining¶

Window size. McKeeman used a fixed window of adjacent instructions [McK65]. Davidson–Fraser combine along def–use links instead of textual adjacency [DF84], and GCC combines up to four linked instructions [GCC-Combine]. Bigger windows find more combinations at quadratic cost.
Cost-checked machine combining. LLVM's MachineCombiner accepts a rewrite only if the critical path computed with the scheduling model does not get longer [LLVM-MachineCombiner].
Superoptimized peepholes. Enumerate short instruction sequences and prove them equivalent to find new combinations offline [BA06]. Ch 13 covers this in depth.

7. In real compilers¶

Macro expansion¶

Wasmtime's baseline compiler Winch ("WebAssembly Intentionally Non-optimizing Compiler and Host") translates each WebAssembly instruction by itself with a value-stack model: winch/codegen/src/visitor.rs has one visit_* method per Wasm operator (Wasmtime v37.0.2) [WT-Winch]. V8's Liftoff does the same for Wasm (src/wasm/baseline/liftoff-compiler.cc), and Sparkplug for JavaScript bytecode (src/baseline/baseline-compiler.cc), both at V8 13.6.99 [V8-Baseline].

Winch (macro expansion) vs Cranelift (tiling) on a[i] = p[3]

Reproduce (Wasmtime 37.0.2 release binary for x86_64-linux; the sed keeps the one function):

cat > store.wat <<'EOF'
(module
  (memory 1)
  (func (export "store") (param $a i32) (param $i i32) (param $p i32)
    (i64.store
      (i32.add (local.get $a) (i32.shl (local.get $i) (i32.const 3)))
      (i64.load offset=24 (local.get $p)))))
EOF
wasmtime compile -C compiler=winch store.wat -o store-winch.cwasm
wasmtime objdump store-winch.cwasm | sed -n '/function\[0\]:/,/^$/p'
wasmtime compile store.wat -o store-cl.cwasm
wasmtime objdump store-cl.cwasm | sed -n '/function\[0\]:/,/^$/p'

Output (complete; Winch first, then Cranelift):

wasm[0]::function[0]:
            pushq   %rbp
            movq    %rsp, %rbp
            movq    8(%rdi), %r11
            movq    0x10(%r11), %r11
            addq    $0x20, %r11
            cmpq    %rsp, %r11
            ja      0x72
            movq    %rdi, %r14
            subq    $0x20, %rsp
            movq    %rdi, 0x18(%rsp)
            movq    %rsi, 0x10(%rsp)
            movl    %edx, 0xc(%rsp)
            movl    %ecx, 8(%rsp)
            movl    %r8d, 4(%rsp)
            movl    8(%rsp), %eax
            shll    $3, %eax
            movl    0xc(%rsp), %ecx
            addl    %eax, %ecx
            movl    4(%rsp), %eax
            movq    0x38(%r14), %rdx
            addq    %rax, %rdx
            addq    $0x18, %rdx
            movq    (%rdx), %rax
            ╰─╼ trap: MemoryOutOfBounds
            movq    0x38(%r14), %rdx
            addq    %rcx, %rdx
            movq    %rax, (%rdx)
            ╰─╼ trap: MemoryOutOfBounds
            addq    $0x20, %rsp
            popq    %rbp
            retq
            ud2
            ╰─╼ trap: StackOverflow
wasm[0]::function[0]:
            pushq   %rbp
            movq    %rsp, %rbp
            movq    0x38(%rdi), %r11
            movl    %r8d, %esi
            movq    0x18(%r11, %rsi), %rsi
            ╰─╼ trap: MemoryOutOfBounds
            leal    (%rdx, %rcx, 8), %edi
            movq    %rsi, (%r11, %rdi)
            ╰─╼ trap: MemoryOutOfBounds
            movq    %rbp, %rsp
            popq    %rbp
            retq

What to notice: Winch computes i << 3, a + …, the heap base plus the address, + 0x18, the load and the store as separate instructions, one per Wasm operator plus the memory-base arithmetic. That is Algorithm 21.1.6. Its only cleverness is the value stack's constant folding (shll $3), the first variant of §6. Cranelift tiles the same operations into two memory instructions whose addressing modes absorb the adds and the shift. The leal is the x86 counterpart of Tessera's shadd, and the base+index+displacement load is ld 24(p). Winch also spills every argument to the stack, but that is register allocation, not selection.

Maximal munch¶

LLVM's SelectionDAG selector is maximal munch over a DAG, with size measured by TableGen. DAGISelEmitter::run in llvm/utils/TableGen/DAGISelEmitter.cpp sorts all patterns by PatternToMatch::getPatternComplexity, which getPatternSize in llvm/utils/TableGen/Common/CodeGenDAGPatterns.cpp computes as 3 per node plus extras for immediates, predicates and complex patterns, plus AddedComplexity (LLVM 23.1.2) [LLVM-DAGISelEmitter]. The generated matcher tries the patterns in that order at each node and commits to the first that matches (Lesson 21.5).

Tessera in TableGen: patterns tried largest first

Reproduce (llvm-tblgen 23.1.2; Tessera.td is a 40-line toy target that uses only llvm/Target/Target.td, installed with LLVM):

cat > Tessera.td <<'EOF'
include "llvm/Target/Target.td"
class TReg<bits<16> enc, string n> : Register<n> { let HWEncoding = enc; let Namespace = "Tessera"; }
foreach i = 0-15 in def R#i : TReg<i, "r"#i>;
def GPR : RegisterClass<"Tessera", [i64], 64, (sequence "R%u", 0, 15)>;
def simm64 : Operand<i64>;
def addr : ComplexPattern<iPTR, 2, "SelectAddr", [], []>;
def memri : Operand<iPTR> { let MIOperandInfo = (ops GPR, simm64); }
class TInst<dag outs, dag ins, string asm, list<dag> pat> : Instruction {
  let Namespace = "Tessera"; let OutOperandList = outs; let InOperandList = ins;
  let AsmString = asm; let Pattern = pat; let Size = 4;
}
def ADD   : TInst<(outs GPR:$d), (ins GPR:$s, GPR:$t), "add $d, $s, $t",
                  [(set GPR:$d, (add GPR:$s, GPR:$t))]>;
def ADDI  : TInst<(outs GPR:$d), (ins GPR:$s, simm64:$c), "addi $d, $s, $c",
                  [(set GPR:$d, (add GPR:$s, imm:$c))]>;
def SHADD : TInst<(outs GPR:$d), (ins GPR:$s, GPR:$t, simm64:$k), "shadd $d, $s, $t, $k",
                  [(set GPR:$d, (add GPR:$s, (shl GPR:$t, imm:$k)))]>;
def MUL   : TInst<(outs GPR:$d), (ins GPR:$s, GPR:$t), "mul $d, $s, $t",
                  [(set GPR:$d, (mul GPR:$s, GPR:$t))]>;
def MADD  : TInst<(outs GPR:$d), (ins GPR:$s, GPR:$t, GPR:$u), "madd $d, $s, $t, $u",
                  [(set GPR:$d, (add (mul GPR:$s, GPR:$t), GPR:$u))]>;
def LD    : TInst<(outs GPR:$d), (ins memri:$a), "ld $d, $a", [(set GPR:$d, (load addr:$a))]>;
def ST    : TInst<(outs), (ins GPR:$v, memri:$a), "st $v, $a", [(store GPR:$v, addr:$a)]>;
def TesseraInstrInfo : InstrInfo;
def Tessera : Target { let InstructionSet = TesseraInstrInfo; }
EOF
llvm-tblgen -gen-dag-isel -I "$(llvm-config --includedir)" Tessera.td \
  | grep -E 'Src:' | sed -E 's/:\{ \*:\[(i64|iPTR)\] \}//g; s/^ +//'

Output (complete; the sed strips the type annotations :{ *:[i64] }):

// Src: (ld addr:$a)<<P:Predicate_unindexedload>><<P:Predicate_load>> - Complexity = 13
// Src: (st GPR:$v, addr:$a)<<P:Predicate_unindexedstore>><<P:Predicate_store>> - Complexity = 13
// Src: (add GPR:$s, (shl GPR:$t, (imm):$k)) - Complexity = 9
// Src: (add (shl GPR:$t, (imm):$k), GPR:$s) - Complexity = 9
// Src: (add GPR:$s, (imm):$c) - Complexity = 6
// Src: (add (mul GPR:$s, GPR:$t), GPR:$u) - Complexity = 6
// Src: (add GPR:$u, (mul GPR:$s, GPR:$t)) - Complexity = 6
// Src: (add GPR:$s, GPR:$t) - Complexity = 3
// Src: (mul GPR:$s, GPR:$t) - Complexity = 3

What to notice: these comments annotate the generated matcher table in the order the selector tries the patterns. Under add, shadd (complexity 9, three nodes) comes before addi and madd (6), and plain add (3) comes last. That is Algorithm 21.1.8 with size measured as 3 per node. TableGen also generated the commuted forms of the commutative add by itself (the second shadd and madd lines), which Tessera's rules file has to list by hand. Between addi and madd, which tie at 6, the order is TableGen's, just as Tessera breaks ties by rule number.

Peephole combining¶

GCC selects instructions by expanding GIMPLE into naive RTL and letting combine merge linked instructions. The merge is try_combine, and the recognizer is recog_for_combine, which runs the matcher generated from the machine description, in gcc/combine.cc (gcc-15 branch) [GCC-Combine]. LLVM has two machine-level combiners: PeepholeOptimizer in llvm/lib/CodeGen/PeepholeOptimizer.cpp (fold loads, rewrite copies, optimize compares) and MachineCombiner in llvm/lib/CodeGen/MachineCombiner.cpp (LLVM 23.1.2) [LLVM-MachineCombiner].

GCC's combiner on a[i] = p[3]

Reproduce (GCC 13.3.0 as shipped with Ubuntu 24.04; the dump's pass number differs between GCC versions, hence the *):

cat > store.c <<'EOF'
void store(long *a, long i, long *p) { a[i] = p[3]; }
EOF
gcc -O2 -S -fdump-rtl-combine-details store.c -o store.s
sed -n '/^Trying 4 -> 8/,/^replacement cost/p' store.c.*r.combine
grep -m1 -A12 '^Trying 8 -> 9' store.c.*r.combine

Output (complete):

Trying 4 -> 8:
    4: r88:DI=r91:DI
      REG_DEAD r91:DI
    8: r85:DI=[r88:DI+0x18]
      REG_DEAD r88:DI
Successfully matched this instruction:
(set (reg:DI 85 [ _4 ])
    (mem:DI (plus:DI (reg:DI 91)
            (const_int 24 [0x18])) [1 MEM[(long int *)p_8(D) + 24B]+0 S8 A64]))
allowing combination of insns 4 and 8
original costs 4 + 9 = 13
replacement cost 9
Trying 8 -> 9:
    8: r85:DI=[r91:DI+0x18]
      REG_DEAD r91:DI
    9: [r87:DI*0x8+r89:DI]=r85:DI
      REG_DEAD r89:DI
      REG_DEAD r85:DI
      REG_DEAD r87:DI
Failed to match this instruction:
(set (mem:DI (plus:DI (mult:DI (reg/v:DI 87 [ i ])
                (const_int 8 [0x8]))
            (reg:DI 89)) [1 *_3+0 S8 A64])
    (mem:DI (plus:DI (reg:DI 91)
            (const_int 24 [0x18])) [1 MEM[(long int *)p_8(D) + 24B]+0 S8 A64]))

What to notice: each "Trying i -> j" is one step of Algorithm 21.1.11 along a link: GCC substitutes insn $i$ into insn $j$, asks the machine description whether the result is one instruction (recog), and compares costs ("original costs 4 + 9 = 13, replacement cost 9"). The REG_DEAD notes are the single-use condition of Definition 21.1.10. The failed attempt 8 → 9 is the running example's movm: substituting the load into the store gives a memory-to-memory move, and x86-64 has no such instruction, so combining stops at the optimum movq 24(%rdx), %rax; movq %rax, (%rdi,%rsi,8).

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Macro expansion	one instruction sequence per node; cannot use multi-node instructions or addressing modes	$\Theta(n)$ · lab: 14 µs per program; cost 70866 on the lab corpus (32 % above optimum)	poorest code; very predictable	lowest: a table of templates	baseline and debug compilers: Winch, Liftoff, Sparkplug; first stage of expand-then-combine
Maximal munch	largest tile at each node; locally optimal (Theorem 21.1.13), not optimum (Proposition 21.1.14)	$O(nRp)$ · lab: 36 µs per program; cost 53935 (0.6 % above optimum)	good; loses when a big tile near the root blocks a better one below	low: pattern matcher plus an ordering	LLVM SelectionDAG and GlobalISel (by complexity), Cranelift ISLE (by priority), Appel's Tiger compiler
Peephole combining	whatever single-use links and the recognizer allow; order-dependent local fixed point (Theorem 21.1.16)	$O(m^2 w)$ worst · a linear pass or two in practice	good with a strong recognizer; misses combinations across multiple uses	moderate: RTL substitution, recognizer, liveness	GCC `combine`, LLVM `PeepholeOptimizer` and `MachineCombiner`, the Davidson–Fraser PO and vpo

Choose macro expansion when compile time dominates: baseline JIT tiers, -O0, or the first stage before a combiner.
Choose maximal munch when you want nearly optimal code with a simple implementation and your costs roughly follow tile size (subsumption). This is the default choice of production selectors.
Choose peephole combining when you already have a naive expander and a machine description with a recognizer (GCC's situation), or as a cleanup after any selector.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch21.yaml`)	Drill	Flashcard tag	Exercises
Macro expansion	`macro-cost-running`, `macro-instructions`	`./course drill munch-tiling` asks for macro-free munch tilings; macro costs are asked in `dp-tiling`'s worked solutions and the quiz. A dedicated drill would only count nodes	`macro-expansion`	E1
Maximal munch	`munch-trace-running`, `munch-optimal-vs-optimum`, `llvm-where-complexity`	`./course drill munch-tiling`	`maximal-munch`	E2
Peephole combining	`combine-order`, `combine-single-use`	none: the combiner's result depends on the recognizer and the visiting order, which the quiz fixes instead	`peephole-combining`	—

Largest is not cheapest

Munch compares sizes, never costs, and it cannot undo a choice. movm is the largest STORE tile, so munch takes it whenever the value is a load, even though ld + st cost the same 4 and keep the load's addressing mode available. If you "fix" munch by comparing rule costs at the node, you get a different greedy algorithm that is still not optimum: the cost of a rule says nothing about how cheaply its operands can be computed. Only the dynamic programming of Lesson 21.2 accounts for both.

References¶

See the chapter references.

#	producer \(i\)	consumer \(j\)	combined transfer \(j[i]\)	recognized as	cost before → after
1	`li r1, 3`	`sll r2, i, r1`	\(r2 \leftarrow i \ll 3\)	`slli r2, i, 3` (r15)	2 → 1
2	`slli r2, i, 3`	`add r3, a, r2`	\(r3 \leftarrow a + (i \ll 3)\)	`shadd r3, a, i, 3` (r16)	2 → 1
3	`shadd r3, a, i, 3`	`st r6, 0(r3)`	\(M[a + (i \ll 3)] \leftarrow r6\)	⊥ (no scaled store)	kept
4	`li r4, 24`	`add r5, p, r4`	\(r5 \leftarrow p + 24\)	`addi r5, p, 24` (r9)	2 → 1
5	`addi r5, p, 24`	`ld r6, 0(r5)`	\(r6 \leftarrow M[p + 24]\)	`ld r6, 24(p)` (r18)	3 → 2
6	`ld r6, 24(p)`	`st r6, 0(r3)`	\(M[r3] \leftarrow M[p + 24]\)	⊥ (`movm` has no offset)	kept
7	second pass: no link changes				fixed point

Technique	Worst-case time	Typical time	Space	Justification
Macro expansion	\(\Theta(n)\)	\(\Theta(n)\)	\(O(h)\) recursion (\(h\) = tree height)	one template per node (Proposition 21.1.7)
Maximal munch	\(O(n \cdot R \cdot p)\)	\(O(n \cdot \max_o R_o \cdot p)\) with rules indexed by root operator	\(O(h)\)	at most \(n\) calls (one per tile), each tries \(R\) rules at \(O(p)\) per match
Peephole combining	\(O(m^2 w)\)	\(O(m w)\) (one or two passes)	\(O(m)\) links	Theorem 21.1.16

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Macro expansion	one instruction sequence per node; cannot use multi-node instructions or addressing modes	\(\Theta(n)\) · lab: 14 µs per program; cost 70866 on the lab corpus (32 % above optimum)	poorest code; very predictable	lowest: a table of templates	baseline and debug compilers: Winch, Liftoff, Sparkplug; first stage of expand-then-combine
Maximal munch	largest tile at each node; locally optimal (Theorem 21.1.13), not optimum (Proposition 21.1.14)	\(O(nRp)\) · lab: 36 µs per program; cost 53935 (0.6 % above optimum)	good; loses when a big tile near the root blocks a better one below	low: pattern matcher plus an ordering	LLVM SelectionDAG and GlobalISel (by complexity), Cranelift ISLE (by priority), Appel's Tiger compiler
Peephole combining	whatever single-use links and the recognizer allow; order-dependent local fixed point (Theorem 21.1.16)	\(O(m^2 w)\) worst · a linear pass or two in practice	good with a strong recognizer; misses combinations across multiple uses	moderate: RTL substitution, recognizer, liveness	GCC `combine`, LLVM `PeepholeOptimizer` and `MachineCombiner`, the Davidson–Fraser PO and vpo

Lesson 21.1 — Tree tiling I: macro expansion, maximal munch and peephole combining¶

1. Problem and motivation¶

Macro expansion¶

Maximal munch¶

Peephole combining¶

2. Definitions and algorithms¶

Macro expansion¶

Maximal munch¶

Peephole combining¶

3. Worked example¶

Macro expansion¶

Maximal munch¶

Peephole combining¶

4. Invariants and correctness¶

Macro expansion¶

Maximal munch¶

Peephole combining¶

5. Complexity¶

6. Variants and refinements¶

Macro expansion¶

Maximal munch¶

Peephole combining¶

7. In real compilers¶

Macro expansion¶

Maximal munch¶

Peephole combining¶

8. Comparison¶

9. Assessment¶

References¶