Automatic Generation of Vectorizing Compilers for Customizable Digital Signal Processors

Signal-processing chips get their efficiency from vector instructions, and every vendor variation and every custom instruction needs its own vectorizing compiler, which today means a human hand-crafting a set of rewrite rules by trial and error where an error costs an hours-long timeout; this paper (UT Austin) generates the whole compiler from an executable description of the instruction set — synthesising the rules automatically, then sorting them into three coarse phases purely by what each one does to the cost model, which is what makes the search finish at all, since the unsorted rules exhaust 64 gigabytes on a tiny convolution while the sorted ones solve it in three seconds.

The argument in one glance

Problem

The kernels that matter are the ones no library ships

Low-power devices — remote sensors, virtual reality headsets — hit their energy targets using digital signal processors, which are simple chips built around wide vector units. Large, regular computations are easy, because off-the-shelf linear algebra libraries already handle them. But applications have run into an Amdahl effect: what now limits them is a long tail of small, irregular, application-specific kernels that no library provides. Those have to be vectorised by a compiler, and there is a different compiler needed for every vendor variation of the instruction set and every custom instruction a team wants to add.
What people did

Search the space of vectorizations instead of picking one

The strongest existing answer treats vectorization as a search problem. Write down small local rewrite rules that relate scalar and vector forms, then use EQUALITY SATURATION to apply them in every possible order at once inside a data structure that holds all the equivalent programs simultaneously, and finally pull out the cheapest program according to a cost model. This works remarkably well, beating hand-written vendor libraries by an average of 3.1 times on exactly the irregular kernels that were the problem.
Why it fell short

Somebody still has to write the rules, and it is miserable

The rules are the compiler, and crafting them is a balancing act performed by hand. They must reach interesting programs without looping forever or triggering the NP-complete problem of matching terms up to associativity and commutativity. They must be sound, and rewrite bugs are common even in mature toolchains. The practical design method is trial and error, except that an error usually means an hours-long timeout and then reading a graph with millions of nodes to work out why. And the whole set is specific to one instruction set, so changing the hardware means doing it again.
This paper's idea

Generate the rules, then sort them by what they cost

This paper (UT Austin — Samuel Thomas and James Bornholt) builds Isaria, which produces the compiler from two things the previous approach already required: an executable description of the instruction set, and an abstract cost model. Rules are synthesised automatically rather than written. Then comes the part that makes it work: each rule is scored by what it does to the cost model and sorted into three coarse phases, which are applied one at a time. The phases are not a human ordering decision but a consequence of the cost function, and without them nothing finishes at all.

Why this problem is worth solving

The technique being automated here is worth understanding before the automation is, because its strength and its fragility come from the same place.

A traditional compiler applies transformations DESTRUCTIVELY and in a fixed order, so it must guess which rewrite to do first, and a wrong guess cannot be taken back. Equality saturation avoids the guess. Rewrite rules are applied not to the program but to an E-GRAPH, a data structure that compactly holds a whole set of programs together with the knowledge that they are equal. Rules are applied over and over until the graph stops changing, at which point it has SATURATED and contains every program reachable by applying the rules in any order, including repeatedly. Only then does a cost function pick the cheapest member. For vectorization this is a natural fit, because reaching a good vector form often requires a detour — the example the paper opens with needs a rule that rewrites a term into itself plus zero, purely so that a four-wide vector-add rule becomes applicable afterwards

The difficulty is that the rules are the compiler, and generating them automatically does not simply work.

Tools exist that take a language description and produce SOUND rewrite rules for it, verified against the semantics. Pointing one at this vector language produces 300 rules, against the 28 a human hand-wrote for the same processor, and trying to use them to vectorise a 2 by 2 convolution exhausts 64 gigabytes of memory without producing anything. Two things go wrong. The rules can run BACKWARDS, because a general synthesiser has no idea that the goal is vectorization, so it produces rules that undo it — and saturation guarantees that every reachable permutation of the unvectorized program will eventually be explored. And the rules are REDUNDANT, with many paths to the same result, including paths that vectorise and then unvectorise when plain scalar commutativity would have gone there directly. Both failures inflate the graph past the point where it can ever saturate

