Links

5.3 数据结构

5.3.1 IR Tree 简介

既然在语法分析阶段已经生成了 AST, 为什么这里还需要另外构造一颗 IR Tree 呢?这是一个值得思考的问题!
语法分析阶段生成的 AST 在结构上与语言的文法相对应,其存在的主要价值是用来让编译器检查源程序是否符合文法结构,并做一定的语义分析,例如类型检查。但对于编译器的一些后续操作,例如代码优化、翻译时,这种结构便不是特别友好,例如对于代码 make(chan string)make(map[string]string) 而言,在 AST 中都对应一个 syntax.CallExpr 节点,然而程序在运行时需要调用不同的内置函数来完成对应的操作(分别是 makechan()makemap() ),因此编译器在翻译代码时最好能够直接知道这些信息,但这通过当前 AST 是做不到的(只能继续分析 syntax.CallExpr 的子节点来提取该信息)。我们可以这样认为:AST 中每个节点只反映了该程序片段的性质(上例中两个节点的性质都是方法调用),而编译器的很多后续操作需要知道更细节的信息,例如当前节点涉及到的具体操作(前者是 makechan, 而后者是 makemap )。因此构建一种信息更加丰富的数据结构是有必要的,IR Tree 便是这样的一个数据结构。

5.3.2 IR Tree Node

IR Tree 由 AST 转换而来,对于每一类 AST 节点,几乎都有一个 IR Tree 的节点类型与之对应。例如上文提到的 syntax.CallExpr, 其在语法分析阶段定义如下:
// file: cmd/compile/internal/syntax/nodes.go
type CallExpr struct {
Fun Expr
ArgList []Expr // nil means no arguments
HasDots bool // last argument is followed by ...
expr
}
而在 IR Tree 中与之对应的结构体如下:
// file: cmd/compile/internal/ir/expr.go
type CallExpr struct {
miniExpr
origNode
X Node
Args Nodes
KeepAlive []*Name // vars to be kept alive until call returns
IsDDD bool
Use CallUse
NoInline bool
PreserveClosure bool // disable directClosureCall for this call
}
所有IR Tree 节点都实现了 Node 接口:
// file: cmd/compile/internal/ir/node.go
type Node interface {
// 格式化
Format(s fmt.State, verb rune)
// 源码位置信息
Pos() src.XPos
SetPos(x src.XPos)
// 拷贝当前节点,在函数内联处理时会用到
copy() Node
// 对当前节点的子节点进行遍历并处理每个子节点
doChildren(func(Node) bool) bool
editChildren(func(Node) Node)
// 节点的操作类型,后续有介绍
Op() Op
// 用来以一定顺序遍历本节点的子节点
Init() Nodes
// 类型信息,types.Type 是旧版本类型检查器所定义的类型,在生成 IR Tree 时会将 types2.Type 转换为该类型
Type() *types.Type
SetType(t *types.Type)
// 用来表示所有命名对象的结构,后续会有介绍
Name() *Name
// 符号对象
Sym() *types.Sym
// 如果当前 Node 是常量,用来保存常量值
Val() constant.Value
SetVal(v constant.Value)
// 用来逃逸分析
Esc() uint16
SetEsc(x uint16)
Diag() bool
SetDiag(x bool)
// Typecheck values:
// 0 means the node is not typechecked
// 1 means the node is completely typechecked
// 2 means typechecking of the node is in progress
// 3 means the node has its type from types2, but may need transformation
Typecheck() uint8
SetTypecheck(x uint8)
NonNil() bool
MarkNonNil()
}
Node 是个大杂烩接口,各类节点按需实现各方法,并不是所有的节点都需要用到所有的方法。各种类型的节点主要定义在下列文件中:
  • cmd/compile/internal/ir/type.go
  • cmd/compile/internal/ir/expr.go
  • cmd/compile/internal/ir/stmt.go
  • cmd/compile/internal/ir/func.go
  • cmd/compile/internal/ir/name.go
