WorksComputer Science
MetaphIR: Corpus-Scale Applicability Analysis for LLVM Peephole Optimizations
Abstract
Peephole optimizations replace short source instruction sequences with more efficient equivalents, typically guarded by preconditions such as requiring a constant operand to be a power of two. Since every new rewrite adds maintenance burden and compile-time cost, compiler developers need to know how often real-world programs both match the source pattern and satisfy its preconditions before committing to an implementation. Existing workflows fall short: structural search over an intermediate representation (IR) corpus of 4.8 million functions ignores preconditions and therefore overcounts, whereas implementing the rewrite and recompiling the corpus yields exact counts only after paying the engineering cost, with each run of the corpus's on-demand recompilation pipeline taking a median of 47 minutes. This delay is especially limiting when generalizing a rewrite, as developers often iterate over multiple variants to trade off coverage against complexity. We introduce MetaphIR, a system pairing a domain-specific language for expressing LLVM peephole optimizations with an indexed search engine over large IR corpora. Using a syntax modeled on LLVM's C++ matchers, MetaphIR patterns augment LLVM IR with holes and Boolean preconditions over matched values. To answer queries at interactive speed, MetaphIR builds compact per-function summaries ahead of time and uses abstract interpretation over those summaries to soundly filter out functions that cannot satisfy a query's constraints. Across twenty recent peephole optimizations from LLVM's InstCombine pass, MetaphIR recovers the exact set of functions where each rewrite applies in isolation, achieving 100% precision and recall. Queries complete in a median of 1.27 seconds—a 22x speedup over a full corpus scan—enabling developers to quickly gauge an optimization's reach and generality prior to implementation.
CCS Concepts: • Software and its engineering → Compilers; Domain specific languages; • Theory of computation → Program analysis.
Additional Key Words and Phrases: LLVM, compiler optimization, domain-specific language, abstract interpretation, code search, pattern matching
Introduction
Peephole optimizations replace short instruction sequences with more efficient ones [11]. In LLVM [5], most of these optimizations are implemented in the InstCombine pass [19], which encodes thousands of them in C++ as rewrites. A rewrite pre ⊢ src → tgt replaces instructions that match a source (src) with a target (tgt), provided that a precondition (pre) holds. For example, one rewrite is isPowerOf2(C) ∩ C × C → x ⟫ , which transforms an unsigned division by a power of two into a right shift. In C++, a rewrite matches src and checks pre with the PatternMatch.h matcher library [21], such as m_Power2 for C, and then builds tgt. InstCombine keeps growing: it has expanded from about 36,000 lines of code in LLVM 12 to over 50,000 in LLVM 22. Developers add new rewrites or generalize existing ones to capture missed optimizations, and automated techniques now discover such optimizations at scale [12, 14, 26].
Each new or generalized rewrite raises the same question: does it matter? A rewrite is worth its maintenance and compile-time overhead only if real-world code frequently matches its src and satisfies its pre. To answer this, developers search a corpus of intermediate representation (IR)
Authors’ Contact Information: Hongxu Xu, University of Waterloo, Waterloo, Canada, [email protected]; Xintong Zhou, University of Waterloo, Waterloo, Canada, [email protected]; Chunhao Liao, University of Waterloo, Waterloo, Canada, [email protected]; Chengnian Sun, University of Waterloo, Waterloo, Canada, [email protected]. compiled from real-world programs, such as llvm-opt-benchmark [30], which contains 4.8 million functions. In practice, developers use daggrep [28, 29], which takes a concrete IR instance of as a query and finds instructions with the same structure across the corpus. However, daggrep relies purely on structural matching and cannot express preconditions (). For example, to search for the division rewrite above, a structural query can only match division by any constant divisor; ignoring the precondition , daggrep overmatches on instructions such as where the rewrite cannot apply. Its applicability counts are therefore inaccurate. Alternatively, developers can implement the rewrite in C++ and recompile the corpus. While exact, this measures applicability only after paying the implementation cost, and recompiling for each candidate rewrite is slow. llvm-opt-benchmark provides an on-demand recompilation pipeline, and each run takes a median of 47 minutes [31]. This latency makes iteratively exploring variations of a rewrite impractical.
Challenges. Accurately and quickly assessing where a rewrite applies poses two challenges. First, queries must express both and in a concise, declarative notation that developers can easily write. This is difficult because rewrites in InstCombine are not simple syntactic templates: abstracts over types, bit widths, instruction flags (e.g., nsw), operand commutativity, and interchangeable opcodes (e.g., accepting either add or or disjoint), while involves semantic checks normally implemented in C++, such as single-use restrictions, constant predicates like powers of two, and dataflow facts like absence of overflow. Second, query execution must be fast enough for developers to assess and refine candidate rewrites interactively across millions of functions. Scanning every function in the corpus is impractical because loading and parsing IR bitcode dominates query time. Achieving interactive speed therefore requires an index that prunes irrelevant functions without reading their IR. However, designing such an index is nontrivial: to prune candidates effectively, it must exploit both structural patterns and semantic preconditions, yet never prune a function that contains a match.
MetaphIR. To address these challenges, we present MetaphIR, a system that pairs a domain-specific language (DSL) for specifying the source pattern and precondition of LLVM peephole optimizations with an indexed search engine that accurately finds all matches across a large corpus in seconds. First, to achieve expressiveness (Challenge 1), a MetaphIR pattern (e.g., Figure 1) describes both and of a rewrite: is LLVM IR with holes (meta variables, highlighted in yellow), which MetaphIR matches structurally, and is a set of constraints on the values that the holes bind. To make patterns intuitive to write, MetaphIR directly mirrors LLVM’s C++ matchers and analysis APIs: common checks can be attached directly to holes as metaflags (e.g., :power2 on ?C in Figure 1 corresponds to LLVM’s m_Power2 matcher). Because MetaphIR reuses the checks developers already know, they can easily turn a concrete IR example into a pattern by replacing specific values with holes and attaching constraints. Second, to achieve interactive speed at scale (Challenge 2), MetaphIR prunes irrelevant functions without loading their IR: it precomputes and indexes a compact summary of each function’s features, which instructions occur and which facts hold in each operand slot. A single constraint evaluator operates over two domains: it checks concrete matches on the IR, and, when evaluated over the indexed features, it acts as an abstract interpretation [2] of the constraint language that decides whether any match in the function is possible. We prove that this abstract evaluation is sound, i.e., it never skips a function containing a valid match.

Figure 1. A MetaphIR Pattern.
We evaluate MetaphIR on twenty recent LLVM rewrites against llvm-opt-benchmark [30] (4.8M functions), where MetaphIR identifies the functions each rewrite applies to in isolation with 100 % precision and recall (§ 8.3). LLVM’s upstream test suites (1,912 files of hand-written IR) form a separate corpus that complements llvm-opt-benchmark with forms that real-world code rarely exhibits. On this corpus, the same patterns for the twenty rewrites achieve 100.00 % precision and 99.29 % recall, with only one false negative on an unsupported vector constant predicate. The index leaves a median of 0.019 % of the functions per pattern, so a query takes a median of 1.27 seconds, 22× faster than a full scan. MetaphIR is already in use: in an LLVM issue (link withheld for review), a contributor used it to assess how often a proposed rewrite applies.
Contributions. This paper makes the following contributions.
A DSL for both src and pre (§ 4): LLVM IR with holes and constraints that mirror InstCombine’s matchers and analysis APIs familiar to LLVM developers.
Sound pruning by abstract interpretation (§ 6). The index prunes functions by both structure and preconditions without loading their IR. This pruning is sound and effective: we prove that it never prunes a function that contains a match, and preconditions further reduce the candidate functions per pattern by a median of 2.4× (§ 8.4).
An implementation (§ 7): a WebAssembly app that searches the published corpus index in the browser, so developers need no local corpus or build. A contributor has already used it to assess a proposed LLVM rewrite.
An evaluation (§ 8) on twenty real rewrites and 4.8M functions, which shows that MetaphIR is accurate and fast. MetaphIR patterns match exactly where all twenty rewrites apply in isolation, with 0 false positives against 86,123 for daggrep at equal recall. Queries on 80 threads take a median of 1.27 seconds, 22× faster than a full scan, against 32.5 seconds for daggrep.
Background
This section reviews the LLVM concepts underlying MetaphIR: LLVM IR, missed peephole optimizations, C++ rewrites in InstCombine, and the value-tracking analyses used to check preconditions.
LLVM IR. LLVM IR [5] uses static single-assignment form: each instruction defines at most one value, and each defined value has a name starting with % (e.g., %udiv1). An instruction’s opcode specifies its operation (e.g., add or udiv), and its operands are values defined by other instructions, function arguments, or constants. Types include integers of any bit width, such as i32, and vectors of them, such as <4 x i32>. Flags on an instruction state extra properties, and the instruction’s result becomes poison if a property does not hold.1 For example, add nsw yields poison on signed overflow, and or disjoint yields poison if its operands share any set bits. The uses of a value are the operand slots that hold the value; for example, mul %x, %x is two uses of %x.
Missed Peephole Optimizations. The community often receives issues with concrete instances of missed peephole optimizations, such as Figure 2a from LLVM {link}Issue 132908{link}. The src function computes with two unsigned divisions; because the llvm.assume calls bound both divisors below 15, their product () cannot overflow an i8, allowing tgt to compute instead. InstCombine is the primary peephole optimization pass in LLVM. To handle such optimizations in InstCombine, developers generalize the concrete example into a rewrite by abstracting over the i8 type and replacing the specific llvm.assume bounds with a general check that cannot overflow.

