埋一个坑，有空整理一下自己在完成RCompiler和学习编译原理过程中学到的东西。况且下学期也选了高编，也可以往里面加后端和优化的内容。

Parser & Semantic Check

毕竟似乎是第一年手搓parser，还是多写两句吧。Parser本身并不难，真正容易让人返工的是：一开始觉得“能 parse 出 AST 就行”，结果后面做 semantic check 和 IR generation 时发现 AST 信息不够用，于是又回去给节点补类型、补左值右值、补span、补各种语义标记。

Expression

parser主要问题在于对expression建AST，这里推荐阅读Pratt Parser，伪代码和原理写的很明白了。表达式解析最大的麻烦是优先级和结合性，如果按文法一层一层写，代码会变成一大串parseLogicalOr -> parseLogicalAnd -> parseEquality -> ...，能写但很啰嗦。

Pratt Parser的想法是给不同运算符绑定不同优先级，然后用一个统一的parseExpr(minBp)处理。大概流程是：

  • 先解析一个前缀表达式，比如字面量、变量、括号表达式、一元运算、数组/结构体字面量等
  • 再循环看后面是不是有中缀/后缀运算符
  • 如果后面运算符优先级低于当前minBp，说明当前表达式该收束了
  • 否则吃掉运算符，递归解析右操作数，再把左右两边合成新的AST节点

后缀表达式也建议放在这里统一处理，比如函数调用f(x)、数组下标a[i]、字段访问x.y、方法调用x.f()。它们的优先级通常最高，而且可以连续出现：

1
a.b(c)[i].d

这种表达式如果不统一处理，很容易在AST上拼错层级。笔者比较建议把“primary + postfix chain”作为前缀解析的一部分，先得到最左边的primary，再不断吃后缀，直到后面不是后缀运算符为止。

Semantic Check

Semantic Check 笔者通过神秘操作成功实现了两遍搞定，导致笔者的 semantic check 完成的远快于别人，这也给笔者爽放了个假，直接跑去 HK 玩了四天，自认为自己的 compiler 高枕无忧，这也给我后续 ir 很晚才开始导致的一系列惊险遭遇埋下了伏笔。

惊险遭遇：

写到IR时笔者发现自己完全忘了维护左值右值信息，于是又回炉重造加逻辑。所以建议别一味追求pass数量少，老实按照要求扫4、5遍反而更稳。第一遍收集全局符号，第二遍处理类型/函数签名，第三遍检查语句和表达式，第四遍补常量求值和一些额外约束，这样每一遍都比较清楚。

Semantic Check里还有一个经验是，作用域栈一定要写得干净。进入block push scope，离开block pop scope；函数参数和局部变量在不同层级插入；break/continue需要知道当前是否在循环里；return需要知道当前函数返回类型。把这些上下文都塞进一个SemanticContext里，比到处传零散参数舒服很多。

IR Generation

和Parser建AST的过程几乎一致，递归写，比较容易，调试也有不少技巧，笔者实现了24小时调完。但写的时候由于笔者一开始设计有问题，导致经历了一次大的代码重构，外加笔者去年年底生病了，导致写代码写的非常痛苦，也给笔者留下了不小的心理阴影。但不得不说，ir builder 笔者的设计干净漂亮，让笔者十分得意。

Codegen

实现：不做任何寄存器分配，所有东西都spill 到栈上，每次需要操作时，把变量从栈上load 到寄存器里，操作完了再store回去。但这样会造成大量的load和store指令，性能很差。

一些可能的雷点： 能容纳函数参数的寄存器数量有限，只有a0-a7 8个寄存器，参数大于8时需要spill到栈上；m-extension 指令注意符号拓展；指针解引用时的load store操作；reimu模拟器栈内存默认是32K，很多点需要认为调大栈内存，亲测4096K差不多了；函数返回值是数组或结构体时需要最后将返回值写入a0寄存器；phi指令在ASM中时不存在的，需要人为拆解，一个简单的想法是，每次处理IR Br指令时，前瞻一下跳转到的块内有没有phi指令，如果有，就把phi指令的结果先spill 到栈上保存下来，因为ASM无法记录你是从哪个块跳转过来的。

Register Allocation

lz先写（借用一些神力）了一版linear scan寄存器分配算法，但写完调完的第二天高编集会得知要写图染色，于是被迫再写一遍图染色reg alloc。

Linear Scan