What people did before, and where it broke

Call an off-the-shelf vector library. Vendors ship tuned linear algebra kernels, and for large regular computations these are excellent.
But the bottleneck moved to the kernels libraries do not have. Applications are now limited by a long tail of small irregular custom kernels, which is precisely what a library cannot anticipate.
Use a general-purpose auto-vectorizer. Loop dependence analysis and superword-level parallelism work well on regular code, and the vendor Clang has improved substantially in recent years.
But irregular kernels defeat it. The measurements here show it doing fine on matrix multiplication and the quaternion product and being stymied by anything more complex, losing by up to 25 times.
Search the space with equality saturation and hand-written rules. The prior system takes this route and beats vendor libraries by 3.1 times on average.
But a human has to write and schedule the rules. They must be sound, terminating, and productive, they need custom logic saying when each may fire, and the whole set only applies to one instruction set.
Synthesise the rules with a general rule synthesiser. These tools produce verified-sound rules from a language specification, so soundness stops being a worry.
But the resulting set is unusable. Ten times larger than the hand-written one, full of rules that undo vectorization and of redundant paths to the same program, and saturation dies on the smallest benchmark.
The gap. The reason a person could make this work was never that they wrote better individual rules. It was that they also knew, informally, WHEN each rule was worth applying. Nothing in a rule synthesiser captures that, and nothing in plain equality saturation asks.

How a compiler gets generated from an instruction set description

From an ISA interpreter and a cost model to a working vectorizing compiler

Treat vectorization as a search over rewrite rules

Lift the scalar kernel into an expression language, apply rewrite rules to an E-graph until it saturates, and extract the cheapest program according to a cost model. This is the existing approach the paper builds on and reuses, including its front end and its back end that emits processor intrinsics.
↓ →
Synthesise the rules from an executable ISA specification new

Instead of writing rules, feed an interpreter for the instruction set to a rule synthesiser, which enumerates terms, proposes equalities between them, filters by testing, and verifies soundness against the semantics. The compiler writer now supplies a description of what the instructions do rather than a theory of how to use them.
↓ →
Tell the synthesiser that vector lanes are all alike new

Left alone, the synthesiser wastes its time rediscovering commutativity separately for every lane and every combination of lanes. So collapse each vector instruction to a single lane during synthesis, let it find the per-lane facts once, then widen the rules back to the real vector width with fresh wildcards per lane.
↓ →
Re-verify the widened rules and drop any that fail new

Widening assumes lanes do not interact, which would be wrong for cross-lane operations like reductions. Rather than trusting that, each expanded rule is formally checked against the executable specification. In this experiment none failed, which the authors attribute to how simple these processors are.
↓ →
Score every rule by what it does to cost, and sort into three phases new

Compute two numbers per rule from the cost model. A large drop in cost marks a rule that turns scalar code into vector code, a COMPILATION rule. Among the rest, an expensive pair of sides means both are still scalar, an EXPANSION rule, and a cheap pair means both are already vector, an OPTIMIZATION rule.
↓ →
Saturate one phase at a time, pruning between rounds new

Run expansion rules, then compilation rules, extract the cheapest program, and if it improved, start over from a fresh E-graph containing only that program. When it stops improving, run the optimization rules once. Restarting discards the rest of the graph, which is what keeps it small enough to search deeply.

Implemented on top of the existing compiler as roughly 1,900 lines, driven by an ISA specification of 73 lines and a cost function of 90, targeting an industrial Tensilica DSP.

The idea