由于 IR Tree 是 AST 的一种变体,二者刻画了同一个程序结构,所以这里就不再一一介绍 IR Tree 节点了。但由于 IR Tree 中的节点更加具体,为了支持编译器后续各个阶段的处理,某些节点内包含的信息更加丰富全面,我们重点介绍一下 NameFunc 这两个节点。

5.3.3 Name

节点类型 Name 用来在 IR Tree 中表示程序中的命名对象,源代码中所有有名字的对象都会对应一个 Name 节点,命名对象包括全局函数申明、全局类型申明、全局变量、局部变量、函数参数、甚至函数返回值等。
程序运行时使用的内存被划分为两块:栈(Stack)与堆(Heap)。栈在函数调用时自动分配,在函数执行结束时自动释放,其生命周期与函数调用一致,栈内的数据仅对当前函数可见;而堆是共享的内存块,堆的分配与释放需要单独进行管理,负责回收堆内存的程序模块叫着GC(Garbage Collector)。所以对于函数的局部变量,如果函数执行完成后其再也不会被访问,则为其分配栈上的内存更加简单,可以减轻 GC 的压力;而如果其生命周期长于函数的生命周期,则必须将其分配到堆上,由 GC 决定何时回收。
Go 提供了自动管理内存的功能,对于每个局部变量,编译器都会对其进行分析,然后决定为其分配栈上的内存还是堆上的内存。这个过程叫着逃逸分析(Escape Analysis),后续会有专门的章节进行介绍,而局部变量所对应的 Name 节点会记录逃逸分析的结果。
Name 节点是程序中非常重要的部分,符号解析、内存分配、函数调用等都与该节点相关,该结构定义在文件 cmd/compile/internal/ir/name.go 中,其包含的属性覆盖了编译器后续处理时需要的所有信息:
type Name struct {
miniExpr
BuiltinOp Op // 如果是内置函数,则对应内置函数的 Op 常量
Class Class // uint8
pragma PragmaFlag // int16
flags bitset16
sym *types.Sym
Func *Func // TODO(austin): nil for I.M, eqFor, hashfor, and hashmem
Offset_ int64
val constant.Value
Opt interface{} // 用于逃逸分析
Embed *[]Embed // list of embedded files, for ONAME var
PkgName *PkgName // real package for import . names
// For a local variable (not param) or extern, the initializing assignment (OAS or OAS2).
// For a closure var, the ONAME node of the outer captured variable
Defn Node
// The function, method, or closure in which local variable or param is declared.
Curfn *Func
Ntype Ntype
Heapaddr *Name // temp holding heap address of param
Innermost *Name
Outer *Name
}

5.3.4 Func

函数是编译器处理的重点对象,说其是最重要的对象也不为过,像逃逸分析、闭包处理、函数内联、以及代码编译的处理对象都是函数。因此该结构体内是 IR Tree 中最复杂的,包含很多属性。代码中的函数、闭包、方法都使用 Func 来表示,其定义在 cmd/compiler/internal/ir/func.go 中:
type Func struct {
miniNode
Body Nodes // 函数体
Iota int64
Nname *Name // 函数名对应的 Name 节点
OClosure *ClosureExpr // OCLOSURE node
Shortname *types.Sym
// Extra entry code for the function. For example, allocate and initialize
// memory for escaping parameters.
Enter Nodes
Exit Nodes
// 保存函数体内的绑定变量(Bound Variable),即在函数内声明的局部变量,包括参数及返回值,后面逃逸分析时会用到
Dcl []*Name
// 保存函数体内的自由变量(Free Variable),即该变量在当前函数体内使用,但在更外层的函数体内声明
// 例如:
// var base int
// func makeAdder(i int)func(int)int {
// return func (j int) int {
// return i + j + base
// }
// }
// 对于作为返回值的函数而言,j 是 Bound Variable, i 是 Free Variable. 需要注意的是全局变量不属于 Free Variable, 即该例中的 base 不会保存在该属性中
ClosureVars []*Name
// 保存函数内的闭包,在编译阶段填充。见 walk.Walk() 方法
Closures []*Func
Parents []ScopeID
// Marks records scope boundary changes.
Marks []Mark
FieldTrack map[*obj.LSym]struct{}
DebugInfo interface{}
LSym *obj.LSym // Linker object in this function's native ABI (Func.ABI)
Inl *Inline // 保存能够内联的函数体,函数内联的章节有详细介绍
Closgen int32
Label int32 // largest auto-generated label in this function
Endlineno src.XPos
WBPos src.XPos // position of first write barrier; see SetWBPos
Pragma PragmaFlag // go:xxx function annotations
flags bitset16
// ABI 相关字段,ABI 章节有详细介绍
ABI obj.ABI
ABIRefs obj.ABISet
NumDefers int32 // number of defer calls in the function
NumReturns int32 // number of explicit returns in the function
NWBRCalls *[]SymAndPos
}
函数节点是编译器后续处理的重要对象,该结构体内包含的属性也贯穿整个编译过程,后续章节都会围绕着该节点展开。