线性扫描寄存器分配相对来说比较好理解，首先我复用了codegen部分的一部分代码，做出的修改是，在codegen中对于所有临时变量，我都通过存储在栈上，需要的时候load/store访问，而在reg alloc 里，我先给这些临时变量都分配了一个虚拟寄存器，以便我后续进行reg alloc。线性扫描寄存器分配的核心在于CFG 的构建和live interval的计算。每一个codegen得到的ASM Block都对应了一个CFG block，用来保存这个block的首指令和尾指令编号、def/use 变量集合、liveIn/liveOut 变量集合等信息。首先我们构建一张CFG，方法就是通过块内跳转指令找后继块。得到CFG后就可以计算每个块的liveIn/liveOut了，这是一个虚拟寄存器到存活区间的映射，我们有如下关系：

1
2
liveIn[B] = use[B] U (liveOut[B] - def[B])
liveOut[B] = U liveIn[S] for all S in succ[B]

进行反向迭代直到liveIn/liveOut不再变化为止。
接下来就可以计算每个虚拟寄存器的live interval了，live interval是一个区间，表示这个寄存器在程序中被定义和最后一次使用之间的范围。计算live interval的方法是遍历CFG中的每个块，对于每个块中的每条指令，更新对应寄存器的live interval。最后我们就得到了每个虚拟寄存器的live interval，可以用来进行线性扫描寄存器分配了。线性扫描寄存器分配的核心思想是按照live interval的起始位置对虚拟寄存器进行排序，然后从左到右扫描这些live interval，尝试将它们分配到物理寄存器上。如果当前扫描到的live interval与已经分配的live interval有重叠，那么就需要将其中一个live interval spill到内存上。
值得注意的是，我们需要考虑跨call的情形。在RISC-V架构中，寄存器分为caller-saved和callee-saved两类，caller-saved寄存器在函数调用时需要保存和恢复，而callee-saved寄存器则由被调用函数负责保存和恢复。因此，在进行寄存器分配时，我们需要确保跨call的live interval不会被分配到caller-saved寄存器上，否则就需要将它们spill到内存上。而在进入每个函数前，我们需要将callee-saved寄存器的值保存到栈上，以便在函数返回时恢复它们的值。

Graph Coloring

TBD 其实吧，我觉得 Mx Tutorial 里图染色的讲解已经非常清楚了，笔者甚至都不太打算写。。。anyway，这个再说（

IR Generation Optimization

Mem2Reg

mem2reg 优化本质上是一种去alloca的优化，想法是将本来分配在栈上的对象移动到虚拟寄存器中，首先我用了一个晚上快速写了3种最基础的mem2reg优化：

  • alloca 但没用过的不alloca（毫无效果）
  • 只被定义了一次，那么所有值都可以用定义的值代替（效果明显）
  • 如果一个alloca 只在当前块被使用，那么所有的use都可以被向上最近的一个def替代（效果微弱，可能是因为很少有变量只在一个块里出现吧）

接下来主要分析一下第4种mem2reg优化：如果一个 alloca 只被 load 和 store，那么可以通过在支配边界插入 phi 指令，并将所有的 use 替换为对应的 phi 指令的结果。其实笔者在思考第3种mem2reg优化时就隐约有了推广到跨block处理def/use的一些想法了，利用phi确实是其中之一。

支配树的构建与支配边界

支配集可以这样理解，就是要想到达某个块，必须经过的块的集合，而这构成了一条链，接着就可以构造出支配树了。构建方法是先构建出CFG得到前驱后继关系，然后给所有前驱块找LCA。接下来需要找到支配边界，首先明确支配边界的定义：一个节点 X 是节点 Y 的支配边界，当且仅当 Y 在 X 的一个前驱节点的支配集中但 Y 不在 X 的支配集中。计算方法是遍历前驱块，如果前驱块的支配边界自然是当前块（前驱块数量大于2），往上找前驱块的上一个支配块，递归，直到也在当前块的支配集里为止。

Phi指令的插入和指令删除

Phi指令的插入方法是：对于每个alloca，找到所有def块，遍历def块的支配边界，在支配边界块首插入一个phi指令，重命名入口顶部的 phi 指令所定义的值为alloca定义的值，接着递归地再支配边界的支配边界添加phi指令。接着对每一个被alloca出来的量维护一个栈，每遇到store指令或者新插入phi指令，就把对应的值压入栈顶，每遇到load指令，就把栈顶的值替换掉load指令的结果（和前三种优化类似的，维护一个replaceMap）。同时用当前栈顶更新phi指令的参数。最后，对当前基本块在支配树中的子节点进行递归处理。

