13.4 SSA 中间表示

13.4 SSA 中间表示

TODO: 请不要阅读此小节,内容编排中

核心概念

以下描述的名称可能与 Go 的对应名称弱相关,但是请注意,它们并不完全等价。 例如,Go 块语句具有变量作用域,但 SSA 没有变量概念也没有变量作用域。

值和块以其唯一的顺序 ID 命名也可能令人惊讶。它们很少对应于原始代码中的命名实体, 例如变量或函数参数。顺序 ID 还允许编译器避免映射,并且始终可以使用调试和位置信息将值 追溯到 Go 代码。

值是 SSA 的基本组成部分。根据 SSA 的定义,一个值仅定义一次,但是可以使用多次。 值主要由唯一标识符,运算符,类型和一些参数组成。

一个运算符或 Op 描述了计算该值的操作。每个运算符的语义可以在 gen/*Ops.go 中找到。 例如,OpAdd8 接受两个值参数,这些值参数包含8位整数,并将它们相加。 这是两个 uint8 值相加的可能的 SSA 表示形式:

1
2
// var c uint8 = a + b
v4 = Add8 <uint8> v2 v3

值的类型通常是 Go 类型。例如,以上示例中的值具有 uint8 类型, 而常量布尔值将具有 bool 类型。但是,某些类型不是来自 Go,而是特殊的。

内存类型

memory 代表全局内存状态。占用内存的 Op 参数取决于该内存状态,以及具有内存类型的 Op 影响内存状态。这样可以确保将内存操作保留在正确的顺序。例如:

1
2
3
4
// *a = 3
// *b = *a
v10 = Store <mem> {int} v6 v8 v1
v14 = Store <mem> {int} v7 v8 v10

这里 memory 将其第二个参数(类型为 int)存储到第一个参数中 (类型为 *int)。 最后一个参数是内存状态; 第二个 Store 取决于第一个存储定义的内存值,两个 Store 不能重新排序。

块代表函数控制流程图中的基本块。从本质上讲,它是定义此块操作的值列表。 除了值列表之外,块主要由唯一标识符,种类和后继块列表组成。

最简单的一种是 plain 块。它只是将控制流移交给另一个块,因此其后继列表包含一个块。

另一种常见的块类型是 exit 块。它们具有最终值,称为控制值,该值必须返回存储器状态。 这对于函数返回某些值是必要的,例如,调用者需要某种内存状态依赖,以确保其正确接收这些返回值。

我们将提到的最后一个重要的块类型是 if 块。 它具有一个必须为布尔值的单个控制值, 并且恰好具有两个后继块。如果布尔值是正确的,则将控制流传递给第一个后继块,否则传递给第二个后继块。

这是一个用基本块表示的示例 if-else 控制流:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
// func(b bool) int {
// 	if b {
// 		return 2
// 	}
// 	return 3
// }
b1:
    v1 = InitMem <mem>
    v2 = SP <uintptr>
    v5 = Addr <*int> {~r1} v2
    v6 = Arg <bool> {b}
    v8 = Const64 <int> [2]
    v12 = Const64 <int> [3]
    If v6 -> b2 b3
b2: <- b1
    v10 = VarDef <mem> {~r1} v1
    v11 = Store <mem> {int} v5 v8 v10
    Ret v11
b3: <- b1
    v14 = VarDef <mem> {~r1} v1
    v15 = Store <mem> {int} v5 v12 v14
    Ret v15

函数

函数代表函数声明及其主体。它主要由名称,类型(其签名), 构成其主体的块列表以及该列表内的入口块组成。

调用函数时,控制流将移至其输入框。如果函数终止,则控制流最终将到达出口块, 从而结束函数调用。

请注意,一个函数可能具有零个或多个出口块,就像Go函数可以具有任意数量的返回点一样, 但是它必须恰好具有一个入口点块。

另请注意,某些 SSA 函数是自动生成的,例如用作映射键的每种类型的散列函数。

例如,这是空函数在 SSA 中的样子,只有一个退出块返回无用的内存状态:

foo func()
    b1:
        v1 = InitMem <mem>
        Ret v1

编译器传递

单独使用 SSA 形式的程序不是很有用。它的优点在于编写修改程序以使其更佳的优化非常容易。 Go 编译器通过传递列表来完成此操作。

每遍都以某种方式转换 SSA 功能。例如,无效代码消除过程将删除它可以证明将永远不会执行的块和值, 而无校验检查消除过程将除去可能证明是多余的无校验。

编译器一次传递一个函数的工作,默认情况下顺序运行一次并且恰好一次运行。

lower 传递较为特殊;它将 SSA 表示形式从独立于机器转换为独立于机器。 也就是说,某些抽象运算符将替换为其非通用的对应运算符,从而有可能减少或增加最终值的数量。

SSA 开发

查看和适应编译器的SSA的有效方法是通过GOSSAFUNC。 例如,要查看 func Foo 的初始SSA表单和最终生成的程序集,可以运行:

GOSSAFUNC=Foo go build

生成的 ssa.html 文件还将在每个编译阶段包含SSA函数,从而易于查看每个阶段对特定程序的作用。 您也可以单击值和块以突出显示它们,以帮助遵循控制流程和值。

虽然大多数编译器传递都是直接在 Go 代码中实现的,但其他一些传递是通过代码生成的。 当前这是通过重写规则来完成的,重写规则具有自己的语法,并在 gen/*.rules 中维护。 可以通过这种方式轻松,快速地编写更简单的优化,但是重写规则不适合更复杂的优化。