5.3.5 Node Op

前文中提到 IR Tree 的节点会体现具体操作, Node 接口的方法 Op() Op 反映了这一点。在文件 cmd/compile/internal/ir/node.go 中编译器定义了差不多 200 种具体操作,这里罗列其中一部分:
type Op uint8
const (
OXXX Op = iota
// names
ONAME // var or func name
// Unnamed arg or return value: f(int, string) (int, error) { etc }
// Also used for a qualified package identifier that hasn't been resolved yet.
ONONAME
OTYPE // type name
OPACK // import
OLITERAL // literal
ONIL // nil
// expressions
OADD // Left + Right
OSUB // Left - Right
OADDSTR // +{List} (string addition, list elements are strings)
OADDR // &Left
OANDAND // Left && Right
OAPPEND // append(List); after walk, Left may contain elem type descriptor
OBYTES2STR // Type(Left) (Type is string, Left is a []byte)
OOROR // Left || Right
OPANIC // panic(Left)
OPRINT // print(List)
OPAREN // (Left)
OSEND // Left <- Right
OSLICE // Left[List[0] : List[1]] (Left is untypechecked or slice)
)
Op 所定义的操作非常详细,各个操作符、内置函数、关键字都有对应的操作,每个 IR Tree 的节点都包含该字段,该字段也是编译器很多后续处理的基础。

5.3.6 types.Sym

types.Sym 用来表示包中的一个符号对象,其定义在 cmd/compile/internal/types/sym.go 中,内容如下:
type Sym struct {
Linkname string // link name
Pkg *Pkg
Name string // object name
// saved and restored by Pushdcl/Popdcl
Def Object // definition: ONAME OTYPE OPACK or OLITERAL
Block int32 // blocknumber to catch redeclaration
Lastlineno src.XPos // last declaration for diagnostic
flags bitset8
}
编译器做符号解析时,得到的结果就是该类型的实例,属性 (Pkg, Name) 的组合唯一确定一个符号对象。

5.3.7 types.Pkg

types.Pkg 用来封装通过 import 语句引入的 package 的内容,其内容如下:
// file: cmd/compiler/internal/types/pkg.go
type Pkg struct {
Path string // string literal used in import statement, e.g. "runtime/internal/sys"
Name string // package name, e.g. "sys"
Prefix string // escaped path for use in symbol table
Syms map[string]*Sym
Pathsym *obj.LSym
Height int
Direct bool // imported directly
}
属性 Syms 存放着该包的所有 Export 的符号对象。

5.3.8 types.Type

types.Type 是老版本类型检查器中用来表示类型的数据结构,当前编译器的所有后续操作依然是基于该类型进行的,所以在 IR Tree 的构建过程中,需要将 types2 中定义的类型转换成对应的 types.Type, 该结构体定义在文件 cmd/compile/internal/noder/types.go 中,其中有一些属性我们特别提出来认识一下:
type Type struct {
// 省略掉其他所有字段
Width int64 // 该类型所占用的字节大小
Align uint8 // 该类型的地址对齐要求
}
在编译阶段,编译器需要计算出每种类型所占作用的内存大小,以及地址对齐的要求。关于 Go 类型大小及地址对齐的计算方式请参见 ABI Specification