Go 语言编译过程

Go 语言需要编译才能够运行，为了理解 Go 的执行过程，我们从编译原理的一些基础概念出发，对 Go 的编译过程进行探讨。

编译原理预备知识

抽象语法树

（AST），是源代码语法的结构的一种抽象表示，它用树状的方式表示编程语言的语法结构1。抽象语法树中的每一个节点都表示源代码中的一个元素，每一颗子树都表示一个语法元素，例如一个 if else 语句，我们可以从 2 * 3 + 7 这一表达式中解析出下图所示的抽象语法树。

2019-12-20-15768548776645-abstract-syntax-tree

作为编译器常用的数据结构，抽象语法树抹去了源代码中不重要的一些字符 - 空格、分号或者括号等等。编译器在执行完语法分析之后会输出一个抽象语法树，这个抽象语法树会辅助编译器进行语义分析，我们可以用它来确定语法正确的程序是否存在一些类型不匹配或不一致的问题。

静态单赋值

静态单赋值（Static Single Assignment, SSA）是中间代码的一个特性，如果一个中间代码具有静态单赋值的特性，那么每个变量就只会被赋值一次2。在实践中我们通常会用添加下标的方式实现每个变量只能被赋值一次的特性，这里以下面的代码举个例子：

x := 1
x := 2
y := x

根据分析，我们其实能够发现上述的代码其实并不需要第一个将 1 赋值给 x 的表达式，也就是 x := 1 这一表达式在上述的代码片段中是没有作用的。

x1 := 1
x2 := 2
y1 := x2

当我们使用具有 SSA 特性的中间代码时，就可以非常清晰地发现变量 y1 的值和 x1 是完全没有任何关系的，所以在机器码生成时其实就可以省略第一步，这样就能减少需要执行的指令来优化这一段代码。

在中间代码中使用 SSA 的特性能够为整个程序实现以下的优化：

  1. 常数传播（constant propagation）
  2. 值域传播（value range propagation）
  3. 稀疏有条件的常数传播（sparse conditional constant propagation）
  4. 消除无用的程式码（dead code elimination）
  5. 全域数值编号（global value numbering）
  6. 消除部分的冗余（partial redundancy elimination）
  7. 强度折减（strength reduction）
  8. 寄存器分配（register allocation）

因为 SSA 的主要作用是对代码进行优化，所以它是编译器后端 3 的一部分；当然代码编译领域除了 SSA 还有很多中间代码的优化方法。

指令集

最后要介绍的一个预备知识就是 指令集 了，很多开发者都会遇到在生产环境运行的结果和本地不同的问题，导致这种情况的原因其实非常复杂，不同机器使用不同的指令也是可能的原因之一。

我们在命令行中输入 uname -m 就能够获得当前机器上硬件的信息：

$ uname -m
x86_64

x86 是目前比较常见的指令集，除了 x86 之外，还有很多其他的指令集，不同的处理器使用了不同的架构和机器语言，所以很多编程语言为了在不同的机器上运行需要将源代码根据架构翻译成不同的机器代码。

复杂指令集计算机（CISC）和精简指令集计算机（RISC）是目前的两种 CPU 区别，它们在设计理念上会有一些不同，从名字我们就能看出来这两种不同的设计有什么区别：

  • 复杂指令集通过增加指令的数量减少需要执行的指令数；
  • 精简指令集能使用更少的指令完成目标的计算任务；

早期的 CPU 为了减少机器语言指令的数量使用复杂指令集完成计算任务，这两者其实并没有绝对的好坏，它们只是在一些设计上的选择不同以达到不同的目的。

Go 编译

Go 语言编译器的源代码在 src/cmd/compile 目录中，目录下的文件共同组成了 Go 语言的编译器。编译器有前端和后端，编译器的前端一般承担着词法分析、语法分析、类型检查和中间代码生成几部分工作，而编译器后端主要负责目标代码的生成和优化，也就是将中间代码翻译成目标机器能够运行的二进制机器码。

complication-process

Go 的编译器在逻辑上可以被分成四个阶段：词法与语法分析、类型检查和 AST 转换、通用 SSA 生成和最后的机器代码生成。

词法与语法分析

