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 中的节点更加具体，为了支持编译器后续各个阶段的处理，某些节点内包含的信息更加丰富全面，我们重点介绍一下 Name 与 Func 这两个节点。

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