define i8 @src(i8 %a, i8 %b, i8 %c) {
%b.small = icmp ult i8 %b, 15
call void @llvm.assume(i1 %b.small)
%c.small = icmp ult i8 %c, 15
call void @llvm.assume(i1 %c.small)
%udiv1 = udiv i8 %a, %b
%udiv2 = udiv i8 %udiv1, %c
ret i8 %udiv2
}
define i8 @tgt(i8 %a, i8 %b, i8 %c) {
%m = mul nuw i8 %b, %c
%udiv = udiv i8 %a, %m
ret i8 %udiv
}1 Instruction *visitUDiv(BinaryOperator &I) {
2 Value *Op0 = I.getOperand(0),
3 *Op1 = I.getOperand(1);
4 ...
5 Value *X, *Y;
6 if (match(Op0,
7 m_OneUse(
8 m_UDiv(m_Value(X), m_Value(Y))
9 ))
10 && willNotOverflowUnsignedMul(Y, Op1, I)) {
11 Value *YZ = Builder.CreateNUWMul(Y, Op1);
12 return BinaryOperator::CreateUDiv(X, YZ);
13 }
14 ...
15 }Figure 2. A Concrete IR Example illustrating a missed peephole optimization (a), and the Rewrite implemented in InstCombine in PR 214541 realizing this optimization (b). It transforms nested unsigned divisions ( /ᵤ ) /ᵤ into /ᵤ () when the inner division has one use and cannot overflow. The assumptions in src ensure that the product does not overflow.
Rewrites in InstCombine. Figure 2b shows the C++ rewrite that resolves this issue in pull request (PR) {link}214541{link}. InstCombine visits each instruction and calls the handler for its opcode, such as visitUDiv for the outer udiv (%udiv2). Lines 6–9 match src with LLVM’s PatternMatch.h matcher library [21], whose matchers compose recursively by taking sub-matchers as arguments: m_UDiv(m_Value(X), m_Value(Y)) matches Op0 (%udiv1) as a udiv and uses m_Value to bind Op0’s operands to X (%a) and Y (%b). Wrapping m_UDiv in m_OneUse (line 7) requires the inner division Op0 to have a single use (as the dividend of I). If Op0 has more than one use, Op0 could not be removed, because the rewrite would add a multiplication without eliminating a division. Finally, line 10 completes pre by checking that (%b and %c) cannot overflow, and lines 11–12 build the tgt.
Value Tracking. Preconditions that PatternMatch.h cannot check, such as ruling out overflow or requiring a nonzero operand, rely on dataflow facts. InstCombine obtains these facts from LLVM’s ValueTracking analyses, which infer known bits and value bounds from defining instructions and branch conditions. Because a fact may hold only at certain points in a function, each ValueTracking query takes a context instruction to check whether the fact holds there. On line 10 of Figure 2b, willNotOverflowUnsignedMul(Y, Op1, I) uses ValueTracking to check that will not overflow at context instruction I. For example, if Y is zero-extended from 16 to 32 bits and Op1 is 7, ValueTracking knows from Y’s defining instruction that its upper 16 bits are zero, so ; their 32-bit unsigned product is therefore below and cannot overflow.
Overview
This section illustrates MetaphIR using the missed optimization in Figure 2a. A developer first expresses the optimization’s applicability conditions as a MetaphIR pattern. The developer then evaluates the pattern over a large corpus accurately and efficiently before implementing the optimization in C++ in LLVM.
Writing a MetaphIR Pattern. Starting from the function @src in Figure 2a, a developer generalizes the concrete IR into a surface pattern (Figure 3), written in MetaphIR’s DSL (§ 4) to specify both src and pre. To express src, MetaphIR uses meta variables (names starting with ?) as holes. The operands %a, %b, and %c become ?x, ?y, and ?z, each matching any value (like m_Value). Likewise, the type i8 becomes i?bits, matching an integer type of any width and binding that width to ?bits. Names starting with % (%udiv1 and %udiv2) are local names for the pattern’s instructions. Subsequent instructions and constraints refer to instructions by these local names (e.g., %udiv2 takes %udiv1 as its dividend). To express pre, MetaphIR provides metaflags and constraints. A metaflag, written after a colon, refines an instruction or operand inline. For example, :s on %udiv1 requires the inner division to have a single use (like m_OneUse on line 7 of Figure 2b). A line starting with ;; adds a constraint. Rather than matching the specific llvm.assume calls in @src,