codegen中对phi指令的消除

phi指令并不是risc-v指令集中的指令，所以在codegen阶段需要将phi指令消除掉。事实上，笔者本人在写mem2reg优化前先实现了一个版本的phi指令消除：在每个前驱块中插入一个副本（一个新的虚拟寄存器），在末尾进行mv dst tmp的指令添加。很简单的想法，鉴于是虚拟寄存器存储所以不存在数据冲突问题，也顺利通过了测试点，不过事后来看，这种写法有性能上的缺陷：

  • 徒增虚拟寄存器数量，给regalloc带来压力
  • 产生更多死代码

更标准的解法应该是————拆分关键边！想法是在关键边上加入一个块，把要给到下游块的值先copy到这个块中。but转折来了，笔者实现之后进行了一个测试，发现和我原本的实现竟然没有任何区别，是的，没有一个测试点有任何一点性能上的差异！于是笔者细细品味了一下，发现这两种实现本质上似乎是基本等价的。没啥说的必要了。建议用我第一遍的实现，因为实现难度低且非常容易理解。

Dead Code Elimination

从死代码消除开始就是上古 Mx Tutorial 里不涉及的部分了。

DCE的目的是删除那些“计算了一个值，但这个值不会影响程序可观察结果”的指令，举个例子：

1
2
b = 114514
c = b + 1

其中 c 的值在后续程序中永远不会被使用到，所以c = b + 1 是死代码，可以被删除掉。

如果你已经实现了linearScan regalloc，那么恭喜你，DCE的剩余码量不超过30行，在每个块中，我会维护一个liveSet，初始时是liveOut集合，逆序遍历每条指令，如果指令的 def 变量不在liveSet中，那么这个指令就是死代码，可以删除掉；如果指令不是死代码，那么就把它 use 的变量加入liveSet中，并把它定义的变量从liveSet中移除掉。多次遍历直至没有代码被删除。

Constant Propagation

常量传播是最容易想到、也最容易写出第一版的优化之一。最简单的版本就是维护一个valueMap，如果某个变量已经能确定是常量，那么后续使用这个变量的地方就直接替换成常量。比如：

1
2
a = 1
b = a + 2

可以直接变成b = 3。但这个版本只适合在一个基本块里做局部优化，一旦遇到分支、循环、phi，事情就会变复杂。

更完整的做法是 SCCP（Sparse Conditional Constant Propagation），它同时做常量传播和不可达分支删除。核心思想是给每个SSA值维护一个三值状态：

  • Unknown：还不知道这个值是什么
  • Constant：已经确定是某个常量
  • Overdefined：不是常量，或者无法安全确定

SCCP和普通常量传播最大的不同在于，它只沿着可执行边传播。也就是说，如果一个分支条件已经能被折叠成常量，那么另一条永远不会走到的边就不应该继续参与后续phi的计算。这个细节非常重要，否则不可达块里的值会污染phi，让本来可以折叠的值变成Overdefined。

举个例子：

1
2
3
4
5
if (x == 0) {
    y = 1
} else {
    y = 2
}

如果已经知道x = 0，那么只有true edge是可执行的，phi里只需要看y = 1这一侧，最后y也能继续被传播为常量。这个优化和CFGClean、DCE通常要连着跑：SCCP把分支折掉，CFGClean删除不可达块并清理phi，DCE再把剩下的无用计算删掉。

除了SCCP之外，还可以做一个更局部的ConstantFold，专门折叠二元运算、cast、常量getptr和常量分支。这类pass实现成本低，但收益很稳定，尤其是在inline或者memory forwarding之后，经常会突然暴露出一堆新的常量表达式，所以pipeline里一般会重复跑几轮。

SROA

SROA（Scalar Replacement of Aggregates）可以理解成“把小聚合对象拆成标量”。比如一个局部struct只有几个字段，而且所有访问都是常量字段访问，那么与其在内存里维护整个struct，不如把它拆成几个独立的alloca：

1
2
3
struct Pair { x, y }
p.x = a
p.y = b

可以近似看成：

1
2
p_x = a
p_y = b

这样拆完之后，每个字段都能继续交给mem2reg提升成SSA值，后续SCCP、CSE、DCE也更容易发挥作用。这个优化对小结构体、固定长度小数组、helper函数里的临时聚合对象比较有用。