Phases come back, but nobody chooses them. The usual argument for equality saturation in a compiler is that it dissolves the PHASE ORDERING problem — you no longer have to decide whether to inline before unrolling, because all the orders are explored at once. Isaria observes, apparently against that argument, that vectorization has natural phases anyway. A program starts fully scalar and ends fully vector, an individual rule is small, so the transition has to be gradual; and once a term has been profitably vectorised, applying more scalar rewrites to it is almost always wasted work, even though the graph cannot tell. The resolution is that these phases are not a human ordering decision reintroduced through the back door. They are read off the cost model, they are far coarser than a traditional compiler pass pipeline, and the ablation is decisive — with the phases removed, not one benchmark saturates, and every program extractable from the graph before it runs out of memory contains no vector instructions at all. Discovering that a structure the field had congratulated itself on eliminating is still needed, but should be derived rather than declared, is the same recover-the-good-part-of-the-old-approach move covered elsewhere on this site where a technique adopted to escape a rigid pipeline turns out to need some of that rigidity back, on different terms.

The synthesiser is sound but not goal-directed, and the cost model is where the goal lives. A rule synthesiser will happily give you a rule and its exact inverse, because both are true. Truth is not the property that matters here. Saturation applied to a set of true rules will, given enough memory, enumerate every permutation of the program you started with, most of them useless, and some of them reached by vectorising and then unvectorising. What distinguishes a useful rule is not its correctness but its ROLE in the journey from scalar to vector, and the only artefact in the system that knows anything about that journey is the cost function. So Isaria extracts the role from cost, using two numbers per rule — how much cheaper the right side is than the left, and how expensive both sides are in absolute terms. A large drop means the rule crosses from scalar to vector. A small drop with both sides expensive means it is still shuffling scalars around; a small drop with both sides cheap means it is polishing vectors. A purely syntactic test was tried and abandoned, because it mishandles rules whose real work is buried inside a nested subterm. Recovering intent from a quantitative model when the symbolic form does not reveal it is the same let-the-cost-function-say-what-you-mean discipline covered elsewhere on this site where a compiler is steered by what the hardware actually charges rather than by the shape of the code.

Giving up completeness makes the search find better answers, not worse ones. Between rounds, Isaria extracts the single cheapest program and throws the entire E-graph away, restarting from that one program. This is straightforwardly greedy and abandons the completeness guarantee that motivated equality saturation in the first place, and on small kernels it does cost a little quality — with pruning disabled, the compiler occasionally finds a slightly better result. But on large kernels the relationship inverts, and pruning finds FASTER programs than not pruning, because the graph stays small enough for the search to go deeper before memory runs out. There is a nice observation attached: synthesised rules tend to be shortcuts that compress what a human would have written as several rules, which grows the graph faster but also travels further per iteration, and pruning is what lets you take the upside without the downside. Deliberately trading a guarantee you cannot afford for depth you can is the same bounded-search-beats-exhaustive-search instinct covered elsewhere on this site where restricting the space being explored is what allows a tool to explore any of it usefully.

Watching the rules get sorted and applied

From 7,735 candidate rules to a vectorized kernel in three seconds

All measurements from the paper, targeting a Tensilica Fusion G3 DSP with results from its cycle-level simulator.

Step 1 of 5

Start with rules that are correct and useless

A general rule synthesiser is pointed at the vector language. It considers 7,735 candidate rules and, after filtering out the ones derivable from others, keeps 300 — an order of magnitude more than the 28 a human wrote for the same processor. Every one of them is verified sound. Handing them to equality saturation exhausts 64 gigabytes on a 2 by 2 convolution and returns nothing.

tweaking the saturation settings reduces the memory but still finds no vectorized program after an hour of searching
for comparison, the finished system solves the same kernel in 3 seconds using 0.2 gigabytes

Why it works

The compiler writer already had to supply an executable ISA description and a cost model → those two inputs are enough to synthesise verified-sound rewrite rules → so nobody needs to hand-write rules or reason about their termination.
A rule synthesiser has no notion of the goal and will produce inverses of its own rules → the cost model is the only component that knows scalar is expensive and vector is cheap → so sorting rules by their effect on cost recovers what each rule is FOR.
A program moves gradually from fully scalar to fully vector, and scalar rewrites are near-useless once a term is vectorised → running expansion, compilation and optimization rules in separate saturations removes that interference → turning a search that never finishes into one that finishes in seconds.
Extracting one program and restarting from a fresh graph discards everything else → the graph stays small enough to keep exploring rather than filling memory → which on large kernels yields faster code than the complete search does.
Vector lanes behave identically and independently → collapsing to one lane during synthesis and widening afterwards avoids rediscovering the same algebra per lane → letting the synthesiser reach genuinely interesting vectorization rules.

