这是一个 2025 年全国大学生计算机系统能力大赛 编译系统设计赛道 毕昇杯， 由 Rust 编写的 SysY2022 RISC-V 64 编译器， 2025.07.05-2025.08-15
LycorisRecompile 接收自组委会的祖传神必 C 语言子集 SysY2022，输出 RV64GC 汇编，目标机器是 BOOM v3 乱序双发射软核，整个项目大约4.7w行，4.3w+ Rust，2500+ ISLE，以及测试脚本，目前官方 199 个测试用例在 QEMU PASS
该神必编译器动工的理由，并不是为了去拿奖，而是为了一碟醋才包的这盘饺子，其初始目的想亲手实现一遍 E-Graph 和 ISLE 的醋， 来源于 Cranelift 基于项重写的声明式指令选择，以及基于等价图的中端优化，比赛和编译器本身只是顺带产出的饺子
Cranelift 的 ISLE 工具链整个搬进了仓库 crates/isle，islec 编译 .isle 规则生成 Rust 代码，其中 ISLE 的介绍博客、语言参考和官方 README 均放在 docs/markdown/ISLE/
该神必编译器流水线如下：
SysY 源码 -> Lexer -> Parser -> SSA IR -> [可选的 SSA 解释器] -> ISLE 指令选择 -> 寄存器分配 -> RV64 汇编
每阶段 Pass 用命令行参数 --stage 指定，中间 100% Vibe Coding 而成的神必解释器，直接解释执行 SSA IR，并用于和 QEMU 输出对拍。可以说，几万行石山代码，这个神必解释器占了很大一部分，端到端 prompt 让各路 ai 们一层又一层往里面加补丁，越来越臃肿
中端则是花费两个星期的反复重构的，诡异和莫名其妙的 SSA IR。
第一个抄自 Cranelift，没有显式 Phi 指令用块参数。基本块像函数一样声明形参，前驱跳转时像调用一样传实参，块参数不需要像 Phi 节点需要知道任何前驱信息，数据流直观且避开了 Phi 指令变换的边界情况，其中 SSA 的构造算法同样抄自 Cranelift，使用 Braun 等人 2013 年的算法，按需插入块参数，为了避免深递归，实现改写成了显式状态机。
第二个是内存令牌，指针和内存状态被拆成两个东西 (ptr, token)，每条Read都要消费一个令牌来证明自己读的是哪个版本的内存，每条Write消费旧 token，产生新 token，内存依赖显式成为 SSA 图普通可见的数据依赖边，这受启发自 LLVM Memory SSA，但在当时我写这玩意时，匮乏的编译原理知识没有让我意识到，世界上早就已经有这样的设计了，我又重复发明了轮子
%ptrA, %memA_v0 = array.alloc i32[10]
%memA_v1 = array.put %ptrA, [0], 42, (%memA_v0) ; 消费 v0，产生 v1
%val = array.get %ptrA, [1], (%memA_v1) ; 消费 v1
优化器不再需要做完整的别名分析，不同内存对象各有各的令牌链。函数调用也同样遵循该原则，指针参数必须携带令牌，调用返回新令牌，这依靠 IR 多返回值来表达。
可惜理论好处颇多，但工程化简直是灾难。介于时间不够，那些基于内存令牌的优化算法，没有一个被真正实现，全部停留在空想😭😭😭
后端的指令选择，则是饺子醋本身。介于 ISLE 的神必语法和反直觉的解构表达式，当时没一个 ai 能写出完全正确的复杂 isle 规则。因此单就研究这 isle 基本上又花了一周时间，啥也没干，就整天写各种规则做实验，并试图通过冥想来悟出 isle 的真理😭
;; 乘以2的幂常数 -> 左移 强度削减
(rule 2 (lower (has_type (ty_i64 ty) (imul x (pow2_shift k))))
(let (
(dst XReg (xreg_new))
(x_reg XReg (x_operand x))
(_ Unit (emit (MInst.Slli dst x_reg (imm6_from_i64 k)))))
(InstOutput.OutputReg dst)))同样灾难的是SSA IR的设计缺陷，把比较和分支拆开了：icmp 产生 Bool 值并由 brif 消费，拆成了两条指令，IR 因此简单，但却忘记了 RISC-V 本来就有 blt 这样的融合比较分支
因此，为了给这个缺陷擦屁股，想到 Cranelift 里有一套并不完整的 instruction coloring 与 sinking 机制来处理"两条 IR 指令融合到一条机器指令"的问题，其主要用于 x86 的内存操作数合并。于是我被迫把这套机制完整实现了一遍，用于缝合被解耦的 if 和 cond
具体来说，降级前先按副作用点给指令染色；ISLE 的提取器可以"看穿"一个值，直达定义它的指令，只要定义和使用同色，所谓中间没有副作用边界，且这个值只被用这一次或复算成本可以接受，就允许把定义指令 sink 使用点，融合成一条机器指令，原指令不再单独发射
如下 isle 规则是我写过的最优雅和精妙的代码之一，可惜无人在意😭：
;; 高级封装: Value=>Inst
;; 判断定义Value的Inst能否融合, 如果可以就返回该Inst
(decl peek_def_inst (Inst) Value)
; (extractor (peek_def_inst pinst)
; (def_inst (can_sink_inst pinst)))
(extern extractor peek_def_inst peek_def_inst)
;; 判断是否可以融合
;; ⚠️后端实现比较复杂: 需要同时判断:
;; - InstColor: 判断是否跨越副作用指令
;; - InputSourceInst: 判断指令的使用次数 & 复制成本
; (decl can_sink_inst (Inst) Inst)
; (extern extractor can_sink_inst can_sink_inst)
;; 融合指令 -- 仅仅只是通知后端进行融合, 不做判断
(decl sink_inst (Inst) Unit)
(extern constructor sink_inst sink_inst)
;; "看穿"一个Value并尝试提取比较运算
(decl peek_icmp_eq (Value Value Inst) Value)
(extractor (peek_icmp_eq x y pinst) (peek_def_inst pinst @ (and
(eq x y)
(arg1_has_type (and (ty_fit_xreg) (ty_fit_signed)) _))))
(decl peek_icmp_lti (Value Value Inst) Value)
(extractor (peek_icmp_lti x y pinst)
(peek_def_inst pinst @ (and
(lt x y)
(arg1_has_type (and (ty_fit_xreg) (ty_fit_signed)) _))))
; 匹配 eq
(rule 2 (lower_branch (brif (peek_icmp_eq x y pinst) _ _) (two_targets then else))
(let (
(x_reg XReg (x_operand x))
(y_reg XReg (x_operand y))
(_ Unit (emit (MInst.Beq x_reg y_reg then)))
(_ Unit (emit (MInst.J else))))
(sink_inst pinst))
)
; 匹配 lt-signed
(rule 2 (lower_branch (brif (peek_icmp_lti x y pinst) _ _) (two_targets then else))
(let (
(x_reg XReg (x_operand x))
(y_reg XReg (x_operand y))
(_ Unit (emit (MInst.Blt x_reg y_reg then)))
(_ Unit (emit (MInst.J else))))
(sink_inst pinst))
)具体来说效果如下：
slt t0, a0, a1
bnez t0, .L_then -> blt a0, a1, .L_then
j .L_else j .L_else
还是那句话，无人在意😭
寄存器分配拆成两个阶段：先用 MIN 算法把每个程序点的寄存器压力降到 k 以下（RISC-V k=25），溢出决策基于操作系统同款的 next-use 距离，并对函数调用点做了额外处理；然后把降压后的程序交给 Appel 与 George 的迭代寄存器合并做 IRC 图着色
理论上，该算法是完美的，降到 k 以下之后干涉图必然可着色，第二阶段不该再失败
但现实在工程化上同样是个灾难，IR 在溢出重写之后不再是严格 SSA，跨块的长活跃区间偶尔仍会让理论失效，这直接导致了决赛现场我通宵调试也没调出来😭
时隔一年重新回来看了一眼，Fable 5 给我加了一大堆补丁，让实现变得丑陋起来，但至少能 AC 所有测例了
E-Graph 的设计对标 Cranelift 的 aegraph，IR 里已经加入了表达等价值的 Union 和 Alias 节点，等价类的数据结构，值到等价类的映射，IR 建图，饱和循环的驱动骨架，等价图的 Graphviz 可视化，都写完了；六百多行的 ISLE 绑定层已经把 SSA 的全部指令模式暴露给了规则语言，islec 的代码生成管道也接通了。这些东西都在仓库里，都能编译。
然而，就一个月时间，让一条重写规则被完整执行，都成为了奢望，终究当我把这盘饺子做出来时，发现醋碟里还是空的 😭😭😭
需要 Rust 工具链（edition 2024）、riscv64-linux-gnu-gcc 和 qemu-riscv64。
# 构建
RUSTFLAGS="-A warnings" cargo build --release
# 编译单个文件到汇编
cargo run --release -- input.sy -S -o output.s
# 单文件完整验证（编译 -> 交叉链接 -> QEMU 执行 -> 对拍）
./scripts/run/03-simple-run.sh run qemu tests_self/99-simple-add.sy
# 跑全部测试
./scripts/run/03-simple-run.sh qemu官方测试数据包含数百MB的神必测试输入/输出 case，因此全部以 submodule 形式存在，想找的自己去找
tests_self/ 有多个用例可用，修改 .isle 规则后，需要手动运行 ./scripts/run/04-isle-gen.sh 重新生成 selection.rs
compiler/src/
├── lexer/ 手写词法分析
├── parser/ 手写递归下降
├── ssa/ SSA IR、Braun 构造、优化 Pass、E-Graph
├── interpreter/ SSA 解释器（差分测试用）
├── asm/ ISLE 指令选择、MIN 溢出、IRC 着色、栈帧
└── utils/ RefMap 等基础设施
crates/isle/ Cranelift ISLE 工具链（vendored）
docs/markdown/ 设计文档与 ISLE 中文翻译
tests_self/ 自写测试用例
这个编译器直接实现或借鉴..（誊抄）了下面这些工作：
- Braun et al., Simple and Efficient Construction of Static Single Assignment Form（CC 2013）——SSA 构造
- Braun & Hack, Register Spilling and Live-Range Splitting for SSA-Form Programs（CC 2009）——溢出算法
- George & Appel, Iterated Register Coalescing（TOPLAS 1996）——图着色
- Cranelift Chris Fallin 关于 ISLE 的 介绍文章是这一切的起点
crates/ ISLE 工具链来自 wasmtime Apache-2.0 WITH LLVM-exception
作者：NKID00、zmr-233、lux-QAQ、aurora0x27
主仓库代码以 MIT 许可发布，crates/ Cranelift 组件保留其所有原始许可