Finding Reusable Instructions via E-Graph Anti-Unification

Chips get faster by adding custom instructions that trigger dedicated hardware for common operations, and RISC-V makes this easy — but the tools that automatically find which custom instructions to add only spot code that looks identical, so they miss the many places that do the same thing written differently, and the instructions they produce are barely reused; this paper (Peking University — Youwei Xiao, Yun Liang, and colleagues) presents ISAMORE, which rewrites programs into a compact form capturing all their equivalent variants and then uses anti-unification to find the shared pattern across syntactically different code, discovering custom instructions with about ten times higher reuse.

The argument in one glance

Problem

Custom instructions only pay off if they are reused, but finders miss the reuse

A powerful way to speed up a chip for a particular application area is to add custom instructions: new machine instructions that, when executed, trigger a dedicated hardware unit to do some common operation in one shot instead of many ordinary instructions. This balances performance against cost, because you only build hardware for the operations that matter, and RISC-V — an open, extensible instruction set — has made adding such instructions easy and popular. The hard part is deciding which custom instructions to add. You want to look across the programs in a domain, find operations that recur often enough to be worth turning into hardware, and add an instruction for each. This choice is usually automated, because a human cannot eyeball a large codebase and spot the best candidates. But the existing automated finders have a serious blind spot: they only recognize code that is syntactically similar — sequences of scalar instructions that look the same. Real code, though, expresses the same computation in many different ways: the same underlying operation appears with operands reordered, with algebraically equivalent forms, or structured differently by the compiler. A syntactic finder sees these as unrelated, so it misses that they are the same operation. The consequence is that the custom instructions it produces are reused in only a few places, which means the hardware you paid to build sits mostly idle and the performance gain is small. So the very property that makes a custom instruction worthwhile — being reused a lot — is exactly what the finders fail to maximize.
What people did

Find custom instructions by syntactically matching and merging code

The established approach scans the program for hot spots and identifies or merges instruction sequences that are syntactically similar — patterns of scalar operations that appear the same in the code. Where two hot code fragments look alike, it proposes a custom instruction to cover them, matching on the surface form of the instructions.
Why it fell short

Syntactic matching misses semantically equivalent code, so reuse is low

Matching on surface syntax fundamentally undercounts reuse, because the same computation is written in many syntactically different ways. Two code fragments can compute exactly the same function while looking nothing alike — one might add before multiplying where another multiplies before adding an equivalent quantity, or the compiler might have scheduled and structured them differently, or the operands might be in a different order. A syntactic finder treats each surface form as a distinct pattern, so it either fails to see that these fragments could share one custom instruction, or it needs a separate instruction for each variant. Either way, the reuse factor of any given custom instruction stays low: it matches only the handful of places that happen to be written in its exact form. Low reuse is fatal to the economics of custom instructions, because a dedicated hardware unit that is invoked rarely does not justify its area cost, and the overall speedup is modest. The approaches are also limited to scalar sequences, so they do not exploit the data-level parallelism that many of these recurring operations actually have. What was missing was a way to recognize that syntactically different code is semantically the same, so that one reusable custom instruction can cover all of it — and to do so at the scale of real programs.
This paper's idea

Expose equivalences with e-graphs, then find the shared pattern by anti-unification

ISAMORE is an end-to-end framework for discovering reusable custom instructions using a semantic-aware method the authors call Reusable Instruction Identification. Instead of matching surface syntax, it works in two big moves. First, it makes semantic equivalence visible. Each program is encoded in a structured domain-specific language and represented as an e-graph — a data structure that compactly stores many equivalent versions of an expression at once — and then equality saturation is run on it: rewrite rules (algebraic identities, reassociations, and so on) are applied repeatedly until the e-graph contains all the equivalent forms the computation can take. Now two fragments that were written differently but mean the same thing are represented together. Second, it finds the shared pattern across fragments by anti-unification: given several code segments, anti-unification computes their most specific common generalization — a template that matches all of them, with holes where they differ — which is precisely the reusable operation a single custom instruction should implement. Doing this over the equality-saturated e-graph ("e-graph anti-unification") lets ISAMORE discover patterns that recur across syntactically different code, so a single custom instruction covers far more sites. It then vectorizes the discovered patterns into SIMD-style instructions to exploit data-level parallelism, and uses hardware-aware, Pareto-optimal selection to balance the performance gain of each candidate instruction against its area cost. The authors report that this finds custom instructions with about ten times higher reuse factors than syntactic approaches, yielding performance improvements of roughly 1.12 to 2.69 times; the paper received a Best Paper Award at ASPLOS 2026.

Why this problem is worth solving

Custom instructions are one of the main remaining ways to get more performance per chip, and their whole value hinges on reuse.

