Fast Instruction Selection for Fast Digital Signal Processing

Alexander J. Root, Maaz Bin Safeer Ahmad, Dillon Sharlet, Andrew Adams, Shoaib Kamil and Jonathan Ragan-Kelley

Modern chips have specialized fixed-point instructions for signal processing — rounding, saturating, fused multiply-adds — but a programmer writing portable code has to spell those idioms out in plain integer arithmetic, and compilers like LLVM usually fail to recognize the giant blobs of primitive operations that result, wasting the fast instructions; this work from Stanford, MIT, and Adobe builds Pitchfork, which first lifts the messy integer code into a clean shared fixed-point language and then lowers it per chip, using rules learned offline so it runs up to 8 times faster than LLVM while compiling no slower and 100,000 times faster than the synthesis-based state of the art.

The argument in one glance

Problem

Chips have fast fixed-point instructions that portable code cannot reach

High-performance signal processing runs on fixed-point arithmetic, and modern vector chips (ARM Neon, x86 AVX2, Hexagon HVX) provide rich specialized instructions for it, with many rounding, saturating, and type-conversion modes, often fusing several operations into one. But to write portable code a programmer must express these idioms in plain integer arithmetic, and a compiler must then recognize the resulting tangle and map it back to the right fast instruction — which is exactly what compilers struggle to do.
What people did

Pattern-match in the compiler, synthesize, or hand-write assembly

Three routes exist. Rule-based compilers like LLVM try to pattern-match the primitive integer arithmetic directly to hardware instructions. Synthesis-based selectors like Rake use program synthesis to reason semantically about what instruction a piece of code equals. And when neither works, developers give up on portability and write the low-level hardware instructions by hand.
Why it fell short

Each forces a bad trade among quality, compile time, and portability

LLVM routinely fails to match even basic fixed-point patterns, so it leaves the fast instructions unused, inflates instruction counts, and forces wide intermediate values that halve vector throughput. Synthesis reasons powerfully but increases compile times by orders of magnitude, making it unusable in practice. Hand-written assembly is fast but non-portable, demanding fresh effort for every new chip. And building direct-translation rules means a separate rule for every idiom on every backend — a combinatorial explosion of compiler-engineering effort.
This paper's idea

Lift to a shared fixed-point IR, then lower, with rules learned offline

Pitchfork inserts a portable fixed-point intermediate representation, FPIR, whose instructions name the common idioms. It lifts messy integer code up into FPIR with one shared, target-agnostic rewrite system, then lowers FPIR into each chip's instructions with a small per-backend rewrite system — turning a rule per idiom-times-backend into a few rules each. The hard rewrite rules are learned offline by program synthesis from real code, so the expensive reasoning is paid once and compile time stays as fast as LLVM, for up to 8 times faster runtime.

Why this problem is worth solving

The difficulty starts with how alien fixed-point arithmetic is to the integer operations a language actually exposes.

Fixed-point is a way of representing fractional numbers using integers with an implied scale, and it powers high-performance signal processing — camera pipelines, quantized machine-learning kernels, image filters — because it needs simpler, more efficient hardware than floating point and spreads its representable values evenly. But unlike floating point, which scales dynamically, fixed-point forces the programmer to reason about the magnitude of every value. Most fixed-point operations increase precision, so after, say, adding two 8-bit values the programmer must decide what to do with the extra bit: drop it (with or without rounding), widen the result to a larger type, saturate (clamp to the maximum instead of overflowing), or simply wrap around. Each choice is right for some algorithm, and each is expressed as a different pattern of primitive integer arithmetic. So a conceptually simple fixed-point operation — a rounding average, an absolute difference, a saturating narrow — explodes into a large composition of primitive adds, multiplies, shifts, mins, and casts. A compiler is then supposed to recognize that whole composition and realize it equals one specialized hardware instruction. State-of-the-art compilers like LLVM routinely fail at this: they miss the fused multiply-accumulate, the dot-product, the saturating cast. Missing the match is not free — it leaves the fast instruction unused, lengthens the critical path, and often forces the computation to carry wider intermediate values, which cuts the number of vector lanes in half and can even require emulating types the hardware does not support.

Even when a compiler team is willing to write the matching rules, the effort scales the wrong way.

