Vector instruction selection for digital signal processors using program synthesis

Compilers pick vector instructions by matching hand-written patterns, which means they only find what someone thought to write down — Rake searches for a provably equivalent instruction sequence instead, and beats a backend that Qualcomm and Google spent years tuning.

Why this problem is worth solving

Accelerators are how phones do image processing, and the only way to use them well is through exotic instruction intrinsics or a domain-specific language. Halide is the dominant answer for image and tensor code: you write the algorithm once, write a separate schedule describing how to tile and vectorise it, and the compiler produces optimised code for CPUs, GPUs or DSPs. It is used in production at Google and Adobe. But at the very bottom of that pipeline sits

The difficulty is that modern vector instruction sets are not uniform collections of arithmetic, and that fitting a computation onto them also requires deciding how data is arranged across lanes — a

What people did before, and where it broke

• Rely on LLVM’s own vectoriser and instruction selector. The general-purpose path. The paper is direct about why this is insufficient: LLVM cannot fully exploit complex vector sets like HVX, which is exactly why Halide carries its own backend-specific pass.
• Hand-written pattern-matching rewrites. Halide’s Hexagon optimiser is a list of patterns built by engineers experienced with that hardware. Effective, production-proven, and the baseline this paper competes against.
• Extend the pattern library. Prior work has added patterns to LLVM. It helps, but it does not change the fundamental property: matching is greedy, so a rule that fires early can foreclose a better sequence later, and no rule fires for a pattern nobody wrote.
• Formulate selection as dynamic programming. Elegant for tree-shaped problems, but struggles once expressions get large and the instruction set gets irregular.
• Enumerate instruction sequences up to a fixed length under a cost model. The superoptimiser approach. It finds things rule lists miss, but it either caps the sequence length far below what real loop bodies need or demands a sophisticated cost model to prune the search.
• Restrict synthesis to a manageable slice. Some prior work extracts a directed acyclic graph of operations with a single output, or targets middle-end IR rather than concrete instructions. Both scale better, but mostly on scalar code — vectorised code adds not just more instruction variety but the need for data shuffling between operations.
• The gap. Pattern matching is fast but blind; search is thorough but cannot reach the scale of a real loop body. Nobody had made synthesis-based instruction selection work on expressions dozens of instructions long against an instruction set with hundreds of members.

How Rake decomposes the search

The idea

Specify what the instructions mean, not how to use them. The pitch of the paper is a change in what a compiler developer has to supply. Under pattern matching you write rewrite rules and, implicitly, decide the order they should fire in. Under Rake you write down the semantics of the target instructions and the system searches for a sequence provably equivalent to the input. That shift is what makes the results possible: Rake found three separate optimisations in the Sobel filter alone that Halide’s rule set missed — recognising a sliding-window three-point reduction, using an accumulating variant of a multiply-add to fold away a following addition, and collapsing a minimum-then-cast into a single saturating instruction. Together they were worth 27% on that benchmark. Replacing an ordered list of rewrites with a search over a space that contains all of them at once is the same bet made by superoptimisers that explore equivalence classes rather than applying rules in sequence, covered elsewhere on this site.

Abstract the instruction set before searching it. The scaling trick is the uber-instruction. Modern ISAs implement far fewer distinct compute patterns than they offer intrinsics — many intrinsics are specialisations of one general idea differing only in saturation, rounding or width. So Rake defines a small vocabulary where, for instance, one uber-instruction covers every vector-scalar multiply-add form, including plain addition (a multiply-add whose weights are both one). Lifting the input into this vocabulary does two jobs at once: it groups the input operations that form a single compute pattern, and it tells the lowering stage which small slice of the ISA is worth enumerating. The design is a balance the paper is explicit about — too coarse and lowering becomes intractable, too fine and there are so many valid liftings and so few lowerings that the whole thing degenerates into a greedy selector. Deriving a compact abstract vocabulary from a target’s instruction set so that a search can operate above the level of raw intrinsics is the same manoeuvre behind efforts to generate vectorising compilers automatically from an ISA description, covered elsewhere on this site.

Decide what to compute before deciding how to move data. The third idea is to refuse to solve two problems at once. When Rake lowers an uber-instruction it inserts holes where loads and shuffles would go, each hole standing for a symbolic vector in which every lane may hold any available value of the right type. This means the synthesiser can pick compute instructions while treating data placement as free, and only afterwards work out which shuffles realise the placement it assumed. The separation also enables a subtler optimisation: because Rake parameterises lowering over the output layout, it can leave an intermediate result deinterleaved when a later instruction will undo the permutation anyway, or defer a shuffle to a point where it is cheaper — it costs far less to permute the output of a large reduction than to permute all of its inputs. Treating data movement as a distinct concern with its own cost, rather than something that falls out of the compute choices, is the same structural decision that separates vectorisation from layout in compilers for encrypted arithmetic, covered elsewhere on this site.