所有的编译过程其实都是从解析代码的源文件开始的，词法分析的作用就是解析源代码文件，它将文件中的字符串序列转换成 Token 序列，方便后面的处理和解析，我们一般会把执行词法分析的程序称为词法解析器（lexer）。

而语法分析的输入就是词法分析器输出的 Token 序列，这些序列会按照顺序被语法分析器进行解析，语法的解析过程就是将词法分析生成的 Token 按照语言定义好的文法（Grammar）自下而上或者自上而下的进行规约，每一个 Go 的源代码文件最终会被归纳成一个 SourceFile 结构：

SourceFile = PackageClause ";" { ImportDecl ";" } { TopLevelDecl ";" } .

词法分析会返回一个不包含空格、换行等字符的 Token 序列，例如：package, json, import, (, io, ), …，而语法分析会把 Token 序列转换成有意义的结构体，也就是语法树：

"json.go": SourceFile {
    PackageName: "json",
    ImportDecl: []Import{
        "io",
    },
    TopLevelDecl: ...
}

将 Token 转换成上述语法树就会使用语法解析器，语法解析的结果其实就是上面介绍过的抽象语法树（AST），每一个 AST 都对应着一个单独的 Go 语言文件，这个抽象语法树中包括当前文件属于的包名、定义的常量、结构体和函数等。

golang-files-and-ast

图 2-3 从源文件到语法树

如果在语法解析的过程中发生了任何语法错误，都会被语法解析器发现并将消息打印到标准输出上，整个编译过程也会随着错误的出现而被中止。

类型检查

当拿到一组文件的抽象语法树之后，Go 语言的编译器会对语法树中定义和使用的类型进行检查，类型检查分别会按照以下的顺序对不同类型的节点进行验证和处理：

  1. 常量、类型和函数名及类型；
  2. 变量的赋值和初始化；
  3. 函数和闭包的主体；
  4. 哈希键值对的类型；
  5. 导入函数体；
  6. 外部的声明；

通过对整颗抽象语法树的遍历，我们在每一个节点上都会对当前子树的类型进行验证，以保证当前节点上不会出现类型错误的问题，所有的类型错误和不匹配都会在这一个阶段被发现和暴露出来，结构体是否实现了某些接口也会在这一阶段被检查出来。

类型检查阶段不止会对节点的类型进行验证，还会展开和改写一些内建的函数，例如 make 关键字在这个阶段会根据子树的结构被替换成 makeslice 或者 makechan 等函数。类型检查这一过程在整个编译流程中还是非常重要的，Go 语言的很多关键字都依赖类型检查期间的展开和改写。

中间代码生成

当我们将源文件转换成了抽象语法树、对整棵树的语法进行解析并进行类型检查之后，就可以认为当前文件中的代码不存在语法错误和类型错误的问题了，Go 语言的编译器就会将输入的抽象语法树转换成中间代码。

在类型检查之后，就会通过一个名为 compileFunctions 的函数开始对整个 Go 语言项目中的全部函数进行编译，这些函数会在一个编译队列中等待几个后端工作协程的消费，这些并发执行的 Goroutine 会将所有函数对应的抽象语法树转换成中间代码。
concurrency-compiling

由于 Go 语言编译器的中间代码使用了 SSA 的特性，所以在这一阶段我们就能够分析出代码中的无用变量和片段并对代码进行优化。

Go 语言源代码的 src/cmd/compile/internal 目录中包含了很多机器码生成相关的包，不同类型的 CPU 分别使用了不同的包生成机器码，其中包括 amd64、arm、arm64、mips、mips64、ppc64、s390x、x86 和 wasm，其中比较有趣的就是 WebAssembly（Wasm）7了。

作为一种在栈虚拟机上使用的二进制指令格式，它的设计的主要目标就是在 Web 浏览器上提供一种具有高可移植性的目标语言。Go 语言的编译器既然能够生成 Wasm 格式的指令，那么就能够运行在常见的主流浏览器中。

$ GOARCH=wasm GOOS=js go build -o lib.wasm main.go

我们可以使用上述的命令将 Go 的源代码编译成能够在浏览器上运行 WebAssembly 文件，当然除了这种新兴的二进制指令格式之外，Go 语言经过编译还可以运行在几乎全部的主流机器上，不过对于除了 Linux 和 Darwin 之外的机器上兼容性上可能还是有一些问题，例如：Go Plugin 至今仍然不支持 Windows8。

