Go 编译器 SSA 中间代码探究

徐徐   in Beijing

# 环境

  • Go 版本：1.15.6

# 起因

前一段时间，在某个 Go 交流学习群里有一个群友发出下面两段特殊的代码：

代码段 1 ：

package main

import "time"

func main() {
	var i = 1
	go func() {
		time.Sleep(1*time.Second)
		println(i)
	}()
	i = 2
	for  {
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

代码段 2 ：

package main

import "time"

func main() {
	var i = 1
	go func() {
		time.Sleep(1*time.Second)
		println(i)
	}()
	i = 2
	select  {
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这两段程序的输出是什么？大部分人可能会觉得这两个程序会输出 2，毕竟 goroutine 在等待 1 秒钟之后才会输出 i 的值，这个时候 i = 2 这一行肯定已经执行了。但是事实是，这两段代码输出的结果不相同，代码段 1 输出的是 1，代码段 2 输出的是 2。这两段代码唯一的区别就是最后的部分，一个是 for，一个是 select，两者都会造成程序最终阻塞。

排查这个问题最容易想到的方式就是先看一下这段代码编译之后的汇编。

# 汇编代码

执行如下命令查看两者的汇编代码：

go tool compile  -S main.go
1

这里只截取代码段 1 的部分汇编：

0x0024 00036 (main.go:6)        LEAQ    type.int(SB), AX
0x002b 00043 (main.go:6)        MOVQ    AX, (SP)
0x002f 00047 (main.go:6)        PCDATA  $1, $0
0x002f 00047 (main.go:6)        CALL    runtime.newobject(SB)
0x0034 00052 (main.go:6)        MOVQ    8(SP), AX
0x0039 00057 (main.go:6)        MOVQ    $1, (AX)
0x0040 00064 (main.go:7)        MOVL    $8, (SP)
0x0047 00071 (main.go:7)        LEAQ    "".main.func1·f(SB), CX
0x004e 00078 (main.go:7)        MOVQ    CX, 8(SP)
0x0053 00083 (main.go:7)        MOVQ    AX, 16(SP)
0x0058 00088 (main.go:7)        CALL    runtime.newproc(SB)
0x005d 00093 (main.go:12)       PCDATA  $1, $-1
0x005d 00093 (main.go:12)       XCHGL   AX, AX
0x005e 00094 (main.go:12)       NOP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

可以看到，第 11 行已经被编译器优化掉了，所以代码 1 执行的结果是 1，而代码段 2 并没有被优化。

# 编译器优化部分：SSA 中间代码的生成与优化

接下来主要是研究一下这部分编译器的优化逻辑。

Go 的源代码在解析成 AST 之后，并不会直接生成目标机器代码，而是先转换成 SSA (opens new window) 形式的中间代码，SSA 叫做静态单赋值形式，是一种中间代码的表现形式。然后通过对中间代码一系列的优化，最终才会生成目标机器码。中间代码的生成也是我们常说的编译器前端的组成部分，也是前端处理源码的最后一步。

Go 的 SSA 中间代码形式大概如下（截取部分）：

v1 (?) = InitMem <mem>
v2 (?) = SP <uintptr>
v3 (?) = SB <uintptr>
v4 (?) = Addr <*uint8> {type.int} v3
v5 (?) = OffPtr <**uint8> [0] v2
v6 (6) = Store <mem> {*uint8} v5 v4 v1
v7 (6) = StaticCall <mem> {runtime.newobject} [16] v6
1
2
3
4
5
6
7

大致意思是（从左到右）：操作类型、变量类型、函数名称、依赖参数等，不同操作的写法也不一样。 每一行的 SSA 变量的定义源码在：ssa/value.go#L19 (opens new window)

基于一个适当定义的中间表示形式，可以把针对源语言 i 的前端和针对目标机器 j 的后端组合起来，构造得到源语言 i 在目标机器 j 上的一个编译器。这种创建编译器组合 的方法可以大大减少工作量：只要写出 m 种前端和 n 种后端处理程序，就可以得到 m*n 种编译程序。

《编译原理》第六章 中间代码的生成

Go 也提供一个工具可以帮助我们查看代码从源码到 AST 再到最终 汇编的过程：

GOSSAFUNC=main go build main.go
1

执行之后，Go 编译器会在源码所在位置的文件夹生成一个 html 文件，其中一共记录着从源码到最后的汇编代码变化过程。

讨论代码的 SSA 中间代码为(来源：golang.design (opens new window) 在线生成)：

我们略过 AST 部分，直接看 start 也就是从 AST 到 SSA 被构建的第一步。 其中代码段 1 的 v21、v22 部分给变量 i 赋值成 2 的中间代码已经是灰色，也就是 deadcode 无效代码。而代码段 2 则是正常的。

感兴趣的可以自行探究这部分代码，构建 SSA 的逻辑代码入口在 gc/ssa.go#L296 (opens new window)

简单说一下 SSA 生成的规则：

例如如下代码：

package test

func test1() int {
	var s = 10
	return s
}
1
2
3
4
5
6

其中变量 s 的定义对应的 SSA 如下：

v6 (?) = Const64 <int> [10] (s[int])
1

你可能会问，代码段 1 中的变量 i 的定义和上面不一样：

v6 (6) = Store <mem> {*uint8} v5 v4 v1
v7 (6) = StaticCall <mem> {runtime.newobject} [16] v6
v8 (?) = OffPtr <**int> [8] v2
v9 (6) = Load <*int> v8 v7 (&i[*int])
v10 (?) = Const64 <int> [1]
v11 (6) = Store <mem> {int} v9 v10 v7
1
2
3
4
5
6

这是因为变量 i 被闭包 goroutine 使用了，所以发生了逃逸，变量 i 实际上是一个指针。我们也可以从 AST 中发现，变量 i 这一行生成了两个 AST 节点，第一个节点是关于调用 runtime.newobject 的，第二个节点 left 的类型是 DEREF，其含义为指针。定义位置在 gc/syntax.go#L735 (opens new window)。当变量为指针时，SSA 写法也会发生相应的变化，后面两行的逻辑在：gc/ssa.go#L3041 (opens new window)，其中函数 storeType 会生成最后这一行（v11）。

其中特殊的 mem 类型表示全局内存状态，定义在 types/type.go#L1463 (opens new window)，Store 操作定义在：gen/genericOps.go#L349 (opens new window) 。v11 这行 v9、v10、v7 均为操作参数，意思为把 v10 存储到 v9，最后一个参数 v7 代表内存状态。这一部分可以看一下 Go 官方文档 (opens new window)的介绍。其中最后一个参数可以理解为操作 v11 依赖操作 v7，所以这两个内存操作是不能重新排序的。

# Deadcode 逻辑

代码段 1 的中间代码 v21、v22 被标记成灰色，证明这部分代码是无效的，最终并不会生成到二进制文件中。

v21 (?) = Const64 <int> [2]
v22 (11) = Store <mem> {int} v9 v21 v20
1
2

deadcode 的逻辑并不复杂，这部分代码在：ssa/deadcode.go#L13 (opens new window)。ReachableBlocks 函数返回可达的 Block 列表，函数从 f.Entry 开始遍历，Block 结构中的 Succs 字段保存着后续关联的 Block。知道了可达的 Block，接下来就是遍历这些 Block，找到 liveValues。这部分的主要逻辑在：ssa/deadcode.go#L109 (opens new window)。

示例中的 SSA 只有 b1 Block 有代码，其他的都是空块，你也可以尝试写一个简单的 if else 语句，或者在 for 循环中加点东西，这样其他 Block 也会有代码了，if、else、for 等是会生成新的 Block。

遍历 Block 部分代码：

for _, b := range f.Blocks {
		// ...
		for _, v := range b.ControlValues() {
			// ...
			// ControlValues 均为 live value
		}
		for _, v := range b.Values {
			if (opcodeTable[v.Op].call || opcodeTable[v.Op].hasSideEffects) && !live[v.ID] {
				// ...
				// 操作类型是 call、hasSideEffects（例如 atomic store 操作） 的是 live value
			}
			if v.Type.IsVoid() && !live[v.ID] {
				// ...
				// TypeVoid 类型相关逻辑，未深究
			}
		}
	}

	for len(q) > 0 {
		// ...
		// 前面找到的 live value 的参数 Args，除了 OpPhi 的特殊情况，其他均为 live value
		for i, x := range v.Args {
			if v.Op == OpPhi && !reachable[v.Block.Preds[i].b.ID] {
				// Phi 就是 SSA 中的 φ 表示，如果参数中的 Phi 的 Preds Block 是不可达的，则不是 live value
				continue
			}
			// ...
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

做一个不严谨但是简单的总结，live value 就是从 Entry 开始所有的可达块中 ControlValues、call、hasSideEffects 类型的变量并且加上其参数（当然还有代码中的特殊情况，就不列举了）。

代码段 2 中，由于最后的 select 本质上会在编译阶段替换成 runtime.block 函数，导致前面定义的 mem 类型（Store <mem> {int} v9 v21 v20）被函数调用（StaticCall <mem> {runtime.block} v22）依赖，成为参数，所以 i = 2 这一行成了 live value。

根据这些逻辑，我们只要把代码段 1 修改成这样就会和代码 2 的行为一样了：

package main

import "time"

func main() {
	var i = 1
	go func() {
		time.Sleep(1 * time.Second)
		println(i)
	}()
	i = 2
	println() // 没错，只需要随便加一个函数调用就可以了
	for {
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

以上只是涉及到 Go 中间代码一小部分逻辑，其中还有很多优化以及处理器架构等相关的逻辑，可以使用 Go 自带的 GOSSAFUNC 方法查看整个过程的， 其中每一步的动作的代码都会在这里注册：ssa/compile.go#L418 (opens new window)。

# 其他细节

# 参考资料

环境
起因
汇编代码
编译器优化部分：SSA 中间代码的生成与优化
Deadcode 逻辑
其他细节
参考资料