凹语言map与Φ指令的纠葛

柴树杉

3 Nov 2024

自我介绍

2

主题大纲

3

主题大纲

4

凹语言简介

5

发展历程

6

SSA背景介绍

7

SSA：静态单赋值

8

凹语言对Go语言SSA的依赖

注意的是，该包并未用于 Go 编译器本身，主要用于代码分析等外部工具。

9

map优化时遇到了问题

10

map特性的诞生路径

map诞生花了2年多时间，是凹语言最复杂的特性之一。

但是最初版本运行时是用数组实现，亟需优化...

11

一个Issue引发的争议

12

SSA踩坑记(01)

我们试图使用红黑树（RBTree）对map实现进行优化时，运行结果却始终不符合预期。经过一天的排查，我们将问题代码缩减、定位如下：

13

SSA踩坑记(02)

从程序逻辑上看，由于 root 在 main 函数中已经初始化，insert 函数的 20行、24行应均被执行，且输出相同的非空值，然而，上述代码的运行结果如下：

=====================
0x3fffff0
0x0

既在循环体内时，y 被赋值，而离开循环体后，y 被置空？

14

SSA踩坑记(03)

使用 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
15

SSA踩坑记(04)

Φ指令: 上述代码中的 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 仓库发起了 Issue69929。

16

Issue69929 引争议(01)

原始的描述是：i guess the ssa lose the y = x in for loop. the test code should print(root) twice.。我们猜测是生成的SSA可能丢失了y = x的赋值语句。

17

Issue69929 引争议(02)

Issue69929 发出后不久，Alan Donovan 就将它关闭了，他表示 SSA 没问题，并建议我们先学习 SSA 的基础知识。(然后就引起了一些情绪上的争议, 口述无责任八卦内容...)

18

深挖Φ指令10年坑

19

草根的坚持

20

转机：大佬的高风亮节

很快，Alan Donovan 证实了 Bug 确实存在，然而出问题的并不是 ssa 包，而是 ssa/interp 包，既生成的 SSA 是正确的，但解释执行时存在错误。并给出了参考文献：Practical Improvements to the Construction and Destruction of Static Single Assignment Form。

问题出在这里：

t6 = phi [0: t1, 1: t4]
t7 = phi [0: t1, 1: t6]
...

实际上这2个phi指令是并行执行的，因此并不存在执行先后的依赖关系。

21

我们其实也考虑过Phi指令并行的可能...

实际上在之前的私下讨论中，考虑过“Phi 应并行执行”的可能。

但 ssa/interp 包有问题确实超出了我们的意料（世界草台班子理论）。

22

结果及思考

23

问题解决，凹语言map终于用上红黑树

Alan Donovan 迅速提交了修正 golang.org/x/tools/go/ssa/interp 包的 pr；我们也对凹语言中处理 Phi 指令的部分进行了修改。我们使用的方法和 Alan Donovan 所用的不同，但都满足了“同一个 Block 中的 Phi 指令并行执行”这一约束，经测试表明结果正确。至此问题解决。

24

Phi指令并行并非多大的共识

对一些专业人士来说，“Phi并行”或许是常识，但这一知识在多大范围内被熟知？我们做了一些不严谨的调查，情况不乐观。在查阅过龙书、虎书等经典出版物后，仅在《Learn LLVM 12》一书的 91 页发现了一句相关的内容：“……在第二个 phi 指令的参数列表中使用了相同的寄存器，但该值假定为通过第一个phi指令改变它之前的值。”

另一方面，该问题存在于 golang.org/x/tools/go/ssa/interp 包中的时间已经有10年之久，在基于 Golang 发展的诸多语言项目中，为何仅我们发现了它？可能的原因之一是：与很多项目使用 LLVM 作为后端不同，凹语言的后端是自制的。由于 LLVM 恰当的处理了 Phi 指令，他们避免了掉入该陷阱的同时，错过了发现 interp 包中隐藏问题的机会。

25

在战争中学习战争

通过这次事件，我们：

经常有人质问我们：“重复发明轮子有何意义？”，这一经历正好可以用来作为回应。

26

Phi指令再进化

27

Phi指令进化为Block参数

在更新的MLIR和SwiftIR都引入了Block参数，通过提前计算以避免Phi指令并行的干扰。

28

参考链接

29

Thank you

柴树杉

3 Nov 2024

https://wa-lang.org

Use the left and right arrow keys or click the left and right edges of the page to navigate between slides.
(Press 'H' or navigate to hide this message.)