supported-hardware

编译器入口

Go 语言的编译器入口在 src/cmd/compile/internal/gc/main.go 文件中，这个 600 多行的 Main 函数就是 Go 语言编译器的主程序，该函数会先获取命令行传入的参数并更新编译选项和配置，随后就会开始运行 parseFiles 函数对输入的所有文件进行词法与语法分析得到文件对应的抽象语法树：

func Main(archInit func(*Arch)) {
	...

	lines := parseFiles(flag.Args())

接下来就会分九个阶段对抽象语法树进行更新和编译，就像我们在上面介绍的，整个过程会经历类型检查、SSA 中间代码生成以及机器码生成三个部分：

  1. 检查常量、类型和函数的类型；
  2. 处理变量的赋值；
  3. 对函数的主体进行类型检查；
  4. 决定如何捕获变量；
  5. 检查内联函数的类型；
  6. 进行逃逸分析；
  7. 将闭包的主体转换成引用的捕获变量；
  8. 编译顶层函数；
  9. 检查外部依赖的声明；

对整个编译过程有一个顶层的认识之后，我们重新回到词法和语法分析后的具体流程，在这里编译器会对生成语法树中的节点执行类型检查，除了常量、类型和函数这些顶层声明之外，它还会对变量的赋值语句、函数主体等结构进行检查：

for i := 0; i < len(xtop); i++ {
	n := xtop[i]
	if op := n.Op; op != ODCL && op != OAS && op != OAS2 && (op != ODCLTYPE || !n.Left.Name.Param.Alias) {
		xtop[i] = typecheck(n, ctxStmt)
	}
}

for i := 0; i < len(xtop); i++ {
	n := xtop[i]
	if op := n.Op; op == ODCL || op == OAS || op == OAS2 || op == ODCLTYPE && n.Left.Name.Param.Alias {
		xtop[i] = typecheck(n, ctxStmt)
	}
}

类型检查会遍历传入节点的全部子节点，这个过程会对 make 等关键字进行展开和重写，在类型检查会改变语法树中的一些节点，不会生成新的变量或者语法树，这个过程的结束也意味着源代码中已经不存在语法错误和类型错误，中间代码和机器码都可以根据抽象语法树正常生成了。

	initssaconfig()

	peekitabs()

	for i := 0; i < len(xtop); i++ {
		n := xtop[i]
		if n.Op == ODCLFUNC {
			funccompile(n)
		}
	}

	compileFunctions()

	for i, n := range externdcl {
		if n.Op == ONAME {
			externdcl[i] = typecheck(externdcl[i], ctxExpr)
		}
	}

	checkMapKeys()
}

在主程序运行的最后，会将顶层的函数编译成中间代码并根据目标的 CPU 架构生成机器码，不过在这一阶段也有可能会再次对外部依赖进行类型检查以验证正确性。

参考

  1. 抽象语法树 https://en.wikipedia.org/wiki/Abstract_syntax_tree ↩︎

  2. 静态单赋值 https://en.wikipedia.org/wiki/Static_single_assignment_form ↩︎

  3. 编译器一般分为前端和后端，其中前端的主要工作是将源代码翻译成编程语言无关的中间表示，而后端主要负责目标代码的优化和生成。 ↩︎

  4. 指令集架构是计算机的抽象模型，也被称作架构或者计算架架构 https://en.wikipedia.org/wiki/Instruction_set_architecture ↩︎

  5. SourceFile 表示一个 Go 语言源文件，它由 package 定义、多个 import 语句以及顶层的声明组成 https://golang.org/ref/spec#Source_file_organization ↩︎

  6. 关于 Go 语言文法的是不是 LALR(1) 的讨论 https://groups.google.com/forum/#!msg/golang-nuts/jVjbH2-emMQ/UdZlSNhd3DwJ

    LALR 的全称是 Look-Ahead LR，大多数的通用编程语言都会使用 LALR 的文法 https://en.wikipedia.org/wiki/LALR_parser ↩︎

  7. WebAssembly 是基于栈的虚拟机的二进制指令，简称 Wasm https://webassembly.org/ ↩︎

  8. plugin: add Windows support #19282 https://github.com/golang/go/issues/19282 ↩︎