What it costs (trade-offs and scope)

Compilation is slower. An average of 2.1 times slower than the hand-crafted compiler, because the synthesised rule set is larger. The authors argue the productivity gain is worth it, which is a judgement rather than a measurement.
It fully unrolls loops. That is how the parallelism is exposed, but it produces a 77,000-line C function for the largest convolution, and on large kernels both this system and its predecessor lose to hand-written library code that keeps its loops.
Pruning is greedy. Completeness is abandoned, and on small kernels disabling pruning sometimes finds a slightly better result. The benefit only appears once kernels are large enough for memory to be the binding constraint.
The phase boundaries are two hand-chosen numbers. The rules do fall into visible clusters and a wide range of values works, but the authors say plainly they would prefer to derive the boundaries automatically and have not.
The ISA customization demonstration is about process, not speed. Adding two new instructions to accelerate QR decomposition yields 1.7 percent, 0.5 percent, and 2.0 percent together. The claim being supported is that a DSP engineer can try an instruction without building a compiler, not that these instructions are valuable.

The evaluation

The benchmarks are the ones the prior system used, drawn from computer vision and machine perception: two-dimensional convolution, matrix multiplication, QR decomposition and the quaternion product, compiled as a specialised kernel per input size because real libraries also pick an implementation by size. Performance comes from the vendor cycle-level simulator, normalised against unvectorized C++ compiled with auto-vectorization switched off. The two ablations matter more than the headline numbers, since they establish that the phasing and the pruning are load-bearing rather than tuning.

Property	Hand-written rules	Synthesised rules, unphased	Synthesised rules, phased and pruned
Who writes the rules
Does the search finish
Memory on a small convolution
Speed versus vendor library kernels
Effort to try a new custom instruction

Against the hand-crafted equality-saturation compiler the generated one is 34 percent faster on average, skewed by large kernels where the hand-crafted compiler runs out of memory; against the vendor auto-vectorizer it wins by up to 25 times. Offline rule synthesis takes about a day by default, but shrinking that to 60 seconds costs only 1.4 times performance on average, and the step runs once per instruction set rather than once per program.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

Read the comparison against the hand-crafted compiler carefully. The 34 percent average advantage is stated by the authors themselves to be skewed by large kernels where the competitor runs out of memory before finding a good vectorization, so the honest summary is parity on kernels both can handle, plus an advantage where the other one fails. The strong claim is elsewhere, in the ablations: with phasing removed, no benchmark saturates and nothing extractable from the graph uses a single vector instruction, which is about as clear as a negative result gets. Compilation is 2.1 times slower than the hand-crafted compiler, and the argument that automation is worth that price is a judgement rather than something measured. Two limits are structural. The system fully unrolls loops to expose parallelism, which produces a single 77,000-line C function for the largest convolution, breaks the vendor simulator, and means both this compiler and its predecessor lose to library kernels that keep their loops at large sizes — the authors name loop-aware saturation as the fix and do not have it. And the phase boundaries are two constants chosen by hand; the paper shows the rules fall into visible clusters and that a wide range of values works, then says directly it would prefer to derive them automatically. Finally, the custom instruction study demonstrates a workflow rather than a win, with speedups of 1.7, 0.5 and 2.0 percent, and the new instructions were not added to the closed-source simulator but substituted with instructions of the expected latency.

Background

When the technique that removed a structure needs it back

