Lesson 10.5 — Pattern matching on IR: hand-written, PatternMatch, and rule DSLs¶

Techniques: hand-written matching (casts and operand checks), llvm::PatternMatch combinators (m_Add, m_Value, m_Specific, m_Deferred, m_ConstantInt, m_c_*, m_OneUse, …), declarative rule DSLs (GlobalISel's TableGen combiner rules, GCC's match.pd, Cranelift's ISLE) · Pebble uses: PatternMatch in its peephole passes (Ch 13) · Lab: Lab 10.3 (raw casts vs InstVisitor vs PatternMatch) · Prerequisites: Lesson 10.4 · Time: 3 hours

"Is %c of the form (Y - X) + X?" Answering it by hand means: dyn_cast<BinaryOperator>, check the opcode, look at operand 0, dyn_cast again, check its opcode, compare its operand 1 with %c's operand 1, and then do it all again with the operands swapped, because addition commutes. PatternMatch writes it as

match(C, m_c_Add(m_Sub(m_Value(Y), m_Value(X)), m_Deferred(X)))

and a rule DSL writes it as a line of declarative text that a generator turns into matching code. This lesson defines what match means precisely, proves when it is right, shows a case where it is incomplete, and compares the three approaches.

1. Problem and motivation¶

Peephole optimizers (Ch 13) consist of hundreds of rules of the form "if the IR around this instruction looks like $\ell$ (and a side condition holds), replace it with $r$". Recognizing $\ell$ is the bulk of the code, and it is where bugs hide: a forgotten operand order, a missing type check, a matched value with extra uses. The history of the field is a move from hand-written matchers to embedded combinators to external DSLs that generate matchers [LLVM-PatternMatch, GCC-matchpd, ISLE].

Hand-written matching¶

Casts, opcode tests and operand comparisons written directly. This is the most flexible approach and is still common in LLVM's older passes (Reassociate, parts of InstCombine), but it is verbose and easy to get wrong in the commuted case. It is Lab 10.3's Style::RawCasts.

PatternMatch combinators¶

llvm/IR/PatternMatch.h embeds a pattern language in C++ templates. Each m_* function returns a small matcher object with a match(Value *) method, and composing them builds the pattern. Binding (m_Value(X)), equality (m_Specific, m_Deferred), constants (m_ConstantInt, m_APInt, m_Power2), commutativity (m_c_Add) and use-count conditions (m_OneUse) are all first class. InstCombine and InstSimplify are written almost entirely in it [LLVM-PatternMatch, LLVM-ICGuide].

Declarative rule DSLs¶

When the rule set grows into the thousands, rules move out of C++ into a DSL, and a generator produces the matching code, often as a decision tree shared among rules:

GCC's match.pd, compiled by genmatch into both GENERIC and GIMPLE simplifiers [GCC-matchpd];
LLVM GlobalISel's combiner rules in TableGen (GICombineRule with MIR patterns) [LLVM-MIRPatterns];
Cranelift's ISLE term-rewriting language for lowering and mid-end rules [ISLE].

2. Definitions and algorithms¶

Definition 10.5.1 (Pattern language)

Patterns over LLVM values:

\[ P ::= \mathsf{Value}(x) \mid \mathsf{Specific}(v) \mid \mathsf{Deferred}(x) \mid \mathsf{ConstantInt}(c) \mid \mathsf{Const}_{\pi} \mid \mathsf{Bin}_{o}(P, P) \mid \mathsf{cBin}_{o}(P, P) \mid \mathsf{OneUse}(P) \]

$x, c$ are pattern variables.
$v$ is a fixed value.
$\pi$ is a predicate on constants: $\mathsf{Power2}$, $\mathsf{AllOnes}$ or $\mathsf{Zero}$.
$o$ is an opcode.

m_Not(P) abbreviates $\mathsf{cBin}_{\mathit{xor}}(\mathsf{Const}_{\mathsf{AllOnes}}, P)$, and m_Neg(P) abbreviates $\mathsf{Bin}_{\mathit{sub}}(\mathsf{Const}_{\mathsf{Zero}}, P)$ (PatternMatch.h, LLVM 23). A pattern is linear if no variable is bound by two $\mathsf{Value}$ occurrences, and deferred-closed if every $\mathsf{Deferred}(x)$ comes after (in left-to-right order) a $\mathsf{Value}(x)$ that binds $x$.

Definition 10.5.2 (Instance)

A value $v$ is an instance of $P$ under an assignment $\rho$ (variables to values) if:

$P = \mathsf{Value}(x)$: $\rho(x) = v$.
$P = \mathsf{Specific}(w)$: $v = w$.
$P = \mathsf{Deferred}(x)$: $v = \rho(x)$.
$P = \mathsf{ConstantInt}(c)$: $v$ is an integer constant and $\rho(c) = \mathrm{zext}(v)$.
$P = \mathsf{Const}_\pi$: $v$ is a constant satisfying $\pi$.
$P = \mathsf{Bin}_o(P_1, P_2)$: $v$ is an instruction with opcode $o$ and operands $v_0, v_1$, where $v_0$ is an instance of $P_1$ and $v_1$ an instance of $P_2$ under $\rho$.
$P = \mathsf{cBin}_o(P_1, P_2)$: as $\mathsf{Bin}_o$, or with the operands swapped.
$P = \mathsf{OneUse}(P')$: $v$ has exactly one use and is an instance of $P'$.

Algorithm 10.5.3 (PatternMatch's matcher)

Input: a pattern $P$, a value $v$, an environment $\rho$ (mutable).
Output: true or false; $\rho$ updated.
Precondition: $P$ is deferred-closed.
Postcondition: Theorem 10.5.6 (soundness) and Theorem 10.5.7 (completeness under restrictions).
Invariant: bindings are written in left-to-right order and never undone (a failed attempt may leave bindings behind).

function Match(P, v, ρ):
    case P of
        Value(x):        ρ[x] ← v; return true
        Specific(w):     return v = w
        Deferred(x):     return v = ρ[x]
        ConstantInt(c):  if v is a ConstantInt: ρ[c] ← zext(v); return true
                         return false
        Const_π:         return v is a constant satisfying π
        OneUse(P'):      return hasOneUse(v) ∧ Match(P', v, ρ)
        Bin_o(P1, P2):   return IsOp(v, o) ∧ Match(P1, op0(v), ρ) ∧ Match(P2, op1(v), ρ)
        cBin_o(P1, P2):  if not IsOp(v, o): return false
                         if Match(P1, op0(v), ρ) ∧ Match(P2, op1(v), ρ): return true
                         return Match(P1, op1(v), ρ) ∧ Match(P2, op0(v), ρ)

This is BinaryOp_match<LHS, RHS, Opcode, Commutable>::match in llvm/include/llvm/IR/PatternMatch.h: (L.match(Op0) && R.match(Op1)) || (Commutable && L.match(Op1) && R.match(Op0)). The drill pattern-match implements exactly this algorithm and is checked against real LLVM on 360 cases (tests/ch10/unit/OracleCrossCheckTest.cpp).

Hand-written matching¶

Algorithm 10.5.4 (Hand-written recognizer for (Y − X) + X, either order)

Input: a value $v$.
Output: $Y$ if $v$ is add (sub Y, X), X or add X, (sub Y, X), else nothing.
Precondition: none.
Postcondition: the returned $Y$ satisfies $v = (Y - X) + X$ as IR structure.
Invariant: each operand order is tried independently.

function MatchAddSubCancel(v):
    a ← dyn_cast<BinaryOperator>(v)
    if a = null or opcode(a) ≠ add: return nothing
    for (s, other) in [(op0(a), op1(a)), (op1(a), op0(a))]:
        b ← dyn_cast<BinaryOperator>(s)
        if b ≠ null and opcode(b) = sub and op1(b) = other:
            return op0(b)
    return nothing

How much of LLVM is hand-written vs PatternMatch?

Reproduce (LLVM source at llvmorg-23.1.2; curl and grep count lines containing each token):

for f in Transforms/InstCombine/InstCombineAddSub.cpp Transforms/Scalar/Reassociate.cpp; do
  curl -s https://raw.githubusercontent.com/llvm/llvm-project/llvmorg-23.1.2/llvm/lib/$f -o x.cpp
  echo "$f: $(grep -c 'match(' x.cpp) lines with match(, $(grep -c 'dyn_cast<' x.cpp) with dyn_cast<, $(grep -c 'getOpcode()' x.cpp) with getOpcode()"
done

Output (complete):

Transforms/InstCombine/InstCombineAddSub.cpp: 257 lines with match(, 26 with dyn_cast<, 20 with getOpcode()
Transforms/Scalar/Reassociate.cpp: 35 lines with match(, 36 with dyn_cast<, 42 with getOpcode()

What to notice: InstCombine's add/sub combines are overwhelmingly PatternMatch (257 match( lines against 46 hand-written tests). Reassociate, which manipulates expression trees rather than recognizing fixed shapes, is mostly hand-written (78 against 35). Both styles are alive, each where it fits.

PatternMatch combinators¶

PatternMatch on a small function, and what InstCombine does with the same shapes

Reproduce (clang 23.1.2, LLVM 23.1.2, Linux x86-64):

cd chapters/10-llvm-cpp-api/examples
clang++-23 $(llvm-config --cxxflags) -std=c++23 pm.cpp $(llvm-config --ldflags --libs) \
  -Wl,-rpath,$(llvm-config --libdir) -o pm && ./pm
opt -passes=instcombine -S ic.ll

Output (complete for ./pm; the opt output's module header and attribute lines are cut):

n1: m_Not(A=x) m_Xor(A, -1)
n2: m_Not(A=y)
m: m_Mul(A=x, 2^3)
s: m_c_Add(A=y, mul(B=x, _))
c:
mx: select(icmp sgt A, B), A, B)
mn:

define i32 @f(i32 %x, i32 %y) {
  %m = shl i32 %x, 3
  %n = xor i32 %y, -1
  %s = add i32 %m, %n
  %mx = call i32 @llvm.smax.i32(i32 %s, i32 %y)
  ret i32 %mx
}

What to notice:

m_Not matched both xor %x, -1 and xor -1, %y (it is commutative), while m_Xor(m_Value(A), m_AllOnes()) matched only the canonical order.
m_c_Add bound A = %y for add %y, %m: the first attempt failed and the swap succeeded (Algorithm 10.5.3).
m_Select(m_ICmp(P, A, B), m_Deferred(A), m_Deferred(B)) matched %mx but not %mn, whose arms are swapped.
m_SMax matched nothing: in LLVM 23 it matches only the llvm.smax intrinsic, and InstCombine canonicalizes the select form into that intrinsic (second listing).
InstCombine also canonicalized xor -1, %y to xor %y, -1 (constants on the right) and mul %x, 8 to shl %x, 3. Canonical forms are what make non-commutative matchers sufficient most of the time.

Declarative rule DSLs¶

Definition 10.5.5 (Rewrite rule, rule set, rewriting)

A rewrite rule is a triple $\ell \xrightarrow{\ \theta\ } r$ of a pattern $\ell$, a side condition $\theta$ on the bindings, and a replacement template $r$ whose variables are among $\ell$'s. A rule set $\mathcal{R}$ rewrites $v$ to $r\rho$ when $v$ is an instance of $\ell$ under $\rho$ (Definition 10.5.2) and $\theta(\rho)$ holds. A combiner applies rules until no rule applies (a normal form) or a limit is hit. A generator (genmatch, llvm-tblgen -gen-global-isel-combiner, islec) compiles $\mathcal{R}$ into a matching automaton, usually a decision tree on opcodes and operand kinds shared by all rules.

Rules as data: GlobalISel's TableGen combiner and GCC's match.pd

Reproduce (LLVM at llvmorg-23.1.2, GCC at releases/gcc-15.2.0; curl and grep):

curl -s https://raw.githubusercontent.com/llvm/llvm-project/llvmorg-23.1.2/llvm/include/llvm/Target/GlobalISel/Combine.td \
  | grep -n "Transform (add x, (sub y, x)) -> y" -A 11
curl -s https://raw.githubusercontent.com/gcc-mirror/gcc/releases/gcc-15.2.0/gcc/match.pd -o match.pd
echo "$(grep -c '(simplify' match.pd) lines with (simplify"; grep -n "X \* 1, X / 1 -> X" -A4 match.pd

Output (complete):

1715:// Transform (add x, (sub y, x)) -> y
1716-// Transform (add (sub y, x), x) -> y
1717-def add_sub_reg_frags : GICombinePatFrag<
1718-  (outs root:$dst), (ins $src),
1719-  [
1720-    (pattern (G_ADD $dst, $x, $tmp), (G_SUB $tmp, $src, $x)),
1721-    (pattern (G_ADD $dst, $tmp, $x), (G_SUB $tmp, $src, $x))
1722-  ]>;
1723-def add_sub_reg: GICombineRule <
1724-  (defs root:$dst),
1725-  (match (add_sub_reg_frags $dst, $src)),
1726-  (apply (GIReplaceReg $dst, $src))>;
834 lines with (simplify
495:/* X * 1, X / 1 -> X.  */
496-(for op (mult trunc_div ceil_div floor_div round_div exact_div)
497-  (simplify
498-    (op @0 integer_onep)
499-    (non_lvalue @0)))

What to notice: the GlobalISel rule is Algorithm 10.5.4 as data. The two patterns are the two operand orders (a fragment with alternatives instead of a commutative flag), the repeated $x is m_Deferred, and apply is the replacement $r$. GCC states one rule for six opcodes with for and uses predicates (integer_onep) for the constant tests. GCC 15's match.pd has 834 simplify forms, and genmatch turns them into a decision tree.

3. Worked example¶

The instruction is %t = add i32 %m, %b with %m = mul i32 %a, %b, and the pattern is $P = \mathsf{cBin}_{\mathit{add}}(\mathsf{cBin}_{\mathit{mul}}(\mathsf{Value}(X), \mathsf{Value}(Y)), \mathsf{Deferred}(X))$, "an add of a product and one of its factors". It has an instance: $X = \%b$, $Y = \%a$.

PatternMatch combinators¶

Algorithm 10.5.3 step by step:

step	matcher	on	ρ after	result
1	outer `m_c_Add`: opcode add?	`%t`	{}	yes
2	attempt 1, L = `m_c_Mul(X, Y)` on op0	`%m`
3	inner attempt 1: `Value(X)` on `%a`, `Value(Y)` on `%b`		{X=%a, Y=%b}	inner match
4	R = `Deferred(X)` on op1	`%b`		`%b` ≠ `%a`: fail
5	attempt 2, L = `m_c_Mul(X, Y)` on op1	`%b`	{X=%a, Y=%b} (stale)	`%b` is an argument, not a mul: fail
6	outer result		{X=%a, Y=%b}	no match

Step 3 committed to the first operand order of the inner product. When step 4 failed, the outer matcher retried only its own operands (step 5) and never the inner product's swapped order ($X = \%b$). The real-world box of §4 shows LLVM returning "no match" on this input. Writing the pattern as $\mathsf{cBin}_{\mathit{add}}(\mathsf{cBin}_{\mathit{mul}}(\mathsf{Value}(Y), \mathsf{Value}(X)), \mathsf{Deferred}(X))$ happens to work here, because $X$ is then bound to the second factor first.

Hand-written matching¶

Algorithm 10.5.4, generalized to "add of a product and one of its factors", would loop over both operand orders of the add and both factors of the product explicitly: four combinations, checked one by one. The first successful combination is (mul in op0, factor %b = op1 of the mul), which gives $X = \%b$. Hand-written code can express the full search, but only because the programmer spelled it out.

Declarative rule DSLs¶

In a GlobalISel GICombinePatFrag you would list the alternatives explicitly. The fragment for "add of a product and a factor" needs four patterns (two orders of the add times two positions of the factor). The generator then builds one decision tree that tests the opcode once and the operand positions for all four alternatives: the complete search, stated declaratively.

Try it

./course drill pattern-match --seed 7 --difficulty hard gives a pattern with m_c_/m_Deferred/m_OneUse; --solution prints the matcher trace.

4. Invariants and correctness¶

PatternMatch combinators¶

Theorem 10.5.6 (Soundness of the matcher)

If Match(P, v, ρ) returns true, then $v$ is an instance of $P$ under the final $\rho$ (Definition 10.5.2), provided $P$ is linear and deferred-closed.

Proof

By structural induction on $P$, with the stronger hypothesis "the bindings of the successful attempt are the last writes to each of $P$'s variables". Leaves: $\mathsf{Value}(x)$ writes $\rho[x] = v$. $\mathsf{Specific}$, $\mathsf{Deferred}$ and $\mathsf{Const}_\pi$ check exactly the instance condition. $\mathsf{ConstantInt}$ writes the zero-extended value. $\mathsf{OneUse}(P')$: the use check plus the induction hypothesis for $P'$. $\mathsf{Bin}_o(P_1, P_2)$: the opcode check and two successful sub-matches on the operands. By the hypothesis each operand is an instance under the bindings its sub-match wrote last, and by linearity the two sub-patterns write disjoint variables, so neither overwrites the other's bindings. $\mathsf{cBin}_o$: if the first attempt succeeds, as for $\mathsf{Bin}_o$. If it fails, the second attempt re-runs both sub-matches, which rewrite every variable of $P_1$ and $P_2$ that they bind on success (each $\mathsf{Value}$ in a successful sub-match executes). So the stale bindings of the failed attempt are overwritten, and the result is an instance with the operands swapped.

Without linearity, m_Add(m_Value(X), m_Value(X)) would succeed on add %a, %b with $X = \%b$, which is not an instance. That is why "same operand twice" must be written with m_Deferred.

Theorem 10.5.7 (Completeness needs choice-independent deferred references)

Call an occurrence of $\mathsf{Deferred}(x)$ in $P$ choice-independent if every $\mathsf{cBin}$ node that lies above the $\mathsf{Value}(x)$ binding $x$ also lies above that $\mathsf{Deferred}(x)$. If $P$ is linear and deferred-closed, every $\mathsf{Deferred}$ occurrence in $P$ is choice-independent, and $v$ is an instance of $P$ under some $\rho^\ast$, then Match(P, v, {}) returns true. Without the condition, completeness fails, even when $P$ has a single commutative node.

Proof

Write $\mathrm{vars}(Q)$ for the variables bound by $\mathsf{Value}$ nodes of a sub-pattern $Q$. We prove, by structural induction on $Q$, the stronger claim: for every value $u$ and environment $\rho$, if $u$ is an instance of $Q$ under some $\rho'$ that agrees with $\rho$ outside $\mathrm{vars}(Q)$, then Match(Q, u, ρ) returns true, and it leaves $\rho$ unchanged outside $\mathrm{vars}(Q)$. The theorem is the case $Q = P$, $\rho = \{\}$: by deferred-closedness $P$ reads no variable outside $\mathrm{vars}(P)$.

Leaves. $\mathsf{Value}$, $\mathsf{Specific}$, $\mathsf{ConstantInt}$ and $\mathsf{Const}_\pi$ test exactly the instance condition. $\mathsf{Deferred}(x)$ binds nothing, so $x \notin \mathrm{vars}(Q)$ and $\rho(x) = \rho'(x)$. $\mathsf{OneUse}(Q')$ adds the use test to the induction hypothesis.

$\mathsf{Bin}_o(Q_1, Q_2)$. By deferred-closedness, $Q_1$ reads no variable of $Q_2$, so $\mathrm{op}_0(u)$ is an instance of $Q_1$ under $\rho$ updated with $\rho'$ on $\mathrm{vars}(Q_1)$, and the hypothesis for $Q_1$ gives a successful match that leaves an environment $\rho_1$. Now $Q_2$ may read three kinds of variable: its own, which the hypothesis for $Q_2$ lets range freely; those outside $Q$, where $\rho_1 = \rho = \rho'$; and some $x \in \mathrm{vars}(Q_1)$. For such an $x$, the $\mathsf{Deferred}(x)$ lies outside $Q_1$, so by choice-independence no $\mathsf{cBin}$ inside $Q_1$ lies above $\mathsf{Value}(x)$. The path from $Q_1$'s root to $\mathsf{Value}(x)$ then consists of $\mathsf{Bin}$ and $\mathsf{OneUse}$ nodes, each of which passes a fixed operand down, so any successful match and any instance both bind $x$ to the same operand of $u$: $\rho_1(x) = \rho'(x)$. Hence $\mathrm{op}_1(u)$ is an instance of $Q_2$ under $\rho_1$ updated with $\rho'$ on $\mathrm{vars}(Q_2)$, and the hypothesis for $Q_2$ makes the second sub-match succeed.

$\mathsf{cBin}_o(Q_1, Q_2)$. Each attempt is the $\mathsf{Bin}$ case on one operand order (the condition holds inside $Q_1$ and $Q_2$, since a $\mathsf{cBin}$ above both is irrelevant to it). $u$ is an instance in at least one order. If the first attempt fails, the instance uses the swapped order, and the second attempt succeeds by the $\mathsf{Bin}$ argument. The stale bindings the failed attempt left behind are all in $\mathrm{vars}(Q)$, where the claim puts no requirement on $\rho$, and deferred-closedness means the second attempt rebinds each of them before reading it.

Failure without the condition. In m_Add(m_c_Mul(m_Value(X), m_Value(Y)), m_Deferred(X)) the only commutative node lies above $\mathsf{Value}(X)$ but not above $\mathsf{Deferred}(X)$. On add (mul %a, %b), %b, an instance with $X = \%b$, $Y = \%a$, the inner matcher succeeds on its first order with $X = \%a$, the deferred test fails, and nothing retries the inner choice: LLVM 23.1.2 returns false. The worked example is the same failure one level down, under a commutative add.

Nested commutative matchers do not backtrack

Reproduce (clang 23.1.2, LLVM 23.1.2, Linux x86-64):

cd chapters/10-llvm-cpp-api/examples
clang++-23 $(llvm-config --cxxflags) -std=c++23 incomplete.cpp $(llvm-config --ldflags --libs) \
  -Wl,-rpath,$(llvm-config --libdir) -o incomplete && ./incomplete

Output (complete):

m_c_Add(m_c_Mul(X, Y), m_Deferred(X)) on %r = add (mul %a, %b), %b: no match
m_c_Add(m_c_Mul(Y, X), m_Deferred(X)) on the same instruction:     match with X = b

What to notice: the counterexample of Theorem 10.5.7 on real LLVM. InstCombine avoids the problem by relying on canonical operand order (complexity-based ranking puts constants and "simpler" operands on the right), and sometimes by writing both variants of a pattern.

Hand-written matching¶

Hand-written matchers are correct exactly when the programmer enumerates every alternative the rule intends. There is no general theorem, only the per-matcher obligation, which Algorithm 10.5.4 discharges by looping over both operand orders. The Lab 10.3 tests catch the typical omission (the commuted add-sub-cancel) with 600 planted functions.

Declarative rule DSLs¶

Theorem 10.5.8 (Termination of a rule set by a decreasing measure)

Let $\mu$ map IR functions to a well-founded order (for example, $(\#\text{instructions}, \text{a canonical-form ranking})$ compared lexicographically). If every application of every rule in $\mathcal{R}$ strictly decreases $\mu$, then every rewriting sequence terminates.

Proof

An infinite rewriting sequence $F_0 \to F_1 \to \cdots$ would give an infinite strictly decreasing chain $\mu(F_0) > \mu(F_1) > \cdots$, contradicting well-foundedness.

When it breaks: two canonicalizations that undo each other ($A \to B$ in one rule, $B \to A$ in another) violate the hypothesis. InstCombine has had such infinite loops, which is why its driver caps the number of iterations (InstCombineOptions::MaxIterations in llvm/include/llvm/Transforms/InstCombine/InstCombine.h, default 1 in LLVM 23, with an optional fixpoint verification) and why its contributor guide insists on one canonical form per pattern [LLVM-ICGuide]. Theorem 10.5.8 gives termination only. Confluence (the same normal form regardless of rule order) is a separate property that rule sets generally lack. Equality saturation (Ch 17) sidesteps it by keeping all forms.

5. Complexity¶

Variables: $\lvert P \rvert$ = number of pattern nodes, $k$ = number of $\mathsf{cBin}$ nodes on the deepest root-to-leaf path, $n$ = number of rules.

Technique	Match time (worst)	Match time (typical)	Code size	Notes
Hand-written	whatever the code does; the full search over $k$ nested commutative nodes is $O(2^{k} \lvert P \rvert)$	$O(\lvert P \rvert)$	largest	complete if written so
PatternMatch	$O(2^{k} \lvert P \rvert)$ (Proposition 10.5.9)	$O(\lvert P \rvert)$: most nodes fail on the opcode test	small; templates inline	incomplete when an `m_Deferred` depends on an inner `m_c_` choice
Rule DSL	$O(\text{depth of the decision tree})$ per value to find candidate rules, plus side conditions	near-linear in $\lvert P \rvert$, shared across $n$ rules	generated	the generator's job

Proposition 10.5.9 (Cost of Algorithm 10.5.3)

Let $T(P)$ be the worst-case number of matcher calls. Then $T(\mathsf{leaf}) = 1$, $T(\mathsf{Bin}(P_1, P_2)) \le 1 + T(P_1) + T(P_2)$ and $T(\mathsf{cBin}(P_1, P_2)) \le 1 + 2(T(P_1) + T(P_2))$. Hence $T(P) \le 2^{k} \lvert P \rvert$ when every root-to-leaf path passes through at most $k$ commutative nodes.

Proof

The recurrences count one call for the node itself plus the calls of each attempt; a commutative node makes at most two attempts. Unfolding, each leaf is visited at most $2^{j}$ times, where $j \le k$ is the number of commutative nodes above it. Summing over the at most $\lvert P \rvert$ nodes (inner nodes are bounded the same way) gives $T(P) \le 2^{k} \lvert P \rvert$.

Pathological input. $k$ is small in practice ($\le 3$), so matching is effectively linear. The real cost is running many patterns one after another on the same instruction. Lab 10.3's PatternMatch style tries up to nine patterns per instruction, each starting with an opcode test, and measured 11.5 ms against 2.3 ms for the raw-cast style, which switches on the opcode once (ch10-apibench, 2 000 rounds). A decision tree (a DSL generator's output, or a switch before the match calls) removes that overhead.

Hand-written matching¶

switch on the opcode, then specific checks: the structure InstVisitor automates (Lesson 10.4).
Helper predicates (isKnownNonZero, computeKnownBits) as side conditions, shared with PatternMatch code.

PatternMatch combinators¶

m_Deferred vs m_Specific: m_Specific(V) captures the pointer when the pattern is constructed (before matching), so it cannot refer to a value bound earlier in the same pattern. m_Deferred(X) reads X at match time.
m_OneUse, m_OneUse(m_Value()): a profitability guard. Rewriting a value that has other users duplicates work.
Flag-aware matchers (m_NSWAdd, m_NUWShl, m_Exact): match only when the poison-generating flag is present (Ch 13).
Splat-aware constant matchers: m_APInt and m_Power2 also accept vector splat constants, so one pattern covers scalars and vectors.

Declarative rule DSLs¶

Alive2-verified rules: DSL rules are data, so a tool can check each rule for refinement (Ch 13).
ISLE's extractors and constructors: patterns call Rust functions, and overlapping rules (allowed by design) are ordered by explicit priorities [ISLE].
GCC match.pd for and with blocks: one rule instantiated over several opcodes, with local C++ computations [GCC-matchpd].

7. In real compilers¶

Hand-written matching¶

LLVM

llvm/lib/Transforms/Scalar/Reassociate.cpp (isReassociableOp, LinearizeExprTree: expression trees built with dyn_cast<BinaryOperator> and opcode tests) [LLVM-Reassociate].

GCC RTL's instruction combiner (gcc/combine.cc, releases/gcc-15.2.0) is hand-written switch-and-test code over RTL codes.

PatternMatch combinators¶

LLVM

llvm/include/llvm/IR/PatternMatch.h: match, BinaryOp_match (the Commutable template parameter), bind_ty (m_Value), deferredval_ty (m_Deferred), specificval_ty (m_Specific), m_Not, m_Neg, and m_SMax, which in LLVM 23 matches the intrinsic only. Users: llvm/lib/Analysis/InstructionSimplify.cpp, llvm/lib/Transforms/InstCombine/* [LLVM-PatternMatch].

MLIR has its own matchers (mlir/include/mlir/IR/Matchers.h: m_Constant, m_Op<…>) in the same spirit.

Find where LLVM does it. In PatternMatch.h, find struct BinaryOp_match and read its match method. Question: in which order are the two operand assignments tried for a commutative matcher, and are bindings from the failed first attempt reset? (Quiz llvm-where-binaryop-match.)

Declarative rule DSLs¶

LLVM GlobalISel

llvm/include/llvm/Target/GlobalISel/Combine.td (GICombineRule, GICombinePatFrag, GIReplaceReg), documented in llvm/docs/GlobalISel/MIRPatterns.rst [LLVM-MIRPatterns].

GCC gcc/match.pd and the generator gcc/genmatch.cc (releases/gcc-15.2.0) [GCC-matchpd].
Cranelift cranelift/codegen/src/opts/*.isle (mid-end rewrites) and cranelift/isle/ (the language), Wasmtime v37.0.2 [ISLE].

8. Comparison¶

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Hand-written	anything, including searches the others cannot express	fastest when structured as a switch (2.3 ms in Lab 10.3)	commuted cases are easy to forget	high; verbose	expression-tree passes (Reassociate), one-off checks
PatternMatch	sound (Theorem 10.5.6); complete when no `m_Deferred` depends on an inner `m_c_` choice (Theorem 10.5.7)	$O(\lvert P \rvert)$ per pattern, but patterns run one after another (11.5 ms in Lab 10.3)	compile errors are template-heavy; patterns read like the math	low per rule	InstCombine, InstSimplify, most modern LLVM peepholes
Rule DSL	declarative; alternatives explicit; verifiable as data	decision tree shared by all rules	the generator checks well-formedness (and, in ISLE, overlaps)	a generator to build and maintain	GlobalISel combiners, GCC `match.pd`, Cranelift ISLE

Choose hand-written code for tree-shaped algorithms and when you need a full search. Choose PatternMatch for peepholes on canonical IR: every LLVM reviewer expects it, and the code is the rule. Choose a DSL when rules number in the hundreds or thousands, when you want to verify rules mechanically, or when the matcher's performance matters enough to generate a decision tree.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch10.yaml`)	Drill	Flashcard tag	Exercises
Hand-written	`handwritten-commuted`, `dsl-alternatives`	`./course drill pattern-match` (reason about the same shapes)	`handwritten-match`	Lab 10.3 R1
PatternMatch	`pm-bindings`, `pm-nested-incomplete`, `llvm-where-binaryop-match`	`./course drill pattern-match`	`patternmatch`	Lab 10.3 R3
Rule DSL	`dsl-termination`, `dsl-alternatives`, `dsl-rewrite-trace`	`./course drill pattern-match --difficulty hard` (a rule = a pattern + a replacement)	`rule-dsl`	Lab 10.3 ★ (a rule table)

Pitfall

m_Add(m_Value(X), m_Value(X)) does not mean "the same value twice". The second m_Value(X) simply overwrites the first binding, so it matches every add. Use m_Add(m_Value(X), m_Deferred(X)). Also remember m_Specific(X) reads X when the pattern object is built, which is before X has been bound.

References¶

See the chapter references.

Technique	Match time (worst)	Match time (typical)	Code size	Notes
Hand-written	whatever the code does; the full search over \(k\) nested commutative nodes is \(O(2^{k} \lvert P \rvert)\)	\(O(\lvert P \rvert)\)	largest	complete if written so
PatternMatch	\(O(2^{k} \lvert P \rvert)\) (Proposition 10.5.9)	\(O(\lvert P \rvert)\): most nodes fail on the opcode test	small; templates inline	incomplete when an `m_Deferred` depends on an inner `m_c_` choice
Rule DSL	\(O(\text{depth of the decision tree})\) per value to find candidate rules, plus side conditions	near-linear in \(\lvert P \rvert\), shared across \(n\) rules	generated	the generator's job

Lesson 10.5 — Pattern matching on IR: hand-written, PatternMatch, and rule DSLs¶

1. Problem and motivation¶

Hand-written matching¶

PatternMatch combinators¶

Declarative rule DSLs¶

2. Definitions and algorithms¶

Hand-written matching¶

PatternMatch combinators¶

Declarative rule DSLs¶

3. Worked example¶

PatternMatch combinators¶

Hand-written matching¶

Declarative rule DSLs¶

4. Invariants and correctness¶

PatternMatch combinators¶

Hand-written matching¶

Declarative rule DSLs¶

5. Complexity¶

6. Variants and refinements¶

Hand-written matching¶

PatternMatch combinators¶

Declarative rule DSLs¶

7. In real compilers¶

Hand-written matching¶

PatternMatch combinators¶

Declarative rule DSLs¶

8. Comparison¶

9. Assessment¶

References¶