Go 程序是如何编译成目标机器码的

今天我们一起来研究 Go 1.11 的编译器,以及它将 Go 程序代码编译成可执行文件的过程。以便了解我们日常使用的工具是如何工作的。
本文还会带你了解 Go 程序为什么这么快,以及编译器在这中间起到了什么作用。

首先,编译器的三个阶段:

  1. 逐行扫描源代码,将之转换为一系列的 token,交给 parser 解析。
  2. parser,它将一系列 token 转换为 AST(抽象语法树),用于下一步生成代码。
  3. 最后一步,代码生成,会利用上一步生成的 AST 并根据目标机器平台的不同,生成目标机器码。

注意:下面使用的代码包(go/scannergo/parsergo/tokengo/ast)主要是让我们可以方便地对 Go 代码进行解析和生成,做出更有趣的事情。但是 Go 本身的编译器并不是用这些代码包实现的。

扫描代码,进行词法分析

任何编译器的第一步都是将源代码文本分解成 token,由扫描程序(也称为词法分析器)完成。token 可以是关键字,字符串,变量名,函数名等等。每一个有效的词都由 token 表示。
在 Go 中,我们写在代码上的 "package""main""func" 这些都是 token

token 由代码中的位置,类型和原始文本组成。我们可以使用 go/scanner 和 go/token 包在 Go 程序中自己执行扫描程序。这意味着我们可以像编译器那样扫描检视自己的代码。
下面,我们将通过一个打印 Hello World 的示例来展示 token

package main import ( "fmt" "go/scanner" "go/token" ) func main() {
    src := []byte(`
package main

import "fmt"

func main() {
    fmt.Println("Hello, world!")
}
`) var s scanner.Scanner
    fset := token.NewFileSet()
    file := fset.AddFile("", fset.Base(), len(src))
    s.Init(file, src, nil, 0) for {
        pos, tok, lit := s.Scan()
        fmt.Printf("%-6s%-8s%q\n", fset.Position(pos), tok, lit) if tok == token.EOF { break }
    }
} 

首先通过源代码字符串创建 token 集合并初始化 scan.Scanner,它将逐行扫描我们的源代码。
接下来循环调用 Scan() 并打印每个 token 的位置,类型和文本字符串,直到遇到文件结束(EOF)标记。

输出:

2:1 package "package" 2:9 IDENT "main" 2:13 ; "\n" 4:1 import "import" 4:8 STRING "\"fmt\"" 4:13 ; "\n" 6:1 func "func" 6:6 IDENT "main" 6:10 ( "" 6:11 ) "" 6:13 { "" 7:2 IDENT "fmt" 7:5 . "" 7:6 IDENT "Println" 7:13 ( "" 7:14 STRING "\"Hello, world!\"" 7:29 ) "" 7:30 ; "\n" 8:1 } "" 8:2 ; "\n" 8:3 EOF ""

以第一行为例分析这个输出,第一列 2:1 表示扫描到了源代码第二行第一个字符,第二列 package 表示 token 是 package,第三列 "package" 表示源代码文本。
我们可以看到在 Scanner 执行过程中将 \n 换行符标记成了 ; 分号,像在 C 语言中是用分号表示一行结束的。这就解释了为什么 Go 不需要分号:它们是在词法分析阶段由 Scanner 智能地解释的。

语法分析

源代码扫描完成后,扫描结果将被传递给语法分析器。语法分析是编译的一个阶段,它将 token 转换为 抽象语法树(AST)。 
AST 是源代码的结构化表示。在 AST 中,我们将能够看到程序结构,比如函数和常量声明。

我们使用 go/parser 和 go/ast 来打印完整的 AST

package main import ( "go/ast" "go/parser" "go/token" "log" ) func main() {
    src := []byte(`
package main import "fmt" func main() {
    fmt.Println("Hello, world!")
}
`)

    fset := token.NewFileSet()

    file, err := parser.ParseFile(fset, "", src, 0) if err != nil {
        log.Fatal(err)
    }

    ast.Print(fset, file)
}