The natural approach is to write rules that translate the primitive integer patterns directly into each backend’s instructions. But consider the accounting. If there are k different ways a programmer might write a given idiom — say a rounding halving add — in primitive integer arithmetic, and n backends that each implement it as their own instruction, then a direct-translation compiler needs a rule for every combination: k times n rules, just for that one idiom, and the same blowup repeats for every idiom. Worse, the backends offer substantially similar fixed-point instructions, so this is largely redundant work done over and over. Pitchfork’s structural insight is to break the translation in half with a shared intermediate representation. First, lift any of the k integer spellings up to a single named FPIR instruction; that takes k rules, written once and shared across all backends. Then lower that one FPIR instruction to each of the n targets; that takes n rules. Plus one fallback that emulates the operation efficiently on backends lacking it. So k times n collapses to k plus n plus one. Adding a new backend now costs a handful of lowering rules instead of re-deriving every idiom, and adding a new idiom costs a few rules shared everywhere. The shared IR is what makes building and maintaining a fixed-point instruction selector tractable at all.

What people did before, and where it broke

Rule-based pattern matching (LLVM). Write rules that match primitive integer patterns directly to hardware instructions. Where it broke. LLVM misses even basic fixed-point patterns — converting a multiply into a shift and thereby breaking a multiply-add match, or having no rule for absolute difference — so the fast instructions go unused and vector throughput is halved by wide intermediates.
Synthesis-based instruction selection (Rake). Use program synthesis to reason semantically about which instruction a code fragment is equivalent to. Where it broke. The semantic search increases compile times by multiple orders of magnitude, which is unacceptable for everyday development, so it cannot be used in most real workflows.
Hand-written assembly and intrinsics. When compilers fail, write the low-level fixed-point instructions directly, as production systems like XNNPACK, libjpeg-turbo, and Photoshop do. Where it broke. It delivers speed but sacrifices portability, requiring significant and ongoing developer effort for every new hardware generation.
Direct-translation rule sets. Maintain per-backend rule sets mapping integer patterns to instructions. Where it broke. Because substantially similar instructions recur across backends, this demands a rule for every idiom on every target — a combinatorial explosion of redundant engineering effort.
The gap. No selector was simultaneously powerful (matching the complex fused fixed-point instructions), fast to compile, and portable across backends; you had to give up one. Bridging that with a shared IR plus offline-learned rules is what Pitchfork provides.

How Pitchfork works

From a tangle of integer ops to the right fixed-point instruction

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

The idea

Insert one shared layer so effort adds instead of multiplying. Rather than teach every backend to recognize every way of writing every fixed-point idiom, Pitchfork lifts all those spellings to a single named FPIR instruction once, then lowers that instruction per backend — collapsing a rule for every idiom-times-backend into a few lifting rules plus a few lowering rules. Replacing redundant per-target work with one shared representation reused across all of them is the same move the circuit-deduplication work covered elsewhere on this site makes, generating a single shared version of a repeated component instead of duplicating it for every instance and paying the combinatorial cost.

Lift to a clean abstraction first, so the hard matching becomes easy. The core mismatch is between messy integer arithmetic and the fixed-point idioms it stands for, and Pitchfork bridges it by normalizing the input up into a small, well-defined vocabulary before ever thinking about hardware, which turns an intractable direct match into two simple stages. Reducing a tangled domain problem to a clean, normalized form that standard, well-understood machinery can then handle is exactly the strategy the concurrency data-structure work covered elsewhere on this site follows, casting an awkward reachability question into a textbook primitive so an efficient standard method applies directly.

Pay the expensive reasoning once, offline, so every compile is fast. The powerful semantic search that lets a synthesis compiler match complex instructions is too slow to run on every build, so Pitchfork runs it ahead of time over real code, generalizes the results into rewrite rules, and ships those cheap rules to the compiler. Moving a rare, costly computation offline to make the frequent operation nearly free is the same bargain the virtualized-memory-translation work covered elsewhere on this site strikes, doing the expensive layout management infrequently up front so that the constant, high-frequency operation reduces to a single cheap step.

Following a Sobel filter through Pitchfork

Selecting instructions for an image gradient filter

Tracing the Sobel benchmark shows lift, then lower, then verified predicated rules.

Step 1 of 5

Start from portable integer code

A Sobel edge-detection filter is written in portable Halide and lowered to an expression of primitive integer operations — widening adds and shifts for the kernel, a min-and-cast that clamps the result to 8 bits — plus one absolute-difference idiom.

This vectorized integer tangle is what a conventional compiler would try to match directly.

Why it works

Naming an idiom makes it selectable. A fixed-point idiom explodes into a big tangle of primitive integer operations → but naming each idiom in a shared IR lets the compiler recognize it as one unit → so the fast fused instruction that implements it can actually be selected.
A shared IR turns multiplication into addition. Direct translation needs a rule for every idiom on every backend → but lifting to a shared IR splits that into k lifting rules plus n lowering rules → so adding a backend or an idiom costs a handful of rules, not their product.
Normalization makes lowering simple. Lifting canonicalizes many messy input spellings into a small set of idioms → so each backend’s lowering only faces fixed-point-to-fixed-point mapping → so the per-target rules stay simple and easier to get right.
Offline synthesis buys quality without compile-time cost. Powerful rule discovery is expensive to run → but doing it offline by synthesis from real code and generalizing bakes the results into cheap rules → so compile time stays as fast as LLVM while matching a synthesis compiler’s quality.
The right instructions keep values narrow. Primitive integer code forces wide intermediates and misses fused operations → but selecting the proper fixed-point instructions keeps values narrow and fuses work → so vector throughput doubles and runtime drops up to 8 times versus LLVM.

