Phi并行-凹语言与Golang共有问题的复盘

原创
11/04 09:45
阅读数 74
AI总结

近日,凹语言开发组(以下简称我们)发现了一个与 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 编译器本身,而是主要用于代码分析等外部工具。

  1. 问题初现

凹语言近期支持了 Map 的基本语义,然而,当我们试图使用红黑树(RBTree)对其实现进行优化时,运行结果却始终不符合预期。经过一天的排查,我们将问题代码缩减、定位如下:

图中左侧是 凹语言 代码,右侧是等价的 Golang 代码。从程序逻辑上看,由于 rootmain 函数中已经初始化,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 的值。

按照常规逻辑(注意这里,后面会提到),我们将上述代码的执行顺序及逻辑推演如下:

  1. Block 0, t1 = 0x3fffff0, jump 3
  2. Block 3, 自Block 0进入, t6(既x) = 0x3fffff0, t7(既y) = 0x3fffff0, jump 1
  3. Block 1, 打印t6(0x3fffff0), t4 = x.next = nil, jump 3
  4. Block 3, 自Block 1进入, t6 = nil, t7 = nil, jump 2
  5. 打印t7(nil), 返回

既:在离开循环体后,y 会被错误赋值为空。我们认为这是一个生成了错误 SSA 代码的问题,于是在 Golang 仓库发起了 Issue:https://github.com/golang/go/issues/69929

  1. 争议

Issue 发出后不久,Alan Donovan 就将它关闭了,他表示 SSA 没问题,并建议我们先学习 SSA 的基础知识。

然而我们坚持 ssa 包存在问题的观点,原因一方面是上述 SSA 代码不长,它的执行逻辑推理起来并不困难;更重要的是我们发现:使用 ssa/interp 包的 Interpret() 函数解释执行上述 SSA 代码时,y 仍然被错误的赋为空值,打印结果与凹语言版本的输出别无二致!于是我们补充提交了使用 ssa/interp.Interpret() 解释执行的相关证据和结果,期望重新打开该 Issue。

  1. 转机

很快,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 包有问题确实超出了我们的意料。

  1. 结果及思考

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 解释执行器中的错误。

经常有人质问我们:"重复发明轮子有何意义?",这一经历正好可以用来作为回应。

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
0 评论
0 收藏
0
分享
AI总结
返回顶部
顶部