【翻译】Go 编译器理解: 新增一个关键字语句-Part2
这是介绍Go编译器系列的第二篇,在第1部分中,我们在Go中添加了一个新的关键词语句,通过构建修改版本的编译器来支持该关键字。为此,我们按照此图介绍了编译器的前五个阶段:
在最后,我们是通过在"重写AST"阶段将其替换为for
来实现until
。另外,在gc/walk.go
中,其他类似的转换也是在编译器进行SSA转换和代码生成之前完成的。
在这一部分中,我们将通过在编译流程中处理新的until
语句来介绍编译器的其余阶段。
SSA
在gc
运行walk
转换后,它调用buildssa
(在gc/ssa.go
中)将AST转换为新的中间表示(intermediate representation (IR)),其形式为静态单赋值(SSA)形式。
注:一个Go程序元素只有包、类型、函数、变量和常量 (packages, types, functions, variables and constants)这五种。ssa定义了的他们的数据结构,使用函数体的静态单赋值(ssa)形式中间表示(IR)。
SSA是什么意思?为什么编译器会将AST转为SSA?让我们从第一个问题开始;我建议阅读上面链接的SSA维基百科页面和其他资源,但这是一个快速说明。
静态单赋值意味着IR中分配的每个变量仅赋值一次。考虑以下伪IR:
x = 1
y = 7
// do stuff with x and y
x = y
y = func()
// do more stuff with x and y
这不是SSA,因为名称x和y被多次赋值。如果将此代码段转换为SSA,我们可能会得到类似以下内容的信息:
x = 1
y = 7
// do stuff with x and y
x_1 = y
y_1 = func()
// do more stuff with x_1 and y_1
请注意,每个赋值如何获得唯一的变量名。当x
被重新分配了一个不同的值时,一个新的名字x_1
被创建了。您可能想知道这在一般情况下是如何工作的……类似的代码会发生什么:
x = 1
if condition: x = 2
use(x)
如果我们只是简单地将第二个赋值重命名为x_1 = 2
,那么use
将会使用 x
或x_1
或…?为了处理这种重要情况,SSA形式的IR具有特殊的 phi (最初为 phony )功能,可以根据其来自的代码路径来选择一个值。它看起来像这样:
当分析和优化此类IR时,编译器使用该phi节点来维护SSA,并在以后的阶段用实际的机器代码代替。
SSA名称的static 部分起着与 static类型中类似的作用;这意味着在查看源代码时(在编译时或静态),每个名称的赋值都是唯一的,但是在运行时可能会多次发生。例如上面显示的代码示例处于循环中,则实际的x_1 = 2
赋值可能会发生多次。
既然我们对什么是SSA有一个基本的了解,那么下一个问题就是为什么编译器会将AST转为SSA。
优化是编译器后端的最重要部分,因此后端通常是专门为促进有效和高效的优化而构建的。再次查看此代码段:
x = 1
if condition: x = 2
use(x)
并假设编译器要运行一个非常通用的优化-常数传播 ( constant propagation),该优化希望在x = 1
赋值后用1替换所有使用x
的地方。这需要怎么做呢?它不能在赋值之后找到对x
的所有引用进行替换,因为x
可以重写为其他内容(x = 2
)。
请考虑以下代码段:
z = x + y
在一般情况下,编译器必须执行数据流分析才能找到:
x
和y
在什么地方定义的。在存在控制流的情况下,这并不容易,需要进行“优势”分析。在定义之后使用
z
的地方,这同样具有挑战性。
就时间和空间而言,这种分析的创建和维护成本很高。此外,必须在每次优化后重新运行(至少部分运行)。
SSA提供了一个很好的选择。如果SSA中有z = x + y
,我们会立即知道x
和y
定义的地方(且只能是一个),并且我们会立即知道z
的使用位置(此语句后对z
的所有引用)。在SSA中,使用和定义在IR中进行了编码,并且优化不会违反不变性。
Go 编译器中的SSA
我们继续介绍如何在Go编译器中SSA是如何构造和使用的。 SSA是Go的相对较新的新增功能。除了将AST转换为SSA的大量代码(位于gc/ssa.go
)外,其大部分代码都保存在ssa/
中。 ssa
目录中的README
文件是Go SSA的非常有用的说明(务必查看)!
Go SSA实现还具有一些我见过的最好的编译器工具。通过设置环境变量GOSSAFUNC
,我们可以获得一个HTML页面,其中包含所有编译阶段以及每个编译阶段之后的IR,因此,如果需要,我们可以轻松地检测出哪个优化出错了。附加设置可以绘制每次pass
时的控制流图。
让我们研究一下如何从下述代码的AST中创建初始SSA:
func usefor() {
i := 4
for !(i == 0) {
i--
sayhi()
}
}
func sayhi() {
fmt.Println("Hello, for!")
}
我将fmt.Println("Hello, for!")
打印输出移至其sayhi()
的原因是为了使结果SSA更加整洁。使用-l
进行编译以禁用内联,这会留下一个对sayhi()
的微小调用(而由于常量字符串,对fmt.Println
的调用会生成更多代码)。
产生的SSA为:
b1:
v1 (?) = InitMem <mem>
v2 (?) = SP <uintptr>
v3 (?) = SB <uintptr>
v4 (?) = Const64 <int> [4] (i[int])
v6 (?) = Const64 <int> [0]
v9 (?) = Const64 <int> [1]
Plain → b2 (10)
b2: ← b1 b4
v5 (10) = Phi <int> v4 v10 (i[int]) // 第一次循环,选择V4
v14 (14) = Phi <mem> v1 v12
v7 (10) = Eq64 <bool> v5 v6
If v7 → b5 b3 (unlikely) (10)
b3: ← b2
v8 (11) = Copy <int> v5 (i[int])
v10 (11) = Sub64 <int> v8 v9 (i[int])
v11 (12) = Copy <mem> v14
v12 (12) = StaticCall <mem> {"".sayhi} v11
Plain → b4 (12)
b4: ← b3
Plain → b2 (10)
b5: ← b2
v13 (14) = Copy <mem> v14
Ret v13
这里要注意的有趣部分是:
bN
是控制流程图的基本块(一个作用域).Phi
节点是显式的。 最有趣的是对v5
的赋值。这正是选择器给i
赋值的语句:一条路径来自v4
(初始化赋值),另一条路径来自v10
(i--
)循环。- 在本练习中,忽略带有
<mem>
的节点。 Go有一种有趣的方式可以在其IR中显式传播内存状态,在本文中我们将不涉及它。如果有兴趣的话,请参阅前面的README
了解更多详细信息。
顺便说一句,这里的for
循环正是我们想要将until
语句转换成的。
转换 until
AST 节点到 SSA
像往常一样,我们的代码将以for
语句的处理为模型。首先,让我们开始看下until
语句的控制流图 :
现在,我们只需要用代码构建此控制流图 。提醒:我们在第1部分中添加了新的AST节点类型OUNTIL
。我们将在gc/ssa.go
中的state.stmt
方法中添加一个新的switch
分支,以将OUNTIL
的AST节点转换为SSA。代码块和注释的命名应使代码易于阅读,并与上面显示的控制流图中命名相关。
case OUNTIL:
// OUNTIL: until Ninit; Left { Nbody }
// cond (Left); body (Nbody)
bCond := s.f.NewBlock(ssa.BlockPlain)
bBody := s.f.NewBlock(ssa.BlockPlain)
bEnd := s.f.NewBlock(ssa.BlockPlain)
bBody.Pos = n.Pos
// 首先 ,上一个 Block结束块 连接到当前的 CondBlock块
// first, entry jump to the condition
b := s.endBlock()
b.AddEdgeTo(bCond)
// 开始生成 CondBlock
// generate code to test condition
s.startBlock(bCond)
if n.Left != nil {
// left 不为空,直接使用condBranch,if for 都使用这个函数
s.condBranch(n.Left, bEnd, bBody, 1)
} else {
// left 为空 无限循环。直接结束生成代码
b := s.endBlock()
b.Kind = ssa.BlockPlain
b.AddEdgeTo(bBody) // 添加到 Body的连接
}
// 设置 continue/break
// set up for continue/break in body
prevContinue := s.continueTo
prevBreak := s.breakTo
s.continueTo = bCond
s.breakTo = bEnd
lab := s.labeledNodes[n]
if lab != nil {
// labeled until loop
lab.continueTarget = bCond
lab.breakTarget = bEnd
}
// 开始 生成 Body代码
// generate body
s.startBlock(bBody)
s.stmtList(n.Nbody)
// 拆除 continue/break,这里是置为上一个 prevContinue和 prevBreak
// 因为有循环嵌套
// tear down continue/break
s.continueTo = prevContinue
s.breakTo = prevBreak
if lab != nil {
lab.continueTarget = nil
lab.breakTarget = nil
}
// done with body, goto cond
if b := s.endBlock(); b != nil {
b.AddEdgeTo(bCond)
}
// 生成结束代码
s.startBlock(bEnd)
如果您想知道n.Ninit
在哪里处理-它在switch
之前完成,对于所有节点类型都是统一的。
实际上,这是我们在编译器的最后阶段处理 until
语句的全部工作!如果我们运行编译器,像以前一样打印出下述代码的SSA:
func useuntil() {
i := 4
until i == 0 {
i--
sayhi()
}
}
func sayhi() {
fmt.Println("Hello, for!")
}
如预期的那样,我们将得到SSA,该SSA在结构上等同于条件为 for
的循环所用的SSA。
SSA transformations 变换
构造了初始SSA之后,编译器会在SSA IR上执行以下一系列漫长的遍历操作:
- 执行优化
- 将其转换为更接近机器代码的形式
所有 passes 都可以在ssa/compile.go
的passes
切片中找到,并且可以在同一文件的passOrder
切片中对它们的运行顺序进行一些修改。对于现代编译器而言,优化是相当标准的。降低针对特定体系结构的指令选择,以及寄存器分配。
有关这些 passes 的更多详细信息,请参见SSA README和this post,其中详细介绍了如何指定SSA优化规则。
生成机器码
最后,编译器调用genssa
(在gc/ssa.go
中)从SSA IR中生成机器代码。我们不必修改任何代码,因为我们为until
语句生成的SSA构造块,是编译器已经实现的,我们不添加新的指令类型。
但是,研究useuntil
函数生成的机器代码是有学习知道意义的。 Go具有自己的汇编语法。我不会在这里讨论所有细节,但是下面是带注释的(带有#注释
)汇编实现,应该很容易阅读。我删除了一些垃圾回收器(garbage collector)的指令(PCDATA
和 FUNCDATA
),以使输出变小。
"".useuntil STEXT size=76 args=0x0 locals=0x10
0x0000 00000 (useuntil.go:5) TEXT "".useuntil(SB), ABIInternal, $16-0
# Function prologue
0x0000 00000 (useuntil.go:5) MOVQ (TLS), CX
0x0009 00009 (useuntil.go:5) CMPQ SP, 16(CX)
0x000d 00013 (useuntil.go:5) JLS 69
0x000f 00015 (useuntil.go:5) SUBQ $16, SP
0x0013 00019 (useuntil.go:5) MOVQ BP, 8(SP)
0x0018 00024 (useuntil.go:5) LEAQ 8(SP), BP
# AX will be used to hold 'i', the loop counter; it's initialized
# with the constant 4. Then, unconditional jump to the 'cond' block.
0x001d 00029 (useuntil.go:5) MOVL $4, AX
0x0022 00034 (useuntil.go:7) JMP 62
# The end block is here, it executes the function epilogue and returns.
0x0024 00036 (<unknown line number>) MOVQ 8(SP), BP
0x0029 00041 (<unknown line number>) ADDQ $16, SP
0x002d 00045 (<unknown line number>) RET
# This is the loop body. AX is saved on the stack, so as to
# avoid being clobbered by "sayhi" (this is the caller-saved
# calling convention). Then "sayhi" is called.
0x002e 00046 (useuntil.go:7) MOVQ AX, "".i(SP)
0x0032 00050 (useuntil.go:9) CALL "".sayhi(SB)
# Restore AX (i) from the stack and decrement it.
0x0037 00055 (useuntil.go:8) MOVQ "".i(SP), AX
0x003b 00059 (useuntil.go:8) DECQ AX
# The cond block is here. AX == 0 is tested, and if it's true, jump to
# the end block. Otherwise, it jumps to the loop body.
0x003e 00062 (useuntil.go:7) TESTQ AX, AX
0x0041 00065 (useuntil.go:7) JEQ 36
0x0043 00067 (useuntil.go:7) JMP 46
0x0045 00069 (useuntil.go:7) NOP
0x0045 00069 (useuntil.go:5) CALL runtime.morestack_noctxt(SB)
0x004a 00074 (useuntil.go:5) JMP 0
您可能已经注意到cond
块移到了函数的末尾,而不是它最初在SSA表示中的位置。这是为什么?
答案是最后阶段在SSA上运行的loop rotate
pass。此 pass 会对块进行重新排序,以使 body flows直接流入cond,从而避免每次迭代产生额外的跳跃。如果您有兴趣,请参见ssa/looprotate.go
了解更多详细信息。
结论
在这两篇文章中,我们以两种不同的方式实现了一条新语句,从而了解了Go编译器的一些内部结构。当然,这只是冰山一角,但我希望它为您自己开始探索提供了一个良好的起点。
最后一点:我们在这里构建了一个可运行的编译器,但是Go工具都无法识别新的until
关键字。不幸的是,此时Go工具使用了完全不同的方法来解析Go代码,并且没有与Go编译器本身共享此代码(例如gopls ,golint,所以不能针对新关键字自动实现自动补全之类的功能)。我将在以后的文章中详细介绍如何使用工具处理Go代码。
附录-复现这些结果
要重现我们最终在此处使用的Go工具链的版本,您可以从第1部分开始,在 walk.go
中还原 AST 转换代码,然后添加上述 AST-> SSA转换。或者,您也可以从我的仓库上抓取adduntil2分支。
要获得从所有SSA的until
SSA,并在单个方便的HTML文件中传递代码生成,请在构建新编译器后运行以下命令:
GOSSAFUNC=useuntil <src checkout>/bin/go tool compile -l useuntil.go
然后在浏览器中打开ssa.html
。如果您还想查看控制流图的某些 pass,请在函数名后添加 pass 名,并以:
分隔。 例如 GOSSAFUNC=useuntil:number_lines
.
要获取机器代码,请运行:
<src checkout>/bin/go tool compile -l -S useuntil.go