输出:

  0  *ast.File {  1  .  Package: 2:1  2  .  Name: *ast.Ident {  3  .  .  NamePos: 2:9  4  .  .  Name: "main"  5  .  }  6  .  Decls: []ast.Decl (len = 2) {  7  .  .  0: *ast.GenDecl {  8  .  .  .  TokPos: 4:1  9  .  .  .  Tok: import  10  .  .  .  Lparen: -  11  .  .  .  Specs: []ast.Spec (len = 1) {  12  .  .  .  .  0: *ast.ImportSpec {  13  .  .  .  .  .  Path: *ast.BasicLit {  14  .  .  .  .  .  .  ValuePos: 4:8  15  .  .  .  .  .  .  Kind: STRING  16  .  .  .  .  .  .  Value: "\"fmt\""  17  .  .  .  .  .  }  18  .  .  .  .  .  EndPos: -  19  .  .  .  .  }  20  .  .  .  }  21  .  .  .  Rparen: -  22  .  .  }  23  .  .  1: *ast.FuncDecl {  24  .  .  .  Name: *ast.Ident {  25  .  .  .  .  NamePos: 6:6  26  .  .  .  .  Name: "main"  27  .  .  .  .  Obj: *ast.Object {  28  .  .  .  .  .  Kind: func  29  .  .  .  .  .  Name: "main"  30  .  .  .  .  .  Decl: *(obj @ 23)  31  .  .  .  .  }  32  .  .  .  }  33  .  .  .  Type: *ast.FuncType {  34  .  .  .  .  Func: 6:1  35  .  .  .  .  Params: *ast.FieldList {  36  .  .  .  .  .  Opening: 6:10  37  .  .  .  .  .  Closing: 6:11  38  .  .  .  .  }  39  .  .  .  }  40  .  .  .  Body: *ast.BlockStmt {  41  .  .  .  .  Lbrace: 6:13  42  .  .  .  .  List: []ast.Stmt (len = 1) {  43  .  .  .  .  .  0: *ast.ExprStmt {  44  .  .  .  .  .  .  X: *ast.CallExpr {  45  .  .  .  .  .  .  .  Fun: *ast.SelectorExpr {  46  .  .  .  .  .  .  .  .  X: *ast.Ident {  47  .  .  .  .  .  .  .  .  .  NamePos: 7:2  48  .  .  .  .  .  .  .  .  .  Name: "fmt"  49  .  .  .  .  .  .  .  .  }  50  .  .  .  .  .  .  .  .  Sel: *ast.Ident {  51  .  .  .  .  .  .  .  .  .  NamePos: 7:6  52  .  .  .  .  .  .  .  .  .  Name: "Println"  53  .  .  .  .  .  .  .  .  }  54  .  .  .  .  .  .  .  }  55  .  .  .  .  .  .  .  Lparen: 7:13  56  .  .  .  .  .  .  .  Args: []ast.Expr (len = 1) {  57  .  .  .  .  .  .  .  .  0: *ast.BasicLit {  58  .  .  .  .  .  .  .  .  .  ValuePos: 7:14  59  .  .  .  .  .  .  .  .  .  Kind: STRING  60  .  .  .  .  .  .  .  .  .  Value: "\"Hello, world!\""  61  .  .  .  .  .  .  .  .  }  62  .  .  .  .  .  .  .  }  63  .  .  .  .  .  .  .  Ellipsis: -  64  .  .  .  .  .  .  .  Rparen: 7:29  65  .  .  .  .  .  .  }  66  .  .  .  .  .  }  67  .  .  .  .  }  68  .  .  .  .  Rbrace: 8:1  69  .  .  .  }  70  .  .  }  71  .  }  72  .  Scope: *ast.Scope {  73  .  .  Objects: map[string]*ast.Object (len = 1) {  74  .  .  .  "main": *(obj @ 27)  75  .  .  }  76  .  }  77  .  Imports: []*ast.ImportSpec (len = 1) {  78  .  .  0: *(obj @ 12)  79  .  }  80  .  Unresolved: []*ast.Ident (len = 1) {  81  .  .  0: *(obj @ 46)  82  .  }  83  }

分析这个输出,在 Decls 字段中,包含了代码中所有的声明,例如导入、常量、变量和函数。在本例中,我们只有两个:导入fmt包 和 主函数
为了进一步理解它,我们可以看看下面这个图,它是上述数据的表示,但只包含类型,红色代表与节点对应的代码:

09-02-19-1518845290-5bab1bdf43c6b_articlex.jpg

main函数由三个部分组成:NameType 和 BodyName 是值为 main 的标识符。由 Type字段指定的声明将包含参数列表和返回类型(如果我们指定了的话)。正文由一系列语句组成,里面包含了程序的所有行,在本例中只有一行fmt.Println("Hello, world!")

我们的一条 fmt.Println 语句由 AST 中很多部分组成。
该语句是一个 ExprStmt表达式语句(expression statement),例如,它可以像这里一样是一个函数调用,它可以是字面量,可以是一个二元运算(例如加法和减法),当然也可以是一元运算(例如自增++,自减--,否定!等)等等。
同时,在函数调用的参数中可以使用任何表达式。

然后,ExprStmt 又包含一个 CallExpr,它是我们实际的函数调用。里面又包括几个部分,其中最重要的部分是 Fun 和 Args。 
Fun 包含对函数调用的引用,在这种情况下,它是一个 SelectorExpr,因为我们从 fmt 包中选择 Println 标识符。
但是至此,在 AST 中,编译器还不知道 fmt 是一个包,它也可能是 AST 中的一个变量。

