Golang

Golang 21_Golang编译原理及编译过程

一、Golang 编译器简介

1.1 Golang 编译器简介

Golang 是一门需要编译才能运行的编程语言，也就是说代码在运行之前需要通过编译器编辑生成二进制可执行文件（机器码）才能在目标机器上运行。

Go语言的编译器和工具链是用Go语言编写的，而不是C++，Go语言的编译器将Go源代码编译为机器码，并将其打包成可执行文件或库。

Golang编译器 的实现是基于LLVM进行的。这个开源的编译器基础设施项目，它提供了一个跨平台的编译框架，可以将中间代码转换为目标纯汇编或目标机器代码。不仅仅是Golang编译器，众多编译器都在使用LLVM作为编译后端，如Swift、Rust等。

Golang编译器将编写的代码翻译成机器码的过程可以分为四个主要的阶段：词法分析、语法分析、中间代码生成 和 代码优化。

词法分析：词法分析器是将源代码分成一个个的token（标记）。一个合法的token就是最小有效的代码单元，它可以是一个标识符、关键字、操作符、分隔符等等。

语法分析：语法分析器按照Golang的文法规则将token集合转化为一颗抽象语法树。然后，进行语义分析，去除无用的语法单元（如注释、空格等）和进行类型检查。

中间代码生成：语法树再经过中间代码生成器的处理，将高级语言转化为低级语言。这一步通常会生成一组较为朴素的、没有被优化的中间代码。

代码优化：在生成的一组较为朴素的中间代码上，进行代码优化。目前的编译器大多有三种优化级别。优化级别越高，生成的代码越高效，但是越耗费时间。

最终，编译器会根据优化后的中间代码，生成目标机器的可执行程序。

二、Go 语言编译基础概念介绍

2.1 抽象语法树

抽象语法树（Abstract Syntax Tree、AST） 是源代码语法结构的一种抽象表示，它用树状的方式表示编程语言的语法结构。抽象语法树（AST） 中的每一个节点都表示源代码中的一个元素，每一棵子树都表示一个语法元素，以表达式 2 * 3 + 7 为例，编译器的语法分析阶段会生成如下图所示的抽象语法树： 作为编译器常用的数据结构，抽象语法树（AST） 抹去了源代码中不重要的一些字符 —— 空格、分号 或者 括号 等等；编译器在执行完语法分析之后会输出一个抽象语法树，这个抽象语法树会辅助编译器进行语义分析，我们可以用它来确定语法正确的程序是否存在一些类型不匹配的问题。

2.2 静态单赋值

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

1
2
3

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

经过简单的分析，我们就能够发现上述的代码第一行的赋值语句 x := 1 不会起到任何作用。下面是具有 SSA 特性的中间代码:

1
2
3

x_1 := 1
x_2 := 2
y_1 := x_2

我们可以清晰地发现变量 y_1 和 x_1 是没有任何关系的，所以在机器码生成时就可以省去 x := 1 的赋值，通过减少需要执行的指令优化这段代码。

因为 SSA 的主要作用是对代码进行优化，所以它是编译器后端的一部分；当然代码编译领域除了 SSA 还有很多中间代码的优化方法，编译器生成代码的优化也是一个古老并且复杂的领域，这里就不会展开介绍了。

SSA的特性优化点：

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

2.3 指令集

很多开发者都会遇到在本地开发环境编译和运行正常的代码，在生产环境却无法正常工作，这种问题背后会有多种原因，而不同机器使用的不同指令集可能是原因之一。

x86 是目前比较常见的指令集，除了 x86 之外，还有 arm 等指令集，苹果最新 Macbook 的自研芯片就使用了 arm 指令集，不同的处理器使用了不同的架构和机器语言，所以很多编程语言为了在不同的机器上运行需要将源代码根据架构翻译成不同的机器代码。

复杂指令集计算机（CISC） 和 精简指令集计算机（RISC） 是两种遵循不同设计理念的指令集，从名字我们就可以推测出这两种指令集的区别： 复杂指令集：通过增加指令的类型减少需要执行的指令数(x86)； 精简指令集：使用更少的指令类型完成目标的计算任务(arm)；

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

三、Golang编译原理

3.1 Golang编译简介

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

编译原理的核心过程：

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

Tips: 编译器入口文件 src/cmd/compile/internal/gc/main.go

