ADR 0015: Vectorizable fused pipelines
Status: accepted, 2026-10-03
Problem
Fused map/filter loops (ADR 0008) check every Int operation with __builtin_*_overflow and a trap branch. LLVM does not vectorize the overflow intrinsics, and each trap branch is an early exit, so clang left every checked pipeline scalar. A C++ programmer who keeps the same checks gets scalar code too; one who drops them gets SIMD and wrong answers on overflow.
Decision
Eligible fused pipelines get a second, branch-free loop body (crates/sspur-native/src/cgen/simd.rs) that computes each block of 64 elements with wrapping arithmetic and ORs every trap condition into a flag. One branch per block decides:
- flag clear: commit the block (sum, count, or written slice) and continue;
- flag set: discard the block and re-run exactly those elements with the ordinary sequential code, which traps at the same element, with the same kind and value, as before.
Every flag is a superset of the trap condition it replaces, so a clear block is one the sequential code would also finish without a trap. Results and traps are bit-identical to sequential semantics by construction.
What vectorizes
| Ending | Vector body |
|---|---|
Int sum | Unsigned block sum; each summand must lie in [-2^56, 2^56) and the running sum in [-2^62, 2^62], so no prefix inside the block can overflow |
len | Masked count |
map into a list (map stages only, scalar result) | Store into the preallocated buffer |
Stages are one-parameter lambdas built from literals, names, arithmetic, comparisons, if, to_f64, F64 abs/sqrt/floor/round, len, and indexing of captured scalar lists. Calls, **, and allocation keep the existing code. Filters become a keep mask: later stages run on every element, but their flags and contributions are masked, so a dropped element can never trap or count.
Checks become flags:
| Check | Flag |
|---|---|
a + b, a - b | sign bit of (a ^ r) & (b ^ r) (resp. (a ^ b) & (a ^ r)) |
a * k, constant k | a outside the exact range [MIN / k, MAX / k] |
a * b | either operand outside Int32; the product is then a widening 32 x 32 multiply (smull on NEON, pmuldq on x86) |
-a | a == MIN |
a / k, a % k, constant k not 0 or -1 | none needed |
xs[i], i the range variable | once per block: lo >= 0 && hi < xs.len |
Anything else (division by a variable, an index that is not the range variable) disables the vector body for that pipeline.
Small-value assumption
Flags cost instructions. The body is generated twice if needed: first plainly, and if that version still has flags, again under the assumption that the source element and every captured Int lie in [-2^30, 2^30). The interval prover (ADR 0007) then proves most operations safe; they compile to plain wrapping arithmetic, and each stage’s output interval feeds the next stage. The assumption itself is checked: per element for list sources, once per block for range bounds and captures. Proofs that depend on the assumption never justify a memory access or a division; index safety is re-proved with the assumed facts removed, and only literal divisors are allowed. Arithmetic in the vector body is always wrapping, so a discarded block never executes undefined behavior.
When blocks keep failing (data outside the assumptions), a miss counter stops attempting the vector body after about one block in eight, so the cost degrades to the old sequential loop.
The same blocking is used in the sequential warm-up of parallel pipelines and inside the parallel workers (ADR 0011); worker sums also track the block’s positive and negative parts, which bound its running sum for the overflow-safe combine. Plain xs.sum over Int uses the same scheme in a runtime helper.
Floats
F64 element-wise maps vectorize freely: there are no traps and no reassociation. F64 sums are left alone: the order of additions must stay sequential, and an ordered reduction is latency-bound, so vectorizing it gains nothing (measured slower). Sums now start from -0.0, matching the interpreter, so [-0.0].sum is -0.0 (fuzzing found the earlier 0.0).
No explicit vector type yet
docs/design/05-systems-layer.md lists Vec[T, N] and intr.* for Phase 5. They need checker and interpreter support that is outside the native backend, and the documented example (simd.zip(a, b).map(_ * _).sum) is already covered by fusing (0..a.len).map(i => a[i] * b[i]). Deferred.
Result
bench/native/simd (Int map/filter/sum, squares, counts, a mapped list, F64 dot product and saxpy over 1M-element lists, 40 rounds), Apple Silicon, best of 3: 0.25s against 0.29s for C++ -O2 with the same checks (0.86x); with SSPUR_THREADS=1 0.31s (before: 0.38s). Checked Int kernels run about twice as fast as before and as C++ (affine 18 ms vs 35 ms before and 42 ms C++). The two kernels that build new lists are bounded by first-touch page faults in the GC heap, not by the loops. Other benchmarks are unchanged or slightly faster.
Verification
tests/programs/pipelines.ssp covers sums that reach exactly MAX and MIN, values that force the sequential re-run without trapping, masked overflow in dropped elements, and indexing. vectorized_pipelines_trap_exactly_like_the_interpreter (suite) adds traps at elements 63, 64, 127, and 128, constant and variable multiply overflow, negation of MIN, out-of-bounds indexing, overflow before and after an index fault, and 2M-element pipelines, and requires identical output to the interpreter for 1, 3, and all threads. The 199-program corpus is identical normally, under GC stress, and single-threaded; fuzz --differential (with and without --edge) is clean on every suite program.