Following the Sobel filter through Rake

Across the 21 benchmarks this yields 450 qualifying vector expressions. Rake ignores scalar and trivial vector expressions — single variables, plain loads, scalar broadcasts — assuming LLVM handles those correctly.

Why it works

• The abstraction shrinks the branching factor where it matters. Hundreds of intrinsics at every step is intractable → lifting names the compute pattern first, so lowering enumerates only the intrinsics implementing that pattern → a synthesis problem that would not terminate becomes dozens of small ones.
• Bottom-up lifting turns one big query into many small ones. Sub-expressions are lifted before their parents → each query concerns a fragment, not the whole 38-instruction sequence → the approach scales to expressions of 103 intrinsics rather than the handful prior superoptimisers manage.
• Deferring data movement removes it from the compute search. Holes let the synthesiser assume any lane arrangement it likes → compute selection never reasons about shuffles → and layout becomes a parameter that can be optimised separately, letting a deinterleave be skipped when something downstream undoes it anyway.
• Search finds what nobody wrote a rule for. The space contains every equivalent sequence, not just the rewritten ones → Rake discovers optimisations requiring semantic reasoning, such as proving a value is never negative to unlock an unsigned-only multiply → these are exactly the context-dependent wins a syntactic pattern cannot express.
• Equivalence is proved, not assumed. Synthesis proposes a candidate satisfying a few input-output examples, then the solver either proves it correct or returns a counterexample that is added to the examples → so the aggressive rewrites are safe → which matters when the transformation depends on a range fact the programmer never stated.

What it costs (trade-offs and scope)

• Compilation takes about an hour per benchmark. The mean is 62 minutes, the median around 21. This is not a drop-in replacement for a pattern matcher; the authors position it as an offline fine-tuning tool, and as a way to discover which optimisations are worth adding to a hand-written backend.
• Data movement dominates and is not solved. Nearly 70% of compile time goes to synthesising shuffles, for three reasons the paper names: symmetry in the search space, no way to specialise the grammar because lifting supplies no semantic hints, and backtracking effort spent proving a shuffle is impossible within budget.
• The manual effort is reduced and relocated, not eliminated. You no longer write rewrite rules, but you do hand-derive the Uber-Instruction IR, and the paper states plainly that generated code quality is sensitive to that design. You also implement an interpreter for the target intrinsics.
• Half the benchmarks did not get faster. Of 21 benchmarks, 10 improved beyond the simulator’s 3% margin of error, 10 were unchanged, and 1 regressed to 0.93x. Manual inspection showed Rake often did improve instruction selection in the unchanged cases, but the benchmarks were memory-bound or the improvement was off the critical path.
• Performance is simulated, not measured on hardware. All numbers come from cycle counts reported by Qualcomm’s Hexagon Simulator v8.3.07.
• Portability is claimed, not demonstrated. Extending to ARM Neon is described as preliminary, with the encouraging observation that the HVX uber-instructions largely carry over and that much of the Neon interpreter could be generated from Halide’s existing ARM rewrite rules.

The evaluation

Check yourself

Sources

The paper is “Vector Instruction Selection for Digital Signal Processors using Program Synthesis” by Maaz Bin Safeer Ahmad, Alexander J. Root, Andrew Adams, Shoaib Kamil and Alvin Cheung, published at ASPLOS 2022, pages 1004-1016, DOI 10.1145/3503222.3507714. The authors were at Adobe, MIT CSAIL and UC Berkeley. The system is called Rake and its source is at github.com/uwplse/rake.

This explainer is written from the full text, read from the author copy hosted at people.eecs.berkeley.edu. All figures above come from the paper’s own sections 2, 6 and 7: the 18% average and 2.1x maximum speedup, the 0.93x worst case, the 10-of-21 improvement count and 3% simulator error margin, the 27% Sobel result, the 38-intrinsic Sobel expression and 103-intrinsic maximum, the 450 qualifying vector expressions, and the 62-minute mean and 21-minute median compilation times with their 9%, 21% and 70% breakdown. One small inconsistency worth flagging for readers checking against the original: the text describes a suite of 21 benchmarks while the caption of the speedup figure refers to 22; the per-benchmark discussion and the compilation-statistics table follow the count of 21, which is what is used here.