3.2 词法、语法分析 和 AST转换

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

lex3 是用于生成词法分析器的工具，lex 生成的代码能够将一个文件中的字符分解成 Token 序列，很多语言在设计早期都会使用它快速设计出原型，lexer 通过正则匹配的方式将机器原本很难理解的字符串进行分解成很多的 Token。

入口文件（src/cmd/compile/internal/syntax/scanner.go ） token类型：（src/cmd/compile/internal/syntax/tokens.go ）

词法分析会返回一个不包含空格、换行等字符的 Token 序列，例如：

1

package, json, import, (, io, ), …，

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

1

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

语法分析会把 Token 序列转换成有意义的结构体，即抽象语法树（AST）：

1
2
3
4
5
6
7

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

Token 序列 到上述抽象语法树（AST）的转换过程会用到 语法解析器（go用的是LALR），每一个 AST 都对应着一个单独的 Go 语言文件，这个抽象语法树中包括当前文件属于的包名、定义的常量、结构体和函数等。

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

3.3 类型检查

1、 静态类型检查 静态类型检查是基于对源代码的分析来确定运行程序类型安全的过程，如果我们的代码能够通过静态类型检查，那么当前程序在一定程度上就满足了类型安全的要求，它也可以被看作是一种代码优化的方式，能够减少程序在运行时的类型检查。

2、动态类型检查 动态类型检查就是在运行时确定程序类型安全的过程，这个过程需要编程语言在编译时为所有的对象加入类型标签和信息，运行时就可以使用这些存储的类型信息来实现动态派发、向下转型、反射以及其他特性。

3、golang 类型检查 Go 语言的编译器不仅使用静态类型检查来保证程序运行的类型安全，还会在编程期引入类型信息，让工程师能够使用反射来判断参数和变量的类型。

当拿到一组文件的抽象语法树之后，Go 语言的编译器会对语法树中定义和使用的类型进行检查，类型检查会按照以下的顺序分别验证和处理不同类型的节点： 1）常量、类型和函数名及类型； 2）变量的赋值和初始化； 3）函数和闭包的主体； 4）哈希键值对的类型； 5）导入函数体； 6）外部的声明；

通过对整棵抽象语法树的遍历，我们在每个节点上都会对当前子树的类型进行验证，以保证节点不存在类型错误，所有的类型错误和不匹配都会在这一个阶段被暴露出来，其中包括：结构体对接口的实现。

类型检查阶段不止会对节点的类型进行验证，还会展开和改写一些内建的函数，例如 make 关键字在这个阶段会根据子树的结构被替换成 runtime.makeslice 或者 runtime.makechan等函数。

在类型检查阶段对 make 进行改写： 类型检查这一过程在整个编译流程中还是非常重要的，Go 语言的很多关键字都依赖类型检查期间的展开和改写。

3.4 中间代码生成

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

在类型检查之后，编译器会通过 cmd/compile/internal/gc.compileFunctions 编译整个 Go 语言项目中的全部函数，这些函数会在一个编译队列中等待几个 Goroutine 的消费，并发执行的 Goroutine 会将所有函数对应的抽象语法树转换成中间代码。

并发编译过程：

1） SSA配置初始化 SSA 配置的初始化过程其实就是做中间代码生成之前的准备工作，在这个过程中我们会缓存可能用到的类型指针、初始化 SSA 配置和一些之后会调用的运行时函数，还有 CPU 架构设置用于生成中间代码和机器码的函数，当前编译器使用的指针、寄存器大小、可用寄存器列表、掩码等编译选项。

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

文件入口： initssaconfig (/src/cmd/compile/internal/gc/ssa.go)开始分析配置初始化的过程。

2） 遍历和替换 在生成中间代码之前，我们还需要对抽象语法树中节点的一些元素进行替换（使用 walk 系列函数处理）：

1
2
3
4
5
6
7
8
9

func walk(fn *Node)
func walkappend(n *Node, init *Nodes, dst *Node) *Node
...
func walkrange(n *Node) *Node
func walkselect(sel *Node)
func walkselectcases(cases *Nodes) []*Node
func walkstmt(n *Node) *Node
func walkstmtlist(s []*Node)
func walkswitch(sw *Node)