不过SROA的边界一定要保守。笔者的理解是，第一版只应该处理局部alloca，字段数/元素数很小，字段类型是整数或指针，地址不逃逸，并且所有访问路径都是常量字段或常量下标。如果遇到动态下标、把聚合对象地址传给函数、复杂memcpy/memset，最好先跳过。优化最怕“看起来能拆”，结果alias一不小心就WA。

Function Inline

函数内联的收益很直观：省掉call/return和参数搬运，同时把callee内部的计算暴露给caller，方便后续优化继续处理。比如很多模运算wrapper、getter/setter、小算术helper，如果不inline，后端会看到一堆函数调用；inline之后，SCCP、ConstantFold、MemoryForward都可能继续把里面的代码压扁。

但inline不是越多越好。过度inline会让函数体变大，live range变长，后端寄存器压力上升，最后可能被大量spill抵消掉收益。比较稳妥的策略是：

  • 不inline main
  • 不inline递归函数
  • 优先inline单调用、小函数、纯算术helper
  • 对参数很多、返回复杂聚合对象、基本块很多的函数加惩罚
  • 控制caller的代码增长预算

inline之后最好再跑一轮SCCP和CFG清理。原因很简单：inline经常把实参里的常量带进函数体，也会暴露出原来跨函数看不到的分支和store-load链。

Memory Forwarding

Memory Forwarding的目标是减少没有必要的load/store。最典型的情况是：

1
2
store v, p
x = load p

如果中间没有任何可能修改p指向内存的操作，那么x可以直接替换成v。进一步，如果某个load已经读过同一个精确地址，并且中间没有写入，也可以复用上一次load的结果。

这个pass的关键是“精确地址”和“保守alias”。比较安全的做法是沿支配树维护一份memory state，只在确认是同一个地址时做转发。对于结构体字段，可以把地址规范化成类似base + field path的key：同一个根对象、不同常量字段通常可以认为不别名；但遇到动态数组下标、函数调用、未知store、memcpy/memset，就要清空或废弃相关状态。

Memory Forwarding和ConstantFold也很搭。很多时候load被替换成了一个literal，后面立刻就能折叠出常量分支；store被后续store覆盖且中间没有读取，也可以直接删掉前一个store。这个优化对结构体字段反复读写、解释器状态变量、数组/结构池里的重复load都比较有用。

Local CSE / Dominator GVN

CSE（Common Subexpression Elimination）处理的是重复表达式，例如：

1
2
t1 = a + b
t2 = a + b

第二个a + b可以直接复用t1。如果只在一个基本块内做，这就是Local CSE；如果沿支配树向下维护表达式表，就可以做一个简化版Dominator GVN。

实现时可以给纯表达式建立一个key，比如op + lhs + rhs + type + flags。对于加法、乘法这种交换律成立的运算，可以把左右操作数规范化，避免a + b和b + a被当成两个表达式。除了二元运算，getptr、sext/zext/trunc这类纯cast也很适合放进CSE里。

这里有一个容易踩坑的点：key里一定要带上语义标记和类型信息，比如是否是unsigned、是否是i8、是否保持64-bit语义等。否则两个看起来操作数一样的表达式，实际含义可能不一样。load的CSE也要非常保守，通常不如交给MemoryForward统一处理。

CSE对数组地址计算很有帮助。很多IR会反复生成相同的getptr链，CSE之后不仅少了重复计算，也能让MemoryForward更容易识别“这是同一个地址”。

LICM

LICM（Loop Invariant Code Motion）就是把循环不变量提到循环外。比如：

1
2
3
4
while (...) {
    t = n * 8
    a[i] = base[t + i]
}

如果n在循环里不变，那么t = n * 8就没必要每轮都算。

实现上先通过back edge识别natural loop，再找循环的preheader，把安全的循环不变量移动到preheader里。判断一条指令能不能hoist，大概看两个条件：

  • 指令本身没有副作用
  • 它的所有操作数都定义在循环外，或者来自已经被hoist的循环不变量

比较适合提升的是mul/div/mod/shift这类较贵的scalar binary、纯getptr、cast，以及服务于地址链的add/sub。但是不要轻易hoist load，除非你有足够强的alias analysis证明循环内不会改这块内存。

LICM也不是越激进越好。把便宜的计算提前到循环外，可能会拉长live range，增加寄存器压力，最后后端spill更多。尤其是解释器、hash pipeline这类live value很多的程序，过度hoist反而可能负优化。所以比较保守的策略是：贵运算可以提，地址链相关的便宜add/sub可以提，其余cheap binary先别乱动。

Strength Reduction