What it costs (trade-offs and scope)

It only does local rewriting, not global reordering. Term-rewriting matches local patterns, so it cannot perform the global computation reorderings a search-based compiler can, and it trails that compiler on benchmarks where such reordering is the key win.
It ignores data-movement (swizzle) optimization. On Hexagon, performance depends heavily on how data is shuffled between vector lanes, which Pitchfork does not optimize — the main reason it lags the synthesis compiler on that target, most on matrix multiply.
Its compile-time reasoning is deliberately limited. To stay fast, its bounds and predicate reasoning is simpler than a synthesis compiler’s, so it sometimes fails to prove a fact that would unlock a better instruction, or a specialized sliding-window instruction.
The offline synthesis leans on an oracle and a corpus. Lowering rules for two backends are generated using an existing synthesis compiler as the oracle (x86 rules are hand-written), and rule quality depends on the corpus of real fixed-point code, which is scarce enough that a strict train-test split was not possible.
Only the lifting rules are formally verified. The target-specific lowering rules are trusted but not yet proven correct, which would require formal models of every target instruction; that verification is left as future work.
It is instruction selection on already-vectorized code, inside Halide. Pitchfork picks concrete instructions for vectorized IR and does not itself vectorize; the prototype lives in the Halide compiler rather than LLVM, and a synthesized rule can occasionally regress a benchmark.

The evaluation

Three ways to select fixed-point instructions

Property	LLVM pattern matching	Synthesis (Rake)
Selects the fused fixed-point instructions		Yes, by synthesis
Compile time	Fast
Cost of adding a backend or idiom		A synthesis backend per target
Runtime versus LLVM	Baseline	Strong, but impractical

Three ways to select fixed-point instructions, evaluated on 16 fixed-point Halide benchmarks (quantized ML, computational photography, image processing, computer vision) across ARM Neon, x86 AVX2, and Hexagon HVX. Pitchfork's lift-then-lower design with offline-synthesized rules delivers geometric-mean speedups over LLVM of 1.31 times on x86, 1.82 times on ARM, and 2.44 times on Hexagon (up to 8.33 times), coming within 2 percent of the synthesis compiler Rake on ARM and 13 percent on Hexagon while compiling as fast as LLVM (or faster, by generating less IR) and at least three orders of magnitude faster than Rake — capturing synthesis-level quality at rule-based speed.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

Pitchfork is a clean answer to a real engineering trilemma: fixed-point instruction selection had forced a choice among quality, compile speed, and portability, and this work gets all three by adding a shared fixed-point IR and moving the expensive rule discovery offline. The lift-then-lower structure collapses a combinatorial rule count into a linear one, the offline synthesis captures a synthesis compiler’s quality at rule-based speed (up to 8 times faster runtime than LLVM, within a small margin of the synthesis baseline, while compiling as fast as LLVM and a hundred-thousand times faster than the synthesis compiler), and formal verification even hardened the lifting rules. Read it with its scope. Term-rewriting is local, so it misses the global reorderings and data-swizzle optimizations a search-based compiler finds, which is where it still trails on some targets; its compile-time reasoning is intentionally limited; only the lifting rules are verified, not the lowering ones; and the offline synthesis depends on an existing synthesis compiler as an oracle and on a scarce corpus of real fixed-point code. It selects instructions for already-vectorized code and lives in Halide rather than LLVM. The durable lesson is that the right intermediate abstraction, plus a willingness to pay expensive reasoning once offline, can dissolve a trade-off that looked fundamental — turning per-target, per-idiom drudgery into a small shared vocabulary that many backends and many programmers can reuse.

Background

Why portability keeps coming back to the right shared layer

It helps to see Pitchfork as one more instance of a recurring pattern in systems: the way to make one program run fast on many different pieces of hardware is almost never to hand-tune it for each, but to find the right shared abstraction that captures what the programs mean and lets a compiler specialize it per target. Fixed-point code kept being written in non-portable assembly precisely because no such abstraction existed for these idioms; FPIR supplies it, so a single portable program can reach the specialized instructions of chips as different as ARM, x86, and Hexagon. The unified-framework work covered elsewhere on this site pursues the same goal in a neighboring domain, building one common layer so that a technique written once applies across many otherwise-incompatible backends instead of being re-implemented for each. The broad lesson is that portability and performance are not opposites to be traded off but a design problem to be solved by abstraction: pick a vocabulary at the right level — high enough to be shared, precise enough to lower efficiently — and the same code can be both write-once and fast-everywhere, with the per-target expertise captured in reusable rules rather than scattered through hand-written variants.