3） SSA代码生成 经过 walk 系列函数的处理之后，AST 的抽象语法树就不再会改变了，Go 语言的编译器会使用 compileSSA 函数（/src/cmd/compile/internal/gc/pgen.go**）将抽象语法树转换成中间代码，我们可以先看一下该函数的简要实现：

1
2
3
4
5
6
7

// #L297-L326
func compileSSA(fn *Node, worker int) {
    f := buildssa(fn, worker)
    pp := newProgs(fn, worker)
    genssa(f, pp)
    pp.Flush()
}

buildssa 就是用来具有 SSA 特性的中间代码的函数，我们可以使用命令行工具来观察当前中间代码的生成过程，假设我们有以下的 Go 语言源代码，其中只包含一个非常简单的 hello 函数：

1
2
3
4
5

package hello
func hello(a int) int {
    c := a + 2
    return c
}

可以使用 GOSSAFUNC 环境变量构建上述代码并获取从源代码到最终的中间代码经历的几十次迭代，所有的数据都被存储到了 ssa.html 文件中：

1
2
3

$ GOSSAFUNC=hello go build hello.go
# command-line-arguments
dumped SSA to ./ssa.html

中间代码的生成过程其实就是从 AST 抽象语法树到 SSA 中间代码的转换过程，在这期间会对语法树中的关键字在进行一次改写，改写后的语法树会经过多轮处理转变成最后的 SSA 中间代码.

3.5 机器码生成

机器码的生成过程其实就是对 SSA 中间代码的降级（lower）过程，在 SSA 中间代码降级的过程中，编译器将一些值重写成了目标 CPU 架构的特定值，降级的过程处理了所有机器特定的重写规则并对代码进行了一定程度的优化。

Go 语言源代码的 src/cmd/compile/internal 目录中包含了很多机器码生成相关的包，不同类型的 CPU 分别使用了不同的包生成机器码，其中包括 amd64、arm、arm64、mips、mips64、ppc64、s390x、x86 和 wasm： Go 语言支持的架构：

其中比较有趣的就是 WebAssembly（Wasm）了。

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

我们可以使用 $ GOARCH=wasm GOOS=js go build -o lib.wasm main.go 命令将 Go 的源代码编译成能够在浏览器上运行 WebAssembly 文件，当然除了这种新兴的二进制指令格式之外，Go 语言经过编译还可以运行在几乎全部的主流机器上。

交叉编译

1
2
3
4
5
6
7

# Mac 下编译 Linux 和 Windows 64位可执行程序
CGO_ENABLED=0 GOOS=linux GOARCH=amd64 go build main.go
CGO_ENABLED=0 GOOS=windows GOARCH=amd64 go build main.go
# Linux 下编译 Mac 和 Windows 64位可执行程序
CGO_ENABLED=0 GOOS=darwin GOARCH=amd64 go build main.go
CGO_ENABLED=0 GOOS=windows GOARCH=amd64 go build main.go
# 交叉编译不支持 CGO 所以要禁用它

机器码的生成 在 Go 的编译器中主要由两部分协同工作，其中一部分是负责 SSA 中间代码降级和根据目标架构进行特定处理的 src/cmd/compile/internal/ssa 包，另一部分是负责生成机器码的 src/cmd/internal/obj：

  • src/cmd/compile/internal/ssa 主要负责对 SSA 中间代码进行降级、执行架构特定的优化和重写并生成 obj.Prog 指令；
  • src/cmd/internal/obj 作为一个汇编器会将这些指令最终转换成机器码完成这次的编译

通过命令输出汇编结果:

1

GOOS=linux GOARCH=amd64 go tool compile -S hello.go

3.6 编译器入口

Go 语言的编译器入口在src/cmd/compile/internal/gc/main.go 文件中。该函数会先获取命令行传入的参数并更新编译选项和配置，随后对输入的文件进行词法与语法分析得到对应的抽象语法树：

1
2
3
4

func Main(archInit func(*ssagen.ArchInfo)) {
     ...
     // Parse and typecheck input.
     noder.LoadPackage(flag.Args())

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

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

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

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

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

四、golang 编译器总结

参考文献： golang 编译原理 ：https://draveness.me/golang/docs/part1-prerequisite/ch02-compile/golang-compile-intro/ 走进golang编译原理：https://segmentfault.com/a/1190000020996545

Go Golang Go语言
Licensed under CC BY-NC-SA 4.0
最后更新于 2022-08-23 16:16 CST