Args 包含一个表达式列表,它是函数的参数。这里,我们将一个文本字符串传递给函数,因而它由一个类型为 STRING 的 BasicLit 表示。

显然,AST 包含了许多信息,我们不仅可以分析出以上结论,还可以进一步检查 AST 并查找文件中的所有函数调用。下面,我们将使用 go/ast 包中的 Inspect 函数来递归地遍历树,并分析所有节点的信息。

package main import ( "fmt" "go/ast" "go/parser" "go/printer" "go/token" "os" ) func main() {
    src := []byte(`
package main

import "fmt"

func main() {
    fmt.Println("Hello, world!")
}
`)

    fset := token.NewFileSet()

    file, err := parser.ParseFile(fset, "", src, 0) if err != nil {
        fmt.Println(err)
    }

    ast.Inspect(file, func(n ast.Node) bool {
        call, ok := n.(*ast.CallExpr) if !ok { return true }

        printer.Fprint(os.Stdout, fset, call.Fun) return false })
}

输出:

fmt.Println

上面代码的作用是查找所有节点以及它们是否为 *ast.CallExpr 类型,上面也说过这种类型是函数调用。如果是,则使用 go/printer 包打印 Fun中存在的函数的名称。

构建出 AST 后,将使用 GOPATH 或者在 Go 1.11 及更高版本中的 modules 解析所有导入。然后,执行类型检查,并做一些让程序运行更快的初级优化。

代码生成

在解析导入并做了类型检查之后,我们可以确认程序是合法的 Go 代码,然后就走到将 AST 转换为(伪)目标机器码的过程。

此过程的第一步是将 AST 转换为程序的低级表示,特别是转换为 静态单赋值(SSA)表单。这个中间表示不是最终的机器代码,但它确实代表了最终的机器代码。 SSA 具有一组属性,会使应用优化变得更容易,其中最重要的是在使用变量之前总是定义变量,并且每个变量只分配一次。

在生成 SSA 的初始版本之后,将执行一些优化。这些优化适用于某些代码,可以使处理器执行起来更简单且更快速。例如,可以做 死码消除。还有比如可以删除某些 nil 检查,因为编译器可以证明这些检查永远不会出错。

现在通过最简单的例子来说明 SSA 和一些优化过程:

package main import "fmt" func main() {
    fmt.Println(2)
}

如你所见,此程序只有一个函数和一个导入。它会在运行时打印 2。但是,此例足以让我们了解SSA。

为了显示生成的 SSA,我们需要将 GOSSAFUNC环境变量设置为我们想要跟踪的函数,在本例中为main 函数。我们还需要将 -S 标识传递给编译器,这样它就会打印代码并创建一个HTML文件。我们还将编译Linux 64位的文件,以确保机器代码与您在这里看到的相同。
在终端执行下面的命令:

GOSSAFUNC=main GOOS=linux GOARCH=amd64 go build -gcflags -S main.go

会在终端打印出所有的 SSA,同时也会生成一个交互式的 ssa.html 文件,我们用浏览器打开它。

09-02-19-1518845290-5bab1bdf43c6b_articlex.jpg

当你打开 ssa.html 时,将显示很多阶段,其中大部分都已折叠。start 阶段是从 AST 生成的SSAlower 阶段将非机器特定的 SSA 转换为机器特定的 SSA,最后的 genssa 就是生成的机器代码。

start 阶段的代码如下:

b1:
    v1  = InitMem <mem>
    v2  = SP <uintptr>
    v3  = SB <uintptr>
    v4  = ConstInterface <interface {}>
    v5  = ArrayMake1 <[1]interface {}> v4
    v6  = VarDef <mem> {.autotmp_0} v1
    v7  = LocalAddr <*[1]interface {}> {.autotmp_0} v2 v6
    v8  = Store <mem> {[1]interface {}} v7 v5 v6
    v9  = LocalAddr <*[1]interface {}> {.autotmp_0} v2 v8
    v10 = Addr <*uint8> {type.int} v3
    v11 = Addr <*int> {"".statictmp_0} v3
    v12 = IMake <interface {}> v10 v11
    v13 = NilCheck <void> v9 v8
    v14 = Const64 <int> [0]
    v15 = Const64 <int> [1]
    v16 = PtrIndex <*interface {}> v9 v14
    v17 = Store <mem> {interface {}} v16 v12 v8
    v18 = NilCheck <void> v9 v17
    v19 = IsSliceInBounds <bool> v14 v15
    v24 = OffPtr <*[]interface {}> [0] v2
    v28 = OffPtr <*int> [24] v2
If v19 → b2 b3 (likely) (line 6)

