The QBE backend¶

The qbe backend lowers the shared typed-SSA IR to QBE IL — the compact intermediate language of the QBE compiler backend. The external qbe tool turns that IL into native assembly, which the C compiler then assembles into an object file. QBE follows the platform C ABI, so its objects are call-compatible with C and link against the same pp_<name> export-wrapper translation unit the C backend uses — no glue, no forward declarations (spec §9.1).

It consumes the same IR as the C backend, and its output is held to one rule: byte-identical to C wherever the arithmetic is exact. That equivalence is the backend's correctness oracle.

Pipeline¶

IR Module
  → emit_module  →  QBE IL (.ssa)
  → qbe -o out.s out.ssa      (IL → native assembly)
  → cc -O2 -fPIC -c out.s     (assemble → .o)
  → link with the C export wrappers (+ ipow runtime if used) → .so / .dylib

QBEBackend implements the backend protocol: emit returns the IL text, compile_object runs qbe then hands the .s to the toolchain's compile_c, and is_available is true when the qbe binary and a C compiler are both on PATH (QBE needs cc to assemble its output and to build the export wrappers). Its source_ext is .ssa.

Select it per build:

postc build kernel.py --backend qbe

or with the POSTC_BACKEND=qbe environment variable or the backend="qbe" API argument. The default backend remains c.

Coverage¶

QBE covers the full scalar + array kernel subset the C backend supports: int/float/bool arithmetic including floor-div, mod, float **, abs, casts, and select; array load/store/dim/stride/alloc and len(); mutable locals and output-by-pointer stores (via stack slots); and the NumPy generalized-ufunc inner loop. What it does not lower stays on the C path:

The backend's capabilities are the defaults — complex=False, ext_module=False, float16=False. The build driver rejects what a backend cannot do; it does not silently route around it. postc build z.py --backend qbe on a Complex128 program fails with error: dtype Complex128 not supported by the QBE backend, and --ext-module fails with error: the 'qbe' backend does not build CPython extension modules. Choosing the C backend for those is the user's call to make, and the diagnostic says so.

Type mapping¶

QBE's type system is minimal: w (32-bit int), l (64-bit int/pointer), s (f32), d (f64), plus b/h in memory for narrow loads and stores.

Because QBE keeps the full w after arithmetic while C truncates on assignment, sub-word integer results are re-narrowed to their declared width (extsb, extuh, …), and QBE has no implicit promotion, so mixed-type operands get explicit coercions following C's usual-arithmetic-conversion rules.

ABI and the integer-power runtime¶

Float ** routes through libm (powf/pow), resolved at link time. Integer and unsigned ** instead call __pp_ipow_i64 / __pp_ipow_u64 — a tiny C runtime (IPOW_RUNTIME_C) that is an extern copy of the C backend's static ipow helpers, so the result is bit-identical. The backend's runtime_sources emits that unit (compiled as C) only when a module actually uses integer **, keeping every object on the platform C ABI.

Optimization passes¶

qbe does register allocation and mem2reg but no loop optimization (and little CSE), and the assemble-only cc -c step cannot add it back. So the backend does its own IR-level passes — each verified to keep the output byte-identical to C:

1. Local CSE (cse). The frontend lowers every a[i] to a fresh dim/stride/i*stride/base+idx/load chain, so x[i] * x[i] recomputes the whole index and loads the element twice. A per-block value-numbering pass folds identical pure computations to one definition and a repeated load of the same address to a single load — unless a store or call has run since, so it stays correct under aliasing and in-place ops. Runs on a copy, leaving the shared IR intact for the other backends.

2. Array-metadata LICM (_hoist_array_meta). Array parameters are immutable pointers available in the entry block, which dominates every loop, so their data+offset base, per-axis strides, and shape are computed once in entry and reused — correct by construction, no dominator analysis needed.

3. Ufunc-loop strength reduction + view hoisting (emit_ufunc_loop). Each ufunc argument pointer becomes a loop induction variable (p += step), dropping the per-element i*step multiply, and each argument's __pp_array view has its invariant fields (shape, strides, ndim, offset) built once in @start — only the data pointer moves per iteration.
4. Scalar-kernel fusion (_inline_scalar_kernel). A single straight-line scalar kernel is spliced directly into the ufunc loop instead of called per element; its IR is cloned with every value name prefixed so it cannot collide with loop temps. Multi-block kernels fall back to a call.
5. Kernel-loop strength reduction (_plan_strength_reduction). The one pass that needs real analysis: it builds the CFG, computes dominators, finds natural loops, identifies each loop's counter, and rewrites array accesses as induction pointers bumped by the counter's stride. It decomposes a byte index into a sum of var*stride products, so matmul's nested a[i][p] (i*s0 + p*s1) reduces too. A stride is either an axis stride read from the array's strides[] descriptor at runtime (so non-contiguous Fortran-order / reversed inputs stay correct) or a constant the frontend folds for a contiguous a[i] (dim*itemsize) — recognizing the latter extends induction-pointer walks (and then unrolling) from the ufunc path to plain whole-array for i in range(n) kernels.
6. Loop unrolling ×4 (_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 indices are unrolled by 4. The accumulator stays threaded through its stack slot, preserving the exact serial fadd order (hence byte-identical), with a remainder loop for the leftover iterations (trip count rounded down with n & -4).

Correctness¶

Verification rests on the byte-identical oracle: every kernel is built through both backends and driven through the real NumPy generalized-ufunc ABI via ctypes, and the two native outputs must agree bit-for-bit. Fuzz harnesses compare QBE against C across random inputs, dtypes, and byte strides taken straight from NumPy. When both backends behave identically-wrongly, the test itself is at fault.

Performance¶

QBE runs at roughly 0.86× the speed of cc -O2 on average — about 15% slower by geometric mean — and roughly 50× faster than CPython.

matmul is the low point: its inner loop is strength-reduced but not unrolled (unrolling is scoped to top-level counted reductions), so it trails the optimizing C compiler by about 1.3×. The residual gap on reductions is not SIMD or FMA — cc -O2 emits neither for FP reductions, because both would reorder the summation and change the bits (they are gated behind -ffast-math, which this project deliberately does not adopt, as it would break the byte-identical oracle). The gap that unrolling closed was loop-branch overhead and load-latency hiding, done bit-exactly at the IR level.

See also¶

• Writing a backend — the protocol QBE implements.
• The C backend — the correctness oracle QBE is measured against.
• IR reference — the input both backends consume.