As general-purpose processor scaling slows, specialization is where much of the remaining performance comes from, and custom instructions are a particularly attractive form of it: instead of building a whole separate accelerator, you extend the processor with a few new instructions that fire dedicated hardware for the operations a domain does most. RISC-V’s open, extensible instruction set has made this practical and popular, so the question of which instructions to add is increasingly important. The economics are all about reuse. Each custom instruction costs silicon area for its hardware unit, and that cost is only justified if the instruction is executed often — across many programs and many sites within them. A custom instruction that is used in just a handful of places is a poor trade: you paid for hardware that mostly sits idle. So the goal of an instruction-finding tool is not merely to find operations that can be turned into hardware, but to find ones that will be reused as widely as possible, because reuse is what converts area into speedup. A finder that systematically undercounts reuse therefore leaves most of the achievable performance on the table, which is why improving it is valuable.

The difficulty is that reuse lives at the level of meaning, but the easy thing to match is surface form.

The reason a custom instruction can be reused widely is that the same underlying operation recurs throughout a domain’s code. But that recurrence is a fact about what the code computes, not about how it is written. Programmers and compilers express the same computation in countless surface forms — different operand orders, algebraically equivalent rearrangements, different instruction schedules — so two fragments that should share a custom instruction often look completely different in the program text. Matching on syntax, which is easy, therefore sees far fewer matches than really exist, and the tool proposes narrow instructions that each cover only their exact surface form. To find the true reuse you have to match on semantics: recognize that syntactically different fragments compute the same thing. That is hard for two reasons. First, you need a way to reveal the equivalences without enumerating every possible rewriting of every fragment, which would explode. Second, once equivalent forms are available, you need to extract the common reusable pattern across many fragments — the shared skeleton with variation only where they genuinely differ — and do it efficiently over real, large programs. Solving both is what turns the intractable-looking semantic-matching problem into a practical instruction finder, and it is exactly where e-graphs and anti-unification come in.

What people did before, and where it broke

Match and merge syntactically similar hot code. Find program hot spots that look alike and propose a custom instruction covering them. Where it broke. The same computation appears in many syntactic forms, so it treats equivalent fragments as unrelated and misses most of the potential reuse.
Add a separate custom instruction per surface variant. Cover each distinct-looking form with its own instruction. Where it broke. Each instruction then has low reuse and its own area cost, so the hardware is poorly justified and the total speedup is small.
Restrict to scalar instruction sequences. Work only with straight-line scalar patterns. Where it broke. Many recurring operations have data-level parallelism that a scalar-only view cannot exploit, leaving performance unclaimed.
Rely on a human to pick custom instructions. Have an expert choose the extensions. Where it broke. Real codebases are far too large to eyeball for the best, most-reused candidates, so this does not scale.
The gap. No automated finder recognized semantically equivalent but syntactically different code as the same operation, so it could not maximize reuse across a real domain’s programs.

How ISAMORE works

From programs to widely-reused custom instructions

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Represent all the equivalent forms of a program compactly, and reason over them at once. ISAMORE’s first move is to stop looking at one surface form of the code and instead build an e-graph that holds every equivalent version, grown by equality saturation, so semantic equivalence becomes something the tool can see directly. Compactly capturing an enormous space of equivalent program variants in an e-graph and optimizing over that space, rather than over a single form, is the same undertaking the work on differentiable e-graph extraction (SmoothE) covered elsewhere on this site pursues, using the e-graph to reason over many equivalent programs together. ISAMORE builds this space specifically so that fragments meaning the same thing are represented together and can be matched.

Find the common reusable pattern that recurs across many places. The heart of ISAMORE is discovering the shared skeleton that appears again and again across a domain’s code — the pattern worth turning into one instruction — by anti-unifying code segments into their most specific common template. Systematically mining a program for the patterns that recur across it, so the common structure can be exploited, is the same principle the work on a compilation-based graph pattern mining system (DecoMine) covered elsewhere on this site is built on, finding the recurring patterns hidden in a large structure. ISAMORE finds them over the equality-saturated e-graph, so the recurrence it detects is semantic, catching patterns that syntactic mining would miss.

Turn the discovered patterns into custom hardware instructions. ISAMORE’s output is a set of custom instructions — extensions to the instruction set that fire dedicated hardware for the recurring operations it found, chosen to balance speedup against area. Automatically generating custom instruction-set extensions that add specialized hardware for an application’s common operations is the same idea the work on high-level synthesis of portable custom instruction-set extensions (Longnail) covered elsewhere on this site develops, producing the hardware instructions that accelerate a domain. ISAMORE contributes the semantic-aware way of choosing which instructions to add, so the ones it produces are reused far more widely.

Following a program through ISAMORE

Discovering a reusable custom instruction across differently-written code