Strength Reduction主要是把一些昂贵运算换成更便宜的形式。最常见的是：

1
2
3
x * 2^k  ->  x << k
x / 2^k  ->  x >> k
x % 2^k  ->  x & (2^k - 1)

但这里要注意有符号/无符号语义。尤其是除法和取模，signed情况下不能随手替换；unsigned的power-of-two转换会安全很多。另外，在RV64GC里mul本身就是一条指令，所以x * (2^k +/- 1)这类展开成slli + add/sub不一定更快，甚至会增加临时寄存器和spill。最后保留最明确安全的power-of-two转换就足够了。

Backend Optimization

IR层优化做完之后，剩下很大一部分性能差距其实在后端：寄存器分配质量、spill/reload数量、函数调用开销、栈帧维护、以及一些汇编层peephole。

Peephole

Peephole优化适合处理一些局部、确定正确的小模式。比如：

  • 删除mv x, x
  • 删除addi x, x, 0
  • 删除跳到下一块的fallthrough j
  • 把seqz/snez/slt/slti + bnez折成直接条件分支
  • 把一次性地址临时折进load/store：addi addr, base, off; ld x, 0(addr)变成ld x, off(base)

这些优化单个看起来都很小，但它们能减少短命临时寄存器，也能降低后续寄存器分配压力。对于模运算热点，还可以识别很小的add_mod/sub_mod/norm helper，在call site直接展开，省掉函数调用和参数搬运。

Linear Scan的改进

前面已经写过linear scan的基本做法，后端优化阶段主要是继续减少spill。朴素linear scan最大的问题是容易把一个虚拟寄存器的生命周期看成从第一次定义到最后一次使用的一个大区间，中间的live hole利用不起来。虽然完整live range splitting实现起来比较麻烦，但仍然有一些性价比很高的改进：

  • 用CFG计算liveIn/liveOut，而不是只看线性文本顺序
  • 对循环块加权，让循环里的use有更高spill cost
  • 跨call的interval优先尝试callee-saved寄存器
  • call只把实际用到的a0-a7参数寄存器计入use
  • 收集mv v1, v2的copy hint，尽量让不冲突的copy两端分到同一个物理寄存器
  • 对单定义li常量做rematerialization，需要时重新生成常量，而不是占一个spill slot

这里的核心判断是：隐藏性能点里很多时候不是IR还不够少，而是热点循环里被插了太多ld/sd。减少spill traffic通常比继续堆IR pass更有效。

栈帧和ABI

栈帧优化也很实在。比如leaf function不需要保存/恢复ra；如果一个leaf function没有call、alloca、spill，也没有使用callee-saved寄存器，就可以直接省略frame setup。callee-saved寄存器也只需要保存实际用到的那些，不要每个函数都机械地保存一堆。

另外RISC-V的load/store立即数偏移只有12-bit，大frame下访问栈槽会变成li + add + ld/sd这种更长的序列，所以large frame场景下要特别注意重复materialize frame address的问题。如果同一个大offset地址在一个基本块里反复出现，可以复用已经算出来的frame address。

Post-regalloc Spill Cleanup

寄存器分配之后还能再做一轮局部清理，专门处理spill/reload产生的冗余栈访问。比如：

  • ld slot后面又重复ld slot，中间没有写这个slot，可以直接复用前一次结果
  • sd same-value slot可以删掉
  • store a, slot; store b, slot中间没有load，可以删掉前一个store
  • large frame下重复的li off; add addr, off, s0可以替换成已有地址寄存器的mv

这个pass只做基本块内就已经能有收益，跨块做当然更强，但正确性压力会明显上升。整体上，后端优化的原则还是保守：先把明显冗余的spill/reload清掉，再考虑更复杂的live range splitting、copy coalescing和块布局调整。

Conclusion

从 2025.8 -> 2026.7，RxCompiler 走了一整年。很难说我对其的态度到底是好是坏，因为它实打实的给我本就上满压力的大二上带来了巨大的负担，但同时它也是我（有可能是这辈子最后一次）感受 de 这么大的工程项目的爽感了。从前端 + codegen & reg alloc 纯手搓手de，到 opt 交给 coding agent，这一年也见识了 coding agent 从 copilot 那样的废物，变身为 codex/cc 那样 harness 和 模型双双强大的 coding agent 的全过程。我并不喜欢编译以及传统sys本身，但很高兴通过编译，我间接地找到了一些我别的感兴趣的东西，也正在为此而努力。

You still have a long way to go, but I hope you can enjoy the process and keep learning.