betaFeedback

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 ⟫ log⁡2C\log_{2} C, 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 srcsrc as a query and finds instructions with the same structure across the corpus. However, daggrep relies purely on structural matching and cannot express preconditions (prepre). For example, to search for the division rewrite above, a structural query can only match division by any constant divisor; ignoring the precondition isPowerOf2(C)isPowerOf2(C), daggrep overmatches on instructions such as x/3x/3 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 srcsrc and prepre in a concise, declarative notation that developers can easily write. This is difficult because rewrites in InstCombine are not simple syntactic templates: srcsrc abstracts over types, bit widths, instruction flags (e.g., nsw), operand commutativity, and interchangeable opcodes (e.g., accepting either add or or disjoint), while prepre 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 srcsrc and prepre of a rewrite: srcsrc is LLVM IR with holes (meta variables, highlighted in yellow), which MetaphIR matches structurally, and prepre 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.

A MetaphIR Pattern

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 (a/ub)/uc(a /_{u} b) /_{u} c with two unsigned divisions; because the llvm.assume calls bound both divisors below 15, their product (≤196\le196) cannot overflow an i8, allowing tgt to compute a/u(b⋅c)a /_{u} (b \cdot c) 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 b⋅cb \cdot c cannot overflow.

Source and target IR and C++ rewrite in InstCombine
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 (aa /ᵤ bb) /ᵤ cc into aa /ᵤ (b⋅cb \cdot c) when the inner division has one use and b⋅cb \cdot c 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 Y∗Op1Y * Op1 (%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 Y∗Op1Y * Op1 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 Y<216Y < 2^{16}; their 32-bit unsigned product is therefore below 7⋅216<2327 \cdot2^{16} < 2^{32} 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,

The running example from the rewrite of PR 214541, showing five stages from lowering through constraint evaluation

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++)MetaphIRMeaning
m_Value(X), m_Deferred(X)?x, its second occurrenceany value; the same value
m_Specific(V)%vthe value of a pattern instruction
m_c_Add(A, B)add:c ?ty A, Bcommutative matching
m_OneUse(P)P:sa single use
m_ZExtOrSelf(P)zext:o ...the instruction or its operand
m_NSWAdd, “no nsw”, a saved flagadd nsw, add !nsw, add nsw:?fflag present, absent, captured
m_APInt(C), m_Power2(C)?c:apInt, ?c:power2constant classes
m_AddLike, m_Shift, m_SignumaddLike, shift, signumcomposite matchers
isKnownNonZero(X, Q)isKnownNonZero(?x)value tracking at the context
C->popcount() == *Spopcount(?c) == ?sa 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.