Figure 3. The Running Example from the Rewrite of PR 214541. Stages run from top to bottom; each reads the input shown on its left and produces the result shown on its right. Yellow highlighting marks how lowering converts :s into a constraint. An arrow udiv→udiv means that a udiv uses another udiv.
noOverflow("umul", ?y, ?z) queries ValueTracking to check that the unsigned product ?y * ?z cannot overflow (like willNotOverflowUnsignedMul on line 10 of Figure 2b).
Querying the Corpus. To see how widely this optimization applies, a developer runs the pattern as a query over llvm-opt-benchmark (4.8M functions from 216 real-world projects, § 8). For this pattern, MetaphIR reports matches in 18 functions in 0.63 seconds, identifying the exact functions where the C++ rewrite applies. Figure 3 illustrates the five stages that execute this query, starting by lowering the surface pattern into simpler core patterns and running them on a small example corpus in which only @f matches.
Stage ①: Lowering. MetaphIR separates the surface language from a minimal core language (§§ § 4 and § 5) for extensibility and maintainability: users can define new abstractions in the surface language, while downstream indexing, matching, and soundness proofs (§ 6.3) need only handle a small set of core primitives. Lowering expands a surface pattern into a set of core patterns, each containing only primitive instructions with meta variables and constraints. In Figure 3, lowering converts the metaflag :s into the constraint hasOneUse(%udiv1) and produces only one core pattern. A surface pattern can lower into multiple core patterns when it uses a composite matcher with alternatives, such as addLike, which matches either add or disjoint.
Stage ②: Index Lookup. Reading IR is the bottleneck of query execution: the corpus contains 11.9 GB of bitcode, and each module must be loaded and parsed before matching, even though most functions do not match. To prune non-matching functions without reading their IR, MetaphIR builds a corpus index in two parts, used by Stage ② and Stage ③, respectively. The first part is an inverted index of posting lists. Each posting list maps a structural feature directly to the functions that exhibit it. Examples of structural features are the opcodes of a function’s instructions and the opcode pairs of instructions where one uses the other; § 6.1 lists all of them. A pattern usually requires several structural features, and MetaphIR intersects their posting lists. In Figure 3, the posting list for the opcode pair udiv→udiv (one udiv using another udiv) contains @f, @g, and @h. These form the initial candidates.
Stage 3: Feature Filtering. The second part of the index stores each function’s features, which include its structural features and the facts that hold for the values in each operand slot. Features are compact. The whole index takes 2.70 GB against 11.9 GB of bitcode, and decoding a function’s features requires no IR parsing. MetaphIR decodes the features of only the candidates from Stage 2 and evaluates the query constraints on them. This evaluation is an abstract interpretation [2] of the constraint language. A constraint evaluates to true, false, or unknown, and MetaphIR prunes a function only when a constraint is false. For @h, the features show that no udiv has a single use, so hasOneUse(%udiv1) is false and @h is pruned, leaving @f and @g. § 6 proves this abstract interpretation sound, i.e., it never prunes a function that has a match.
Stage 4: Structural Matching. Only at this stage does MetaphIR read any IR. On the full corpus, 396 of 4.8M functions remain as candidates, in 223 modules, so MetaphIR loads only these modules. MetaphIR searches each candidate for instantiations: maps from the pattern’s instructions and meta variables to IR values that respect opcodes, types, flags, and operand edges. In Figure 3, @f computes %q = udiv i32 %a, %b and then %r = udiv i32 %q, 7. The instantiation for @f maps the two divisions of the pattern to %q and %r, and each meta variable to the matching operand or width, e.g., ?z to 7. Function @g has the same shape and also yields one instantiation.
Stage 5: Constraint Evaluation. Finally, MetaphIR evaluates each constraint on each instantiation. For @f, hasOneUse(%q) checks the use list of %q, and noOverflow queries ValueTracking at context %r: because %b is zero-extended from 16 bits, %b * 7 cannot overflow (§ 2) and @f matches. In @g, nothing bounds %m and %n, so noOverflow is false and @g is rejected. An instantiation that passes every constraint is a match.
The MetaphIR Language
We design the MetaphIR DSL to be immediately familiar to LLVM developers: patterns use LLVM IR-like syntax to mirror the instructions they match; built-in metaflags and constraints borrow the names and semantics of PatternMatch.h matchers, ValueTracking analyses, and LLVM utility APIs. Table 1 lists common PatternMatch.h idioms and their MetaphIR counterparts.
| PatternMatch.h (C++) | MetaphIR | Meaning |
| m_Value(X), m_Deferred(X) | ?x, its second occurrence | any value; the same value |
| m_Specific(V) | %v | the value of a pattern instruction |
| m_c_Add(A, B) | add:c ?ty A, B | commutative matching |
| m_OneUse(P) | P:s | a single use |
| m_ZExtOrSelf(P) | zext:o ... | the instruction or its operand |
| m_NSWAdd, “no nsw”, a saved flag | add nsw, add !nsw, add nsw:?f | flag present, absent, captured |
| m_APInt(C), m_Power2(C) | ?c:apInt, ?c:power2 | constant classes |
| m_AddLike, m_Shift, m_Signum | addLike, shift, signum | composite matchers |
| isKnownNonZero(X, Q) | isKnownNonZero(?x) | value tracking at the context |
| C->popcount() == *S | popcount(?c) == ?s | a constraint |
Table 1. PatternMatch.h Idioms and Their MetaphIR Counterparts.
For extensibility and maintainability, the MetaphIR DSL (the surface language) layers three abstractions (§ 4.2) over a small core language (§ 4.1): MetaphIR’s standard library and users can define new abstractions in the surface language, while indexing, matching, and soundness proofs need only handle the core primitives. Lowering (§ 5.5) converts surface patterns into core patterns in the core language, which we formalize in § 5.
The Core Language
A core pattern is a sequence of primitive instructions in LLVM IR syntax, followed or interleaved by Boolean constraints.
Patterns Are IR with Holes
The core language covers 49 LLVM instructions, including arithmetic, bitwise and vector operations, casts, compares, select, phi, call, br, and memory accesses. Anything concrete in an instruction must match exactly, and a meta variable ?name is a hole. Each meta variable has a sort, inferred from where it appears (Table 2). All occurrences of a meta variable must bind the same thing.
| Sort | Example | Binds |
| Val | add i8 ?x, ?y | an instruction, argument, constant, or global |
| Nat | add i?bits ..., < ?n x i32> | a bit width, count, or index |
| Type | add ?ty ... | an LLVM type, such as i32 |
| Pred | icmp ?pred i32 ... | a comparison predicate |
| Bool | add nsw:?f ... | whether a flag is present |
| Inst | add:?instr ... | the matched instruction |
| BB | br label ?bb | a basic block |
| Fn | call ?f(...) | a callee |
| Intr | call @llvm.?id(...) | an intrinsic |
| Type[ ], Val[ ] | call i32 @f(...?tys ?vals) | the LLVM types and the values of the remaining operands |
Table 2. Sorts of Meta Variables (sorts may have subsorts and thus overlap, e.g., Inst ⊑ Val, § 5.2).
Flags. LLVM instructions carry flags, such as nsw on add or exact on udiv, which often make the instruction yield a poison value when the flag’s specified property does not hold. A pattern specifies each flag in one of four ways:
omit it (
add i32 ?x, ?y): the flag may or may not be present;write it (
add nsw i32 ?x, ?y): the flag must be present;negate it (
add !nsw i32 ?x, ?y): the flag must be absent;capture it (
add nsw:?f i32 ?x, ?y): the flag may or may not be present, and ?f binds to true if it is present and false otherwise.
Structural Metaflags. Two built-in structural metaflags (:c and :o) are part of the core language and change how an instruction matches (unlike user- and library-defined metaflags such as :s, which lower into constraints, § 4.2.1). The metaflag :c tries the operands in swapped order2, like the m_c_ matchers in PatternMatch.h. The metaflag :o (“or self”) makes the instruction optional: zext:o i8 %t to i32 matches either a zext of %t or %t itself, like m_ZExtOrSelf.
Blocks. By default (or after anyblock:), instructions may lie in any basic block. A label ?bb: restricts subsequent instructions to a single basic block and binds that block to ?bb.
Constraints
A line ;; e adds the constraint e, a Boolean expression over the meta variables. The constraint language has integer, Boolean, and string literals; arithmetic, bitwise, and comparison operators; and 105 built-in operators. The built-in operators cover four groups:
Constant classes, such as isPower2, isLowBitMask, and isSignMask. Each has the semantics of the corresponding PatternMatch.h matcher (isPower2 corresponds to m_Power2).
Inspection of what a meta variable bound. The constraints opcode, predicate, and isa tell which instruction, predicate, or class of value was matched. The constraint bitWidth gives a width of a bound type or value, and use counts such as hasOneUse limit how often a value is used.
Predicate algebra on a comparison predicate bound by a meta variable, as
?pinicmp ?p. The constraintisSigned(?p)accepts only signed predicates such assltandsgt, andswappedPredicatechecks whether two comparisons are the same with their operands swapped. These mirror theCmpInstmethodsisSignedandgetSwappedPredicatein C++ rewrites.Value tracking: 21 queries that call LLVM’s ValueTracking analyses, such as
isKnownNonZero,knownBits,noOverflow, andinUnsignedRange. Each query’s context instruction (§ 2) defaults to the instruction written immediately before the constraint (e.g.,%udiv2fornoOverflowin Figure 3). In a constraint, a meta variable stands for the object it bound; arithmetic and comparison operators implicitly coerce a bound IR value to its integer value if it is a constant, and reject the match if coercion fails (§ 5.2). Arithmetic uses unbounded integers by default (so e.g.?bits + 1never overflows), while fixed-width wrapping operations take the bit width explicitly (e.g.,add(128, 128, 8) == 0).
Extending the Core
Rather than hardcoding every PatternMatch.h idiom, the core language provides only minimal primitives. MetaphIR extends the core into the surface language with three abstractions: named constraints, metaflags, and composite matchers. The standard library stdlib.mpir uses them to define the counterparts of PatternMatch.h (e.g., :s and addLike), and users can define their own in the same way.
Named Constraints and Metaflags
A named constraint is a reusable Boolean expression, and a metaflag attaches a constraint to the value it follows, which keeps patterns short and readable. Below, the named constraint inRange tests a range, and the metaflag :between applies inRange to the flagged value. The first parameter of a metaflag (?v) is the operand or instruction that the metaflag is attached to, and the remaining parameters are written in parentheses, so ?c:between(5, 10) requires ?c to lie in [5, 10]:
constraint inRange(?v, ?lo, ?hi) { sle(?lo, ?v) && sle(?v, ?hi) }
metaflag :between(?v, ?lo, ?hi) { inRange(?v, ?lo, ?hi) }
%r = add i32 ?x, ?c:between(5, 10)
A metaflag declaration also says where the metaflag may be attached: to operands (the default), to instructions (metaflag:i), or to both (metaflag:i:o). Metaflags combine naturally: a value with several metaflags must satisfy all of them, :or(...) accepts a value that satisfies any one of them, and :not(...) accepts a value that fails the given metaflag.
Composite Matchers
A match declaration defines a new instruction-like matcher with one or more alternative bodies, called branches, separated by or. The standard library’s addLike, the counterpart of m_AddLike, accepts an add or an or disjoint:
match:c addLike [nsw, nuw] Binary (?ty ?x, ?y) { %ret = add nsw ?nsw nuw ?nuw ?ty ?x, ?y }
or [nsw = true, nuw = true] { %ret = or disjoint ?ty ?x, ?y }
The declaration specifies that addLike is commutative (match:c) and supports the flags nsw and nuw; the instruction named %ret gives the result of each branch.
Invocation Forms. The form fixes the shape of an invocation. Binary requires two operands of one type ?ty, so an invocation is written like a binary operation, as in addLike nsw i32 %a, %b. Table 3 lists the four forms.
| Form | Signature | Example Invocation | stdlib.mpir Matchers |
| Unary | (?ty ?x) | neg nsw i32 ?a | neg, signum, fnegLike |
| Binary | (?ty ?x, ?y) | addLike nsw i32 ?a, ?b | addLike, shift, idiv |
| Cast | (?ty1 ?x to ?ty2) | zextOrSext i8 ?a to i32 | zextOrSext, sextLike, itofp |
| Nary | (?ty1 ?x1, ?ty2 ?x2, ...) | selectEq i8 ?x, i32 ?a, i32 ?b | selectEq, selectEqZero |
Table 3. Invocation Forms of Composite Matchers.
Flag Binding. An invocation may specify each declared flag (e.g., nsw and nuw) in the same four ways as an instruction: omitted, required, negated, or captured. In the above example, the first branch passes these flags on to its add. An or disjoint has no such flags, so the second branch fixes both to true, since a disjoint or never wraps. In this way, the flags are kept meaningful for every branch: an invocation that writes !nsw or !nuw drops the second branch, and an invocation that captures a flag, as in addLike nsw:?f, binds ?f to true when the second branch matches.
Formal Semantics
This section formalizes the core language of MetaphIR, defines when a core pattern matches an IR function, and shows that lowering preserves the matches of a surface pattern.
Syntax
We formalize the core language, the language of the core patterns that lowering produces (§ 5.5). Figure 4 gives its abstract syntax (corresponding to the IR-like concrete syntax of § 4.1), and Figure 5 shows a core pattern in concrete syntax alongside its abstract syntax. A core pattern is a sequence of instruction nodes and a sequence of constraints. An operand must name an earlier node, so nodes form a directed acyclic graph. The nodes that no other node uses are the roots of the core pattern, and a core pattern may have more than one root.

Figure 4. Abstract Syntax of the Core Language. holds the partial maps from to , square brackets mark optional parts, is a vector type, and is a constraint with context instruction .

Figure 5. Concrete and Abstract Syntax of a Core Pattern.
Instruction Nodes. Each instruction node defines a local name and has an opcode , a flag specification , keyed arguments , an optional type argument , and typed operands . A node may also bind a meta variable to the instruction that the node matches (as ) and require that instruction to lie in a given basic block (in ). Every instruction, whatever its surface syntax, becomes a node of this form. Most parts of an instruction that are not flags or operands, such as the predicate of a compare or the alignment of a load, become keyed arguments. A type that is not an operand’s type, such as the destination type of a cast, becomes the type argument. An operand list may also end with a variadic tail, which binds the remaining operands and their types to two array meta variables; for simplicity, we omit the tail from the rules.
Flags and Marks. The flag specification maps each flag that the pattern mentions to (present), (absent), or a meta variable that captures whether the flag is present. A flag that the pattern does not mention may be present or absent. The marks hold the structural metaflags: c for commutative matching, and o() for a node that may match the operand instead.
Sorts and Well-Formedness
One set of sorts classifies both meta variables and constraint expressions:
They are the sorts of meta variables in Table 2, the sorts of values that constraints compute (Int, Str, and BV for bit vectors), and Opd, the sort of an operand position. An operand usually binds an IR value (Val), but also a meta variable that is a width (Nat), as ?n in add i?n ?x, ?n, binds a number and matches the constant with that value.
Subsorts. A subsort means that every object of sort is also one of sort , so such an object may be used wherever is expected. The order is generated by
Sorts of Meta Variables. A sort environment maps each meta variable to the meet (greatest lower bound) of the sorts that its occurrences require. In our setting, the meet of two sorts is just the more specific one. For example, a meta variable used as both an operand and a width has sort Nat (the meet of Opd and Nat), as for ?n in add i?n ?x, ?n. When no occurrence is more specific than Opd, as for ?x in add i8 ?x, ?y, gives the meta variable the default sort Val.
Sorts of Constraints. Each built-in operator has a signature of the form , such as noOverflow : Str Val Val Bool. An argument is accepted if its sort lies below a sort that coerces to the parameter’s:
| S-Var | S-Loc | S-Op |
Binary operators such as + are just operators in written infix. The coercion relation is reflexive and contains , , , , , , and . A coercion converts a value to sort , or err if no coercion applies or the conversion fails on . For example, Val Int succeeds only on an integer constant (§ 5.4).
Well-Formedness. While parsing, MetaphIR checks the surface pattern: every meta variable has a sort, every constraint has sort Bool, each flag in is supported by , the structural mark c appears only on commutative operations and compares, and every named meta variable is bound by every match. A pattern that passes these checks is well-formed.
Targets and Structural Matching
Structural matching is the judgment : the instruction node of a core pattern matches the value of an LLVM IR function under the instantiation .
Targets. A target is an IR function , which we view as a graph whose nodes are the values of (its instructions, arguments, constants, globals, and basic blocks) and whose edges lead from each instruction to its operands. Table 4 lists the functions that matching uses to inspect an instruction.
| Function | Gives | Example |
| the opcode | icmp | |
| the set of present flags | ||
| the keyed arguments, such as a predicate or an alignment | ||
| the type argument, usually the result type, such as the destination type of a cast | i1 | |
| the basic block | %entry | |
| the operands | ||
| the type of the th operand | i32 |
Table 4. Functions on an Instruction . The examples are for in block \texttt{%entry}.
Instantiations. An instantiation maps each local name of to a value of and each meta variable to a semantic object of its sort: values for Val, natural numbers for Nat, LLVM types for Type, and likewise for the other sorts.
Rules. Figure 6 gives the rules for . M-Inst checks the opcode, the flags, the keyed arguments, the types, and each operand, and binds the capture and the block. The flag premise of M-Inst, , defined by M-Flags, requires that each flag is present, each flag is absent, and each captured flag binds its meta variable to whether it is present. M-Comm matches