A trace, based on the paper's abstract and the authors' repository, of ISAMORE's pipeline. Some details reflect the repository's description; specifics should be read in the paper.

Step 1 of 5

Encode the domain programs as e-graphs

ISAMORE takes the domain's programs (with profile data) and encodes them in a structured domain-specific language, building an e-graph that can hold many equivalent versions of each expression.

Two code fragments that mean the same thing may still look syntactically different at this point.

Why it works

Equality saturation reveals reuse that syntax hides. The same computation appears in many surface forms → but building an e-graph and saturating it with rewrites gathers those forms together → so fragments that syntactic matching saw as unrelated are now recognizably the same.
Anti-unification extracts exactly the reusable template. Equivalent fragments still differ in their specifics → but anti-unifying them yields the most specific common generalization → so the custom instruction covers all of them while leaving holes only where they truly vary.
Semantic matching multiplies the reuse factor. A syntactic instruction matches only its exact form → but a semantically-found pattern matches every equivalent site → so a single instruction is reused far more widely (about ten times, per the authors), justifying its hardware.
Vectorization captures parallelism scalar finders ignore. Recurring operations often apply across many data elements → but generating SIMD-style vectorized instructions → exploits that data-level parallelism instead of doing the work one element at a time.
Pareto selection spends area only where it pays. Not every discovered pattern is worth dedicated hardware → but weighing each candidate’s speedup against its area on a Pareto frontier → keeps the instructions that give the best performance per unit of silicon.

What it costs (trade-offs and scope)

Equality saturation can be expensive and must be controlled. Growing an e-graph with rewrite rules can blow up in size, which is why ISAMORE uses a phase-oriented, heuristic process to keep it tractable on real codebases; the quality of the discovered patterns depends on the rewrite rules and how far saturation is pushed.
Results depend on the rewrite rules and the DSL encoding. The equivalences ISAMORE can find are those its rewrite rules and structured DSL can express; equivalences outside that vocabulary would not be exposed, so coverage is bounded by the rule set.
Adding custom instructions has real hardware and toolchain cost. Each selected instruction needs a hardware unit and support in the toolchain; the Pareto selection manages the area tradeoff, but custom-instruction extension is still a heavier commitment than a pure software change.
The gains vary with the domain and its redundancy. The reported reuse improvement and 1.12 to 2.69 times speedup come from the paper’s domains; applications with little semantic recurrence, or already well-served by existing instructions, would benefit less.
This explainer is drawn from limited source material. The full paper text was not accessible for this write-up; the description here is based on the paper’s abstract and the authors’ public repository, so the precise algorithms (the anti-unification procedure, the saturation phases, the selection), the experimental setup, and the detailed results should be confirmed in the paper.

How it compares

Finding custom instructions for a domain

Property	Syntactic matching/merging	Per-variant instructions	ISAMORE (semantic)
Matches equivalent-but-different code
Reuse factor per instruction
Exploits data-level parallelism
Area versus performance tradeoff
Reported performance

A comparison, based on the paper's abstract and the authors' repository, of ways to find custom instructions. By exposing semantic equivalences with e-graph equality saturation and extracting the shared reusable pattern by anti-unification, then vectorizing and selecting on a hardware-aware Pareto frontier, ISAMORE reports about ten times higher reuse factors than syntactic approaches and 1.12 to 2.69 times performance. Specific per-benchmark figures should be read from the paper.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is based on the paper’s abstract and the authors’ public code repository, not its full text, which was not accessible for this write-up. The system and claims described are the authors’: ISAMORE (the tool named in the repository for the paper “Finding Reusable Instructions via E-Graph Anti-Unification”) is an end-to-end framework for discovering reusable custom instructions from domain applications, addressing the limitation that prior approaches identify or merge only syntactically similar, scalar instruction sequences and miss semantically equivalent patterns. Per the abstract and the repository, its Reusable Instruction Identification method encodes programs in a structured domain-specific language as e-graphs, applies phase-oriented equality saturation to discover semantically equivalent variants, uses e-graph anti-unification to identify common reusable patterns across program segments, vectorizes the patterns into SIMD-style custom instructions, and uses hardware-aware Pareto-optimal selection to balance performance gains against area overhead. The authors report about ten times higher reuse factors than syntactic approaches and performance improvements of 1.12 to 2.69 times, and the paper received a Best Paper Award at ASPLOS 2026. The ten times and 1.12-to-2.69 times figures and the method steps are the authors’ own (from the abstract and repository); the precise algorithms, the experimental setup, and detailed per-benchmark results were not available for this write-up and should be confirmed in the paper. This page is marked as a draft for that reason.

Background

Why finding what is 'the same' is a recurring lever in compilers and hardware