This paper sits in the site’s compilers cluster and rhymes with several ideas covered elsewhere on this site. Its sharpest connection is a disagreement rather than an echo: the high-level-synthesis superoptimizer page presents equality saturation precisely as the escape from phase ordering, and this paper finds that inside that escape, coarse phases are not merely useful but necessary, with the difference being that here they are derived from a cost model rather than decreed by a person. Its diagnosis that a synthesised rule can be perfectly sound and still actively harmful, because soundness says nothing about direction, rhymes with the encrypted-arithmetic vectorizing compiler page, where aggressive vectorization can leave code slower than scalar because the real cost lives somewhere the transformation does not look. Its motivating scenario — a hardware team wanting to try a custom instruction and being blocked by the toolchain that would have to understand it — is the same barrier the portable custom instruction page attacks from the hardware side, and both conclude that the right fix is to let a compact specification stand in for the expertise. Its willingness to abandon a completeness guarantee in exchange for a search that fits in memory is the same bounded-exploration bargain the compiler autotuning and tensor scheduling pages make. And its structure — spend a day offline per instruction set so that every subsequent compile is cheap — is the same amortise-it-once-per-target arrangement several accelerator pages rely on.

If you remember only three things

1. Digital signal processors get their efficiency from vector instructions, and the kernels that now limit embedded applications are small, irregular and custom, so a library cannot supply them and a vectorizing compiler must. The best existing approach searches for a vectorization using equality saturation, which applies rewrite rules in all orders at once inside an E-graph and then extracts the cheapest program. It beats vendor libraries by 3.1 times. But a person has to write the rewrite rules and the logic saying when each may fire, by trial and error in which an error means an hours-long timeout, and the whole set applies to exactly one instruction set.
2. Synthesising the rules automatically is easy and produces something unusable. A general synthesiser verifies soundness but knows nothing about the goal, so it emits rules alongside their own inverses; equality saturation then guarantees exploring every permutation of the unvectorized program, including permutations reached by vectorising and unvectorising again. The result is 300 rules where a human wrote 28, and 64 gigabytes exhausted on a 2 by 2 convolution with no answer. The fix is to notice that the cost model is the only component that knows scalar is expensive and vector is cheap, and to use it to infer what each rule is FOR — a large cost drop marks a rule that vectorises, while among the rest an expensive pair of sides marks scalar rearrangement and a cheap pair marks vector polishing.
3. Applying those three groups in separate rounds, and discarding the entire E-graph between rounds to restart from the single best program found, turns a search that never finishes into one that takes three seconds and 0.2 gigabytes. Both moves are load-bearing: without phases no benchmark saturates and nothing extractable uses any vector instruction, and pruning gives up completeness yet finds FASTER code on large kernels because the graph stays small enough to search deeper. The generated compiler beats expert-written vendor kernels by 3.5 times on average from 163 lines of ISA specification and cost model, at the price of compiling 2.1 times slower and unrolling loops until a kernel becomes a 77,000-line function.

Check yourself

Check your understanding

1. Pointing a general rule synthesiser at the vector language produces 300 sound rules, and equality saturation with them exhausts 64 gigabytes on a tiny convolution without ever producing vectorized code. Predict what is going wrong, given that every rule is verified correct.
2. The rules must be sorted by role, but the synthesiser does not label them and the obvious syntactic test — is the top node of each side scalar or vector — was tried and abandoned. Predict what Isaria uses instead.
3. Between rounds, Isaria extracts the single cheapest program and throws the whole E-graph away, restarting from just that program. This abandons the completeness guarantee that made equality saturation attractive. Predict the effect on the quality of the compiled code.
4. Equality saturation is usually motivated as the cure for phase ordering, yet this paper reintroduces phases and shows they are essential. Predict how the tension is resolved.

Sources

Samuel Thomas and James Bornholt. “Automatic Generation of Vectorizing Compilers for Customizable Digital Signal Processors.” ASPLOS 2024, La Jolla. The University of Texas at Austin. DOI 10.1145/3617232.3624873. The system is named Isaria. The work was subsequently selected as a Communications of the ACM research highlight.
Full text of the paper was used for this explainer, including the background on rewriting for vectorization and the E-graph explosion example in Section 2, the rule generation, phase discovery and compile-time scheduling in Section 3, the implementation breakdown in Section 4, and all five evaluation questions in Section 5 covering performance, the phasing and pruning ablations, the offline budget, the ISA customization study and the parameter sensitivity analysis.