[读书笔记]编译器_Go语言底层原理剖析第一章

type

Post

status

Published

date

Apr 10, 2022

slug

go-bottom-up-book-note-1

summary

Go语言底层原理剖析 第一章读书笔记

第一章 Go编译器

经典的三阶段编译器分为编译器前端, 优化器和编译器后端, 职能分别为解析, 优化和生成

Go语言编译器一般缩写为 gc (小写), 而垃圾回收缩写为 GC (大写) gc相关代码主要位于 src/cmd/compile/internal 目录下

词法解析

Go源文件的文本会被符号(token)化, 比如变量名变成_Name, +变成_IncOp

这些token定义在syntax/tokens.go文件中, 均为通过itoa定义的const常量简单摘录部分源码如下:


const (
	 _ token = iota
	 _EOF // EOF

	 // names and literals
	 _Name // name
	 _Literal // literal
	...

以语句a := b + c(12)为例, 其词法解析如下:

语法解析

使用自上而下的递归下降算法对符号化后的Go文件进行解析, 核心算法位于syntax/nodes.go和syntax/parser.go中

简单摘录位于nodes.go中的赋值声明AssignStmt的结构体源码如下:


AssignStmt struct {
	Op       Operator // 0 means no operation
	Lhs, Rhs Expr     // Rhs == ImplicitOne means Lhs++ (Op == Add) or Lhs-- (Op == Sub)
	simpleStmt
}

语法解析丢弃了不重要的标识符(如括号(等), 将语义存储到了对应的结构体中 而这些结构体是有对应的层次结构的, 这是构建抽象语法树的基础

依然以语句a := b + c(12)为例, 其语法解析转换为AssignStmt结构体如下图, 可以看到两个括号是被省去了的, 并且语句被解析成树状结构

抽象语法树构建

抽象语法树简称AST, 任何import, type, const, func声明都是AST的一个根节点

每个节点都包含了当前节点树形的Op字段, 定义在gc/syntax.go中, 类似词法解析中的token, 也是用itoa定义的, 摘录部分定义如下:


const (
	OXXX Op = iota

	// names
	ONAME    // var or func name
	ONONAME  // unnamed arg or return value: f(int, string) (int, error) { etc }
	OTYPE    // type name
	OPACK    // import
	OLITERAL // literal
	...

每个Op字段都包含了语义信息, 比如OAS代表的语义为Left := Right

替换上一节中结构体图示得到语句a := b + c(12)的抽象语法树如下:

类型检查

这个阶段中, gc会遍历节点树, 决定节点的类型, 其中既有代码中显式指定的类型, 也有未直接声明的(比如:=) 会对某些类型做特别的检查(比如"数组索引是不是正整数")

除了上述检查外, 还有一些其它的工作: 计算编译时常量, 将标识符与声明绑定 我想, 这也是为了进行完整的类型检查, 毕竟这些工作不完成, 就意味着有些类型无法确定

变量捕获

主要针对闭包场景的优化, 确定闭包函数中引用的闭包外的变量是采用值传递还是指针传递

函数内联

将较小的函数直接组合进调用者, 是现代编译器优化的一种核心技术, 可以减少函数调用的开销过于复杂或含for, range, go, select等语句的函数不会被内联

逃逸分析

决定变量内存应该分配在栈区还是堆区, 总的来说, gc会尽量把变量放在栈区

针对指向栈上对象的指针分配遵循以下两个原则:

不能被存储到堆中

不能超过该栈上对象的生命周期

gc会对抽象语法树进行静态数据流分析, 构建带权重的有向图, 权重可表明该变量引用和解引用的数量有向图可能成环, 此时会采用Bellman Ford算法遍历查找权重小于0的节点

闭包重写

仍然是针对闭包场景的优化, 对以下两种场景分别进行优化:

闭包定义后被立即调用

将闭包转换为普通函数的调用形式, 相当于一个普通的外部函数, 其调用嵌入到原闭包函数的位置

闭包定义后不被立即调用

创建闭包对象

值传递的小变量通过在函数体内创建局部变量的形式产生
指针变量or值传递的大变量则以指针类型产生

遍历函数

识别出声明但未使用的变量在此之前会对某些表达式or语句进行重新排序(这也是为了遍历)

SSA生成

"其实就是将def-use换成use-def方便做代码优化"

SSA, 静态单赋值, 是一种中间代码特性, 用于确保每个变量只被赋值一次

同一个变量的多次赋值, 每次赋值都会产生"替身", 用不到的"替身"是无效的比如下列代码:


a = 0
a = 1
b = a

可被转化为:


a1 = 0
a2 = 1
b1 = a2

可以看到, a1 = 0是无效的, 可以被清除掉

机器码生成---汇编器

gc调用与特定指令集有关的汇编器生成obj文件, 以作为后续链接器的输入

特定指令集是在SSA阶段就决定了的, SSA阶段最终生成的是与特定指令集有关的指令和寄存器分配方式

机器码生成---链接

将编写的程序与外部程序组合在一起, 生成可执行文件, 分为两种方式:

静态链接

类似值传递, 占用空间大, 运行速度快, 可移植
发生在编译时的最后一步, 亦即被链接器执行

动态链接

类似指针传递, 存储的是动态链接库的位置, 在运行时调用
发生在程序加载到内存时

gc默认使用静态链接

总结

将上述步骤按照三阶段编译器的分类如下:

编译器前端

词法解析
语法解析
抽象语法树构建
类型检查

优化器

变量捕获
函数内联
逃逸分析
闭包重写
遍历函数
SSA生成

编译器后端

机器码生成---汇编器
机器码生成---链接