Figure 6. Structural Matching. The type argument , the instruction binding (as ), and the block binding (in ) are optional; when they are omitted, the rules drop the premises that check them. In M-Var, also lets a Nat meta variable match the constant with its value. In M-Comm, , and unless is a comparison, which swaps its predicate with the operands (a predicate meta variable is swapped after it is bound). We write for a constant . The relation compares integers at the value’s width and also accepts a splat vector of ; type equality likewise accepts a vector of the scalar type.
a node marked c if the node matches with its two operands swapped (and c dropped, to avoid swapping again), and M-Self lets a node marked o() match a value whenever matches it.
Definition 5.1 (Structural matches). Let be a target and a core pattern. Let and be the local names and the meta variables of , and let be the node of that defines the local name . The set holds the instantiations with such that for every .
Constraint Semantics
Constraints evaluate to concrete values . Evaluation can fail, for example on division by zero or on arithmetic over a non-constant value, so the result lies in . Each built-in operator has a concrete semantics , where is the target function and is the context instruction, as some operators rely on information from them. Figure 7 gives the semantics .

Figure 7. Concrete Semantics of Constraints for . The target function and the context instruction are fixed and left implicit in . Each argument is coerced to the parameter sort of its operator; is the -th parameter sort of , and is the coercion of to (§ 5.2). Overloaded operators, such as ==, have no fixed parameter sort and coerce their arguments themselves. The logical operators short-circuit as in C++.
Definition 5.2 (Matches). The matches of a core pattern in a function are its structural matches under which every constraint evaluates to true:
Lowering
A surface pattern extends the core language with definitions of metaflags and composite matchers. A metaflag with arguments on an operand or instruction , written , matches when two conditions hold: matches , and the body of evaluates to true once the first parameter of is substituted by and the others by . A composite matcher invocation is an instruction node whose opcode is a composite matcher , with arguments . It matches when some branch of that is compatible with matches after substituting for the parameters, and its marks act as on built-in nodes. We write for the resulting set of instantiations, restricted to the meta variables that itself declares. The other meta variables of the branch are local to the invocation. The function produces a finite set of core patterns by removing both abstractions, recursively for nested invocations:
Composite matcher invocations. An invocation marked :c is first duplicated with its operands swapped. Each branch is inlined as its own core pattern, with its meta variables renamed apart, such as ?r$k for ?k in the invocation %r; branches whose fixed flags or types conflict with
invocation are dropped. A :o(N) on the invocation marks each branch’s root with , where is the invocation’s -th operand, so the root may match that operand instead.
Metaflags. Each metaflag becomes its body as a constraint whose context is the flagged instruction. Lowering leaves the c and marks of built-in nodes in place, because M-Comm and M-Self handle them during matching.
Theorem 5.3 (Lowering preserves matches). For every well-formed surface pattern and function , .
Note that restricts to the meta variables of , because the core patterns may bind meta variables that does not declare, such as the renamed meta variables of inlined branches. § A.1 proves theorem 5.3 by induction on the depth of composite matcher definitions. Theorem 5.3 lets the rest of the paper work with core patterns only.
Pruning Functions by Abstract Interpretation
MetaphIR decides whether can be non-empty from the features of stored in an index (Stage ③ of Figure 3), without reading the IR of , and we prove that this never loses a match. Throughout this section, we fix an IR function and leave it implicit in notation such as .
Features of an IR Function
The features , an abstraction of , record which values occur where, which facts hold for them, and how the instructions of connect (Figure 8 shows an example).

Figure 8. Features of a Function and Their Use for Pruning.
Sites. Features describe values by where they occur. A site is an opcode and a set of slots , each an operand position or res for the result. The values of at are
We write for for simplicity. In Figure 8a, the value at is the constant 2, the value at is the argument %x, and the value at is %r.
Facts. A fact is a unary predicate on values from a fixed set: the constant classes such as isPower2, isa classes, hasOneUse, and equality with some small integers. A site records a fact when some value there satisfies it:
In Figure 8a, records literal 2, isPower2, and isKnownNonZero, but no isZero (Figure 8b). Pruning relies on the missing facts: if a pattern requires a value with at a site and is missing there, the function has no match, as for the first query in Figure 8c. Two further kinds of facts are recorded in the same way. First, a value-tracking predicate such as isKnownNonZero depends on a context instruction, so if holds for at the context itself, for some with opcode . In Figure 8a, value tracking knows that 2 is non-zero at %r, so records isKnownNonZero. Second, queries that compare a numeric property with a threshold, such as the number of known trailing zero bits, use a measure, a fact that carries a number: a site records the minimum or maximum of the property over its values, and a query whose threshold lies beyond it is ruled out.
Structural Features. Finally, also records the opcodes present in , the edges such that an instruction with opcode uses one with opcode , the siblings whose instructions share an operand, the globals used, and a partial signature for each instruction. In Figure 8a, these are the opcodes urem and add, the edge (add, urem) because %s uses %r, and the signatures urem i32 and add i32.
Structural Requirements of a Core Pattern
Features summarize an IR function, while a core pattern ’s structural requirements specify the structural features a function must have to match it. The certain nodes of are the nodes without an mark, which every match maps to an instruction with their own opcode. The structural requirements of are ① the opcode of each certain node, ② the edge whenever a certain node with opcode has a certain operand node with opcode , ③ the sibling pair whenever a meta variable is an operand of two certain nodes with these opcodes, ④ the written and negated flags and the fixed widths of each certain node, and ⑤ each global that names. The second query in Figure 8c requires the edge , which Figure 8b lacks, so is ruled out for this query by Lemma 6.1 below.
Lemma 6.1 (Requirements are necessary). If , then .
Typings. Type-level meta variables such as ?bits can be bound from the signatures. A typing is a partial map from type-level meta variables to LLVM types and sizes. The set holds the typings of that the partial signatures in allow. For example, for a core pattern with nodes urem i?n ... and add i?n ..., the signatures urem i32 and add i32 in Figure 8b give it the single typing ?n = 32. Because each node may match multiple signatures in , the number of combinations can grow exponentially with the number of nodes; MetaphIR therefore caps at 256 typings. Above the cap, MetaphIR uses the empty typing.
Lemma 6.2 (Typings are sound). If , then some satisfies .
Evaluating Constraints over an Abstract Domain
Constraints share a single evaluator parameterized by a value domain: Stage ⑤ runs it on concrete IR values (, Figure 7), and Stage ③ runs it on the index domain over features (Figure 9). Both stages thus share expression traversal, coercions, and concrete operator evaluation, reducing the soundness of the abstract constraint evaluation to the soundness of each abstract transformer.

