凹语言Phi并行-凹语言与Golang共有问题的复盘
- 时间：2024-11-02
- 撰稿：凹语言开发组
- 转载请注明原文链接：https://wa-lang.org/smalltalk/st0060.html
近日，凹语言开发组（以下简称我们）发现了一个与 Golang 共有的错误，该问题与 SSA 相关，过程颇为戏剧性，记录如下。
1. 相关背景介绍
凹语言 是基于 Golang 开发的通用编程语言，交集部分的语义与 Golang 一致，语法有所差异。凹语言的前端（源码至 AST阶段）由 Golang 1.17 修改而来，AST 至 SSA 转换使用 golang.org/x/tools/go/ssa 包，后端（SSA 至 Wasm指令阶段）为我们自主开发。
SSA（静态单赋值）是一种代码的中间表示形式，典型特征是变量在代码中仅被赋值一次。SSA 形式有助于程序分析和优化，更多信息参考：https://en.wikipedia.org/wiki/Static_single-assignment_form。
golang.org/x/tools/go/ssa 包是 Golang 提供的工具包，提供了将 Go-AST 转换为 Go-SSA 等功能，很多基于 Golang 的语言项目均基于或使用了它——包括 TinyGo、Go+ 等，凹语言亦然。但值得注意的是，该包并未用于 Golang 编译器本身，而是主要用于代码分析等外部工具。
2. 问题初现
凹语言近期支持了 Map 的基本语义，然而，当我们试图使用红黑树（RBTree）对其实现进行优化时，运行结果却始终不符合预期。经过一天的排查，我们将问题代码缩减、定位如下：
图中左侧是 凹语言 代码，右侧是等价的 Golang 代码。从程序逻辑上看，由于 root 在 main 函数中已经初始化，insert 函数的 20行、24行应均被执行，且输出相同的非空值，然而，上述凹语言代码的运行结果如下：
===
0x3fffff0
0x0
既在循环体内时，y 被赋值，而离开循环体后，y 被置空？
使用 wa ssa test.wa 命令，可得 insert 函数的 SSA 形式如下：
# Location: test.wa:12:6
func insert():
0: entry P:0 S:1
t0 = println("===...":string) ()
t1 = *root *node
jump 3
1: for.body P:1 S:1
t2 = println(t6) ()
t3 = &t6.next [#0] **node
t4 = *t3 *node
jump 3
2: for.done P:1 S:0
t5 = println(t7) ()
return
3: for.loop P:2 S:2
t6 = phi [0: t1, 1: t4] #x *node
t7 = phi [0: t1, 1: t6] #y *node
t8 = t6 != nil:*node bool
if t8 goto 1 else 2
根据 SSA 的定义，任何变量均只能被赋值一次，而真实的程序中，大量存在根据条件判断为一个变量赋予不同值的情况，为表达这类逻辑，SSA 中有一种特殊的
phi指令，它的作用是根据代码执行路径选择不同的返回值，例如上述代码中的t6 = phi [0: t1, 1: t4]，它表示如果是从Block 0 进入，返回t1的值，如果是从 Block 1 进入，则返回t4的值。
按照常规逻辑（注意这里，后面会提到），我们将上述代码的执行顺序及逻辑推演如下：
- Block 0, t1 = 0x3fffff0, jump 3
- Block 3, 自Block 0进入, t6(既x) = 0x3fffff0, t7(既y) = 0x3fffff0, jump 1
- Block 1, 打印t6(0x3fffff0), t4 = x.next = nil, jump 3
- Block 3, 自Block 1进入, t6 = nil, t7 = nil, jump 2
- 打印t7(nil), 返回
既：在离开循环体后，y 会被错误赋值为空。我们认为这是一个生成了错误 SSA 代码的问题，于是在 Golang 仓库发起了 Issue：https://github.com/golang/go/issues/69929。
3. 争议
Issue 发出后不久，Alan Donovan 就将它关闭了，他表示 SSA 没问题，并建议我们先学习 SSA 的基础知识。
然而我们坚持 ssa 包存在问题的观点，原因一方面是上述 SSA 代码不长，它的执行逻辑推理起来并不困难；更重要的是我们发现：使用 ssa/interp 包的 Interpret() 函数解释执行上述 SSA 代码时，y 仍然被错误的赋为空值，打印结果与凹语言版本的输出别无二致！于是我们补充提交了使用 ssa/interp.Interpret() 解释执行的相关证据和结果，期望重新打开该 Issue。
4. 转机
很快，Alan Donovan 证实了 Bug 确实存在，然而出问题的并不是 ssa 包，而是 ssa/interp 包，既生成的 SSA 是正确的，但解释执行时存在错误。并给出了参考文献：Practical Improvements to the Construction and Destruction of Static Single Assignment Form。
问题出在这里：
3:
t6 = phi [0: t1, 1: t4]
t7 = phi [0: t1, 1: t6]
...
Block 3 中存在两条 Phi 指令，按照之前提到的常规逻辑，第一条指令的结果是第二条指令的入参，指令执行存在先后关系；而实际上生成 Phi 指令时，基于这样一个假设，既：“同一个 Block 中的 Phi 指令并行执行”，也就是说 phi [0: t1, 1: t6] 中的 t6，应该取其进入 Block 3 前的值，而非 phi [0: t1, 1: t4] 的返回值。按照这一假设，t7（既y） 的值为上一次迭代的 t6（既x），运行逻辑便与源代码意图一致了。巧合的是，凹编译器和 ssa/interp 犯了相同的错误——既按串行方式处理 Phi 指令。
实际上在之前的私下讨论中，考虑过“Phi 应并行执行”的可能：
但 interp 包有问题确实超出了我们的意料。
5. 结果及思考
Alan Donovan 迅速提交了对 ssa/interp 包的修正： https://go-review.googlesource.com/c/tools/+/621595。
我们也对凹语言中处理 Phi 指令的部分进行了修改：https://gitee.com/wa-lang/wa/commit/8138ee420dac88463515328b1edaef99eda43974。
我们使用的方法和 Alan Donovan 所用的不同，但都满足了“同一个 Block 中的 Phi 指令并行执行”这一约束，经测试结果正确，至此问题解决。
对一些专业人士来说，“Phi并行”或许是常识，但这一知识在多大范围内被熟知？我们做了一些不严谨的调查，情况不乐观。与其它指令顺序执行相比，Phi 显得鹤立鸡群（甚至可以说不符合常识），但它的特殊性并未被书籍、文章所强调，在查阅过龙书、虎书等经典出版物后，仅在《Learn LLVM 12》一书的第五章第1节（91页）发现了一句相关的内容：
……在第二个 phi 指令的参数列表中使用了相同的寄存器，但该值假定为通过第一个phi指令改变它之前的值。
另一方面，该问题存在于 golang.org/x/tools/go/ssa/interp 包中的时间已经有10年之久，在基于 Golang 发展的诸多语言项目中，为何仅我们发现了它？可能的原因之一是：与很多项目使用 LLVM 作为后端不同，凹语言的后端是自制的。由于 LLVM 恰当的处理了 Phi 指令，他们避免了掉入该陷阱的同时，错过了发现 interp 包中隐藏问题的机会。
通过这次事件，我们：
- 学习到了 SSA 中 Phi 指令的特殊约束，并通过本文在中文社区传播这一知识；
- 构造了可以稳定触发 Phi并发 的测试用例；
- 意外协助 Golang 解决了存在于 SSA 解释执行器中的错误。
经常有人质问我们：“重复发明轮子有何意义？”，这一经历正好可以用来作为回应。