#azhzx/qbe

A MoonBit rewrite of QBE

#Project Documentation

Qbe.mbt API Documentation

#Project Overview

#Core Feature Scope

#Quick Start

///|
test {
  let src =
    #|export function w $add(w %a, w %b) {
    #|@start
    #|  %s =w add %a, %b
    #|  ret %s
    #|}
    #|
  match @qbe.compile(src) {
    Ok(assembly) => {
      assert_true(assembly.contains("addl"))
      assert_true(assembly.contains("add:"))
    }
    Err(_) => fail("compile failed")
  }
  match @qbe.compile_debug(src, "P") {
    Ok(dump) => assert_true(dump.contains("After parsing"))
    Err(_) => fail("compile failed")
  }
}

///|
test {
  let src =
    #|export function w $add(w %a, w %b) {
    #|@start
    #|  %s =w add %a, %b
    #|  ret %s
    #|}
    #|
  match @qbe.compile_wasm(src) {
    Ok(wat) => {
      assert_true(wat.contains("(func $add"))
      assert_true(wat.contains("i32.add"))
    }
    Err(_) => fail("wasm compile failed")
  }
}

///|
test {
  let src =
    #|export function w $add(w %a, w %b) {
    #|@start
    #|  %s =w add %a, %b
    #|  ret %s
    #|}
    #|
  match @qbe.compile_rv64(src) {
    Ok(assembly) => {
      assert_true(assembly.contains("add:"))
      assert_true(assembly.contains("addw a0, a0, a1"))
    }
    Err(_) => fail("rv64 compile failed")
  }
}

#Technical Details

#Package Structure and Compilation Pipeline

parse → fillrpo → fillpreds → filluse → memopt
      → filldom → fillfron → filllive(false) → phiins → renblk → filluse → ssacheck
      → fillloop → fillalias → loadopt → filluse → ssacheck
      → copy → filluse → fold
      → abi → fillpreds → filluse
      → isel
      → fillrpo → filllive → fillcost → spill → rega
      → fillrpo → simpljmp → fillrpo → fillpreds
      → emitfn

parse → fillrpo → fillpreds → filluse → memopt
      → filldom → fillfron → filllive(false) → phiins → renblk → filluse → ssacheck
      → fillloop → fillalias → loadopt → filluse → ssacheck
      → copy → filluse → fold
      → abi_wasm → fillpreds → filluse
      → isel_wasm
      → [skip spill/rega — wasm has no physical registers]
      → emit_wasm

parse → fillrpo → fillpreds → filluse → memopt
      → filldom → fillfron → filllive(false) → phiins → renblk → filluse → ssacheck
      → fillloop → fillalias → loadopt → filluse → ssacheck
      → copy → filluse → fold
      → abi_rv64 → fillpreds → filluse
      → isel_rv64
      → init_rv64_target()   ← switch TargetCfg (register layout)
      → fillrpo → filllive → fillcost → spill → rega
      → fillrpo → simpljmp → fillrpo → fillpreds
      → emit_rv64

#Intermediate Representation Design

• SSA IR: Functions (Fn), basic blocks (Blk), temporary variables (Tmp), instructions (Ins) are all mutable structs, modified in place without producing copies; supports phi nodes and multiple jump forms (unconditional jump, conditional jump, integer/float conditional jump, 5 return types).
• Opcodes: Op enum covers all 100+ QBE instructions (arithmetic, bitwise, shifts, comparisons, load/store, extensions/conversions, alloc, vararg, call and internal instructions Nop/Addr/Swap/Xcmp etc.), with OpInfo carrying operand properties and foldable markers.
• Reference Types: Ref is an operand reference, unifying temporary variables (RTmp), constants (RCon), types (RType), stack slots (RSlot), call points (RCall), memory (RMem).
• Bit Sets BSet: Compact bit sets implemented with Array[UInt64], used for liveness variable sets and register masks.
• Register Numbers: RAX=1..RSP=16, XMM0=17..XMM15=32, RXX=0 means "no register".

#Key Algorithms