Figure 9. The Index Domain. In c, we omit the subscript , local names evaluate as meta variables do, and constants are coerced to Bool as in Figure 7.
Abstract Values. Fix a core pattern , a function , and a typing . An abstract value describes the results that an expression can have across all matches of in that agree with . Figure 9a lists the four kinds of abstract values, which form the abstract domain , and their concretization into the concrete domain .
Sites of a Meta Variable or Local Name. The set sites() holds the sites where a meta variable or local name certainly occurs in every match. If is operand of a certain node with opcode op, then , or when the node has the c mark, since may be in either slot. A local name and its capture get the site if their node is certain, and also the site of as an operand of each certain user. For example, in %r = add i32 ?a, 1 and %s = urem i32 %r, ?c, . If add has mark :o, loses .
Abstract Semantics. The abstract semantics evaluates a constraint in the index domain under the typing (Figure 9c). It differs from Figure 7 in only three places. A variable evaluates to what the features know about it. An operator evaluates concretely when all its operands are concrete, and otherwise asks the operator’s abstract transformer . Finally, a connective whose left side is unknown may still be decided by its right side, as in Kleene logic.
Abstract Transformers. An operator’s abstract transformer returns only when a recorded feature rules out every value, and otherwise. For a fact predicate (including for a small literal ), its abstract transformer gives if for some ; a threshold query likewise returns when its threshold lies beyond the measure at . For a value-tracking predicate in @e@, the index computes only with the instruction that uses the operand as the context (§ 6.1); so checks only the site where the argument is an operand of itself, when is certain, and returns otherwise. Each abstract transformer is sound in the following sense: if and , then for the context of any match. For a fact predicate , this holds because and give by Equation (1). Table 5 evaluates sample constraints on function .
| Constraint | Abstract result | Function | ||
?c == 2 | : literal 2 is recorded at (urem, 1), so ?c may be 2 | kept | ||
?c == 4 | const(false): literal 4 is missing | pruned | ||
| `?c == 4 | ?c == 2` | const(false) = | kept | |
?c == ?x && ?c == 4 | const(false) = const(false) | pruned | ||
isKnownNonZero(?x) | const(false): value-tracking fact missing at (urem, 0) | pruned | ||
isZero(add(?c, 1)) | : add has no abstract transformer | kept | ||
?n == 8 | const(32 == 8) = const(false) | pruned | ||
udiv(1, 0) == 0 | err | pruned |
Table 5. Abstract Evaluation on Function f of Figure 8a, for the Core Pattern %r = urem i?n ?x, ?c and the Typing ?n = 32.
Soundness
The following lemma states that the index domain over-approximates the concrete domain at every subexpression.
Lemma 6.3 (Abstract evaluation is sound). Let and . For every constraint of and every subexpression of , .
The proof is by induction on (see § A.3).
Theorem 6.4 (Pruning is sound). Let be a core pattern. If , or if for every typing some constraint of has , then .
Proof. Suppose . By Lemma 6.1, . By Lemma 6.2, some has ; take the constraint that the hypothesis gives for it. By Lemma 6.3, , so , a contradiction. □
Corollary 6.5 (Indexed search is exact). For every pattern and corpus, pruning with the index before matching the functions returns the same matches as matching every function in the corpus.
The corollary follows from theorems 5.3 and 6.4.
Implementation
MetaphIR is implemented in C++ on top of LLVM. It consists of a parser, the lowering pass, the matcher, the constraint evaluator with its two domains, and the corpus index, exposed through command-line tools and a WebAssembly-based application.
The Corpus Index. In addition to the posting lists, the index stores features at two levels: per-module features (the union of its functions’ features) and the full features of each function, decoded only on demand. A query intersects the shortest few posting lists of each core pattern, takes the union over core patterns, checks the per-module features, and only then decodes the features of each candidate and runs the abstract evaluation. Over the evaluation corpus, the index takes 2.70 GB, against 11.9 GB of bitcode.
Web Application. The C++ query engine also compiles to WebAssembly (4.2 MB). A web application lets a user write a pattern and run it against the published index (1,238 MB). Alongside the index, each IR function is packed into a bitcode module (5.56 GB). The application reads the index and the packed function IR with HTTP range requests, so a query downloads only the posting lists and candidate functions it needs.
Evaluation
We evaluate MetaphIR on twenty real InstCombine rewrites and a large corpus of IR compiled from real-world programs, and answer three research questions.
RQ1 (Expressiveness). Can the MetaphIR DSL express where LLVM rewrites apply?
RQ2 (Accuracy). How accurately do the matches identify where the rewrites apply, and how does this compare with daggrep?
RQ3 (Efficiency). How much work does the index save, and how fast are queries?
Setup
We describe the rewrites, the datasets, the ground truth, and the machine.
Rewrites. We collected twenty LLVM PRs (Table 6) that each add or generalize an InstCombine or InstSimplify rewrite. They were merged between June 20 and August 18, 2026. Each PR states a clear transformation from a source to a target and has a regression test. The rewrites cover arithmetic, bitwise, shift, compare, select, and cast operations. For each PR, we wrote one or two patterns specifying where the rewrite applies, totaling 23 patterns.
| PR | MetaphIR | MetaphIR | MetaphIR TP | MetaphIR P/R/F1 | MetaphIR | MetaphIR | MetaphIR | daggrep | daggrep TP | daggrep P/R/F1 | daggrep | Web Sz | Web | Web SzNC | Web |
| 204089 | 0 | 0 | 0 | 100.0 / 100.0 / 100.0 | 0.9 | 0.9 | 26.2 | 0 | 0 | 100.0 / 100.0 / 100.0 | 43.1 | 97 | 10.8 | 131 | 14.4 |
| 204927 | 1,973 | 1,973 | 1,973 | 100.0 / 100.0 / 100.0 | 3.3 | 3.2 | 26.0 | 4,343 | 1,973 | 45.4 / 100.0 / 62.5 | 64.5 | 1,825 | 283.5 | 2,194 | 358.5 |
| 204928 | 1,266 | 1,266 | 1,266 | 100.0 / 100.0 / 100.0 | 1.5 | 1.7 | 26.0 | 5,163 | 1,266 | 24.5 / 100.0 / 39.4 | 65.1 | 343 | 56.2 | 370 | 65.5 |
| 205383 | 0 | 0 | 0 | 100.0 / 100.0 / 100.0 | 0.9 | 1.0 | 51.5 | 0 | 0 | 100.0 / 100.0 / 100.0 | 86.6 | 70 | 8.4 | 72 | 8.6 |
| 207462 | 31 | 31 | 31 | 100.0 / 100.0 / 100.0 | 2.3 | 2.4 | 51.3 | 212 | 31 | 14.6 / 100.0 / 25.5 | 42.5 | 826 | 87.8 | 885 | 93.9 |
| 207564 | 52 | 52 | 52 | 100.0 / 100.0 / 100.0 | 1.4 | 1.6 | 26.3 | 54 | 52 | 96.3 / 100.0 / 98.1 | 21.7 | 539 | 57.3 | 736 | 78.2 |
| 209322 | 0 | 0 | 0 | 100.0 / 100.0 / 100.0 | 0.9 | 4.4 | 25.9 | 68,175 | 0 | 0.0 / 100.0 / 0.0 | 21.4 | 852 | 89.7 | 3,564 | 382.6 |
| 210499 | 10 | 10 | 10 | 100.0 / 100.0 / 100.0 | 2.0 | 2.0 | 26.8 | 5,524 | 10 | 0.2 / 100.0 / 0.4 | 86.7 | 1,169 | 125.9 | 1,925 | 206.6 |
| 212132 | 0 | 0 | 0 | 100.0 / 100.0 / 100.0 | 3.2 | 3.4 | 51.7 | 0 | 0 | 100.0 / 100.0 / 100.0 | 44.1 | 812 | 85.5 | 852 | 89.6 |
| 213313 | 0 | 0 | 0 | 100.0 / 100.0 / 100.0 | 0.8 | 0.8 | 26.1 | 0 | 0 | 100.0 / 100.0 / 100.0 | 43.1 | 68 | 7.6 | 68 | 7.6 |
| 213709 | 9 | 9 | 9 | 100.0 / 100.0 / 100.0 | 1.8 | 2.5 | 26.0 | 9 | 9 | 100.0 / 100.0 / 100.0 | 43.5 | 863 | 91.3 | 1,256 | 132.8 |
| 214376 | 0 | 0 | 0 | 100.0 / 100.0 / 100.0 | 1.2 | 1.2 | 25.9 | 0 | 0 | 100.0 / 100.0 / 100.0 | 21.1 | 151 | 16.2 | 226 | 24.0 |
| 214381 | 9 | 9 | 9 | 100.0 / 100.0 / 100.0 | 0.7 | 1.0 | 25.3 | 14 | 9 | 64.3 / 100.0 / 78.3 | 21.5 | 183 | 19.4 | 223 | 23.5 |
| 214517 | 24 | 24 | 24 | 100.0 / 100.0 / 100.0 | 0.9 | 1.2 | 26.7 | 475 | 24 | 5.1 / 100.0 / 9.6 | 21.4 | 269 | 28.4 | 289 | 30.6 |
| 214541 | 18 | 18 | 18 | 100.0 / 100.0 / 100.0 | 0.6 | 0.7 | 26.3 | 284 | 18 | 6.3 / 100.0 / 11.9 | 20.7 | 73 | 8.2 | 81 | 9.0 |
| 215122 | 32 | 32 | 32 | 100.0 / 100.0 / 100.0 | 2.0 | 2.9 | 26.0 | 168 | 32 | 19.0 / 100.0 / 32.0 | 21.9 | 907 | 95.5 | 1,483 | 156.3 |
| 215130 | 3 | 3 | 3 | 100.0 / 100.0 / 100.0 | 0.9 | 0.9 | 26.6 | 14 | 3 | 21.4 / 100.0 / 35.3 | 22.4 | 52 | 5.9 | 55 | 6.2 |
| 216046 | 57 | 57 | 57 | 100.0 / 100.0 / 100.0 | 1.4 | 1.7 | 26.5 | 1,680 | 57 | 3.4 / 100.0 / 6.6 | 21.2 | 233 | 25.0 | 274 | 29.3 |
| 216436 | 44 | 44 | 44 | 100.0 / 100.0 / 100.0 | 1.0 | 1.4 | 25.7 | 52 | 44 | 84.6 / 100.0 / 91.7 | 21.1 | 229 | 24.5 | 410 | 44.0 |
| 216470 | 333 | 333 | 333 | 100.0 / 100.0 / 100.0 | 2.8 | 3.1 | 26.3 | 3,817 | 333 | 8.7 / 100.0 / 16.0 | 43.9 | 1,254 | 133.3 | 1,362 | 144.3 |
| Avg | 3,861 | 3,861 | 3,861 | 100.0 / 100.0 / 100.0 | 1.3 | 1.6 | 26.2 | 89,984 | 3,861 | 4.3 / 100.0 / 8.2 | 32.5 | 306 | 42.3 | 390 | 54.7 |
| Avg | 100.0 / 100.0 / 100.0 | 49.7 / 100.0 / 55.4 |
Table 6. Per-Rewrite Accuracy and Query Time (seconds) on llvm-opt-benchmark. , , and TP count the functions in the ground truth (where the C++ rewrite applies), in the prediction (matched by a tool), and in both (true positives, ). P/R/F1 are in percent; a precision or recall with an empty denominator counts as 100. The last two rows give the micro and macro averages of P/R/F1, and the summed counts and median times and sizes. is the query time, and and are the MetaphIR times without abstract constraint evaluation (over the features) and without the index. Web gives the downloaded size (Sz, in MB) and the time in the web application at 10 MB/s, with the full index and without abstract constraint evaluation (NC).
Datasets. Our main dataset is llvm-opt-benchmark [30], the corpus LLVM developers use to assess the applicability of optimizations. It holds the LLVM IR of 216 open-source projects in C, C++, and Rust, including the Linux kernel, FFmpeg, and OpenCV, in 68,843 modules. To obtain IR on which the rewrites can still apply, we built an LLVM with each of the twenty rewrites disabled and ran its O2 pipeline on every module. We drop the functions marked optnone (disabled optimizations), since the compiler does not optimize them. As a second dataset, we used the upstream InstCombine and InstSimplify test suites (1,912 files). We evaluate accuracy separately on the two datasets (RQ2). The index and timing measurements (RQ3) are one run over both, 4,771,730 functions and 11.9 GB of bitcode, of which the test suites are a negligible share.
Ground Truth. We extract each rewrite’s C++ matching logic verbatim into a standalone LLVM pass plugin, replacing the IR transformation with a logging call. The functions where this plugin logs a match form the ground truth , and the functions matched by a MetaphIR pattern form the predictions . We compare them as sets of (module, function) pairs and count the true positives . We report precision , recall , and their harmonic mean F1.
Machine. All experiments ran on a machine with an 80-core Neoverse-N1 CPU (aarch64), 502 GiB of memory, and Ubuntu 22.04, using 80 threads. Timings are the median of three runs.
RQ1: Expressiveness
The MetaphIR DSL expresses where the rewrite applies in each of the twenty PRs, aside from a single corner case in the test suites (§ 8.3). The 23 patterns are compact, totaling 75 instruction lines and 20 constraint lines, with at most six instructions per pattern. In contrast, daggrep checks only instruction opcodes, flags, literal constants, m_ImmConstant, and isGuaranteedNotToBePoison, and must drop single-use checks, comparison predicates, constant classes, and other constraints. As a result, it captures all preconditions of only 3 of the 23 patterns, namely PR 204809, PR 207564, and PR 213313, and even on PR 207564 it overmatches because it ignores types. It also requires 118 instruction lines against 75 in MetaphIR, because each alternative of a composite matcher must be written as a separate pattern file (see § C).
Beyond the evaluated rewrites, the standard library of MetaphIR reproduces 23 PatternMatch.h matchers that combine several instructions (such as m_AddLike, m_Signum, and m_LogicalAnd), all 23 constant classes, and 21 ValueTracking queries. To measure coverage beyond these rewrites, we counted the PatternMatch.h matchers and ValueTracking functions that InstCombine calls at LLVM commit 79b321b, the one we evaluated on. A matcher counts as covered if a pattern Table 6. Per-Rewrite Accuracy and Query Time (seconds) on llvm-opt-benchmark. , , and TP count the functions in the ground truth (where the C++ rewrite applies), in the prediction (matched by a tool), and in both (true positives, ). P/R/F1 are in percent; a precision or recall with an empty denominator counts as 100. The last two rows give the micro and macro averages of P/R/F1, and the summed counts and median times and sizes. is the query time, and and are the MetaphIR times without abstract constraint evaluation (over the features) and without the index. Web gives the downloaded size (Sz, in MB) and the time in the web application at 10 MB/s, with the full index and without abstract constraint evaluation (NC).
express it with an instruction, a flag, a constant class, a standard-library composite matcher, or a literal. InstCombine uses 206 distinct matchers, and MetaphIR covers 178 of them (86.4%), which account for 96.4% of the 7,022 calls. A match call combines several matchers, so it is expressible only if all of them are covered. By this measure, 2,129 of the 2,359 match calls (90.3%) are expressible. Of the 60 ValueTracking functions that InstCombine calls, MetaphIR covers 24 (40.0%), which account for 67.0% of the 437 calls. Supporting the remaining matchers and ValueTracking functions is primarily a matter of engineering effort rather than a design limitation, and is left to future work.
RQ1: The MetaphIR DSL expresses all twenty rewrites more compactly and completely than daggrep (75 vs. 118 instruction lines, whereas daggrep expresses only 3 of them), and covers 90.3% of InstCombine’s match expressions.
RQ2: Accuracy
We score the matches of MetaphIR and daggrep against the ground truth on the two datasets. llvm-opt-benchmark. As Table 6 shows, for all twenty rewrites, the patterns match where the rewrite applies. For six of these rewrites, no function in llvm-opt-benchmark triggers the rewrite, and MetaphIR correctly reports no match. For one of these six rewrites, PR 209322, daggrep cannot express the knownNegative constraint and reports 68,175 false positives.
Test Suites. The test suites consist of small, hand-written IR functions, which exercise forms that compiled real-world code rarely produces. On them, the patterns for the twenty rewrites reach 100.00 % precision and 99.29 % recall: no false positive and one false negative among 141 ground-truth functions. The false negative is a vector multiplication by the non-splat constant <i32 3, i32 5> in a test of PR 214376. The rewrite uses m_CheckedInt, which checks a custom C++ lambda predicate on every vector element. MetaphIR has no counterpart for it yet, so the pattern states the predicate as a constraint on a constant, which binds only to scalars and splat vectors.
Comparison with daggrep. For each rewrite, we use the closest daggrep pattern from § 8.2, which drops the conditions that daggrep cannot express. On llvm-opt-benchmark, daggrep reaches 100.00 % recall but only 4.29 % precision, with 86,123 false positives against 0 for MetaphIR. On the test suites, its precision is 17.10 %, against 100.00 % for MetaphIR.
RQ2: MetaphIR patterns match exactly where all twenty rewrites apply. Daggrep cannot state most preconditions, so it reports many false positives.
RQ3: Efficiency of the Index
We measure how many functions the index prunes, how long queries take with and without it, and what each part of the index contributes.
Index Cost. Building the index over the whole corpus takes 142 seconds (113 without value-tracking facts), so it can simply be rebuilt when the corpus changes.
Pruning. The index leaves few candidates. Per pattern, a median of 893 of 4,771,730 functions (0.019 %) remain after pruning, in a median of 361 modules (0.51 %). Even for the least selective pattern, PR 204927, only 17,996 functions (0.38 %) remain.
Query Time. Table 6 lists the time of each rewrite. With the index, every query we ran finished in 0.63–3.26 seconds on 80 threads, with a median of 1.27 seconds. Without it, a query scans all 4,771,730 functions and takes a median of 26.2 seconds, for a median per-rewrite speedup of 22× (8.0× to 57×). In our runs, both returned identical matches for every rewrite, confirming Corollary 6.5. Daggrep scans every module on every query. On the same 80 threads, its median query takes 32.5 seconds (20.7–86.7). The web application runs on fewer cores and fetches the IR of each candidate over the network, so it depends on the index even more: without the index, a single query may take over an hour, so we did not measure full scans there.
Ablation. We ran an ablation of abstract constraint evaluation on all patterns (column of Table 6). Without evaluating constraints in the abstract domain over the features, the median pattern keeps 2,167 functions instead of 893 (2.4×), and 20 of the 23 patterns keep more functions. On the command line, checking these extra candidates across 80 local cores raises the median time from 1.27 to 1.65 seconds. In the web application (column Web of Table 6), extra candidates must be fetched over the network: the median time grows from 42.3 to 54.7 seconds, and several rewrites download hundreds of megabytes more. The gain is largest when a pattern’s structure is unselective and its selectivity lies in its constraints, as in PR 209322 (duv i?bits ?x, ?y:knownNegative), which structurally matches any udiv instruction and relies entirely on :knownNegative to prune candidates: without constraint evaluation, candidates jump from 19 to 68,782, downloaded data from 852 to 3,564 MB, and query time from 90 to 383 seconds (4.3×).
RQ3: The index leaves a median of 0.019 % of the functions without losing a match, so a query over 4.8M functions on 80 threads takes a median of 1.27 seconds, faster than a full scan, against 32.5 seconds for daggrep. The index matters more in the web application, where it avoids downloading the IR of most functions.
Discussion
We discuss what MetaphIR matches and how its design extends.
Interaction Between Rewrites. MetaphIR finds where a rewrite applies to a static IR snapshot, whereas rewrites in a live compiler interact dynamically. Within a single InstCombine pass, earlier rewrites may transform matched instructions (preempting a target rewrite) or construct the exact IR shape it requires (enabling the target rewrite). The full O2 pipeline compounds these interactions by invoking InstCombine repeatedly as other passes transform the IR. Nevertheless, static queries remain predictive: measured against where the rewrites apply in O2, our patterns achieve 70.54 % precision and 79.56 % recall (macro-averaged across all twenty rewrites). Accounting for interactions within InstCombine itself is an interesting direction for future work: one could migrate InstCombine’s rewrites into MetaphIR to match patterns against the intermediate forms a function can take. Representing the function as an e-graph [24] could support this: the index could track the features of all equivalent forms within each e-class, allowing our abstract interpretation to apply.
Generality. The design is not specific to LLVM. Matching patterns with constraints and indexing functions by their features apply to other IRs. In particular, the abstract interpretation can be reused, since it needs only sites, facts, and abstract transformers for the operators.
Related Work
Languages for Peephole Optimizations. Alive [7] introduced a DSL for LLVM peephole optimizations written in LLVM IR syntax with preconditions and verified with an SMT solver; Alive2 [6] validates pairs of concrete IR functions. The MetaphIR DSL adopts the idea of IR-like patterns, but asks where an optimization applies rather than whether a rewrite is sound. Whereas Alive fixes instruction flags and comparison predicates (and limits preconditions to a fixed set of analyses such as isPowerOf2 and MaskedValueIsZero), MetaphIR lets patterns bind flags, predicates, and types as meta variables and refer to them in constraints. GCC’s match.pd [17, 18], MLIR’s PDLL [22] and pattern generation language [1], and Cranelift’s ISLE [16] serve similar matching and rewriting roles, but target in-compiler rewriting rather than providing an indexed search engine.
Pattern Matching and Indexing. Tree pattern matchers for instruction selection can be generated by tools such as iburg [3]. Theorem provers retrieve the instances of a term from large term sets with discrimination trees and path indexing [10] and compile subsumption checks into code trees [23]; databases filter graphs by indexed paths or frequent substructures before subgraph matching [15, 27]; code search tools index the syntactic features of a corpus to retrieve similar code [8], match wildcard patterns over syntax trees [9], or run declarative queries over a database extracted from the code [4]; and Bonsai [13] prunes subtrees of a data structure with conditions that interval analysis derives from the query and per-node metadata. Code search relies on syntactic structure, and Bonsai covers numeric and geometric predicates. MetaphIR instead handles the constraints of compiler peephole optimizations by abstract interpretation [2] over recorded facts, to prune functions while provably never discarding a match.
Conclusion
We presented MetaphIR, a system for matching LLVM peephole optimizations that combines a pattern DSL with an indexed search engine. Its single constraint evaluator runs both on concrete IR and, via sound abstract interpretation, on function features, enabling queries over 4.8M functions in seconds. MetaphIR enables developers to interactively assess and refine candidate rewrites at corpus scale before committing to a C++ implementation.
AI Use
We used Claude Code as a coding assistant, mainly for code refactoring, utility scripts, and enriching tool features. The authors designed the core language, the matching algorithm, and the abstract interpretation, and reviewed every AI-assisted change. No AI tool is part of the matching pipeline.
Data-Availability Statement
We open-source MetaphIR together with our evaluation results at [25]. The web application and its published index are also hosted online.
Proofs
Proof of Theorem 5.3 (Lowering Preserves Matches)
Theorem 5.3 (Lowering Preserves Matches). For every well-formed surface pattern and function ,
The proof proceeds by induction over lowering steps. We first define the measure that each step decreases, then show that a single step preserves matches, and finally combine the steps.
Termination. A composite matcher body can invoke only composite matchers defined before it, so definitions are not recursive. Let the depth of a composite matcher be one more than the largest depth of the composite matchers its branches invoke, and zero if they invoke none. Lowering removes one abstraction at a time. We write when removing one abstraction from yields the patterns , such as one per branch of an inlined composite matcher. Lowering then lowers each in turn, so . Each step either removes a metaflag, which adds no invocation, or replaces an invocation of depth by bodies whose invocations have depth below . So each step decreases the pair of the multiset of invocation depths and the number of metaflags, ordered lexicographically with the multiset order first, and lowering terminates.
Preservation. We show that for every step, case by case.
Metaflags. Lowering replaces a metaflag by its body as a constraint at the flagged instruction, which is the metaflag’s meaning (§ 5.5), and changes no node, so .
Composite matcher invocations. Let contain , and let inline the -th branch of that is compatible with : its parameters substituted by , its result node renamed to , and its other meta variables renamed apart. By definition, the invocation matches iff some compatible branch matches, so the equation holds once three points are checked. Compatibility: for a flag of , a branch either passes on to its result node, where then imposes exactly the invocation’s condition, or fixes to a Boolean . A fixed branch can match only if and , or and , or , or , in which case lowering adds the constraint , which holds exactly when ; so the dropped branches have no match, and the kept ones bind as the invocation’s meaning does. Hygiene: the renamed meta variables are disjoint from those of and of other invocations, so a match of may bind them freely, and restricting to removes them, as the invocation’s meaning restricts to the meta variables of . Or-self: an invocation with :o(N) marks each inlined root with , so by M-Self the root also matches what matches, which is the meaning of :o(N) on an invocation.
The :c mark on composite matchers. Lowering yields and with the invocation’s operands in either order, and a :c invocation matches iff it matches in one of the two orders.
Well-formedness keeps each step well-sorted, since the arguments have the sorts that its form requires.
Induction. By induction on this measure. A pattern without composite matcher invocations, and without metaflags other than the marks c and o(·), is already a core pattern, so and the theorem holds by definition. Otherwise, take a step , and assume the theorem for each . Then
The last step uses , since a step only adds renamed meta variables and constraints, so the two restrictions amount to one, and .
Proofs of Lemmas 6.1 and 6.2
Lemma 6.1 (Requirements are necessary). If , then .
Lemma 6.2 (Typings are sound). If , then some satisfies .
These proofs and the proof of Lemma 6.3 use one fact. Since a certain node has no o(·) mark, is derived by M-Inst or M-Comm, so the instruction that maps to, the image of , has the opcode of .
Lemma 6.1. Each requirement is witnessed by : a certain node’s image has its written flags and lacks its negated ones; a certain node with a certain operand node gives an edge between their images; a meta variable used by two certain nodes is a shared operand of their images.
Lemma 6.2. For each certain node, the signature of its image is among the signatures of and is consistent with ’s bindings of type-level meta variables. The function includes every consistent combination, so it includes restricted to the type-level meta variables of the certain nodes, . If the set exceeds the cap, the empty typing satisfies .
Proof of Lemma 6.3 (Abstract Evaluation Is Sound)
Lemma 6.3 (Abstract evaluation is sound). Let and . For every constraint of and every subexpression of , .
Fix and , and recall that for every . We prove by induction on .
Literals. We have .
Variables. If , then . Otherwise, if , take any . By the definition of sites, is operand of a certain node with opcode . By § A.2, the image of is an instruction with opcode . Without the c mark, , and is operand of the image. With the c mark, M-Comm may swap the operands, so is operand 0 or 1 of the image, and by the definition of sites (§ 6.3). A local name and its capture may also have the result site of their own certain node ; there, is the image of itself, an instruction with opcode . In every case, . Since this holds for every , . Otherwise the result is .
Operators. Let and by induction. If some , then , which lies in every concretization. Otherwise: (i) if every , then , and , or both are ; (ii) if , the soundness of abstract transformers gives ; (iii) otherwise the result is .
Conjunction. Let and .
: then , so .
: then , so the result is or , both in by induction.
and : by induction, . In concrete evaluation, either short-circuits to false (when ), evaluates to (when ), or fails with ; in all cases, .
Otherwise, , and .
Disjunction is dual, with deciding. When the left side is unknown and the right side is or , the result is , which is trivially sound.
Negation. If for a Boolean , then , so ; if , the result is ; otherwise .
The Matching Algorithm
Algorithm 1 computes . It matches the roots of one after another (line 3), each against every instruction of (line 6), and descends from each node to its operands (line 16). Matching extends a partial instantiation: an extension of keeps every binding of and binds more names. tries each rule of Figure 6 that applies (line 13), so the search explores every choice the rules allow. A node whose local name is an operand of two other nodes is reached twice. The second time, only checks that is the same value (line 10), so both uses refer to one instruction. After the roots, is , which then filters by Definition 5.2 (line 8).
Patterns of the Evaluation
Table 7 compares the MetaPIR pattern of each rewrite with the closest daggrep patterns (§ 8.2), and Figure 10 shows the largest MetaPIR pattern next to the C++ code it describes.

