# 5.3 数据结构

## 5.3.1 IR Tree 简介 <a href="#org02e11eb" id="org02e11eb"></a>

既然在语法分析阶段已经生成了 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 <a href="#orge616fec" id="orge616fec"></a>

&#x20;IR Tree 由 AST 转换而来，对于每一类 AST 节点，几乎都有一个 IR Tree 的节点类型与之对应。例如上文提到的 `syntax.CallExpr`, 其在语法分析阶段定义如下：

```go
// 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 中与之对应的结构体如下：

```go
// 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` 接口：

```go
// 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 <a href="#org40f6b70" id="org40f6b70"></a>

节点类型 `Name` 用来在 IR Tree 中表示程序中的命名对象，源代码中所有有名字的对象都会对应一个 `Name` 节点，命名对象包括全局函数申明、全局类型申明、全局变量、局部变量、函数参数、甚至函数返回值等。

程序运行时使用的内存被划分为两块：栈（Stack）与堆（Heap）。栈在函数调用时自动分配，在函数执行结束时自动释放，其生命周期与函数调用一致，栈内的数据仅对当前函数可见；而堆是共享的内存块，堆的分配与释放需要单独进行管理，负责回收堆内存的程序模块叫着GC(Garbage Collector)。所以对于函数的局部变量，如果函数执行完成后其再也不会被访问，则为其分配栈上的内存更加简单，可以减轻 GC 的压力；而如果其生命周期长于函数的生命周期，则必须将其分配到堆上，由 GC 决定何时回收。

Go 提供了自动管理内存的功能，对于每个局部变量，编译器都会对其进行分析，然后决定为其分配栈上的内存还是堆上的内存。这个过程叫着逃逸分析（Escape Analysis），后续会有专门的章节进行介绍，而局部变量所对应的 `Name` 节点会记录逃逸分析的结果。

`Name` 节点是程序中非常重要的部分，符号解析、内存分配、函数调用等都与该节点相关，该结构定义在文件 `cmd/compile/internal/ir/name.go` 中，其包含的属性覆盖了编译器后续处理时需要的所有信息：

```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 <a href="#orgd513060" id="orgd513060"></a>

函数是编译器处理的重点对象，说其是最重要的对象也不为过，像逃逸分析、闭包处理、函数内联、以及代码编译的处理对象都是函数。因此该结构体内是 IR Tree 中最复杂的，包含很多属性。代码中的函数、闭包、方法都使用 `Func` 来表示，其定义在 `cmd/compiler/internal/ir/func.go` 中：

```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 <a href="#org273d76f" id="org273d76f"></a>

前文中提到 IR Tree 的节点会体现具体操作， `Node` 接口的方法 `Op() Op` 反映了这一点。在文件 `cmd/compile/internal/ir/node.go` 中编译器定义了差不多 200 种具体操作，这里罗列其中一部分：

```go
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 <a href="#org031bb5d" id="org031bb5d"></a>

`types.Sym` 用来表示包中的一个符号对象，其定义在 `cmd/compile/internal/types/sym.go` 中，内容如下：

```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 <a href="#org2f8fd01" id="org2f8fd01"></a>

`types.Pkg` 用来封装通过 import 语句引入的 package 的内容，其内容如下：

```go
// 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 <a href="#org9598c27" id="org9598c27"></a>

`types.Type` 是老版本类型检查器中用来表示类型的数据结构，当前编译器的所有后续操作依然是基于该类型进行的，所以在 IR Tree 的构建过程中，需要将 types2 中定义的类型转换成对应的 types.Type, 该结构体定义在文件 `cmd/compile/internal/noder/types.go` 中，其中有一些属性我们特别提出来认识一下：

```go
type Type struct {
    // 省略掉其他所有字段
    Width int64 // 该类型所占用的字节大小
    Align uint8 // 该类型的地址对齐要求
}
```

在编译阶段，编译器需要计算出每种类型所占作用的内存大小，以及地址对齐的要求。关于 Go 类型大小及地址对齐的计算方式请参见 [ABI Specification](https://go.googlesource.com/go/+/refs/heads/dev.regabi/src/cmd/compile/internal-abi.md#memory-layout)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://gocompiler.shizhz.me/golang-bian-yi-qi-ir-tree/3.-shu-ju-jie-gou.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.