SortExampleBinds
Valadd i8 ?x, ?yan instruction, argument, constant, or global
Natadd i?bits ..., < ?n x i32>a bit width, count, or index
Typeadd ?ty ...an LLVM type, such as i32
Predicmp ?pred i32 ...a comparison predicate
Booladd nsw:?f ...whether a flag is present
Instadd:?instr ...the matched instruction
BBbr label ?bba basic block
Fncall ?f(...)a callee
Intrcall @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 ?p in icmp ?p. The constraint isSigned(?p) accepts only signed predicates such as slt and sgt, and swappedPredicate checks whether two comparisons are the same with their operands swapped. These mirror the CmpInst methods isSigned and getSwappedPredicate in C++ rewrites.

  • Value tracking: 21 queries that call LLVM’s ValueTracking analyses, such as isKnownNonZero, knownBits, noOverflow, and inUnsignedRange. Each query’s context instruction (§ 2) defaults to the instruction written immediately before the constraint (e.g., %udiv2 for noOverflow in 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 + 1 never 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.

FormSignatureExample Invocationstdlib.mpir Matchers
Unary(?ty ?x)neg nsw i32 ?aneg, signum, fnegLike
Binary(?ty ?x, ?y)addLike nsw i32 ?a, ?baddLike, shift, idiv
Cast(?ty1 ?x to ?ty2)zextOrSext i8 ?a to i32zextOrSext, sextLike, itofp
Nary(?ty1 ?x1, ?ty2 ?x2, ...)selectEq i8 ?x, i32 ?a, i32 ?bselectEq, 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 PP is a sequence of instruction nodes and a sequence of constraints. An operand ℓ\ell 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.

Abstract syntax of the core language

Figure 4. Abstract Syntax of the Core Language. A⇀BA \rightharpoonup B holds the partial maps from AA to BB, square brackets mark optional parts, ⟨η×τ⟩\langle\eta\times\tau\rangle is a vector type, and e@ℓe@\ell is a constraint ee with context instruction ℓ\ell.

Concrete and abstract syntax of a core pattern

Figure 5. Concrete and Abstract Syntax of a Core Pattern.

Instruction Nodes. Each instruction node II defines a local name ℓ\ell and has an opcode opop, a flag specification φ\varphi, keyed arguments ψ\psi, an optional type argument τ0\tau_0, and typed operands τi oi\tau_i\ o_i. A node may also bind a meta variable to the instruction that the node matches (as xIx_I) and require that instruction to lie in a given basic block (in xbbx_{bb}). 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 φ\varphi 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 μ\mu hold the structural metaflags: c for commutative matching, and o(oo) for a node that may match the operand oo instead.

Sorts and Well-Formedness

One set of sorts classifies both meta variables and constraint expressions:

ς::=Opd∣Val∣Inst∣Fn∣Int∣Nat∣Bool∣Str∣Pred∣Intr∣BB∣Type∣BV∣ς[ ].\varsigma::= \mathop{\mathrm{Opd}} \mid\mathop{\mathrm{Val}} \mid\mathop{\mathrm{Inst}} \mid\mathop{\mathrm{Fn}} \mid\mathop{\mathrm{Int}} \mid\mathop{\mathrm{Nat}} \mid\mathop{\mathrm{Bool}} \mid\mathop{\mathrm{Str}} \mid\mathop{\mathrm{Pred}} \mid\mathop{\mathrm{Intr}} \mid\mathop{\mathrm{BB}} \mid\mathop{\mathrm{Type}} \mid\mathop{\mathrm{BV}} \mid\varsigma[\,].

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 ς⊑ς′\varsigma\sqsubseteq\varsigma' means that every object of sort ς\varsigma is also one of sort ς′\varsigma', so such an object may be used wherever ς′\varsigma' is expected. The order is generated by

Inst,Fn⊑Val⊑OpdBool⊑Nat⊑OpdNat⊑IntPred,Intr⊑Str.\mathop{\mathrm{Inst}},\mathop{\mathrm{Fn}} \sqsubseteq\mathop{\mathrm{Val}} \sqsubseteq\mathop{\mathrm{Opd}} \qquad \mathop{\mathrm{Bool}} \sqsubseteq\mathop{\mathrm{Nat}} \sqsubseteq\mathop{\mathrm{Opd}} \qquad \mathop{\mathrm{Nat}} \sqsubseteq\mathop{\mathrm{Int}} \qquad \mathop{\mathrm{Pred}},\mathop{\mathrm{Intr}} \sqsubseteq\mathop{\mathrm{Str}}.

Sorts of Meta Variables. A sort environment Γ\Gamma 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, Γ\Gamma gives the meta variable the default sort Val.

Sorts of Constraints. Each built-in operator has a signature of the form f:ς1×⋯×ςn→ςf : \varsigma_1 \times\cdots\times\varsigma_n \to\varsigma, such as noOverflow : Str ×\times Val ×\times Val →\to Bool. An argument is accepted if its sort lies below a sort that coerces to the parameter’s:

S-VarS-LocS-Op
Γ⊢x:Γ(x)\Gamma\vdash x : \Gamma(x)Γ⊢ℓ:Inst\Gamma\vdash\ell: \mathrm{Inst}f:ς1×⋯×ςn→ς∀i. Γ⊢ei:ςi′∧ςi′⊑ςif : \varsigma_1 \times\cdots\times\varsigma_n \to\varsigma\qquad\forall i.\ \Gamma\vdash e_i : \varsigma_i' \land\varsigma_i' \sqsubseteq\varsigma_i
Γ⊢f(e1,…,en):ς\Gamma\vdash f(e_1,\ldots,e_n) : \varsigma

Binary operators such as + are just operators in F\mathcal{F} written infix. The coercion relation ⊑\sqsubseteq is reflexive and contains Int⊑Bool\mathrm{Int} \sqsubseteq\mathrm{Bool}, Val⊑Int\mathrm{Val} \sqsubseteq\mathrm{Int}, Type⊑Str\mathrm{Type} \sqsubseteq\mathrm{Str}, Val⊑Str\mathrm{Val} \sqsubseteq\mathrm{Str}, BB⊑Val\mathrm{BB} \sqsubseteq\mathrm{Val}, Type[ ]⊑Str[ ]\mathrm{Type}[\,] \sqsubseteq\mathrm{Str}[\,], and Val[ ]⊑Str[ ]\mathrm{Val}[\,] \sqsubseteq\mathrm{Str}[\,]. A coercion c_ς\mathrm{c}\_{\varsigma} converts a value to sort ς\varsigma, or err if no coercion applies or the conversion fails on cc. For example, Val ⊑\sqsubseteq 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 φ\varphi is supported by opop, 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.

σ(x)=^u\sigma(x) \mathrel{\widehat{=}} u
σ⊢x⇝u\sigma\vdash x \rightsquigarrow u
k=^uk \mathrel{\widehat{=}} u
σ⊢k⇝u\sigma\vdash k \rightsquigarrow u
σ(ℓ)=u\sigma(\ell)=u
σ⊢ℓ⇝u\sigma\vdash\ell\rightsquigarrow u
opc⁡(u)=op⁡σ,flags⁡(u)⊨φ∀κ∈dom⁡(ψ). σ(ψ(κ))=keys⁡(u)(κ)σ(τ0)=^tyarg⁡(u)ops⁡(u)=(u1,…,un)∀i. σ(τi)=^ty⁡(ui)∧σ⊢oi⇝uiσ(xI)=uσ(xbb)=blk⁡(u)\begin{aligned} \operatorname{opc}(u)&=\operatorname{op} & \sigma,\operatorname{flags}(u)&\models\varphi& \forall\kappa\in\operatorname{dom}(\psi).\ \sigma(\psi(\kappa))&=\operatorname{keys}(u)(\kappa) & \sigma(\tau_0)&\mathrel{\widehat{=}}\operatorname{tyarg}(u)\\ \operatorname{ops}(u)&=(u_1,\ldots,u_n) & \forall i.\ \sigma(\tau_i)&\mathrel{\widehat{=}}\operatorname{ty}(u_i)\land\sigma\vdash o_i\rightsquigarrow u_i & \sigma(x_I)&=u & \sigma(x_{bb})&=\operatorname{blk}(u) \end{aligned}
σ⊢op⁡φ,ψ τ0(τ1o1,…,τnon) as xI in xbb⇝u\sigma\vdash\operatorname{op}_{\varphi,\psi}\ \tau_0(\tau_1o_1,\ldots,\tau_no_n)\ \text{as }x_I\ \text{in }x_{bb}\rightsquigarrow u
σ⊢op⁡φ,ψ′ τ0(τ2o2,τ1o1) as xI in xbb⇝u\sigma\vdash\operatorname{op}_{\varphi,\psi'}\ \tau_0(\tau_2o_2,\tau_1o_1)\ \text{as }x_I\ \text{in }x_{bb}\rightsquigarrow u
σ⊢op⁡φ,ψ∪{c} τ0(τ1o1,τ2o2) as xI in xbb⇝u\sigma\vdash\operatorname{op}_{\varphi,\psi\cup\{c\}}\ \tau_0(\tau_1o_1,\tau_2o_2)\ \text{as }x_I\ \text{in }x_{bb}\rightsquigarrow u
o(o)∈μo(o)\in\mu
σ⊢o⇝u\sigma\vdash o\rightsquigarrow u
u is an instructionσ(xI)=uu\text{ is an instruction}\qquad\sigma(x_I)=u
σ⊢op⁡φ,ψ τ0(τ1o1,…,τnon) as xI⇝u\sigma\vdash\operatorname{op}_{\varphi,\psi}\ \tau_0(\tau_1o_1,\ldots,\tau_no_n)\ \text{as }x_I\rightsquigarrow u
∀fl∈dom⁡(φ).(φ(fl)=+⇒fl∈S)∧(φ(fl)=−⇒fl∉S)∧(φ(fl)=x⇒(σ(x)=true⇔fl∈S))\forall fl\in\operatorname{dom}(\varphi).\quad \bigl(\varphi(fl)=+\Rightarrow fl\in S\bigr)\land \bigl(\varphi(fl)=-\Rightarrow fl\notin S\bigr)\land \bigl(\varphi(fl)=x\Rightarrow(\sigma(x)=\text{true}\Leftrightarrow fl\in S)\bigr)
σ,S⊨φ\sigma,S\models\varphi

Targets and Structural Matching

Structural matching is the judgment σ⊢I⇝u\sigma\vdash I\rightsquigarrow u: the instruction node II of a core pattern matches the value uu of an LLVM IR function under the instantiation σ\sigma.

Targets. A target is an IR function FF, which we view as a graph whose nodes are the values of FF (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.

FunctionGivesExample
opc⁡(u)\operatorname{opc}(u)the opcodeicmp
flags⁡(u)\operatorname{flags}(u)the set of present flags{samesign}\{\text{samesign}\}
keys⁡(u)\operatorname{keys}(u)the keyed arguments, such as a predicate or an alignment{pred↦ult}\{\text{pred} \mapsto\text{ult}\}
tyarg⁡(u)\operatorname{tyarg}(u)the type argument, usually the result type, such as the destination type of a casti1
blk⁡(u)\operatorname{blk}(u)the basic block%entry
ops⁡(u)\operatorname{ops}(u)the operands (u1,…,un)(u_1,\ldots,u_n)(%a,%b)(\%a,\%b)
ty⁡(ui)\operatorname{ty}(u_i)the type of the iith operandi32

Table 4. Functions on an Instruction uu. The examples are for u=%c=icmp samesign ult i32 %a, %bu = \%c = \texttt{icmp samesign ult i32 \%a, \%b} in block \texttt{%entry}.

Instantiations. An instantiation σ\sigma maps each local name of PP to a value of FF 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 σ⊢I⇝u\sigma\vdash I\rightsquigarrow u. 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, σ,flags⁡(u)⊨φ\sigma,\operatorname{flags}(u)\models\varphi, 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

Structural matching rules

Figure 6. Structural Matching. The type argument (τ0)(\tau_0), the instruction binding (as xIx_I), and the block binding (in xbbx_{bb}) are optional; when they are omitted, the rules drop the premises that check them. In M-Var, =^\widehat{=} also lets a Nat meta variable match the constant with its value. In M-Comm, c∉μc\notin\mu, and ψ′=ψ\psi'=\psi unless op⁡\operatorname{op} is a comparison, which swaps its predicate with the operands (a predicate meta variable is swapped after it is bound). We write σ(k)=k\sigma(k)=k for a constant kk. The relation k=^uk\mathrel{\widehat{=}}u compares integers at the value’s width and also accepts a splat vector of kk; type equality likewise accepts a vector of the scalar type.

⟦k⟧σ=k⟦x⟧σ=σ(x)⟦ℓ⟧σ=σ(ℓ)⟦!e⟧σ=¬⟦e⟧σ↓Bool if ⟦e⟧σ↓Bool≠err, else err⟦f(e1,…,en)⟧σ=fF,σ(ℓc)(⟦e1⟧σ↓ς1,…,⟦en⟧σ↓ςn) if no ⟦ei⟧σ↓ςi=err, else err⟦e1==e2⟧σ={⟦e1⟧σ=⟦e2⟧σif ⟦e1⟧σ,⟦e2⟧σ∈C have the same sort⟦e1⟧σ↓ς=⟦e2⟧σ↓ςelse if ⟦e1⟧σ↓ς,⟦e2⟧σ↓ς≠err for some ς∈{Int,Str,Str[]}errotherwise⟦e1&&e2⟧σ={falseif ⟦e1⟧σ↓Bool=false⟦e2⟧σ↓Boolif ⟦e1⟧σ↓Bool=trueerrotherwise⟦e1∣∣e2⟧σ={trueif ⟦e1⟧σ↓Bool=true⟦e2⟧σ↓Boolif ⟦e1⟧σ↓Bool=falseerrotherwise\begin{aligned} \llbracket k \rrbracket_\sigma&= k \qquad\llbracket x \rrbracket_\sigma= \sigma(x) \qquad\llbracket\ell\rrbracket_\sigma= \sigma(\ell) \qquad\llbracket!e \rrbracket_\sigma= \neg\llbracket e \rrbracket_\sigma\downarrow_{\mathrm{Bool}}\ \text{if }\llbracket e \rrbracket_\sigma\downarrow_{\mathrm{Bool}} \ne\mathrm{err},\ \text{else err}\\ \llbracket f(e_1,\ldots,e_n) \rrbracket_\sigma&= f_{F,\sigma(\ell_c)}(\llbracket e_1 \rrbracket_\sigma\downarrow_{\varsigma_1},\ldots,\llbracket e_n \rrbracket_\sigma\downarrow_{\varsigma_n})\ \text{if no }\llbracket e_i \rrbracket_\sigma\downarrow_{\varsigma_i}=\mathrm{err},\ \text{else err}\\ \llbracket e_1 == e_2 \rrbracket_\sigma&= \begin{cases} \llbracket e_1 \rrbracket_\sigma= \llbracket e_2 \rrbracket_\sigma& \text{if }\llbracket e_1 \rrbracket_\sigma,\llbracket e_2 \rrbracket_\sigma\in\mathbb{C}\text{ have the same sort}\\ \llbracket e_1 \rrbracket_\sigma\downarrow_{\varsigma} = \llbracket e_2 \rrbracket_\sigma\downarrow_{\varsigma} & \text{else if }\llbracket e_1 \rrbracket_\sigma\downarrow_{\varsigma},\llbracket e_2 \rrbracket_\sigma\downarrow_{\varsigma} \ne\mathrm{err}\text{ for some }\varsigma\in\{\mathrm{Int},\mathrm{Str},\mathrm{Str}[]\}\\ \mathrm{err} & \text{otherwise} \end{cases}\\ \llbracket e_1 \mathbin{\&\&} e_2 \rrbracket_\sigma&= \begin{cases} \mathrm{false} & \text{if }\llbracket e_1 \rrbracket_\sigma\downarrow_{\mathrm{Bool}}=\mathrm{false}\\ \llbracket e_2 \rrbracket_\sigma\downarrow_{\mathrm{Bool}} & \text{if }\llbracket e_1 \rrbracket_\sigma\downarrow_{\mathrm{Bool}}=\mathrm{true}\\ \mathrm{err} & \text{otherwise} \end{cases} \qquad \llbracket e_1 \mathbin{||} e_2 \rrbracket_\sigma= \begin{cases} \mathrm{true} & \text{if }\llbracket e_1 \rrbracket_\sigma\downarrow_{\mathrm{Bool}}=\mathrm{true}\\ \llbracket e_2 \rrbracket_\sigma\downarrow_{\mathrm{Bool}} & \text{if }\llbracket e_1 \rrbracket_\sigma\downarrow_{\mathrm{Bool}}=\mathrm{false}\\ \mathrm{err} & \text{otherwise} \end{cases} \end{aligned}

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(oo) match a value whenever oo matches it.

Definition 5.1 (Structural matches). Let FF be a target and PP a core pattern. Let L(P)\mathcal{L}(P) and X(P)\mathcal{X}(P) be the local names and the meta variables of PP, and let IℓI_\ell be the node of PP that defines the local name ℓ\ell. The set Match⁡struct(P,F)\operatorname{Match}_{\mathrm{struct}}(P,F) holds the instantiations σ\sigma with dom⁡(σ)=L(P)∪X(P)\operatorname{dom}(\sigma)=\mathcal{L}(P)\cup\mathcal{X}(P) such that σ⊢Iℓ⇝σ(ℓ)\sigma\vdash I_\ell\rightsquigarrow\sigma(\ell) for every ℓ∈L(P)\ell\in\mathcal{L}(P).

Constraint Semantics

Constraints evaluate to concrete values C\mathbb{C}. Evaluation can fail, for example on division by zero or on arithmetic over a non-constant value, so the result lies in Cerr=C⊎{err}\mathbb{C}_{\mathrm{err}}=\mathbb{C}\uplus\{\mathrm{err}\}. Each built-in operator ff has a concrete semantics fF,u:Cn→Cerrf_{F,u}:\mathbb{C}^{n}\to\mathbb{C}_{\mathrm{err}}, where FF is the target function and uu is the context instruction, as some operators rely on information from them. Figure 7 gives the semantics ⟦e⟧σ\llbracket e \rrbracket_\sigma.

Concrete semantics of constraints

Figure 7. Concrete Semantics of Constraints for e@ℓce@\ell_c. The target function FF and the context instruction ℓc\ell_c are fixed and left implicit in ⟦e⟧σ\llbracket e \rrbracket_\sigma. Each argument is coerced to the parameter sort of its operator; ςi\varsigma_i is the ii-th parameter sort of ff, and c↓ςc\downarrow_{\varsigma} is the coercion of cc to ς\varsigma (§ 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 PP in a function FF are its structural matches under which every constraint evaluates to true:

Match⁡(P,F)={σ∈Match⁡struct(P,F)∣⟦e⟧σ=true for every constraint e@ℓ of P}.\operatorname{Match}(P,F)=\{\sigma\in\operatorname{Match}_{\mathrm{struct}}(P,F)\mid\llbracket e\rrbracket_\sigma=\mathrm{true}\text{ for every constraint }e@\ell\text{ of }P\}.

Lowering

A surface pattern Pˉ\bar{P} extends the core language with definitions of metaflags and composite matchers. A metaflag gg with arguments a⃗\vec{a} on an operand or instruction xx, written x:g(a⃗)x:g(\vec{a}), matches uu when two conditions hold: xx matches uu, and the body of gg evaluates to true once the first parameter of gg is substituted by xx and the others by a⃗\vec{a}. A composite matcher invocation ℓ=mφμ(a⃗)\ell=m_{\varphi}^{\mu}(\vec{a}) is an instruction node whose opcode is a composite matcher mm, with arguments a⃗\vec{a}. It matches when some branch of mm that is compatible with φ\varphi matches after substituting a⃗\vec{a} for the parameters, and its marks μ\mu act as on built-in nodes. We write Match⁡(Pˉ,F)\operatorname{Match}(\bar{P},F) for the resulting set of instantiations, restricted to the meta variables that Pˉ\bar{P} itself declares. The other meta variables of the branch are local to the invocation. The function Lower⁡(Pˉ)\operatorname{Lower}(\bar{P}) 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 o(oN)o(o_N), where oNo_N is the invocation’s NN-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 o(⋅)o(\cdot) 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 Pˉ\bar{P} and function FF, Match⁡(Pˉ,F)={σ∣X(Pˉ)∣P∈Lower⁡(Pˉ), σ∈Match⁡(P,F)}\operatorname{Match}(\bar{P},F)=\{\sigma|_{X(\bar{P})}\mid P\in\operatorname{Lower}(\bar{P}),\ \sigma\in\operatorname{Match}(P,F)\}.

Note that σ∣X(Pˉ)\sigma|_{X(\bar{P})} restricts σ\sigma to the meta variables X(Pˉ)X(\bar{P}) of Pˉ\bar{P}, because the core patterns may bind meta variables that Pˉ\bar{P} 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 Match⁡(P,F)\operatorname{Match}(P,F) can be non-empty from the features of FF stored in an index (Stage ③ of Figure 3), without reading the IR of FF, and we prove that this never loses a match. Throughout this section, we fix an IR function FF and leave it implicit in notation such as Vals⁡(op,J)\operatorname{Vals}(op,J).

Features of an IR Function

The features α(F)\alpha(F), an abstraction of FF, record which values occur where, which facts hold for them, and how the instructions of FF connect (Figure 8 shows an example).

Features of a Function and Their Use for Pruning

Figure 8. Features of a Function and Their Use for Pruning.

Sites. Features describe values by where they occur. A site s=(op,J)s=(op,J) is an opcode opop and a set of slots JJ, each an operand position or res for the result. The values of FF at ss are

Vals⁡(op,J)={ops⁡(u)j∣u∈F, opc⁡(u)=op, j∈J}∪{u∣u∈F, opc⁡(u)=op, res⁡∈J}.\operatorname{Vals}(op,J)=\{\operatorname{ops}(u)_j\mid u\in F,\ \operatorname{opc}(u)=op,\ j\in J\}\cup\{u\mid u\in F,\ \operatorname{opc}(u)=op,\ \operatorname{res}\in J\}.

We write (op,j)(op,j) for (op,{j})(op,\{j\}) for simplicity. In Figure 8a, the value at (urem,1)(\text{urem},1) is the constant 2, the value at (urem,0)(\text{urem},0) is the argument %x, and the value at (add,0)(\text{add},0) is %r.

Facts. A fact is a unary predicate pp 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:

Facts⁡(op,J)={p∣∃w∈Vals⁡(op,J). p(w)=true}.(1)\operatorname{Facts}(op,J)=\{p\mid\exists w\in\operatorname{Vals}(op,J).\ p(w)=\text{true}\}. \tag*{(1)}

In Figure 8a, (urem,1)(\text{urem},1) records literal 2, isPower2, and isKnownNonZero, but no isZero (Figure 8b). Pruning relies on the missing facts: if a pattern requires a value with pp at a site and pp 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 pp such as isKnownNonZero depends on a context instruction, so p∈Facts⁡(op,j)p\in\operatorname{Facts}(op,j) if pp holds for ops⁡(u)j\operatorname{ops}(u)_j at the context uu itself, for some uu with opcode opop. In Figure 8a, value tracking knows that 2 is non-zero at %r, so (urem,1)(\text{urem},1) 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, α(F)\alpha(F) also records the opcodes present in FF, the edges (op1,op2)(op_1,op_2) such that an instruction with opcode op1op_1 uses one with opcode op2op_2, the siblings (op1,op2)(op_1,op_2) 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 PP’s structural requirements specify the structural features a function must have to match it. The certain nodes of PP are the nodes without an o(⋅)\mathrm{o}(\cdot) mark, which every match maps to an instruction with their own opcode. The structural requirements Req⁡(P)\operatorname{Req}(P) of PP are ① the opcode of each certain node, ② the edge (op1,op2)(op_{1}, op_{2}) whenever a certain node with opcode op1op_{1} has a certain operand node with opcode op2op_{2}, ③ the sibling pair (op1,op2)(op_{1}, op_{2}) 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 PP names. The second query in Figure 8c requires the edge (urem,add)(\mathrm{urem}, \mathrm{add}), which Figure 8b lacks, so ff is ruled out for this query by Lemma 6.1 below.

Lemma 6.1 (Requirements are necessary). If Match⁡(P,F)≠∅\operatorname{Match}(P,F) \ne\varnothing, then Req⁡(P)⊆α(F)\operatorname{Req}(P) \subseteq\alpha(F).

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 Typings⁡(P)\operatorname{Typings}(P) holds the typings of PP that the partial signatures in α(F)\alpha(F) 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 α(F)\alpha(F), the number of combinations can grow exponentially with the number of nodes; MetaphIR therefore caps Typings⁡(P)\operatorname{Typings}(P) at 256 typings. Above the cap, MetaphIR uses the empty typing.

Lemma 6.2 (Typings are sound). If σ∈Match⁡(P,F)\sigma\in\operatorname{Match}(P,F), then some θ∈Typings⁡(P)\theta\in\operatorname{Typings}(P) satisfies θ⊆σ\theta\subseteq\sigma.

Evaluating Constraints over an Abstract Domain

Constraints share a single evaluator parameterized by a value domain: Stage ⑤ runs it on concrete IR values ([ ⁣[⋅] ⁣]σ[\![\cdot]\!]_{\sigma}, 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.

The Index Domain

Figure 9. The Index Domain. In c, we omit the subscript θ\theta, local names evaluate as meta variables do, and constants are coerced to Bool as in Figure 7.

Abstract Values. Fix a core pattern PP, a function FF, and a typing θ\theta. An abstract value describes the results that an expression can have across all matches of PP in FF that agree with θ\theta. Figure 9a lists the four kinds of abstract values, which form the abstract domain D^\hat{D}, and their concretization γ:D^→D\gamma: \hat{D} \to D into the concrete domain D=P(Cerr)D = \mathcal{P}(C_{\mathrm{err}}).

Sites of a Meta Variable or Local Name. The set sites(xx) holds the sites where a meta variable or local name xx certainly occurs in every match. If xx is operand jj of a certain node with opcode op, then (op,{j})∈sites⁡(x)(\mathrm{op}, \{j\}) \in\operatorname{sites}(x), or (op,{0,1})(\mathrm{op}, \{0, 1\}) when the node has the c mark, since xx may be in either slot. A local name ℓ\ell and its capture get the site (op,{res})(\mathrm{op}, \{\mathrm{res}\}) if their node is certain, and also the site of ℓ\ell as an operand of each certain user. For example, in %r = add i32 ?a, 1 and %s = urem i32 %r, ?c, sites⁡(%r)={(add,{res}),(urem,{0})}\operatorname{sites}(\%r) = \{(\mathrm{add}, \{\mathrm{res}\}), (\mathrm{urem}, \{0\})\}. If add has mark :o, sites⁡(%r)\operatorname{sites}(\%r) loses (add,{res})(\mathrm{add}, \{\mathrm{res}\}).

Abstract Semantics. The abstract semantics ⟦e⟧θ\llbracket e \rrbracket_\theta evaluates a constraint ee in the index domain under the typing θ\theta (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 f^\hat{f}. 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 const⁡(false)\operatorname{const}(\mathrm{false}) only when a recorded feature rules out every value, and ⊤\top otherwise. For a fact predicate pp (including x=nx = n for a small literal nn), its abstract transformer p^\hat{p} gives p^(at⁡(S))=const⁡(false)\hat{p}(\operatorname{at}(S)) = \operatorname{const}(\mathrm{false}) if p∉Facts⁡(s)p \notin\operatorname{Facts}(s) for some s∈Ss \in S; a threshold query likewise returns const⁡(false)\operatorname{const}(\mathrm{false}) when its threshold lies beyond the measure at ss. For a value-tracking predicate pp in @e@ℓc_{\ell c}, the index computes pp only with the instruction that uses the operand as the context (§ 6.1); so p^\hat{p} checks only the site where the argument is an operand of ℓc\ell_c itself, when ℓc\ell_c is certain, and returns ⊤\top otherwise. Each abstract transformer is sound in the following sense: if f^(a^)=const⁡(false)\hat{f}(\hat{a}) = \operatorname{const}(\mathrm{false}) and wi∈γ(a^i)w_i \in\gamma(\hat{a}_i), then Ff,u(w⃗)∈{false,err}F_{f,u}(\vec{w}) \in\{\mathrm{false}, \mathrm{err}\} for the context uu of any match. For a fact predicate pp, this holds because w∈Vals⁡(s)w \in\operatorname{Vals}(s) and p∉Facts⁡(s)p \notin\operatorname{Facts}(s) give p(w)≠truep(w) \ne\mathrm{true} by Equation (1). Table 5 evaluates sample constraints on function ff.

ConstraintAbstract resultFunction
?c == 2⊤\top: literal 2 is recorded at (urem, 1), so ?c may be 2kept
?c == 4const(false): literal 4 is missingpruned
`?c == 4?c == 2`const(false) ∨\lor ⊤\top = ⊤\topkept
?c == ?x && ?c == 4⊤∧\top\land const(false) = const(false)pruned
isKnownNonZero(?x)const(false): value-tracking fact missing at (urem, 0)pruned
isZero(add(?c, 1))⊤\top: add has no abstract transformerkept
?n == 8const(32 == 8) = const(false)pruned
udiv(1, 0) == 0errpruned

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 σ∈Match⁡struct(P,F)\sigma\in\operatorname{Match}_{\mathrm{struct}}(P,F) and θ⊆σ\theta\subseteq\sigma. For every constraint e@ℓce@ \ell_c of PP and every subexpression e′e' of ee, ⟦e′⟧σ∈γ(⟦e′⟧θ)\llbracket e' \rrbracket_{\sigma} \in\gamma(\llbracket e' \rrbracket_{\theta}).

The proof is by induction on e′e' (see § A.3).

Theorem 6.4 (Pruning is sound). Let PP be a core pattern. If Req⁡(P)⊈α(F)\operatorname{Req}(P) \not\subseteq\alpha(F), or if for every typing θ∈Typings⁡(P)\theta\in\operatorname{Typings}(P) some constraint ee of PP has ⟦e⟧θ∈{const⁡(false),err⁡}\llbracket e \rrbracket_{\theta} \in\{\operatorname{const}(\mathrm{false}), \operatorname{err}\}, then Match⁡(P,F)=∅\operatorname{Match}(P,F) = \varnothing.

Proof. Suppose σ∈Match⁡(P,F)\sigma\in\operatorname{Match}(P,F). By Lemma 6.1, Req⁡(P)⊆α(F)\operatorname{Req}(P) \subseteq\alpha(F). By Lemma 6.2, some θ∈Typings⁡(P)\theta\in\operatorname{Typings}(P) has θ⊆σ\theta\subseteq\sigma; take the constraint ee that the hypothesis gives for it. By Lemma 6.3, ⟦e⟧σ∈{false,err⁡}\llbracket e \rrbracket_{\sigma} \in\{\mathrm{false}, \operatorname{err}\}, so σ∉Match⁡(P,F)\sigma\notin\operatorname{Match}(P,F), 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 srcsrc to a target tgttgt 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.

PRMetaphIR ∣GT∣|GT|MetaphIR ∣P∣|P|MetaphIR TPMetaphIR P/R/F1MetaphIR TTMetaphIR TNCT_{\mathrm{NC}}MetaphIR TNIT_{\mathrm{NI}}daggrep ∣P∣|P|daggrep TPdaggrep P/R/F1daggrep TTWeb SzWeb TTWeb SzNCWeb TNCT_{\mathrm{NC}}
204089000100.0 / 100.0 / 100.00.90.926.200100.0 / 100.0 / 100.043.19710.813114.4
2049271,9731,9731,973100.0 / 100.0 / 100.03.33.226.04,3431,97345.4 / 100.0 / 62.564.51,825283.52,194358.5
2049281,2661,2661,266100.0 / 100.0 / 100.01.51.726.05,1631,26624.5 / 100.0 / 39.465.134356.237065.5
205383000100.0 / 100.0 / 100.00.91.051.500100.0 / 100.0 / 100.086.6708.4728.6
207462313131100.0 / 100.0 / 100.02.32.451.32123114.6 / 100.0 / 25.542.582687.888593.9
207564525252100.0 / 100.0 / 100.01.41.626.3545296.3 / 100.0 / 98.121.753957.373678.2
209322000100.0 / 100.0 / 100.00.94.425.968,17500.0 / 100.0 / 0.021.485289.73,564382.6
210499101010100.0 / 100.0 / 100.02.02.026.85,524100.2 / 100.0 / 0.486.71,169125.91,925206.6
212132000100.0 / 100.0 / 100.03.23.451.700100.0 / 100.0 / 100.044.181285.585289.6
213313000100.0 / 100.0 / 100.00.80.826.100100.0 / 100.0 / 100.043.1687.6687.6
213709999100.0 / 100.0 / 100.01.82.526.099100.0 / 100.0 / 100.043.586391.31,256132.8
214376000100.0 / 100.0 / 100.01.21.225.900100.0 / 100.0 / 100.021.115116.222624.0
214381999100.0 / 100.0 / 100.00.71.025.314964.3 / 100.0 / 78.321.518319.422323.5
214517242424100.0 / 100.0 / 100.00.91.226.7475245.1 / 100.0 / 9.621.426928.428930.6
214541181818100.0 / 100.0 / 100.00.60.726.3284186.3 / 100.0 / 11.920.7738.2819.0
215122323232100.0 / 100.0 / 100.02.02.926.01683219.0 / 100.0 / 32.021.990795.51,483156.3
215130333100.0 / 100.0 / 100.00.90.926.614321.4 / 100.0 / 35.322.4525.9556.2
216046575757100.0 / 100.0 / 100.01.41.726.51,680573.4 / 100.0 / 6.621.223325.027429.3
216436444444100.0 / 100.0 / 100.01.01.425.7524484.6 / 100.0 / 91.721.122924.541044.0
216470333333333100.0 / 100.0 / 100.02.83.126.33,8173338.7 / 100.0 / 16.043.91,254133.31,362144.3
Avgmicro_{\mathrm{micro}}3,8613,8613,861100.0 / 100.0 / 100.01.31.626.289,9843,8614.3 / 100.0 / 8.232.530642.339054.7
Avgmacro_{\mathrm{macro}}100.0 / 100.0 / 100.049.7 / 100.0 / 55.4

Table 6. Per-Rewrite Accuracy and Query Time (seconds) on llvm-opt-benchmark. ∣GT∣|GT|, ∣P∣|P|, 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, GT∩PGT \cap P). 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. TT is the query time, and TNCT_{\mathrm{NC}} and TNIT_{\mathrm{NI}} 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 GTGT, and the functions matched by a MetaphIR pattern form the predictions PP. We compare them as sets of (module, function) pairs and count the true positives TP=∣GT∩P∣TP = \lvert GT \cap P \rvert. We report precision TP/∣P∣TP/\lvert P \rvert, recall TP/∣GT∣TP/\lvert GT \rvert, 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. ∣GT∣|GT|, ∣P∣|P|, 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, GT∩PGT \cap P). 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. TT is the query time, and TNCT_{\mathrm{NC}} and TNIT_{\mathrm{NI}} 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 TNCT_{\mathrm{NC}} 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, 22×22 \times 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 Pˉ\bar{P} and function FF,

Match⁡(Pˉ,F)={σ∣χPˉ(P)∣P∈Lower⁡(Pˉ), σ∈Match⁡(P,F)}.\operatorname{Match}(\bar{P}, F) = \{ \sigma|_{\chi_{\bar{P}}}(P) \mid P \in\operatorname{Lower}(\bar{P}),\ \sigma\in\operatorname{Match}(P, F) \}.

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 Pˉ⇒{Pˉ1,…,Pˉk}\bar{P} \Rightarrow\{\bar{P}_1, \ldots, \bar{P}_k\} when removing one abstraction from Pˉ\bar{P} yields the patterns Pˉ1,…,Pˉk\bar{P}_1, \ldots, \bar{P}_k, such as one per branch of an inlined composite matcher. Lowering Pˉ\bar{P} then lowers each Pˉi\bar{P}_i in turn, so Lower⁡(Pˉ)=⋃iLower⁡(Pˉi)\operatorname{Lower}(\bar{P}) = \bigcup_i \operatorname{Lower}(\bar{P}_i). Each step either removes a metaflag, which adds no invocation, or replaces an invocation of depth dd by bodies whose invocations have depth below dd. 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 Match⁡(Pˉ,Fˉ)=⋃iMatch⁡(Pˉi,Fˉ)∣X(Pˉ)\operatorname{Match}(\bar{P}, \bar{F}) = \bigcup_i \operatorname{Match}(\bar{P}_i, \bar{F})|_{\mathcal{X}(\bar{P})} 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 Match⁡(Pˉ,Fˉ)=Match⁡(Pˉ1,Fˉ)\operatorname{Match}(\bar{P}, \bar{F}) = \operatorname{Match}(\bar{P}_1, \bar{F}).

  • Composite matcher invocations. Let Pˉ\bar{P} contain ℓ=mφ(a⃗)\ell= m_{\varphi}(\vec{a}), and let Pˉi\bar{P}_i inline the ii-th branch βi\beta_i of mm that is compatible with φ\varphi: its parameters substituted by a⃗\vec{a}, its result node renamed to ℓ\ell, 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 flfl of mm, a branch either passes flfl on to its result node, where φ(fl)\varphi(fl) then imposes exactly the invocation’s condition, or fixes flfl to a Boolean bb. A fixed branch can match only if φ(fl)=+\varphi(fl) = + and b=trueb = \mathit{true}, or φ(fl)=−\varphi(fl) = - and b=falseb = \mathit{false}, or fl∉dom⁡(φ)fl \notin\operatorname{dom}(\varphi), or φ(fl)=x\varphi(fl) = x, in which case lowering adds the constraint x==bx == b, which holds exactly when σ(x)=b\sigma(x) = b; so the dropped branches have no match, and the kept ones bind xx as the invocation’s meaning does. Hygiene: the renamed meta variables are disjoint from those of Pˉ\bar{P} and of other invocations, so a match of Pˉi\bar{P}_i may bind them freely, and restricting to X(Pˉ)\mathcal{X}(\bar{P}) removes them, as the invocation’s meaning restricts to the meta variables of Pˉ\bar{P}. Or-self: an invocation with :o(N) marks each inlined root with o(oN)o(o_N), so by M-Self the root also matches what oNo_N matches, which is the meaning of :o(N) on an invocation.

  • The :c mark on composite matchers. Lowering yields Pˉ1\bar{P}_1 and Pˉ2\bar{P}_2 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 a⃗\vec{a} 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 Lower⁡(Pˉ)={Pˉ}\operatorname{Lower}(\bar{P}) = \{\bar{P}\} and the theorem holds by definition. Otherwise, take a step Pˉ⇒{Pˉ1,…,Pˉk}\bar{P} \Rightarrow\{\bar{P}_1, \ldots, \bar{P}_k\}, and assume the theorem for each Pˉi\bar{P}_i. Then

Match⁡(Pˉ,Fˉ)=⋃iMatch⁡(Pˉi,Fˉ)∣X(Pˉ)(one step)=⋃i{σ∣X(Pˉi)∣Pˉ∈Lower⁡(Pˉi), σ∈Match⁡(P,F)}(hypothesis)={σ∣X(Pˉ)∣Pˉ∈Lower⁡(Pˉ), σ∈Match⁡(P,F)}.\begin{aligned} \operatorname{Match}(\bar{P}, \bar{F}) &= \bigcup_i \operatorname{Match}(\bar{P}_i, \bar{F})|_{\mathcal{X}(\bar{P})} && \text{(one step)}\\ &= \bigcup_i \{\sigma|_{\mathcal{X}(\bar{P}_i)} \mid\bar{P} \in\operatorname{Lower}(\bar{P}_i),\ \sigma\in\operatorname{Match}(P,F)\} && \text{(hypothesis)}\\ &= \{\sigma|_{\mathcal{X}(\bar{P})} \mid\bar{P} \in\operatorname{Lower}(\bar{P}),\ \sigma\in\operatorname{Match}(P,F)\}. \end{aligned}

The last step uses X(Pˉ)⊆X(Pˉi)\mathcal{X}(\bar{P}) \subseteq\mathcal{X}(\bar{P}_i), since a step only adds renamed meta variables and constraints, so the two restrictions amount to one, and Lower⁡(Pˉ)=⋃iLower⁡(Pˉi)\operatorname{Lower}(\bar{P}) = \bigcup_i \operatorname{Lower}(\bar{P}_i).

Proofs of Lemmas 6.1 and 6.2

Lemma 6.1 (Requirements are necessary). If Match⁡(P,F)≠∅\operatorname{Match}(P,F) \ne\varnothing, then Req⁡(P)⊆α(F)\operatorname{Req}(P) \subseteq\alpha(F).

Lemma 6.2 (Typings are sound). If σ∈Match⁡(P,F)\sigma\in\operatorname{Match}(P,F), then some θ∈Typings⁡(P)\theta\in\operatorname{Typings}(P) satisfies θ⊆σ\theta\subseteq\sigma.

These proofs and the proof of Lemma 6.3 use one fact. Since a certain node II has no o(·) mark, σ⊢I⇝σ(ℓI)\sigma\vdash I \leadsto\sigma(\ell_I) is derived by M-Inst or M-Comm, so the instruction σ(ℓI)\sigma(\ell_I) that σ\sigma maps II to, the image of II, has the opcode of II.

Lemma 6.1. Each requirement is witnessed by σ\sigma: 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 FF and is consistent with σ\sigma’s bindings of type-level meta variables. The function Typings⁡\operatorname{Typings} includes every consistent combination, so it includes σ\sigma restricted to the type-level meta variables of the certain nodes, σθ⊆σ\sigma_{\theta} \subseteq\sigma. If the set exceeds the cap, the empty typing satisfies ∅⊆σ\varnothing\subseteq\sigma.

Proof of Lemma 6.3 (Abstract Evaluation Is Sound)

Lemma 6.3 (Abstract evaluation is sound). Let σ∈Match⁡struct(P,F)\sigma\in\operatorname{Match}_{\mathrm{struct}}(P,F) and θ⊆σ\theta\subseteq\sigma. For every constraint e@ℓce@ \ell_c of PP and every subexpression e′e' of ee, ⟦e′⟧σ∈γ(⟦e′^⟧θ)\llbracket e' \rrbracket_\sigma\in\gamma(\llbracket\widehat{e'} \rrbracket_\theta).

Fix σ∈Match⁡struct(P,F)\sigma\in\operatorname{Match}_{\mathrm{struct}}(P,F) and θ⊆σ\theta\subseteq\sigma, and recall that err⁡∈γ(a^)\operatorname{err} \in\gamma(\hat{a}) for every a^\hat{a}. We prove ⟦e⟧σ∈γ(⟦e^⟧θ)\llbracket e \rrbracket_\sigma\in\gamma(\llbracket\widehat{e} \rrbracket_\theta) by induction on ee.

Literals. We have ⟦k⟧σ=k∈γ(const⁡(k))\llbracket k \rrbracket_\sigma= k \in\gamma(\operatorname{const}(k)).

Variables. If x∈dom⁡(θ)x \in\operatorname{dom}(\theta), then ⟦x⟧σ=σ(x)=θ(x)∈γ(const⁡(θ(x)))\llbracket x \rrbracket_\sigma= \sigma(x) = \theta(x) \in\gamma(\operatorname{const}(\theta(x))). Otherwise, if sites⁡(x)=S≠∅\operatorname{sites}(x) = S \ne\emptyset, take any s∈Ss \in S. By the definition of sites, xx is operand jj of a certain node II with opcode opop. By § A.2, the image of II is an instruction with opcode opop. Without the c mark, s=(op,{j})s = (op,\{j\}), and σ(x)\sigma(x) is operand jj of the image. With the c mark, M-Comm may swap the operands, so σ(x)\sigma(x) is operand 0 or 1 of the image, and s=(op,{0,1})s = (op,\{0,1\}) by the definition of sites (§ 6.3). A local name ℓ\ell and its capture may also have the result site s=(op,{res})s = (op,\{\mathrm{res}\}) of their own certain node II; there, σ(ℓ)\sigma(\ell) is the image of II itself, an instruction with opcode opop. In every case, σ(x)∈Vals⁡(s)\sigma(x) \in\operatorname{Vals}(s). Since this holds for every s∈Ss \in S, σ(x)∈γ(at⁡(S))\sigma(x) \in\gamma(\operatorname{at}(S)). Otherwise the result is ⊤\top.

Operators. Let a^i=⟦ei^⟧θ\hat{a}_i = \llbracket\widehat{e_i} \rrbracket_\theta and wi=⟦ei⟧σ∈γ(a^i)w_i = \llbracket e_i \rrbracket_\sigma\in\gamma(\hat{a}_i) by induction. If some wi=err⁡w_i = \operatorname{err}, then ⟦f(e⃗)⟧σ=err⁡\llbracket f(\vec{e}) \rrbracket_\sigma= \operatorname{err}, which lies in every concretization. Otherwise: (i) if every a^i=const⁡(ci)\hat{a}_i = \operatorname{const}(c_i), then wi=ciw_i = c_i, and ⟦f(e⃗)⟧σ=f(c⃗)=⟦f^(e⃗)⟧θ\llbracket f(\vec{e}) \rrbracket_\sigma= f(\vec{c}) = \llbracket\widehat{f}(\vec{e}) \rrbracket_\theta, or both are err⁡\operatorname{err}; (ii) if f^(a⃗^)=const⁡(false)\widehat{f}(\hat{\vec{a}}) = \operatorname{const}(\mathrm{false}), the soundness of abstract transformers gives fF,u(w⃗)∈{false,err⁡}⊆γ(const⁡(false))f_{F,u}(\vec{w}) \in\{\mathrm{false},\operatorname{err}\} \subseteq\gamma(\operatorname{const}(\mathrm{false})); (iii) otherwise the result is ⊤\top.

Conjunction. Let a^1=⟦e1^⟧θ\hat{a}_1 = \llbracket\widehat{e_1} \rrbracket_\theta and r1=⟦e1⟧σ∈γ(a^1)r_1 = \llbracket e_1 \rrbracket_\sigma\in\gamma(\hat{a}_1).

  • a^1∈{const⁡(false),err⁡}\hat{a}_1 \in\{\operatorname{const}(\mathrm{false}),\operatorname{err}\}: then r1∈{false,err⁡}r_1 \in\{\mathrm{false},\operatorname{err}\}, so ⟦e1&&e2⟧σ∈{false,err⁡}⊆γ(a^1)\llbracket e_1 \mathbin{\&\&} e_2 \rrbracket_\sigma\in\{\mathrm{false},\operatorname{err}\} \subseteq\gamma(\hat{a}_1).

  • a^1=const⁡(true)\hat{a}_1 = \operatorname{const}(\mathrm{true}): then r1∈{true,err⁡}r_1 \in\{\mathrm{true},\operatorname{err}\}, so the result is ⟦e2⟧σ\llbracket e_2 \rrbracket_\sigma or err⁡\operatorname{err}, both in γ(⟦e2^⟧θ)\gamma(\llbracket\widehat{e_2} \rrbracket_\theta) by induction.

  • a^1∉B\hat{a}_1 \notin B and ⟦e2^⟧θ∈{const⁡(false),err⁡}\llbracket\widehat{e_2} \rrbracket_\theta\in\{\operatorname{const}(\mathrm{false}),\operatorname{err}\}: by induction, ⟦e2⟧σ∈{false,err⁡}\llbracket e_2 \rrbracket_\sigma\in\{\mathrm{false},\operatorname{err}\}. In concrete evaluation, e1&&e2e_1 \mathbin{\&\&} e_2 either short-circuits to false (when r1=falser_1 = \mathrm{false}), evaluates to ⟦e2⟧σ∈{false,err⁡}\llbracket e_2 \rrbracket_\sigma\in\{\mathrm{false},\operatorname{err}\} (when r1=truer_1 = \mathrm{true}), or fails with err⁡\operatorname{err}; in all cases, ⟦e1&&e2⟧σ∈{false,err⁡}=γ(const⁡(false))\llbracket e_1 \mathbin{\&\&} e_2 \rrbracket_\sigma\in\{\mathrm{false},\operatorname{err}\} = \gamma(\operatorname{const}(\mathrm{false})).

  • Otherwise, ⟦e1&&e2⟧θ=⊤\llbracket e_1 \mathbin{\&\&} e_2 \rrbracket_\theta= \top, and γ(⊤)=Cerr\gamma(\top) = C_{\mathrm{err}}.

Disjunction is dual, with const⁡(true)\operatorname{const}(\mathrm{true}) deciding. When the left side is unknown and the right side is const⁡(false)\operatorname{const}(\mathrm{false}) or err⁡\operatorname{err}, the result is ⊤\top, which is trivially sound.

Negation. If ⟦e^⟧θ=const⁡(b)\llbracket\widehat{e} \rrbracket_\theta= \operatorname{const}(b) for a Boolean bb, then ⟦e⟧σ∈{b,err⁡}\llbracket e \rrbracket_\sigma\in\{b,\operatorname{err}\}, so ⟦!e⟧σ∈{¬b,err⁡}=γ(const⁡(¬b))\llbracket{!}e \rrbracket_\sigma\in\{\lnot b,\operatorname{err}\} = \gamma(\operatorname{const}(\lnot b)); if ⟦e^⟧θ=err⁡\llbracket\widehat{e} \rrbracket_\theta= \operatorname{err}, the result is err⁡\operatorname{err}; otherwise ⊤\top. □\square

The Matching Algorithm

Algorithm 1 computes Match⁡(P,F)\operatorname{Match}(P,F). It matches the roots of PP one after another (line 3), each against every instruction of FF (line 6), and descends from each node to its operands (line 16). Matching extends a partial instantiation: an extension of σ\sigma keeps every binding of σ\sigma and binds more names. MatchNode⁡\operatorname{MatchNode} 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, MatchNode⁡\operatorname{MatchNode} only checks that σ(ℓ)\sigma(\ell) is the same value (line 10), so both uses refer to one instruction. After the roots, SS is Match⁡struct(P,F)\operatorname{Match}_{\mathrm{struct}}(P,F), which Match⁡\operatorname{Match} 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.

The largest pattern of the evaluation, showing the C++ Rewrite in InstCombine and MetaphIR Pattern

Figure 10. The Largest Pattern of the Evaluation, for PR 216470: (X≫C)+zext⁡((X&M)≠0)(X \gg C) + \operatorname{zext}((X \mathbin{\&} M) \ne0) with M=2C−1M = 2^{C} - 1, a Rounding-up Division by 2C2^{C}. The operator ≫\gg 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.

MetaphIRdaggrep
PRInstConsFilesInstExactDropped for daggrep
2049273039single use
2049283039single use
205383103424bit-width equations; predicate
2074627427single use; ?c0 != 0; notUndef
2075643013✓–
2093221011knownNegative
2104992148the i1 result type
212132120212knownPowerOfTwo; single use; predicate
2133135026✓–
2137093426sgt(?bits, 1); predicate; single use
2143762012odd constant (any constant)
2143813213?d != 0; predicate and constant ranges
2145172012single use
2145412112noOverflow; single use
2151223013lowBitMask (any constant); single use
2151302112?c + ?negc == 0; single use
2160461111inSignedRange
2164363013lowBitMask (any constant); single use
21647062211lowBitMask, popcount, noOverflow; single use; predicate
2040892124✓–

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. [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. [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. [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. [4]GitHub. 2026. CodeQL. https://codeql.github.com/. Accessed: 2026-10-29.
  5. [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. [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. [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. [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. [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. [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. [11]W. M. McKeeman. 1965. Peephole Optimization. Commun. ACM 8, 7 (1965), 443–444. doi:10.1145/364995.365000DOI
  12. [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. [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. [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. [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. [16]The Bytecode Alliance. 2026. ISLE: Instruction-Selection / Lowering Expressions. https://github.com/bytecodealliance/wasmtime/tree/main/cranelift/isle. Accessed: 2026-10-28.
  17. [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. [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. [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. [20]The LLVM Project. 2026. LLVM Language Reference Manual: Poison Values. https://llvm.org/docs/LangRef.html#poison-values. Accessed: 2026-11-11.
  21. [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. [22]The MLIR Project. 2026. PDLL - PDL Language - MLIR. https://mlir.llvm.org/docs/PDLL/. Accessed: 2026-10-13.
  23. [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. [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. [25]Hongxu Xu, Xintong Zhou, Chunhao Liao, and Chengnian Sun. 2026. MetaphlR: Artifact. https://github.com/xuhongxu96/metaphlr. Accessed: 2026-11-18.
  26. [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. [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. [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. [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. [30]Yingwei Zheng. 2026. llvm-opt-benchmark: LLVM Optimization Benchmark. https://github.com/dtcxzyw/llvm-opt-benchmark. Accessed: 2026-10-13.
  31. [31]Yingwei Zheng. 2026. llvm-opt-benchmark-nightly: GitHub Actions Runs. https://github.com/dtcxzyw/llvm-opt-benchmark-nightly/actions. Accessed: 2026-11-01.

Paper details

vlnc:W_e4gkunv3
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude Code

View statement
Looking for related papers…
Contents