Figure 10. The Largest Pattern of the Evaluation, for PR 216470: with , a Rounding-up Division by . The operator is a logical right shift. The capture :?zxt binds the matched zext, or the lshr when :o skips the zext, so the last constraint applies the no-overflow check only when there is no zext, like NeedZext in the C++ code.
| MetaphIR | daggrep | |||||
| PR | Inst | Cons | Files | Inst | Exact | Dropped for daggrep |
| 204927 | 3 | 0 | 3 | 9 | single use | |
| 204928 | 3 | 0 | 3 | 9 | single use | |
| 205383 | 10 | 3 | 4 | 24 | bit-width equations; predicate | |
| 207462 | 7 | 4 | 2 | 7 | single use; ?c0 != 0; notUndef | |
| 207564 | 3 | 0 | 1 | 3 | ✓ | – |
| 209322 | 1 | 0 | 1 | 1 | knownNegative | |
| 210499 | 2 | 1 | 4 | 8 | the i1 result type | |
| 212132 | 12 | 0 | 2 | 12 | knownPowerOfTwo; single use; predicate | |
| 213313 | 5 | 0 | 2 | 6 | ✓ | – |
| 213709 | 3 | 4 | 2 | 6 | sgt(?bits, 1); predicate; single use | |
| 214376 | 2 | 0 | 1 | 2 | odd constant (any constant) | |
| 214381 | 3 | 2 | 1 | 3 | ?d != 0; predicate and constant ranges | |
| 214517 | 2 | 0 | 1 | 2 | single use | |
| 214541 | 2 | 1 | 1 | 2 | noOverflow; single use | |
| 215122 | 3 | 0 | 1 | 3 | lowBitMask (any constant); single use | |
| 215130 | 2 | 1 | 1 | 2 | ?c + ?negc == 0; single use | |
| 216046 | 1 | 1 | 1 | 1 | inSignedRange | |
| 216436 | 3 | 0 | 1 | 3 | lowBitMask (any constant); single use | |
| 216470 | 6 | 2 | 2 | 11 | lowBitMask, popcount, noOverflow; single use; predicate | |
| 204089 | 2 | 1 | 2 | 4 | ✓ | – |
Table 7. Per-Rewrite Patterns in MetaphIR and in daggrep. Inst and Cons count the instruction and constraint lines of the MetaphIR patterns (summing two patterns each for PR 205383, PR 207462, and PR 212132); Files counts the daggrep patterns written for the rewrite, and a check mark means that daggrep matches the same instruction structure as MetaphIR. The last column lists the conditions that daggrep cannot state and that we drop.
Algorithm 1: Matching a Core Pattern P against a Function F.
1 function Match(P, F)
2 Σ ← {∅} // partial instantiations
3 foreach root I of P do // assume roots have no o(·) mark
4 Σ′ ← ∅ // extensions that also match I
5 foreach σ in Σ do
6 foreach instruction u of F do Σ′ ← Σ′ ∪ MatchNode(I, u, σ)
7 Σ ← Σ′ // each σ replaced by its extensions
8 return {σ ∈ Σ | ⟦e⟧σ = true for every constraint e@ℓ of P} // Definition 5.2
9 function MatchNode(Iℓ, u, σ) // every way that node Iℓ matches u
10 if σ(ℓ) = u then return {σ}
11 else if σ(ℓ) is defined then return ∅
12 R ← ∅
13 foreach rule ρ of M-Inst, M-Comm, M-Self that applies to Iℓ do
14 if u satisfies the premises of ρ other than the operand matches then // operands are matched below
15 S ← {σ′}, where σ′ extends σ[ℓ ↦ u] with the bindings of these premises
16 foreach operand o of Iℓ and the value u′ that ρ matches it against do
17 S′ ← ∅
18 foreach σ″ in S do S′ ← S′ ∪ MatchOperand(o, u′, σ″)
19 S ← S′
20 R ← R ∪ S
21 return R
22 function MatchOperand(o, u, σ)
23 if o is a local name ℓ then return MatchNode(Iℓ, u, σ)
24 else if o is a meta variable x that u fits by sort, and σ(x) is undefined or σ(x) = u then return {σ[x ↦ u]}
25 else if o is a constant and o = u then return {σ}
26 return ∅
match(&I, m_c_Add(
m_ZExt(m_SpecificICmp(ICmpInst::ICMP_NE,
m_And(m_Value(X), m_LowBitMask(Mask)),
m_ZeroInt())),
m_OneUse(m_ZExtOrSelf(m_OneUse(
m_LShr(m_Deferred(X), m_APInt(ShAmt)))))))
&& Mask->popcount() == *ShAmt
&& (NeedZext ||
willNotOverflowUnsignedAdd(X, MaskC, I))
%and = and:c i?bits ?x, ?mask:lowBitMask
%cmp = icmp ne i?bits %and, 0
%ext = zext i1 %cmp to ?rty
%shr = lshr:s i?bits ?x, ?shift:apIntAllowPoison
%zext = zext:?zxt:s:o i?bits %shr to ?rty
%add = add:c ?rty %ext, %zext
;; popcount(?mask) == ?shift
;; opcode(?zxt) == "zext" || noOverflow("uadd", ?x, ?mask)References
- [1]Wesley Attrot, Luciano Zago, Marcio Pereira, Vinícius Couto, Hervé Yviquel, and Guido Araujo. 2026. A Pattern Generation Language for MLIR Compiler Matching and Rewriting. ACM Trans. Archit. Code Optim. 23, 1 (2026), 6:1–6:25. doi:10.1145/3777905DOI
- [2]Patrick Cousot and Radhia Cousot. 1977. Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL). 238–252. doi:10.1145/512970.512973DOI
- [3]Christopher W. Fraser, David R. Hanson, and Todd A. Proebsting. 1992. Engineering a simple, efficient code-generator generator. ACM Letters on Programming Languages and Systems (LOPLAS) 1, 3 (Sept. 1992), 213–226. doi:10.1145/151640.151642DOI
- [4]GitHub. 2026. CodeQL. https://codeql.github.com/. Accessed: 2026-10-29.
- [5]Chris Lattner and Vikram Adve. 2004. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. In Proceedings of the International Symposium on Code Generation and Optimization (CGO). 75–86. doi:10.1109/CGO.2004.1281665DOI
- [6]Nuno P. Lopes, Youngjoon Lee, Chung-Kil Hur, Zhengyang Liu, and John Regehr. 2021. Alive2: bounded translation validation for LLVM. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. ACM, Virtual Canada, 65–79. doi:10.1145/3453483.3454030DOI
- [7]Nuno P. Lopes, David Menendez, Santosh Nagarakatte, and John Regehr. 2015. Probably correct peephole optimizations with alive. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, Portland OR USA, 22–32. doi:10.1145/2737924.2737965
- [8]Sifei Luan, Di Yang, Celeste Barnaby, Koushik Sen, and Satish Chandra. 2019. Aroma: code recommendation via structural code search. Proceedings of the ACM on Programming Languages 3, OOPSLA (Oct. 2019), 152:1–152:28. doi:10.1145/3360578DOI
- [9]Gabriel Mautz, Wode Ni, Titus Barik, Alvin Cheung, and Sarah E. Chasins. 2024. Syntactic Code Search with Sequence-to-Tree Matching: Supporting Syntactic Search with Incomplete Code Fragments. Proceedings of the ACM on Programming Languages 8, PLDI (June 2024), 230:2051–230:2072. doi:10.1145/3565640DOI
- [10]William McCune. 1992. Experiments with discrimination-tree indexing and path indexing for term retrieval. Journal of Automated Reasoning 9, 2 (Oct. 1992), 147–167. doi:10.1007/BF00245458DOI
- [11]W. M. McKeeman. 1965. Peephole Optimization. Commun. ACM 8, 7 (1965), 443–444. doi:10.1145/364995.365000DOI
- [12]Manasij Mukherjee and John Regehr. 2024. Hydra: Generalizing Peephole Optimizations with Program Synthesis. Proceedings of the ACM on Programming Languages 8, OOPSLA1, Article 120 (2024). doi:10.1145/3649837DOI
- [13]Alexander J Root, Christophe Gyurgyik, Purvi Goel, Kayvon Fatahalian, Jonathan Ragan-Kelley, Andrew Adams, and Fredrik Kjolstad. 2026. Bonsai: Compiling Queries to Pruned Tree Traversals. Proceedings of the ACM on Programming Languages 10, PLDI (June 2026), 178:226–178:252. doi:10.1145/3808256DOI
- [14]Raimondas Sasnauskas, Yang Chen, Peter Collingbourne, Jeroen Ketema, Gratian Lup, Jubi Taneja, and John Regehr. 2018. Souper: A Synthesizing Superoptimizer. arXiv preprint arXiv:1711.04422.
- [15]Dennis Shasha, Jason T. L. Wang, and Rosalba Giugno. 2002. Algorithmics and applications of tree and graph searching. In Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (PODS ’02). Association for Computing Machinery, New York, NY, USA, 39–52. doi:10.1145/543613.543620DOI
- [16]The Bytecode Alliance. 2026. ISLE: Instruction-Selection / Lowering Expressions. https://github.com/bytecodealliance/wasmtime/tree/main/cranelift/isle. Accessed: 2026-10-28.
- [17]The GCC Developers. 2026. gcc/gcc/match.pd at master - gcc-mirror/gcc. https://github.com/gcc-mirror/gcc/blob/master/gcc/match.pd. Accessed: 2026-10-13.
- [18]The GCC Developers. 2026. Match and Simplify (GNU Compiler Collection (GCC) Internals). https://gcc.gnu.org/onlinedocs/gccint/Match-and-Simplify.html. Accessed: 2026-10-13.
- [19]The LLVM Project. 2026. LLVM InstCombine Pass. https://github.com/llvm/llvm-project/tree/main/llvm/lib/Transforms/InstCombine. Accessed: 2026-10-13.
- [20]The LLVM Project. 2026. LLVM Language Reference Manual: Poison Values. https://llvm.org/docs/LangRef.html#poison-values. Accessed: 2026-11-11.
- [21]The LLVM Project. 2026. LLVM PatternMatch.h: A Simple and Efficient Mechanism for Performing General Tree-Based Pattern Matches on the LLVM IR. https://github.com/llvm/llvm-project/blob/main/llvm/include/llvm/IR/PatternMatch.h. Accessed: 2026-10-13.
- [22]The MLIR Project. 2026. PDLL - PDL Language - MLIR. https://mlir.llvm.org/docs/PDLL/. Accessed: 2026-10-13.
- [23]Andrei Voronkov. 1995. The anatomy of vampire: Implementing bottom-up procedures with code trees. Journal of Automated Reasoning 15, 2 (1995), 237–265. doi:10.1007/BF00881918
- [24]Max Willsey, Chandrakana Nandi, Yisu Remy Wang, Oliver Flatt, Zachary Tatlock, and Pavel Panchekha. 2021. egg: Fast and Extensible Equality Saturation. Proceedings of the ACM on Programming Languages 5, POPL (Jan. 2021), 1–29. doi:10.1145/3434304 arXiv:2004.03082 [cs.PL].DOI
- [25]Hongxu Xu, Xintong Zhou, Chunhao Liao, and Chengnian Sun. 2026. MetaphlR: Artifact. https://github.com/xuhongxu96/metaphlr. Accessed: 2026-11-18.
- [26]Zhenyang Xu, Hongxu Xu, Yongqiang Tian, Xintong Zhou, and Chengnian Sun. 2026. LPO: Discovering Missed Peephole Optimizations with Large Language Models. In Proceedings of the 31st ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). doi:10.1145/3779212.3790184DOI
- [27]Xifeng Yan, Philip S. Yu, and Jiawei Han. 2004. Graph indexing: a frequent structure-based approach. In Proceedings of the 2004 ACM SIGMOD international conference on Management of data (SIGMOD ’04). Association for Computing Machinery, New York, NY, USA, 335–346. doi:10.1145/1007568.1007607DOI
- [28]Yingwei Zheng. 2026. dagrep.cpp: A DAG Pattern Scanner for LLVM IR. https://github.com/dtcxzyw/llvm-opt-benchmark/blob/main/daggrep.cpp. Accessed: 2026-10-13.
- [29]Yingwei Zheng. 2026. Grep Y - umin(X, Y) (llvm-opt-benchmark Issue #3123). https://github.com/dtcxzyw/llvm-opt-benchmark/issues/3123. Accessed: 2026-10-13.
- [30]Yingwei Zheng. 2026. llvm-opt-benchmark: LLVM Optimization Benchmark. https://github.com/dtcxzyw/llvm-opt-benchmark. Accessed: 2026-10-13.
- [31]Yingwei Zheng. 2026. llvm-opt-benchmark-nightly: GitHub Actions Runs. https://github.com/dtcxzyw/llvm-opt-benchmark-nightly/actions. Accessed: 2026-11-01.