• SSA Construction: Based on dominance frontiers (fillfron) inserts phi nodes, block and variable renaming establishes SSA form, ssacheck performs validity checking.
• Liveness Analysis: Backward data flow iterates to fixed point; gen_set built once and reused, only recomputing in/out.
• Register Allocation: Spill first by cost (use/definition point count + 10^loop_depth loop weighting, word/double channels evaluated separately by NGPS=9/NFPS=15), then in rega builds interference graph from live sets and does greedy coloring; inconsistent registers at block boundaries get copy inserted for synchronization.
• Instruction Selection: Does semantics-preserving strength reduction — folding immediates into instructions, combining add chains into [base + index*scale + offset] addressing, converting constant divisor division to magic number multiply-add-shift, converting comparison + jnz patterns to amd64 conditional jumps.
• Memory Optimization: memopt eliminates redundant alloc/load/store; loadopt eliminates repeated loads from same address with no intervening store in same block; copy propagation merges equivalent temporary variables.

#ABI and Target Support

• amd64_sysv: abi phase replaces abstract Arg/Par/Ret* with concrete register/stack slot references; aggregate types follow System V rules for register vs memory; outputs two GAS styles (Linux .L / macOS L + _ prefix, selected with -G). Has complete 406-case differential regression.
• wasm: abi_wasm phase replaces Par/Arg instructions with Nop (parameters passed directly via local variables), simplifies Call references; isel_wasm does instruction mapping then skips register allocation (wasm is stack machine, no physical registers), emit_wasm outputs WAT text format. wasm32 pointer width is 32 bits (Km = Kw), no Kl type.
• rv64: abi_rv64 lowers parameters to A0–A7 / FA0–FA7 per RISC-V calling convention, returns via A0/A1 / FA0/FA1; isel_rv64 maps IL instructions to RISC-V instructions (compare + branch merged directly, no flags, no magic number division, no complex addressing); then runs spill/rega same as amd64 — target differences switched at runtime via types.TargetCfg (init_amd64_target() / init_rv64_target()), emit_rv64 outputs RISC-V GAS assembly (fp/ra frame chain, 16-byte stack alignment).

#Debugging and Testing

• Command-line -d <flags> provides per-stage dumps (-dP parse, -dM memopt, -dN SSA, -dC copy, -dF fold, -dA abi, -dI isel, -dL live, -dS spill, -dR rega), combinable; when debug is enabled, assembly is not output. Library entry compile_debug(text, flags) returns the same dump text.
• Tests in three layers:
  • Unit/whitebox tests *_wbtest.mbt: Cover all compilation pipeline packages — types (BSet/Con/Ref/Op/Class/Jump etc.), util (Interner/formatting), lexer, parser, cfg (dominator tree/loop/jump simplification), ssa (phi insertion/copy/memopt), fold, live, abi/abi_wasm/abi_rv64, isel/isel_wasm/isel_rv64, spill, rega, emit/emit_wasm/emit_rv64, cmd/main;
  • Blackbox tests qbe_test.mbt + qbe_snapshot_test.mbt: Directly call @qbe.compile / @qbe.compile_debug, covering end-to-end compilation (arithmetic, floating-point, memory, recursion, loop phi) and error paths; qbe_snapshot_test.mbt generated by python tools/gen_snapshot_mbt.py from test/ categories, anchored with inspect snapshots;
  • Differential regression: test/*.ssa (406 cases) compared byte-by-byte with reference qbe binary (tools/qbe-ref pinned snapshot, built with make -C tools/qbe-ref) (python compare.py, can specify other binary with QBE_REF).
• Run: moon test; update snapshots: moon test --update; coverage: moon coverage analyze.

#Porting and Attribution Notes

© 2015-2017 Quentin Carbonneaux quentin@c9x.me

Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the "Software"),
to deal in the Software without restriction, including without limitation
the rights to use, copy, modify, merge, publish, distribute, sublicense,
and/or sell copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.

#Future Plans

• ✅ WebAssembly (wasm32) code generation support (WAT text output)
• ✅ RISC-V 64 (rv64) code generation (GAS output, reusing spill/rega)
• rv64 backend improvements: data segment and floating-point constant rodata output, differential reference verification
• Add convenient JIT-related interfaces
• Interface with mbtcc to verify full end-to-end feasibility