Lesson 13.2 — Peephole engines: hand-written combiners and pattern DSLs¶

Techniques: hand-written combiners (LLVM InstCombine and the InstSimplify/InstCombine contract); embedded pattern matchers (LLVM PatternMatch); external pattern DSLs compiled to matchers (GCC match.pd + genmatch, Cranelift ISLE, the GlobalISel combiner's TableGen rules) · Pebble implements: pebble-peephole, a flag-aware engine for the rule set R1–R17 (exercise E2) · Lab: the same integer rules as a rule-table/DSL engine, pebble-peephole-dsl, measured against the hand-written one (labs/ch13-peephole, Parts A and D) · Prerequisites: Lesson 13.1, Ch 10 (PatternMatch, IRBuilder) · Time: 5 hours

A peephole optimizer looks at a few adjacent instructions through a small "peephole" and replaces them by something better: add x, x by shl x, 1, (x + 5) - 3 by x + 2, x - x by 0. McKeeman named the idea in 1965 for machine code [McK65]; today every compiler has hundreds or thousands of such rules at the IR level, and the engineering question is how to write, organize, match and trust them. This lesson compares the three ways production compilers write rules: by hand in C++ (LLVM's InstCombine), with a matcher library embedded in the host language (LLVM's PatternMatch), and in a separate pattern language compiled into a matcher (GCC's match.pd, Cranelift's ISLE, LLVM's GlobalISel combiner). Lesson 13.4 then asks when a rule set terminates and gives a unique result, and Lessons 13.8–13.9 how to prove each rule.

1. Problem and motivation¶

Given an instruction and the small expression DAG feeding it, find a cheaper equivalent (a refinement, Definition 9.7.8) and substitute it, repeatedly, until no rule applies. Peephole rules clean up after every other pass: inlining, lowering and unrolling leave patterns such as x * 1, (x + 1) - 1 and x & -1 everywhere. In pebblec, pebble-peephole (exercise E2) implements seventeen such rules on the LLVM IR of Pebble programs, and must decide for each one which poison-generating flags (nsw, nuw, exact, …) the result may keep.

Hand-written combiners¶

The original peephole optimizers matched fixed instruction windows in hand-written code [McK65]; Davidson and Fraser made them retargetable by deriving rules from machine descriptions [DF80]. LLVM's InstCombine is the modern hand-written combiner: one C++ visitor per opcode (visitAdd, visitMul, …), each trying a sequence of folds, driven by a worklist until a fixed point [LLVM-InstCombine]. Its companion InstSimplify answers a narrower question: can this instruction be replaced by an existing value or a constant? Splitting the two keeps the cheap, allocation-free simplifications reusable from every other pass [LLVM-ICGuide].

Embedded pattern matchers¶

Writing if (auto *Sub = dyn_cast<BinaryOperator>(I.getOperand(0))) if (Sub->getOpcode() == ...) for every rule is verbose and error-prone. LLVM's PatternMatch.h embeds a pattern language in C++ templates: match(&I, m_Add(m_Sub(m_Value(A), m_Value(X)), m_Deferred(X))) reads like the rule and compiles to the same nested tests [LLVM-PatternMatch]. The rules are still hand-ordered C++.

External pattern DSLs¶

The next step moves rules out of the host language entirely. GCC's match.pd (Richard Biener, GCC 5, 2015) states simplifications as Lisp-like (simplify (minus @0 @0) ...) rules, and the generator genmatch compiles all of them into one decision tree emitted as C for both GIMPLE and GENERIC [GCC-matchpd]. Cranelift's ISLE (instruction selection/lowering expressions, Fallin et al. 2022–2023) is a typed term-rewriting language used for both lowering and mid-end simplification, compiled to Rust matchers [Cranelift-ISLE]. LLVM's GlobalISel combiner writes GICombineRules in TableGen, from which a matcher table is generated [LLVM-GISelCombine]. The same idea appears in MLIR's PDL/PDLL and declarative rewrite rules.

2. Definitions and algorithms¶

Definition 13.2.1 (Peephole rule)

A peephole rule \(\rho = (L, R, P, \varphi)\) consists of a pattern \(L\), a term over operations, pattern variables \(x, y, \dots\) (matching any value) and constant variables \(C, C_1, \dots\) (matching integer constants); a replacement \(R\), a term over the same variables and over constant expressions (\(-C\), \(C_1 + C_2\), \(\log_2 C\)); a precondition \(P\) over the constants and the matched instructions' flags and types; and a flag function \(\varphi\) that assigns poison-generating flags to the instructions \(R\) creates. A rule is valid if every instance satisfying \(P\) is a refinement: \(\sigma(L) \sqsupseteq \sigma(R)\) with flags \(\varphi(\sigma)\) (Definition 9.7.8).

Rule R9 (add-add-const) of exercise E2

\(L = \mathsf{add}(\mathsf{add}(x, C_1), C_2)\), \(R = \mathsf{add}(x, C_1 + C_2)\), \(P = \mathit{true}\), and \(\varphi\) sets nsw iff both matched adds have nsw and \(C_1 + C_2\) does not overflow as signed values (likewise nuw, unsigned). Theorem 13.8.14 proves this \(\varphi\) is exactly right.

Definition 13.2.2 (Match)

A pattern \(L\) matches a value \(v\) under a substitution \(\sigma\) from variables to values if: \(L\) is a variable \(x\) and \(\sigma(x) = v\); \(L\) is a constant variable \(C\), \(v\) is an integer constant and \(\sigma(C) = v\); \(L\) is a literal constant equal to \(v\); or \(L = \mathsf{op}(L_1, \dots, L_k)\), \(v\) is an instruction \(\mathsf{op}(v_1, \dots, v_k)\) with the same opcode, and each \(L_j\) matches \(v_j\) under \(\sigma\). A variable occurring twice must be bound to the same value (non-linear patterns such as \(\mathsf{sub}(x, x)\)). A pattern is matched up to commutativity if commutative operations may also match with their operands swapped.

Definition 13.2.3 (The InstSimplify/InstCombine contract)

A simplifier maps an instruction \(i\) to an existing value (an operand, another instruction that dominates \(i\), or a constant) that refines \(i\), or to nothing; it never creates instructions. A combiner may also replace \(i\) by newly created instructions, provided it does not increase the instruction count except when replacing an expensive operation (a division) by cheaper ones, and provided its outputs are in canonical form (Lesson 13.4) [LLVM-ICGuide]. A combiner first tries the simplifier on each instruction.

Hand-written combiners¶

Algorithm 13.2.4 (Worklist peephole engine)

Input: a function \(f\); rules \(\rho_1, \dots, \rho_m\) in priority order (for a hand-written combiner: the order of the ifs in each opcode's visitor).
Output: \(f\) rewritten until no rule applies to any instruction.
Precondition: every rule is valid (Definition 13.2.1); the rule set terminates (Theorem 13.4.9 for R1–R17).
Postcondition: no rule matches any instruction of the result; the result refines \(f\) (Theorem 13.2.7).
Invariant: every instruction to which some rule might apply is in \(W\). (A rule of pattern depth at most 2 — true of R1–R17 — can start to apply to an instruction only when it or one of its operands is replaced, or when an operand of one of its operands is; the pushes below cover exactly these.)

function Combine(f, rules):
    W ← instructions of f in program order            # a FIFO set: no duplicates
    while W ≠ ∅:
        i ← pop front of W
        for ρ in rules applicable to opcode(i), in priority order:
            σ ← Match(ρ.L, i)                           # Algorithm 13.2.5
            if σ ≠ fail and ρ.P(σ):
                v ← Build(ρ.R, σ, ρ.φ) before i           # new instructions, or an existing value
                push every new instruction of v to W
                push every user of i, and every user of those users, to W
                replace every use of i by v
                EraseDead(i, W)
                break
    return f

function EraseDead(i, W):                             # i has no uses left
    S ← {i}
    while S ≠ ∅:
        j ← remove any element of S
        remove j from W; delete j
        for o in operands of j that are instructions:
            if o has no uses and no side effects: S ← S ∪ {o}

Build instantiates \(R\) bottom-up: a variable becomes \(\sigma(x)\), a constant expression is evaluated, an operation becomes a new instruction whose flags \(\rho.\varphi(\sigma)\) decides. This is pebble-peephole (exercise E2) and, with a different rule representation, pebble-peephole-dsl (lab Part A).

Embedded pattern matchers¶

Algorithm 13.2.5 (Recursive pattern matching)

Input: a pattern \(L\) (Definition 13.2.2) and a value \(v\).
Output: a substitution \(\sigma\) such that \(L\) matches \(v\) under \(\sigma\), or fail.
Precondition: \(L\) is finite.
Postcondition: the result is a matching substitution with minimal domain (the variables of \(L\)), and fail only if none exists (Lemma 13.2.8).
Invariant: \(\sigma\) binds exactly the variables of the sub-patterns already matched, consistently.

function Match(L, v):
    σ ← empty substitution
    return σ if M(L, v, σ) else fail

function M(L, v, σ):
    case L of
        variable x:        if x ∈ dom(σ): return σ(x) = v
                           σ(x) ← v; return true
        constant var C:    if v is not an integer constant: return false
                           if C ∈ dom(σ): return σ(C) = v
                           σ(C) ← v; return true
        literal k:         return v is the constant k
        op(L1, ..., Lk):   if v is not an instruction with opcode op: return false
                           for j in 1..k:
                               if not M(Lj, operand j of v, σ): return false
                           return true

PatternMatch builds each pattern as a C++ object at compile time (m_Add(m_Value(X), m_APInt(C)) has type BinaryOp_match<bind_ty<Value>, apint_match, Instruction::Add>), so M is inlined into straight-line tests. m_c_Add tries both operand orders (commutative matching); m_Deferred(X) is the second occurrence of a non-linear variable; m_OneUse(P) adds the precondition "has one use" [LLVM-PatternMatch].

External pattern DSLs¶

Algorithm 13.2.6 (Compiling a rule set into a decision tree)

Input: rules \(\rho_1, \dots, \rho_m\) in priority order.
Output: a tree whose internal nodes test one position of the input term (its opcode, or whether it is a constant) and whose leaves list the rules whose patterns agree with every test on the path, in priority order.
Precondition: patterns are finite terms.
Postcondition: for every input \(v\), walking the tree and then checking the leaves' non-linear equalities and preconditions in order yields the same first applicable rule as trying \(\rho_1, \dots, \rho_m\) in sequence (Theorem 13.2.9).
Invariant: each node's rule list is the set of rules consistent with the tests from the root to it, in priority order.

function Build(rules, positions):                    # positions: a queue of term paths, root first
    if positions = ∅ or every rule's pattern is fully tested:
        return Leaf(rules)
    p ← pop front of positions
    node ← Test(p)
    for each label ℓ that some rule has at p (an opcode, "constant"):
        R_ℓ ← [ρ ∈ rules | ρ has ℓ at p, or ρ has a variable at p]      # order kept
        node.child[ℓ] ← Build(R_ℓ, positions + children of p in ρ's with ℓ at p)
    node.default ← Build([ρ ∈ rules | ρ has a variable at p], positions)
    return node

function Run(node, v):
    while node is a Test(p):
        ℓ ← label of the subterm of v at p
        node ← node.child[ℓ] if it exists else node.default
    for ρ in node.rules:                              # priority order
        if the non-linear equalities and ρ.P hold for v: return ρ
    return none

genmatch's dt_node tree "represents the 'match' expression of all simplifies and has those as its leafs" [GCC-matchpd]; ISLE compiles rules into a similar trie with explicit rule priorities [Cranelift-ISLE]; the GlobalISel combiner generates a matcher table from TableGen [LLVM-GISelCombine].

3. Worked example¶

Running example (pebble-peephole's behavior on it is checked by tests/ch13/lit/peephole-stats.ll):

define i32 @peep(i32 %x, i32 %y) {
  %a = mul i32 3, %x
  %b = mul i32 8, %a
  %z = sub i32 %x, %x
  %c = add i32 %z, %y
  %d = add i32 %c, 5
  %e = sub i32 %d, 3
  %r = xor i32 %b, %e
  ret i32 %r
}

flowchart BT
  x([x]) --> a[a = mul 3, x]
  a --> b[b = mul 8, a]
  x --> z[z = sub x, x]
  z --> c[c = add z, y]
  y([y]) --> c
  c --> d[d = add c, 5]
  d --> e[e = sub d, 3]
  b --> r[r = xor b, e]
  e --> r

Hand-written combiners¶

Algorithm 13.2.4 with the rules R1–R17 of exercise E2 (priority: R1 const-rhs first). Each row pops the front of \(W\); a primed name is the new instruction that replaces the old one and takes its name. Pushing \(i\)'s users and their users (Algorithm 13.2.4) only re-inserts instructions already in \(W\) until step 10. The trace is what the reference solution prints with its pebble-peephole<trace> option.

step	popped	rule	effect	\(W\) after (front first)
0	—	—	—	a b z c d e r ret
1	`a = mul 3, x`	R1 const-rhs	a′ = `mul x, 3`	b z c d e r ret a′
2	`b = mul 8, a′`	R1 const-rhs	b′ = `mul a′, 8`	z c d e r ret a′ b′
3	`z = sub x, x`	R5 self-cancel	uses of z := 0; `c` is now `add 0, y`	c d e r ret a′ b′
4	`c = add 0, y`	R1 const-rhs	c′ = `add y, 0`	d e r ret a′ b′ c′
5	`d = add c′, 5`	R9 add-add-const (\(C_1 = 0\), \(C_2 = 5\))	d′ = `add y, 5`; c′ dead, erased	e r ret a′ b′ d′
6	`e = sub d′, 3`	R8 sub-const	e′ = `add d′, -3`	r ret a′ b′ d′ e′
7	`r = xor b′, e′`	—	—	ret a′ b′ d′ e′
8	`ret`	—	—	a′ b′ d′ e′
9	`a′ = mul x, 3`	—	(3 is not a power of two)	b′ d′ e′
10	`b′ = mul a′, 8`	R10 mul-pow2	b″ = `shl a′, 3`; pushes b″, then r (user), ret (user of r)	d′ e′ b″ r ret
11	`d′ = add y, 5`	—	—	e′ b″ r ret
12	`e′ = add d′, -3`	R9 add-add-const	e″ = `add y, 2`; d′ dead, erased	b″ r ret e″
13	`b″ = shl a′, 3`	—	—	r ret e″
14	`r = xor b″, e″`	—	—	ret e″
15	`ret`	—	—	e″
16	`e″ = add y, 2`	—	—	(empty)

Result: %a = mul i32 %x, 3, %b = shl i32 %a, 3, %e = add i32 %y, 2, %r = xor, ret: 5 instructions instead of 8. Step 5 shows why rule order and worklist order matter: R9 fired on add (add y, 0), 5 before R2 (zero-identity) ever saw add y, 0, so the rule statistics are R1 ×3, R5, R8, R9 ×2, R10 — no R2 at all. A different order reaches the same final IR here; Lesson 13.4 says when that is guaranteed.

Embedded pattern matchers¶

Algorithm 13.2.5 matching R9's pattern \(L = \mathsf{add}(\mathsf{add}(x, C_1), C_2)\) against e′ = add d′, -3 at step 12:

call	pattern	value	result	\(\sigma\)
1	\(\mathsf{add}(\mathsf{add}(x, C_1), C_2)\)	`e′ = add d′, -3`	opcode ok	{}
2	\(\mathsf{add}(x, C_1)\)	`d′ = add y, 5`	opcode ok	{}
3	\(x\)	`%y`	bind	{x ↦ y}
4	\(C_1\)	`5`	constant, bind	{x ↦ y, C1 ↦ 5}
5	\(C_2\)	`-3`	constant, bind	{x ↦ y, C1 ↦ 5, C2 ↦ -3}

\(R = \mathsf{add}(x, C_1 + C_2)\) builds add %y, 2; neither add had nsw, so \(\varphi\) sets none. In PatternMatch this is match(&I, m_Add(m_Add(m_Value(X), m_APInt(C1)), m_APInt(C2))).

External pattern DSLs¶

Algorithm 13.2.6 on four integer rules with root opcode add: R1 \(\mathsf{add}(C, x)\), R2 \(\mathsf{add}(x, 0)\), R9 \(\mathsf{add}(\mathsf{add}(x, C_1), C_2)\), R11 \(\mathsf{add}(x, x)\). Positions are paths: \(\epsilon\) is the root, \(1\) and \(2\) its operands, \(1.1\) the first operand of operand 1.

node	tests position	rules (priority order)	children
n0	\(\epsilon\)	R1 R2 R9 R11	`add` → n1
n1	\(1\)	R1 R2 R9 R11	`const` → n2; `add` → n3; other → n4
n2	\(2\)	R1 R2 R11	`const 0` → leaf {R1, R2, R11}; other → leaf {R1, R11}
n3	\(2\)	R2 R9 R11	`const 0` → n5; other `const` → n6; other → leaf
n4	\(2\)	R2 R11	`const 0` → leaf {R2, R11}; other → leaf {R11}
n5	\(1.2\)	R2 R9 R11	`const` → leaf {R2, R9, R11}; other → leaf {R2, R11}
n6	\(1.2\)	R9 R11	`const` → leaf {R9, R11}; other → leaf {R11}

R2 and R11 have a variable at position 1, so they follow every branch of n1; R9 needs an add at 1 and a constant at 2 and at 1.2. The input add (add y, 5), 0 walks n0 → n1 (add) → n3 (const 0) → n5 (5 is a constant) to the leaf {R2, R9, R11} and gets R2, the same answer as trying R1, R2, R9, R11 in sequence. Leaves still check the non-linear equality of R11 (\(x = x\)) and R1's precondition that operand 2 is not a constant (E2 skips all-constant instructions).

Try it

Run the engine on your own inputs: opt -load-pass-plugin=build/<preset>/lib/PebblePasses.so -passes='pebble-peephole<stats>' -S file.ll after exercise E2; ./course drill rewrite-validity --difficulty easy asks whether one rule instance is valid, which is what every rule of a peephole engine must be.

4. Invariants and correctness¶

Hand-written combiners¶

Theorem 13.2.7 (A worklist engine with valid rules refines its input)

If every rule is valid (Definition 13.2.1), each step of Algorithm 13.2.4 produces a function that refines the previous one; hence, if the engine terminates, its result refines its input. At termination no rule applies to any instruction.

Proof

One step. Let rule \(\rho\) fire on \(i\) with \(\sigma\), producing \(v\). Validity gives \(\sigma(L) \sqsupseteq v\) as value expressions over the inputs of the matched sub-DAG. Every use of \(i\) is a context \(C[\cdot]\) built from IR operations with one hole, so Theorem 9.7.16 (refinement is a congruence) gives \(C[i] \sqsupseteq C[v]\); replacing all uses at once is a composition of such steps, and \(\sqsupseteq\) is transitive (Theorem 9.7.16 (a)). The matched inner instructions stay in place as long as they have other uses, so their values are unchanged; EraseDead deletes only instructions without uses and without side effects, which removes no behavior. The new instructions are inserted before \(i\), where all their operands (values of the matched DAG) are available, so the function stays well formed. Whole run. By induction on the number of steps and transitivity of refinement (Theorem 13.8.3). Fixed point. The invariant of Algorithm 13.2.4: initially every instruction is in \(W\). A rule of depth \(\le 2\) applies to \(u\) depending only on \(u\), its operands, and their operands. A step replaces \(i\) by \(v\): the new instructions of \(v\) are pushed; each user \(u_1\) of \(i\) gets a new operand (pushed); each user \(u_2\) of such a \(u_1\) gets an operand whose operands changed (pushed); nothing else changes except deleted dead instructions, which are removed from \(W\). So every instruction whose applicability may have changed is in \(W\), and a popped instruction to which no rule applies stays inapplicable until one of these events re-pushes it. When \(W = \emptyset\), no rule applies.

Deep patterns and the worklist

A rule whose pattern reaches two levels down (R7 neg-neg, R9 add-add-const) can become applicable to an instruction \(u\) when an operand of \(u\)'s operand changes. An engine that pushes only direct users misses such matches: it still produces a correct program (Theorem 13.2.7's refinement part does not need the invariant), but not a fixed point, and the result depends on the order. Push users of users (as Algorithm 13.2.4 does for depth-2 rules), or re-run the whole function until an iteration changes nothing. InstCombine in LLVM 23 runs one iteration by default (InstCombineDefaultMaxIterations = 1 in InstCombine.h) and relies on its worklist; instcombine<verify-fixpoint> runs one more and reports a fatal error "did not reach a fixpoint" if that iteration still changes something.

Embedded pattern matchers¶

Lemma 13.2.8 (The matcher is sound and complete)

Match(L, v) (Algorithm 13.2.5) returns \(\sigma\) iff \(L\) matches \(v\) under \(\sigma\) (Definition 13.2.2), and fail iff no such \(\sigma\) exists (up to commutativity only when the pattern asks for it).

Proof

By structural induction on \(L\), with the invariant that \(\sigma\) agrees with every successful sub-match so far. Variables: the first occurrence binds, later occurrences compare, which is exactly the consistency requirement for non-linear patterns. Constants and literals: direct from the definition. \(\mathsf{op}(L_1, \dots, L_k)\): the opcode test is necessary; by the induction hypothesis each \(M(L_j, v_j, \sigma)\) succeeds iff \(L_j\) matches \(v_j\) under an extension of the current \(\sigma\) consistent with it; since the \(L_j\) are matched left to right with one shared \(\sigma\), all succeed iff a single consistent \(\sigma\) exists. Completeness: a pattern variable can only be bound to the value at its position, so there is no choice to backtrack over; with commutative matching (m_c_*) the matcher tries both orders of the two operands, which is again exhaustive.

External pattern DSLs¶

Theorem 13.2.9 (Decision trees preserve rule priority)

For every input \(v\), Run(Build(rules)) (Algorithm 13.2.6) returns the first rule in priority order whose pattern matches \(v\) and whose precondition holds, or none if there is no such rule.

Proof

Let \(\rho_k\) be the first rule, in priority order, that matches \(v\) and satisfies its precondition. \(\rho_k\) reaches the leaf: at each test node on \(v\)'s path, \(\rho_k\)'s pattern either has the label of \(v\)'s subterm at that position (it matches \(v\)) or a variable there, so \(\rho_k\) is kept in the child taken (or in the default child, which keeps exactly the rules with a variable at \(p\) — and if \(v\)'s label has an explicit child, that child's list also includes all rules with a variable at \(p\)). By induction on the path, \(\rho_k\) is in the leaf's list. Order: every Build step filters a list without reordering it (the node invariant), so the leaf list is in priority order. No earlier rule wins: a rule \(\rho_j\), \(j < k\), in the leaf list agrees with \(v\) on every tested position, so it fails only on an untested non-linear equality or its precondition, which Run checks — and since \(\rho_j\) does not both match and satisfy \(P\) (by the choice of \(k\)), Run skips it. Rules removed on the way disagree with \(v\) at a tested position, so they do not match. Hence Run returns \(\rho_k\). If no rule qualifies, every leaf entry fails its final check and Run returns none.

When it breaks. A rule that is invalid for some instance (a missing flag condition, a width where it fails) makes Theorem 13.2.7 false regardless of the engine: this is what the rule checker of the lab (Part B) and Alive2 (Lesson 13.9) are for. A combiner that creates instructions without the canonical-form discipline can loop forever (Lesson 13.4).

5. Complexity¶

Technique	Time (worst)	Time (typical)	Space	Variables
Hand-written combiner (sequential tries)	\(O(s \cdot m \cdot \ell)\)	\(O(n \cdot \bar m)\) per round	\(O(n)\) worklist	\(s\) steps (rewrites + no-change pops), \(m\) rules per opcode, \(\ell\) pattern size, \(n\) instructions, \(\bar m\) average rules tried
Embedded matcher (one pattern)	\(O(\ell)\) (\(O(2^{c}\ell)\) with \(c\) commutative nodes)	\(O(1)\): the opcode test usually fails first	\(O(\text{vars})\)	\(\ell\) pattern size, \(c\) commutative nodes
Decision tree (compiled DSL)	\(O(d + k)\) per instruction	\(O(d)\)	\(O(\sum_\rho \ell_\rho)\) for the tree	\(d\) tree depth \(\le \max \ell_\rho\), \(k\) rules in the reached leaf

Justification. A sequential engine may try every rule for the opcode on every pop, and each try costs at most the pattern size; the number of pops \(s\) is at most the initial \(n\) plus two pushes per rewrite (new instruction and users), and the number of rewrites is bounded by the termination measure of Theorem 13.4.9. Commutative matching tries two orders at each commutative node, \(2^c\) in the worst case. The decision tree tests each position once on the way down (depth \(\le\) the largest pattern), then checks the leaf's rules; its size is at most the sum of the pattern sizes (each rule adds one path).

Pathological family. \(m\) rules \(\mathsf{add}(\mathsf{add}(\dots \mathsf{add}(x, C_1) \dots), C_j)\) with \(j = 1..m\) (nested to depth \(j\)) all test the same prefix: a sequential engine re-walks the nested adds \(1 + 2 + \dots + m = \Theta(m^2)\) times per instruction, while the decision tree walks the prefix once, \(\Theta(m)\).

Scale. The lab measured both engines of this course on the same rules (labs/ch13-peephole/measure.py, reference solutions, Linux x86-64): on 144 720 instructions (synthetic corpus × 30), both applied the same 40 650 rewrites and left 125 550 instructions; over three runs (best of 7–11 each) the hand-written engine took 25–40 ms and the interpreted DSL engine 75–95 ms beyond the 225–250 ms that opt spends on start-up, parsing and printing the counts (the no-op column). A DSL interpreted at run time pays for its generality; genmatch and ISLE compile rules to code, which removes that cost.

Hand-written combiners¶

Retargetable peephole optimizers [DF80]: rules derived from a machine description and applied to RTL; the ancestor of GCC's combiner (combine.cc). Trade-off: generality vs. hand-tuned speed.
Multi-iteration vs. single-iteration fixed points: InstCombine used to re-run whole-function iterations until no change; LLVM 23 defaults to one iteration and checks in its tests that a second one would change nothing (instcombine<verify-fixpoint>, InstCombinerImpl::run in InstructionCombining.cpp). Trade-off: compile time vs. rule-writing discipline (every rule must push exactly the right instructions).
Simplifier/combiner split (Definition 13.2.3): reuse the allocation-free simplifier from every pass (GVN, EarlyCSE and SCCP call simplifyInstruction).

Embedded pattern matchers¶

One-use and flag-aware matchers: m_OneUse, m_NSWAdd, m_NUWShl, m_Exact put preconditions into the pattern [LLVM-PatternMatch]. Trade-off: patterns get longer; forgetting one is a miscompile.
Commutative and deferred matching (m_c_*, m_Deferred): write one pattern for both operand orders. Trade-off: \(2^c\) tries.
Rust/ML-style pattern matching on algebraic data types in compilers written in those languages (rustc's MIR simplifications, OCaml's Flambda). Trade-off: no need for a template library, but the IR must be a tree of immutable nodes.

External pattern DSLs¶

match.pd features: (for op (plus minus) ...) iterators, :c commutative markers, @@ for "same value", (if ...) preconditions and (with { ... }) C escapes [GCC-matchpd]. Trade-off: escape hatches weaken the "rules are data" property.
ISLE in an e-graph: Cranelift applies its mid-end ISLE rules inside an acyclic e-graph (aegraph), so rules add equivalent forms instead of destructively rewriting, and a cost-based extraction picks the result ([Cranelift-ISLE]; equality saturation in Ch 17). Trade-off: no rule-ordering problems, more memory.
MLIR PDL/PDLL and the greedy pattern rewrite driver: patterns as IR, applied by a worklist driver like Algorithm 13.2.4 [MLIR-Rewrite].
Verified DSLs: Alive's DSL generates InstCombine C++ from proven rules [LMNR15]; ISLE rules have been verified with the Crocus tool (Lesson 13.9).

7. In real compilers¶

Hand-written combiners¶

InstSimplify returns existing values; InstCombine creates new instructions

Reproduce (opt 23.1.2; any OS):

cat > simp.ll <<'EOF'
define i32 @f(i32 %x, i32 %y) {
  %a = sub i32 %x, %x          ; simplifies to an existing value: 0
  %b = or i32 %y, %a           ; then to %y
  %c = mul i32 %b, 8           ; needs a NEW instruction (shl): InstCombine only
  %d = add i32 %c, %c          ; needs a new instruction too
  ret i32 %d
}
EOF
echo "=== instsimplify"; opt -passes=instsimplify -S simp.ll | sed -n '/^define/,/^}/p'
echo "=== instcombine";  opt -passes=instcombine -S simp.ll | sed -n '/^define/,/^}/p'

Output (complete):

=== instsimplify
define i32 @f(i32 %x, i32 %y) {
  %c = mul i32 %y, 8
  %d = add i32 %c, %c
  ret i32 %d
}
=== instcombine
define i32 @f(i32 %x, i32 %y) {
  %d = shl i32 %y, 4
  ret i32 %d
}

What to notice: InstSimplify (Definition 13.2.3) turned sub %x, %x into 0 and or %y, 0 into %y — both existing values — and stopped. InstCombine went on to create new instructions: it turned mul %b, 8 and add %c, %c into the single instruction shl %y, 4.

InstCombine keeps, drops and re-derives flags

Reproduce (opt 23.1.2; any OS):

cat > flags.ll <<'EOF'
define i8 @fold_consts(i8 %x) {
  %a = add nsw i8 %x, 100
  %r = add nsw i8 %a, 100
  ret i8 %r
}
define i8 @fold_consts_small(i8 %x) {
  %a = add nsw i8 %x, 10
  %r = add nsw i8 %a, 20
  ret i8 %r
}
define i8 @self_add(i8 %x) {
  %r = add nsw i8 %x, %x
  ret i8 %r
}
define i8 @mul_min(i8 %x) {
  %r = mul nsw i8 %x, -128
  ret i8 %r
}
EOF
opt -passes=instcombine -S flags.ll | sed -n '/^define/,/^}/p'

Output (complete):

define i8 @fold_consts(i8 %x) {
  %r = add i8 %x, -56
  ret i8 %r
}
define i8 @fold_consts_small(i8 %x) {
  %r = add nsw i8 %x, 30
  ret i8 %r
}
define i8 @self_add(i8 %x) {
  %r = shl nsw i8 %x, 1
  ret i8 %r
}
define i8 @mul_min(i8 %x) {
  %r = shl i8 %x, 7
  ret i8 %r
}

What to notice: exactly the flag functions of rules R9, R10 and R11 of exercise E2: nsw survives x + 10 + 20 but not x + 100 + 100 (the constant sum overflows); add nsw x, x becomes shl nsw x, 1; mul nsw x, -128 becomes shl x, 7 without nsw (Theorem 13.8.13). The source is InstCombinerImpl::visitAdd and visitMul in llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp and InstCombineMulDivRem.cpp (LLVM 23.1.2) [LLVM-InstCombine].

Embedded pattern matchers¶

PatternMatch inside InstCombine's visitAdd

Reproduce (LLVM 23.1.2 sources; curl):

URL=https://raw.githubusercontent.com/llvm/llvm-project/llvmorg-23.1.2/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
curl -sL $URL | grep -B3 -A15 '^  // X + X --> X << 1$'

Output (complete):

  if (Ty->isIntOrIntVectorTy(1))
    return BinaryOperator::CreateXor(LHS, RHS);

  // X + X --> X << 1
  if (LHS == RHS) {
    auto *Shl = BinaryOperator::CreateShl(LHS, ConstantInt::get(Ty, 1));
    Shl->setHasNoSignedWrap(I.hasNoSignedWrap());
    Shl->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
    return Shl;
  }

  Value *A, *B;
  if (match(LHS, m_Neg(m_Value(A)))) {
    // -A + -B --> -(A + B)
    if (match(RHS, m_Neg(m_Value(B))))
      return BinaryOperator::CreateNeg(Builder.CreateAdd(A, B));

    // -A + B --> B - A
    auto *Sub = BinaryOperator::CreateSub(RHS, A);

What to notice: R11 (add-self) in LLVM, with its flag function: Shl copies nsw and nuw from the add. Just before it, add i1 %x, %y becomes xor — so X + X never reaches the shl rewrite at i1, where shl i1 x, 1 would be poison (the bitwidth caveat of Lesson 13.9, and the reason E2 restricts R11 to widths \(\ge 2\)). m_Neg(m_Value(A)) is an embedded pattern (Algorithm 13.2.5), and the -A + B --> B - A rule keeps nsw only when both instructions had it.

External pattern DSLs¶

GCC match.pd: x - x, with the floating-point conditions

Reproduce (GCC 15.1.0 sources via curl; gcc 13.3.0 installed):

curl -sL https://raw.githubusercontent.com/gcc-mirror/gcc/releases/gcc-15.1.0/gcc/match.pd \
  | sed -n '/^\/\* Simplify x - x\./,/{ build_zero_cst (type); }))/p'
cat > g.c <<'EOF'
int    fi(int x)    { return x - x; }
double fd(double x) { return x - x; }
EOF
echo "=== gcc -O2";                     gcc -O2 -c g.c -fdump-tree-original=- -o /dev/null | grep -A2 '^{'
echo "=== gcc -O2 -ffinite-math-only";  gcc -O2 -ffinite-math-only -c g.c -fdump-tree-original=- -o /dev/null | grep -A2 '^{'

Output (complete):

/* Simplify x - x.
   This is unsafe for certain floats even in non-IEEE formats.
   In IEEE, it is unsafe because it does wrong for NaNs.
   PR middle-end/98420: x - x may be -0.0 with FE_DOWNWARD.
   Also note that operand_equal_p is always false if an operand
   is volatile.  */
(simplify
 (minus @0 @0)
 (if (!FLOAT_TYPE_P (type)
      || (!tree_expr_maybe_nan_p (@0)
      && !tree_expr_maybe_infinite_p (@0)
      && (!HONOR_SIGN_DEPENDENT_ROUNDING (type)
          || !HONOR_SIGNED_ZEROS (type))))
  { build_zero_cst (type); }))
=== gcc -O2
{
  return 0;
}
--
{
  return x - x;
}
=== gcc -O2 -ffinite-math-only
{
  return 0;
}
--
{
  return 0.0;
}

What to notice: one (simplify (minus @0 @0) ...) rule serves integers and floating point; the (if ...) precondition is the IEEE reasoning of Proposition 13.1.14 (NaN and infinity make x - x NaN; -0.0 appears under round-downward). genmatch compiles the rule into GENERIC folding, so the integer case is folded while the front end builds the tree (return 0 at -fdump-tree-original), and the double case only when -ffinite-math-only removes NaN and infinity.

Cranelift ISLE: rules and the code they produce

Reproduce (wasmtime 37.0.2 release binary and its sources; objdump 2.42):

curl -sL https://raw.githubusercontent.com/bytecodealliance/wasmtime/v37.0.2/cranelift/codegen/src/opts/arithmetic.isle > arithmetic.isle
grep -A1 '^;; x-x == 0\.' arithmetic.isle
sed -n '/^;; x\*c == x<<log2(c)/,/^(rule (simplify (imul ty (iconst/p' arithmetic.isle
cat > opt.wat <<'EOF'
(module
  (func (export "subself") (param i32) (result i32)
    (i32.sub (local.get 0) (local.get 0)))
  (func (export "mul8") (param i32) (result i32)
    (i32.mul (local.get 0) (i32.const 8))))
EOF
wasmtime compile opt.wat -o opt.cwasm
objdump -d --no-show-raw-insn -M intel opt.cwasm | sed -n '/<wasm\[0\]::function\[[01]\]>:/,/ret/p'

Output (complete):

;; x-x == 0.
(rule (simplify (isub (ty_int ty) x x)) (subsume (iconst_u ty 0)))
;; x*c == x<<log2(c) when c is a power of two.
;;
;; Note that the type of `iconst` must be the same as the type of `imul`,
;; so these rules can only fire in situations where it's safe to construct an
;; `iconst` of that type.
(rule (simplify (imul ty x (iconst _ (imm64_power_of_two c))))
      (ishl ty x (iconst ty (imm64 c))))
(rule (simplify (imul ty (iconst _ (imm64_power_of_two c)) x))
0000000000000000 <wasm[0]::function[0]>:
       0:   push   rbp
       1:   mov    rbp,rsp
       4:   xor    eax,eax
       6:   mov    rsp,rbp
       9:   pop    rbp
       a:   ret
0000000000000020 <wasm[0]::function[1]>:
      20:   push   rbp
      21:   mov    rbp,rsp
      24:   mov    rax,rdx
      27:   shl    eax,0x3
      2a:   mov    rsp,rbp
      2d:   pop    rbp
      2e:   ret

What to notice: ISLE rules are terms with a typed left-hand side ((isub (ty_int ty) x x): integers only, the same precondition as match.pd's !FLOAT_TYPE_P); subsume tells the aegraph to drop the original. Compiling WebAssembly with wasmtime's Cranelift turns x - x into xor eax, eax and x * 8 into shl eax, 3.

GlobalISel's combiner: a TableGen rule, before and after

Reproduce (llc 23.1.2; any OS):

curl -sL https://raw.githubusercontent.com/llvm/llvm-project/llvmorg-23.1.2/llvm/include/llvm/Target/GlobalISel/Combine.td \
  | sed -n '/^def add_sub_reg_frags/,/^  (apply (GIReplaceReg $dst, $src))>;/p'
cat > gisel.ll <<'EOF'
define i32 @f(i32 %a, i32 %x) {
  %t = sub i32 %a, %x
  %r = add i32 %t, %x
  ret i32 %r
}
EOF
for when in before after; do
  echo "=== $when aarch64-prelegalizer-combiner"
  llc -O2 -mtriple=aarch64-linux-gnu -global-isel -stop-$when=aarch64-prelegalizer-combiner gisel.ll -o - | sed -n '/^    %0/,/RET_ReallyLR/p'
done

Output (complete):

def add_sub_reg_frags : GICombinePatFrag<
  (outs root:$dst), (ins $src),
  [
    (pattern (G_ADD $dst, $x, $tmp), (G_SUB $tmp, $src, $x)),
    (pattern (G_ADD $dst, $tmp, $x), (G_SUB $tmp, $src, $x))
  ]>;
def add_sub_reg: GICombineRule <
  (defs root:$dst),
  (match (add_sub_reg_frags $dst, $src)),
  (apply (GIReplaceReg $dst, $src))>;
=== before aarch64-prelegalizer-combiner
    %0:_(i32) = COPY $w0
    %1:_(i32) = COPY $w1
    %2:_(i32) = G_SUB %0, %1
    %3:_(i32) = G_ADD %2, %1
    $w0 = COPY %3(i32)
    RET_ReallyLR implicit $w0
=== after aarch64-prelegalizer-combiner
    %0:_(i32) = COPY $w0
    $w0 = COPY %0(i32)
    RET_ReallyLR implicit $w0

What to notice: add_sub_reg is the rule \((a - x) + x \to a\) as a TableGen pattern fragment with two alternatives (both operand orders of G_ADD), and GIReplaceReg is its replacement. The AArch64 pre-legalizer combiner, generated from Combine.td, removed both instructions: the generic machine IR returns %0 directly.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Hand-written combiner	Unlimited: any C++ (analyses such as KnownBits inside rules)	\(O(m\ell)\) per pop · fast (compiled, hand-ordered)	Rules are code: hard to audit or verify; flag handling by hand	High per rule, lowest infrastructure	LLVM InstCombine, GCC `combine.cc`, `pebble-peephole`
Embedded pattern matcher	Same as its host language, patterns readable	\(O(\ell)\) per pattern · as fast as hand-written	Rules read like math; preconditions still ad hoc	Medium (a template library)	LLVM `PatternMatch`, MLIR C++ patterns
External pattern DSL	Limited to what the DSL expresses (+ escape hatches)	Decision tree \(O(d)\) · compiled: fast; interpreted: slower (lab: 75–95 vs 25–40 ms)	Rules are data: can be verified (Alive, Crocus), listed, counted	High infrastructure, lowest per rule	GCC `match.pd`, Cranelift ISLE, GlobalISel combiner, `pebble-peephole-dsl`

Comparison-lab results (reproduce with uv run python labs/ch13-peephole/measure.py --build build/<preset> after Parts A–C; reference solutions): both engines agree on every function of the corpus (tests/ch13/lab/compare.test); 1 355 rule applications on synthetic.ll (4 824 → 4 185 instructions) and 60 of 70 instructions left in programs.ll; 286 source lines for the hand-written engine vs 403 for the DSL engine including its parser and interpreter (the 29 rules themselves are 29 lines of DSL).

Choose a hand-written combiner when rules need analyses (known bits, dominance) or complex flag reasoning, and you accept that each rule is code to review and test. Choose an embedded matcher in any hand-written combiner, always: it removes the boilerplate without changing the architecture. Choose an external DSL when the rule set is large, when you want to generate matchers for several IRs (GENERIC and GIMPLE) or to verify, count and document rules as data; budget for the generator.

9. Assessment¶

Technique	Quiz questions	Drills	Flashcards	Exercises
Hand-written combiners	`peephole-trace`, `instsimplify-contract`	`./course drill rewrite-validity`, `./course drill flags` (Ch 9)	tag `hand-written-combiner`	E2 (`pebble-peephole`)
Embedded pattern matchers	`pattern-match-bind`, `find-patternmatch`	`./course drill pattern-match` (Ch 10)	tag `pattern-matcher`	E2
External pattern DSLs	`dsl-decision-tree`, `matchpd-fp`	`./course drill rewrite-validity`	tag `pattern-dsl`	Lab Part A (`pebble-peephole-dsl`), Part D

References¶

See the chapter references.

Lesson 13.2 — Peephole engines: hand-written combiners and pattern DSLs¶

1. Problem and motivation¶

Hand-written combiners¶

Embedded pattern matchers¶

External pattern DSLs¶

2. Definitions and algorithms¶

Hand-written combiners¶

Embedded pattern matchers¶

External pattern DSLs¶

3. Worked example¶

Hand-written combiners¶

Embedded pattern matchers¶

External pattern DSLs¶

4. Invariants and correctness¶

Hand-written combiners¶

Embedded pattern matchers¶

External pattern DSLs¶

5. Complexity¶

6. Variants and refinements¶

Hand-written combiners¶

Embedded pattern matchers¶

External pattern DSLs¶

7. In real compilers¶

Hand-written combiners¶

Embedded pattern matchers¶

External pattern DSLs¶

8. Comparison¶

9. Assessment¶

References¶