b2: ← b1
    v22 = Sub64 <int> v15 v14
    v23 = SliceMake <[]interface {}> v9 v22 v22
    v25 = Copy <mem> v17
    v26 = Store <mem> {[]interface {}} v24 v23 v25
    v27 = StaticCall <mem> {fmt.Println} [48] v26
    v29 = VarKill <mem> {.autotmp_0} v27
Ret v29 (line 7)

b3: ← b1
    v20 = Copy <mem> v17
    v21 = StaticCall <mem> {runtime.panicslice} v20
Exit v21 (line 6)

这个简单的程序就已经产生了相当多的 SSA(总共35行)。然而,很多都是引用,可以消除很多(最终的SSA版本有28行,最终的机器代码版本有18行)。

每个 v 都是一个新变量,可以点击来查看它被使用的位置。b 是块,这里有三块:b1,b2,b3。b1 始终会执行,b2 和 b3 是条件块,满足条件才执行。
我们来看 b1 结尾处的 If v19 → b2 b3 (likely)。单击该行中的 v19 可以查看它定义的位置。可以看到它定义为 IsSliceInBounds <bool> v14 v15,通过 Go 编译器源代码,我们知道 IsSliceInBounds 的作用是检查 0 <= arg0 <= arg1。然后单击 v14 和 v15 看看在哪定义的,我们会看到 v14 = Const64 <int> [0],Const64 是一个常量 64 位整数。 v15 定义一样,放在 args1 的位置。所以,实际执行的是 0 <= 0 <= 1,这显然是正确的。

编译器也能够证明这一点,当我们查看 opt 阶段(“机器无关优化”)时,我们可以看到它已经重写了 v19 为 ConstBool <bool> [true]。结果就是,在 opt deadcode 阶段,b3 条件块被删除了,因为永远也不会执行到 b3

下面来看一下 Go 编译器在把 SSA 转换为 机器特定的SSA 之后所做的另一个更简单的优化,基于amd64体系结构的机器代码。下面,我们将比较 lower 和 lowered deadcode
lower

b1:
    BlockInvalid (6)
b2:
    v2 (?) = SP <uintptr>
    v3 (?) = SB <uintptr>
    v10 (?) = LEAQ <*uint8> {type.int} v3
    v11 (?) = LEAQ <*int> {"".statictmp_0} v3
    v15 (?) = MOVQconst <int> [1]
    v20 (?) = MOVQconst <uintptr> [0]
    v25 (?) = MOVQconst <*uint8> [0]
    v1 (?) = InitMem <mem>
    v6 (6) = VarDef <mem> {.autotmp_0} v1
    v7 (6) = LEAQ <*[1]interface {}> {.autotmp_0} v2
    v9 (6) = LEAQ <*[1]interface {}> {.autotmp_0} v2
    v16 (+6) = LEAQ <*interface {}> {.autotmp_0} v2
    v18 (6) = LEAQ <**uint8> {.autotmp_0} [8] v2
    v21 (6) = LEAQ <**uint8> {.autotmp_0} [8] v2
    v30 (6) = LEAQ <*int> [16] v2
    v19 (6) = LEAQ <*int> [8] v2
    v23 (6) = MOVOconst <int128> [0]
    v8 (6) = MOVOstore <mem> {.autotmp_0} v2 v23 v6
    v22 (6) = MOVQstore <mem> {.autotmp_0} v2 v10 v8
    v17 (6) = MOVQstore <mem> {.autotmp_0} [8] v2 v11 v22
    v14 (6) = MOVQstore <mem> v2 v9 v17
    v28 (6) = MOVQstoreconst <mem> [val=1,off=8] v2 v14
    v26 (6) = MOVQstoreconst <mem> [val=1,off=16] v2 v28
    v27 (6) = CALLstatic <mem> {fmt.Println} [48] v26
    v29 (5) = VarKill <mem> {.autotmp_0} v27
Ret v29 (+7)

在HTML中,某些行是灰色的,这意味着它们将在下一个阶段中被删除或修改。
例如,v15 (?) = MOVQconst <int> [1] 显示为灰色。点击 v15,我们看到它在其他地方都没有使用,而 MOVQconst 基本上与我们之前看到的 Const64 相同,只针对amd64的特定机器。我们把 v15 设置为1。但是,v15 在其他地方都没有使用,所以它是无用的(死的)代码并且可以消除。

Go 编译器应用了很多这类优化。因此,虽然 AST生成的初始 SSA 可能不是最快的实现,但编译器将SSA优化为更快的版本。 HTML 文件中的每个阶段都有可能发生优化。

如果你有兴趣了解 Go 编译器中有关 SSA 的更多信息,请查看 Go 编译器的 SSA 源代码
这里定义了所有的操作以及优化。

结论

Go 是一种非常高效且高性能的语言,由其编译器及其优化支撑。要了解有关 Go 编译器的更多信息,源代码的 README 是不错的选择。

发表评论 / Comment

用心评论~