近日,凹语言开发组(以下简称我们)发现了一个与 Golang 共有的错误,该问题与 SSA 相关,过程颇为戏剧性,记录如下。
- 相关背景介绍
凹语言 是基于 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 编译器本身,而是主要用于代码分析等外部工具。
- 问题初现
凹语言近期支持了 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。
- 争议
Issue 发出后不久,Alan Donovan 就将它关闭了,他表示 SSA 没问题,并建议我们先学习 SSA 的基础知识。
然而我们坚持 ssa
包存在问题的观点,原因一方面是上述 SSA 代码不长,它的执行逻辑推理起来并不困难;更重要的是我们发现:使用 ssa/interp
包的 Interpret()
函数解释执行上述 SSA 代码时,y
仍然被错误的赋为空值,打印结果与凹语言版本的输出别无二致!于是我们补充提交了使用 ssa/interp.Interpret()
解释执行的相关证据和结果,期望重新打开该 Issue。
- 转机
很快,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),运行逻辑便与源代码意图一致了。
实际上在之前的私下讨论中,考虑过"Phi 应并行执行"的可能:
但 interp
包有问题确实超出了我们的意料。
- 结果及思考
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 解释执行器中的错误。
经常有人质问我们:"重复发明轮子有何意义?",这一经历正好可以用来作为回应。