If you remember only three things

1. High-performance signal processing runs on fixed-point arithmetic, and modern vector chips (ARM Neon, x86 AVX2, Hexagon HVX) offer rich specialized instructions with many rounding, saturating, and type-conversion modes, often fused. But portable code must express these idioms in primitive integer arithmetic, where a single fixed-point operation explodes into a large tangle of adds, multiplies, shifts, and casts. Compilers like LLVM routinely fail to match that tangle back to the fast instruction, leaving it unused, inflating instruction counts, and forcing wide intermediate values that halve vector throughput; synthesis-based selectors match well but compile orders of magnitude slower; and hand-written assembly is fast but non-portable. Building direct-translation rules also needs a rule for every idiom on every backend.
2. Pitchfork inserts a portable fixed-point intermediate representation, FPIR, whose instructions name the common idioms (saturating cast, absolute difference, rounding halving add, widening multiply-accumulate). It performs a two-stage lift-then-lower selection: a single shared, target-agnostic term-rewriting system lifts messy integer code into FPIR (normalizing it), then a small per-backend term-rewriting system lowers FPIR to each chip's instructions, emulating efficiently where an instruction is missing. This collapses a rule count of k-times-n into k-plus-n. The powerful rewrite rules are discovered offline by program synthesis from a corpus of real fixed-point expressions and generalized into cheap rules, so semantic reasoning is paid once; the same machinery formally verifies the lifting rules, and experts can write directly in FPIR.
3. On 16 fixed-point Halide benchmarks across three ISAs, Pitchfork achieves geometric-mean speedups over LLVM of 1.31 times (x86), 1.82 times (ARM), and 2.44 times (Hexagon), up to 8.33 times, coming within 2 percent of the synthesis compiler Rake on ARM and 13 percent on Hexagon while compiling as fast as LLVM (or faster) and at least three orders of magnitude faster than Rake; synthesized rules add up to 4.99 times over hand-written rules. Its limits: term-rewriting is local (missing global reorderings and Hexagon data-swizzle optimizations, where it trails Rake), its bounds reasoning is intentionally limited, only lifting rules are verified, the offline synthesis needs an oracle and a scarce corpus, and it selects instructions for already-vectorized code inside Halide.

Check yourself

Check your understanding

1. Why do compilers like LLVM fail to use a chip's fast fixed-point instructions?
2. What is the core structural idea of Pitchfork, and why does it reduce the rule count?
3. How does Pitchfork get the matching power of a synthesis compiler without its slow compile times?
4. Which statement best reflects Pitchfork's results and limitations?

Sources

The paper is “Fast Instruction Selection for Fast Digital Signal Processing” by Alexander J. Root, Maaz Bin Safeer Ahmad, Dillon Sharlet, Andrew Adams, Shoaib Kamil, and Jonathan Ragan-Kelley, published at ASPLOS 2023, DOI 10.1145/3623278.3624768. The authors are at Stanford University, Adobe, and MIT (with one independent researcher). The system is named Pitchfork and is built on the Halide compiler.

This explainer is written from the full text of the paper (the author-accessible version in the MIT DSpace repository, since the ACM Digital Library page was behind an anti-bot challenge). Everything above comes from the paper’s own sections: the introduction and overview motivating the impedance mismatch between fixed-point idioms and primitive integer arithmetic and the failures of rule-based, synthesis-based, and hand-written approaches; the fixed-point considerations (rounding, saturating, widening, wrapping) and the Sobel-filter motivating example with its lifted FPIR form and the eight optimizations Pitchfork finds over LLVM; the design of FPIR (portable, curated, integer-interoperable) and the k-times-n versus k-plus-n rule-count argument; the lifting and lowering term-rewriting systems and predicated rules; the offline rule synthesis (lifting-rule pairs, lowering-rule pairs generated with Rake as an oracle up to 10 IR nodes, and generalization) plus the formal verification of the lifting TRS; and the evaluation on 16 fixed-point Halide benchmarks across ARM Neon, x86 AVX2, and Hexagon HVX — the geometric-mean speedups over LLVM (1.31, 1.82, and 2.44 times, up to 8.33 times), the comparison to Rake (within 2 percent on ARM, 13 percent on Hexagon, and three-plus orders of magnitude faster to compile), the compile-time results, the synthesized-rules ablation (up to 4.99 times), and the limitations (local optimization only, data swizzling, limited predicates, x86 offline synthesis, and unverified lowering).