#azhzx/qbe

用Moonbit重写qbe

#项目文档

Qbe.mbt文档

#项目简介

#核心功能范围

#快速上手

///|
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")
  }
}

#技术细节

#包结构与编译流水线

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
      → [跳过 spill/rega — wasm 无物理寄存器]
      → 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()   ← 切换 TargetCfg（寄存器布局）
      → fillrpo → filllive → fillcost → spill → rega
      → fillrpo → simpljmp → fillrpo → fillpreds
      → emit_rv64

#中间表示设计

• SSA IR：函数 (Fn)、基本块 (Blk)、临时变量 (Tmp)、指令 (Ins) 均为可变结构体，就地修改，不产生副本；支持 phi 节点与多种跳转形式（无条件跳转、条件跳转、整数/浮点条件跳转、5 种返回）。
• 操作码：Op 枚举覆盖 qbe 全部 100+ 指令（算术、位运算、移位、比较、load/store、扩展/转换、alloc、vararg、call 与内部指令 Nop/Addr/Swap/Xcmp 等），通过 OpInfo 携带操作数属性与可折叠标记。
• 引用类型：Ref 为操作数引用，统一表示临时变量 (RTmp)、常量 (RCon)、类型 (RType)、栈槽 (RSlot)、调用点 (RCall)、内存 (RMem)。
• 位集 BSet：以 Array[UInt64] 实现的紧凑位集，用于活跃变量集合与寄存器掩码。
• 寄存器编号：RAX=1..RSP=16, XMM0=17..XMM15=32，RXX=0 表示"无寄存器"。

#关键算法

• SSA 构造：基于支配边界 (fillfron) 插入 phi 节点，块与变量重命名建立 SSA 形式，ssacheck 做合法性校验。
• 活跃分析：反向数据流迭代到不动点；gen_set 首建后复用，仅重算 in/out。
• 寄存器分配：spill 先按代价（使用/定义点计数 + 10^loop_depth 循环加权，word/double 通道分别按 NGPS=9/NFPS=15 评估）决定溢出到栈槽的临时变量，再在 rega 中按活跃集合构建干涉图并贪心染色；块边界寄存器不一致处插入 copy 同步。
• 指令选择：做语义保持的强度提升——立即数折叠进指令、add 链组合为 [base + index*scale + offset] 寻址、常量除数除法转魔法数乘加移位、比较+jnz 模式转为 amd64 条件跳转。
• 内存优化：memopt 消除冗余 alloc/load/store；loadopt 消除同块同址的无介入 store 的重复 load；copy 传播合并等价临时变量。

#ABI 与目标支持

• amd64_sysv：abi 阶段把抽象 Arg/Par/Ret* 替换为具体寄存器/栈槽引用，聚合类型按 System V 规则决定走寄存器还是内存；输出两种 GAS 风格（Linux .L / macOS L + _ 前缀，-G 选择）。有完整的 406 用例差分回归。
• wasm：abi_wasm 阶段将 Par/Arg 指令替换为 Nop（参数直接通过局部变量传递），简化 Call 引用；isel_wasm 做指令映射后跳过寄存器分配（wasm 是栈机，无物理寄存器），emit_wasm 输出 WAT 文本格式。Wasm32 指针宽度为 32 位（Km = Kw），无 Kl 类型。
• rv64：abi_rv64 按 RISC-V 调用约定把参数降到 A0–A7 / FA0–FA7，返回值走 A0/A1 / FA0/FA1；isel_rv64 把 IL 指令映射为 RISC-V 指令（比较 + 分支直接合并，无 flags、无魔法数除法、无复杂寻址）；随后与 amd64 一样跑 spill/rega —— 目标差异通过 types.TargetCfg 在运行时切换（init_amd64_target() / init_rv64_target()），emit_rv64 输出 RISC-V GAS 汇编（fp/ra 帧链，16 字节栈对齐）。

#调试与测试

• 命令行 -d <flags> 提供分阶段 dump（-dP parse、-dM memopt、-dN SSA、-dC copy、-dF fold、-dA abi、-dI isel、-dL live、-dS spill、-dR rega），可组合；开启调试时不再输出汇编。库入口 compile_debug(text, flags) 返回同样的 dump 文本。
• 测试分三层：
  • 单元/白盒测试 *_wbtest.mbt：覆盖全部编译流水线包——types（BSet/Con/Ref/Op/Class/Jump 等）、util（Interner/格式化）、lexer、parser、cfg（支配树/循环/跳转简化）、ssa（phi 插入/copy/memopt）、fold、live、abi/abi_wasm/abi_rv64、isel/isel_wasm/isel_rv64、spill、rega、emit/emit_wasm/emit_rv64、cmd/main；
  • 黑盒测试 qbe_test.mbt + qbe_snapshot_test.mbt：直接调用 @qbe.compile / @qbe.compile_debug，覆盖端到端编译（算术、浮点、内存、递归、循环 phi）与错误路径；qbe_snapshot_test.mbt 由 python tools/gen_snapshot_mbt.py 从 test/ 各类别生成，以 inspect 快照锚定汇编输出；
  • 差分回归：test/*.ssa（406 个用例）与参考 qbe 二进制（tools/qbe-ref 中钉住的快照，make -C tools/qbe-ref 构建）逐字节对比（python compare.py，可用 QBE_REF 指定其他二进制）。
• 运行：moon test；更新快照：moon test --update；覆盖率：moon coverage analyze。

#移植或参考说明

© 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.

#未来计划

• ✅ 支持 WebAssembly (wasm32) 的代码生成支持（WAT 文本输出）
• ✅ 支持 RISC-V 64 (rv64) 的代码生成（GAS 输出，复用 spill/rega）
• rv64 后端完善：data 段与浮点常量 rodata 输出、差分参考验证
• 添加方便JIT的相关接口
• 对接mbtcc，验证全流程的端到端的可行性