It helps to see ISAMORE within a long line of work whose payoff comes from recognizing that two things are, at bottom, the same. A great deal of optimization — in compilers, in hardware design, in program synthesis — reduces to detecting equivalence: that two expressions compute the same value, that two code fragments implement the same operation, that a slow form and a fast form are interchangeable. The trouble is that equivalence is a semantic property, while the artifacts we manipulate are syntactic, and the same meaning wears endlessly many syntactic disguises. Tools that match only on surface form therefore chronically undercount how much is really shared, and leave the corresponding optimizations unclaimed. Two ideas have become central to closing this gap. E-graphs with equality saturation give a compact, tractable way to represent an enormous space of equivalent forms and reason over all of them at once, rather than committing to a single form. And anti-unification gives a principled way to extract the common generalization of several terms — the shared template with variation factored out — which is exactly what you need when the goal is to find a reusable abstraction. Bringing these to the problem of custom-instruction discovery is natural, because a good custom instruction is precisely a reusable abstraction over a domain’s recurring computation. The broader effort to compile domain computations onto specialized hardware efficiently is the same terrain the work on an MLIR-based intermediate representation for hardware accelerators (HIR) covered elsewhere on this site occupies, bridging programs and accelerators. ISAMORE contributes the insight that semantic, not syntactic, matching is what makes custom instructions reusable enough to be worth building.

If you remember only three things

1. Custom instructions accelerate a chip by firing dedicated hardware for a domain's common operations, and RISC-V makes adding them easy — but a custom instruction only pays for its silicon if it is reused a lot. Existing automated finders match only syntactically similar, scalar code, so they miss the many places that compute the same thing written differently (different operand orders, algebraically equivalent forms, different schedules). The result is custom instructions with low reuse, idle hardware, and modest speedups.
2. ISAMORE finds custom instructions semantically. It encodes programs in a structured DSL as e-graphs and runs equality saturation to gather all the equivalent forms of each computation, so differently-written fragments that mean the same thing are represented together. It then uses e-graph anti-unification to compute the most specific common generalization of code segments — a template with holes where they differ — which is exactly the reusable operation one custom instruction should implement. It vectorizes the discovered patterns into SIMD-style instructions to exploit data-level parallelism, and selects instructions on a hardware-aware Pareto frontier balancing speedup against area.
3. The authors report about ten times higher reuse factors than syntactic approaches and performance improvements of 1.12 to 2.69 times, and the paper won a Best Paper Award at ASPLOS 2026. The trade-offs: equality saturation can be expensive and must be controlled with heuristics; the equivalences found are bounded by the rewrite rules and DSL; adding custom instructions carries hardware and toolchain cost; and gains vary with how much semantic recurrence a domain has. This explainer is a draft based on the abstract and the authors' repository; the precise algorithms and results should be confirmed in the paper.

Check yourself

Check your understanding

1. Why do syntactic custom-instruction finders produce instructions with poor reuse?
2. How does ISAMORE recognize that syntactically different code fragments are the same operation?
3. What is anti-unification, and why is it the right tool for finding a reusable custom instruction?
4. Predict: ISAMORE discovers a recurring pattern that applies to many data elements and could be turned into a custom instruction, but its hardware unit would be large. What does ISAMORE do, and why?

Sources

The paper is “Finding Reusable Instructions via E-Graph Anti-Unification” by Youwei Xiao, Chenyun Yin, Yitian Sun, Yuyang Zou, and Yun Liang (Peking University), published at ASPLOS 2026, DOI 10.1145/3779212.3790162, where it received a Best Paper Award. The implementation, ISAMORE, is available at github.com/pku-liang/ISAMORE.

This explainer is written from the paper’s abstract and the authors’ public repository, because the full paper text was not accessible for this write-up (the ACM version was not retrievable and the repository’s PDF link was not reachable). Domain-specific accelerators and the custom instructions that invoke them are a growing source of performance, and RISC-V’s extensible ISA popularizes them, but choosing custom instructions automatically is hard: existing approaches identify or merge only syntactically similar, scalar instruction sequences and miss semantically equivalent patterns, giving poor reusability and limited performance. ISAMORE is an end-to-end framework whose Reusable Instruction Identification method encodes programs in a structured domain-specific language as e-graphs, applies phase-oriented equality saturation to discover semantically equivalent variants, uses e-graph anti-unification to identify common reusable patterns across program segments, vectorizes the patterns into SIMD-style custom instructions, and uses hardware-aware Pareto-optimal selection to balance performance gains against area overheads. The authors report about ten times higher reuse factors than syntactic approaches and performance improvements of 1.12 to 2.69 times. The figures and method steps are the authors’ own; the precise algorithms and full results should be confirmed in the paper. This page is marked draft because the full text was unavailable.