ADR-0001 — The QBE backend¶

• Status: Accepted. QBE ships as an opt-in second backend, verified byte-identical to the C backend and benchmarked (see the benchmarking guide for current figures).
• Context: the report below (originally notes/01-qbe-port.md, carried into postc) documents the QBE port — what it covers, how correctness was established, and a full account of performance.

Status: working, verified byte-identical to the C backend, benchmarked. Merged as an opt-in second backend alongside C.

Scope of this note: what the QBE port is, what it does and doesn't cover, how correctness was established, and a full account of performance — including the ceiling we cannot cross and the headroom we chose not to chase yet.

1. Summary¶

postc now has a second code generator, postc/compiler/backends/qbe.py (~950 lines), that lowers the same typed SSA IR as the C backend to QBE IL. qbe turns that into native assembly, which cc assembles and links. It is selected with build_file(..., backend="qbe") or postc build --backend qbe; the default stays c.

The headline results:

• Correctness by parity. On every kernel we tested, the QBE-compiled artifact produces byte-identical native output to the C-compiled one, verified end-to-end through the real NumPy generalized-ufunc ABI. This is backed by 416 passing tests and fuzz harnesses that compare the two backends bit-for-bit across random inputs.

• Coverage. The full scalar + array kernel subset the C backend supports — arithmetic, casts, floor-div/mod/pow, abs, select, arrays (including 2-D indexing), mutable locals, cross-module/libm calls, and the NumPy ufunc inner loop — except complex numbers, Float16, and Str/Bytes, which raise a clear error and stay on the C path.

  Amended — two claims in that sentence have since become false

  There is no "C path", and there never was any automatic routing: build.py reads exactly one capability (ext_module, at build.py:381) and it rejects rather than routes. A Complex128 program built with --backend qbe fails with a diagnostic, and the user chooses the C backend themselves. And Float16/Str/Bytes are no longer a backend matter at all — commit e516af4 made them PP900 in the frontend, on every backend including C, because the C backend was not storing Float16 but truncating it to an integer. The rest of the sentence still holds.

  • Performance. After several rounds of IR-level optimization, QBE runs about 1.25× slower than cc -O2 on average (geomean ~0.80× of C, up from 0.37× for the naive lowering), and about 50× faster than CPython. Every benchmark kernel is now within striking distance of the optimizing C compiler. Notably, the last of the gap was not SIMD or FMA — cc -O2 emits neither for these FP reductions (both would change the result, so it can't without -ffast-math). It was loop unrolling, which QBE now does at the IR level, bit-exactly (see §6.5).

2. Motivation and the shape of the decision¶

The existing C backend emits C99 and leans on the system C compiler for optimization, libm, complex arithmetic, and the CPython/NumPy extension glue. A QBE backend was proposed as an alternative code generator: smaller, self-contained, dependency-light, fast to compile, and a good vehicle for controlling code generation directly rather than delegating to cc.

QBE's type system is minimal — w (32-bit int), l (64-bit int/pointer), s (f32), d (f64), plus b/h in memory. Two things fall outside it:

• Complex numbers. QBE has no complex type. The C backend uses double _Complex and libm's cpow/cabs. Reproducing that in QBE would mean lowering every complex value to a pair of doubles and hand-implementing complex arithmetic.
• The CPython/NumPy extension glue. --ext-module emits C-API macro code (PyUFunc_FromFuncAndData, PyModule_Create) that is C by nature regardless of backend.

Rather than replace C, we added QBE alongside it: C remains the path for complex numbers and extension modules, QBE handles the int/float/bool + array kernel subset. This keeps everything working and lets the two backends validate each other — which turned out to be the single most valuable design choice, because "byte-identical to C" became a testable oracle for the entire port.

3. Architecture and pipeline¶

The IR (postc/compiler/ir.py) is backend-agnostic: typed SSA values, basic blocks with explicit terminators, one instruction per operation. Both backends consume it unchanged.

POST Python source
  → checker → frontend (AST → IR) → typechecker
  → backend:
       c   : emit_module → C99 → cc -O2 -c → .o
       qbe : emit_module → QBE IL → qbe → .s → cc -c → .o
  → link all .o (+ the C export-wrapper TU) → .so / .dylib

Key integration points:

• Shared ABI. QBE follows the platform C ABI, so a QBE function d $f(d, d, d) is call-compatible with a C double f(double, double, double). The stable pp_<name> export wrappers (abi.py) are compiled as C for both backends and link against QBE-produced objects without change.
• Build driver. build.py's _link_modules is backend-aware: per module it either emits C and runs cc -O2 -c, or emits QBE IL, runs qbe, then cc -c on the assembly. The export-wrapper TU is always C.
• Integer power. a ** b on integers lowers to a call into a tiny C runtime (IPOW_RUNTIME_C — extern copies of the C backend's static ipow helpers), linked only when a module actually uses integer **.

Anything the QBE backend cannot lower raises QBEUnsupported, so the build fails loudly rather than miscompiling — consistent with the project's rule to reject unsupported semantics rather than change behavior silently.

4. What works¶

Scalar operations¶

• Arithmetic + - * / and comparisons == != < <= > >=, per dtype, with the correct QBE ops and signed/unsigned dispatch.
• Floor division, modulo, power matching the C backend's exact (and sometimes deliberately non-Pythonic) semantics — signed floor-div rounds toward −∞ via an inline correction; integer % is C's truncated remainder (as the C backend does, not Python's floored %); float mod/pow route through libm; integer pow uses the shared C ipow runtime.
• Unary neg, logical not, and abs (libm for float, a branch-free (x^m)-m for signed ints).
• The full numeric cast matrix — int↔int (width and signedness), int↔float (swtof/sltof/stosi/…), float↔float (exts/truncd), and the special case that conversion into Bool is a compare-against-zero, not a truncation.
• Select (ternary) lowered to a phi diamond, since QBE has no select instruction.
• Mixed-type operands. QBE has no implicit promotion, so the backend inserts explicit coercions (e.g. double / int64 → convert the int operand to double first) and applies C's usual-arithmetic-conversion and integer-promotion rules for comparisons.

Arrays¶

• ArrayLoad/ArrayStore/ArrayDim/ArrayStride/Alloc and len(), lowered against the __pp_array view struct (data, ndim, shape, strides, offset_bytes) with byte-offset indexing matching the C __pp_array_at macro.
• 2-D indexing (a[i][p]) via stride arithmetic — no sub-view objects, so matmul's triple loop lowers cleanly.

Mutable state¶

The IR is not strictly SSA: a local reassigned in a loop, or an output-by-pointer parameter, reuses one value name across blocks. Each such name gets an alloc8 stack slot in the entry block, with load/store on every read/write; instruction results are always fresh single-assignment names, so only AssignValue targets ever need a slot. (qbe's own register allocator then promotes most of these slots back into registers — see §6.)

The NumPy ufunc loop¶

<name>_ufunc_loop is emitted in QBE IL, ABI-compatible with the C backend's emit_ufunc, so the same PyUFuncGenericFunction registration works. It handles the three shapes: scalar-output @vectorize (kernel returns a value stored to the output slot), array-core @guvectorize (per-argument stack-allocated __pp_array views), and multi-output void kernels (modf, frexp).

5. Correctness and verification¶

Correctness rests on a testable oracle: the QBE output must be byte-identical to the C output. Everything is driven through the compiled artifacts.

• Unit + integration tests (tests/test_qbe_backend.py, 23 tests): each kernel is built through both backends and driven via ctypes — scalar wrappers, the dot kernel and its gufunc loop, a fused vectorize loop with a Select, and the sub-word / reassigned-parameter regressions described below. The full suite is 416 tests.
• Fuzz harnesses compare QBE vs C bit-for-bit over random inputs across every example (gaussian, dot, norm, matmul, all of ufuncs_unary/binary/ternary) and across dtypes (Float32/64, Int8–64, UInt8–64, Bool), driving the real gufunc ABI with byte strides taken straight from NumPy.
• The benchmark's proof section (benchmarks/bench.py) reports, for each kernel, byte-identical parity (0.0e+00) and the relative error against a NumPy/analytic reference.

Bugs the verification caught¶

Every one of these was a real backend bug, found by fuzzing or an adversarial code review:

1. Reassigned parameters read uninitialized memory. A parameter that is reassigned (e.g. magnitude in copysign) becomes a stack slot, but the incoming register value was never stored into the slot — the first read returned garbage. Fix: seed each reassigned-parameter slot from its register at entry.
2. Mixed-type binops produced invalid IL. term * xc / k (Float64 / Int64) leaned on C's implicit int→float promotion, which QBE does not do — qbe rejected the IL with a type error. Fix: coerce operands to the result type for arithmetic, and to the common type for comparisons.
3. Sub-word integer results were observed non-canonically. Int8: (100+100) < c compared 200 instead of C's (int8)200 = −56, because QBE keeps the full 32-bit word while C truncates on assignment. Fix: re-narrow sub-word arithmetic results to width (_NARROW).
4. _common skipped C integer promotion. Int8(−1) < UInt8(1) compared unsigned at 8 bits and gave the wrong sign. Fix: promote sub-word operands to signed int32 before choosing the comparison, matching C.

Several harness bugs surfaced along the way too (separate RNG workloads for the two backends, a missing core-dimension argument to matmul, a wrong math.modf reference) — worth recording because they were initially indistinguishable from backend bugs until isolated. The discipline that resolved them: when both backends behave identically-wrongly, the test itself is at fault.

One genuine pre-existing bug was found but is out of scope: the frexp example kernel infinite-loops on negative input (while m < 0.5 with no abs()). This is a bug in the example source, compiled faithfully by both backends.

6. Performance¶

Diagnosis¶

Reading the arm64 that qbe actually emits was more informative than any assumption. The surprise was what qbe does do:

• Register allocation and mem2reg. The dot accumulator lives in a register (d0), the loop counter in x4 — qbe promotes the stack slots we emit. So the stack-slot approach to mutable locals is not the bottleneck.

What qbe deliberately does not do, and the assemble-only cc -c cannot add back:

• No LICM. dot's inner loop reloaded each array's data, offset_bytes, and strides[0] every iteration (~10 redundant loads/iter).
• No strength reduction. i*stride was recomputed each iteration instead of incrementing a pointer.
• No inlining. The scalar ufunc loop did bl _square per element — 2M calls for a 2M-element workload.
• No auto-vectorization / FMA. Scalar fmul + fadd; no SIMD, no fused multiply-add.

The C backend gets all of these from cc -O2 for free. QBE needs them at the IR level — which is where we have leverage.

Optimizations added¶

Five passes, each verified to keep the output byte-identical to the C backend:

1. Array-metadata LICM (_hoist_array_meta). An array parameter is an immutable pointer available in the entry block, which dominates every loop. So its data+offset base, per-axis strides, and shape are computed once in entry and reused — no dominator analysis needed, correct by construction.
2. Ufunc-loop strength reduction + view hoisting (in emit_ufunc_loop). Every ufunc argument pointer is a loop induction variable (p += step), replacing the per-element i*step multiply; and the per-argument view's invariant fields (shape, strides, ndim, offset) are built once in @start, with only the data pointer moving per iteration.
3. Scalar-kernel fusion (_inline_scalar_kernel + _rename_instr). A single-block scalar kernel is spliced into the ufunc loop instead of called per element. The kernel's IR is cloned with every value name prefixed (so it cannot collide with loop temps), its parameters bound to the loaded inputs, and its return value stored directly. This handles declared locals, libm calls, casts, and even Select diamonds inside the loop body; multi-block kernels fall back to a call.
4. Kernel-loop strength reduction (_plan_strength_reduction). The one pass that needs real analysis: it builds the CFG, computes dominators, finds natural loops from back-edges, identifies each loop's basic counter (a slot reassigned to iv + 1), and rewrites array accesses into induction pointers bumped by the counter's stride in the loop's step block. It decomposes the byte index into a sum of var*stride products: the term in the loop's counter drives the pointer bump, and the outer-loop terms are folded into the pointer's per-entry initialisation in the loop preheader — so matmul's nested a[i][p] (index i*s0 + p*s1) strength-reduces too, its a-pointer starting at base + i*s0 each inner-loop entry and bumping by s1. Loops are processed innermost-first so each access is claimed by the loop whose counter varies fastest. This turns mul; add; load into load; add and lets independent loads issue in parallel — a ~1.8× inner-loop win measured in isolation. It fires only when it can prove the pattern (counter starts at 0, steps by 1, index is a clean sum of var*stride-of-that-array products with the outer vars loop-invariant); anything unclear falls back to the LICM'd code. Because every pointer bumps by the runtime stride from the view, non-contiguous (Fortran-order, reversed) inputs stay correct.
5. Loop unrolling (_plan_unroll). Counted reduction loops whose body is one straight-line block, whose array accesses are all strength-reduced, and whose counter is used only in those (now-dead) indices are unrolled by 4: the body is cloned per replica (renaming only its non-slot temps, so the accumulator stays threaded through its stack slot — preserving the exact serial fadd order, hence byte-identical), the induction pointers are bumped between replicas, and the counter steps by 4, with a remainder loop for the leftover iterations (trip count rounded down with n & -4). This amortizes the loop branch and exposes load/multiply ILP — clang's only real edge on dot. Scoped to top-level loops (dot, norm); the C backend's dot at -O2 is likewise a scalar-but-unrolled loop, so this closes most of the gap without changing the arithmetic.

Measured effect¶

Runtime as a fraction of cc -O2 (higher is better), naive lowering → optimized. dot shows the two stages: after the shared passes, then after kernel-loop strength reduction.

So QBE moved from ~2.7× slower than optimized C to ~1.25× slower on average, and every kernel is now within striking distance of the optimizing C compiler — matmul, previously the worst at 0.36×, reached 0.77× once summed-index strength reduction gave its nested inner loop the same pointer-bumping treatment. Against CPython the compiled kernels are ~50× faster (geomean). Codegen time is roughly at parity with cc -O2 (~1.1× geomean, qbe ahead on the array kernels); end-to-end build time is dominated by the shared C export-wrapper compile and link.

gaussian is instructive: it is exp-bound (both backends call the same libm), so once the per-element call and index math are gone, QBE's slightly leaner loop actually edges alongside or ahead of C.

(All figures are min-of-runs on a machine that was under load during this work; the backend-to-backend ratios within a run are the trustworthy metric; the absolute milliseconds drift by 20–30% between runs.)

The ceiling¶

A word on where the last of the gap went, because an earlier draft of this note got it wrong. The residual is not SIMD or FMA. Disassembling the C backend's dot at cc -O2 shows zero fmadd/fmla and zero vector registers — it is a scalar fmul/fadd loop, exactly like QBE's. Clang cannot vectorize or contract an FP reduction at -O2 because either transformation reorders the summation and changes the bits; both are gated behind -ffast-math. Clang's only advantage on dot was loop unrolling — several elements per iteration (independent loads and multiplies, a single serial fadd chain), amortizing the loop branch and hiding load latency. That is an IR-level transform preserving the exact summation order, and pass 5 above now does it: dot went from 0.67× to 0.85× of C (a 1.27× speedup, matching a hand-unrolled prototype), byte-identical throughout. The true architectural ceiling — genuine SIMD, which QBE has no vector types for — only becomes relevant under a -ffast-math contract that permits reassociation, which this project does not adopt (it would break the byte-identical guarantee that is the whole correctness oracle). For memory-bandwidth-bound kernels (square moves 32 MB) none of this matters and QBE already matches C.

An earlier draft of this note listed counter elimination — replacing the i < n bound test with an induction-pointer-vs-end-pointer comparison and dropping the counter — as reachable headroom (measured at ~0.83× of dot). It is not safe. That transformation assumes the stride is positive, but NumPy passes negative strides for reversed views (a[::-1]), which the compiler cannot detect: the pointer then moves backward and ptr < end is the wrong test from the first iteration. The kernel-loop pass deliberately keeps the counter for exactly this reason — a pointer bumped by a runtime stride of either sign accesses the right elements, but only the counter gives a sign-independent bound. (Verified with a negative-stride regression test.) The measured 0.83× was on positive-stride inputs and does not generalise.

7. Limitations¶

Not lowered (raise QBEUnsupported, stay on the C backend)¶

• Complex numbers (Complex64, Complex128) — no QBE complex type; would require lowering to double-pairs and hand-implementing complex arithmetic and cpow/cabs.
• Float16 — stored as uint16 bits in C; QBE has no half-float arithmetic.
• Str / Bytes — pointer types not yet modeled.
• --ext-module — the CPython/NumPy registration shim is C-API macro code and stays on the C path by design (the QBE-emitted _ufunc_loop is still ABI-compatible and links against a C shim, so this is a soft boundary a later phase can cross).

Performance limitations¶

• Unrolling is scoped; no SIMD. Loop unrolling (§6.5) is applied only to top-level counted reduction loops (dot, norm); matmul's nested inner loop is strength-reduced but not unrolled. Genuine SIMD is a real ceiling — QBE has no vector types — but it only applies under -ffast-math reassociation, which this project deliberately does not use.
• Kernel-loop strength reduction is deliberately scoped. It handles counted loops (including nested ones) whose array indices are a clean sum of var*stride products — which covers dot, norm, and matmul. It deliberately does not handle non-zero loop starts, non-unit steps, or indices that aren't sums of stride-products; those fall back to the LICM'd code. It also keeps the loop counter rather than eliminating it (see §6 — counter elimination is unsafe for negative strides).
• QBE target defaults to the host. No -t flag is passed; cross-compilation would need one.

Engineering caveats¶

• The fusion inliner uses a fixed _inl_ name prefix; a source value literally named _inl_* would collide. This is extremely unlikely (frontend names are plain identifiers and generated v1/cmp2 forms) and would surface as a qbe duplicate-definition error, not silent miscompilation — but it is a sharp edge worth knowing about.
• Benchmark numbers are sensitive to machine load; the ratios between backends (self-normalizing within a run) are the trustworthy figures; the absolute milliseconds are unreliable.

8. Future work¶

Roughly in order of value-to-effort:

1. Multi-block kernel fusion — extend inlining from straight-line kernels to ones with real branches (relu, clip, sign), by relabeling their blocks uniquely and turning each return into a jump to a phi join. Would give branchy elementwise kernels the same call-elimination win square got. (Loop unrolling, previously listed here, is now done — §6.5.)
2. Unroll nested loops — extend the unroll pass past top-level loops so matmul's inner loop unrolls as well as strength-reduces.
3. Complex support — if parity with the full C backend is wanted, lower complex to double-pairs. Large, and the payoff depends on how much real code uses complex.
4. A fast-math mode — the only way past the last of the gap on compute-bound kernels is reassociation (SIMD reductions) and FMA, both of which change results. That is a deliberate, opt-in correctness trade-off — it gives up bit-exactness with cc -O2. If it is ever wanted, the clean design is an optional LLVM backend for hot kernels (LLVM already has vectorization and FMA), keeping QBE as the fast-compiling, bit-exact default. Forking QBE to grow vector types would be a large effort to reimplement a slice of LLVM.

9. How to reproduce¶

# tests
uv run pytest

# benchmarks vs the postpyc baseline
uv run python -m benchmarks run

# build any kernel through the QBE backend
postc build FILE.py --backend qbe

In postc the harness lives in benchmarks (the python -m benchmarks command); timing methodology (warmup, adaptive run-until-stable, IQR outlier removal, min-as-headline, geometric-mean speedups) is adapted from the p2w benchmark harness. See the benchmarking guide.

10. File map¶

The reference implementation's guiding rule held throughout: reject unsupported semantics clearly rather than accept code and change its behavior. The byte-identical-to-C oracle is the concrete expression of that rule — a second backend is only worth having if you can prove it agrees with the first.