首页 > 编程笔记 > Go语言笔记

Go语言是怎么完成编译的

Go语言是一门需要编译才能运行的编程语言,也就说代码在运行之前需要通过编译器生成二进制机器码,随后二进制文件才能在目标机器上运行,如果我们想要了解Go语言的实现原理,理解它的编译过程就是一个没有办法绕过的事情。

预备知识

想要深入了解Go语言的编译过程,需要提前了解一下编译过程中涉及的一些术语和专业知识。这些知识其实在我们的日常工作和学习中比较难用到,但是对于理解编译的过程和原理还是非常重要的。

1) 抽象语法树

在计算机科学中,抽象语法树(Abstract Syntax Tree,AST),或简称语法树(Syntax tree),是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的语法结构,树上的每个节点都表示源代码中的一种结构。

之所以说语法是“抽象”的,是因为这里的语法并不会表示出真实语法中出现的每个细节。比如,嵌套括号被隐含在树的结构中,并没有以节点的形式呈现。而类似于 if else 这样的条件判断语句,可以使用带有两个分支的节点来表示。

以算术表达式 1+3*(4-1)+2 为例,可以解析出的抽象语法树如下图所示:

抽象语法树
图:抽象语法树

抽象语法树可以应用在很多领域,比如浏览器,智能编辑器,编译器。

2) 静态单赋值

在编译器设计中,静态单赋值形式(static single assignment form,通常简写为 SSA form 或是 SSA)是中介码(IR,intermediate representation)的属性,它要求每个变量只分配一次,并且变量需要在使用之前定义。在实践中我们通常会用添加下标的方式实现每个变量只能被赋值一次的特性,这里以下面的代码举一个简单的例子:

x := 1
x := 2
y := x

从上面的描述所知,第一行赋值行为是不需要的,因为 x 在第二行被二度赋值并在第三行被使用,在 SSA 下,将会变成下列的形式:

x1 := 1
x2 := 2
y1 := x2

从使用 SSA 的中间代码我们就可以非常清晰地看出变量 y1 的值和 x1 是完全没有任何关系的,所以在机器码生成时其实就可以省略第一步,这样就能减少需要执行的指令来优化这一段代码。

根据 Wikipedia(维基百科)对 SSA 的介绍来看,在中间代码中使用 SSA 的特性能够为整个程序实现以下的优化:

因为 SSA 的主要作用就是代码的优化,所以是编译器后端(主要负责目标代码的优化和生成)的一部分。当然,除了 SSA 之外代码编译领域还有非常多的中间代码优化方法,优化编译器生成的代码是一个非常古老并且复杂的领域,这里就不展开介绍了。

3) 指令集架构

最后要介绍的一个预备知识就是指令集架构了,指令集架构(Instruction Set Architecture,简称 ISA),又称指令集或指令集体系,是计算机体系结构中与程序设计有关的部分,包含了基本数据类型,指令集,寄存器,寻址模式,存储体系,中断,异常处理以及外部 I/O。指令集架构包含一系列的 opcode 即操作码(机器语言),以及由特定处理器执行的基本命令。

指令集架构常见种类如下:
不同的处理器(CPU)使用了大不相同的机器语言,所以我们的程序想要在不同的机器上运行,就需要将源代码根据架构编译成不同的机器语言。

编译原理

Go语言编译器的源代码在 cmd/compile 目录中,目录下的文件共同构成了Go语言的编译器,学过编译原理的人可能听说过编译器的前端和后端,编译器的前端一般承担着词法分析、语法分析、类型检查和中间代码生成几部分工作,而编译器后端主要负责目标代码的生成和优化,也就是将中间代码翻译成目标机器能够运行的机器码。


Go的编译器在逻辑上可以被分成四个阶段:词法与语法分析、类型检查和 AST 转换、通用 SSA 生成和最后的机器代码生成,下面我们来分别介绍一下这四个阶段做的工作。

1) 词法与语法分析

所有的编译过程其实都是从解析代码的源文件开始的,词法分析的作用就是解析源代码文件,它将文件中的字符串序列转换成 Token 序列,方便后面的处理和解析,我们一般会把执行词法分析的程序称为词法解析器(lexer)。

而语法分析的输入就是词法分析器输出的 Token 序列,这些序列会按照顺序被语法分析器进行解析,语法的解析过程就是将词法分析生成的 Token 按照语言定义好的文法(Grammar)自下而上或者自上而下的进行规约,每一个 Go 的源代码文件最终会被归纳成一个 SourceFile 结构:

SourceFile = PackageClause ";" { ImportDecl ";" } { TopLevelDecl ";" }

标准的 Golang 语法解析器使用的就是 LALR(1) 的文法,语法解析的结果其实就是上面介绍过的抽象语法树(AST),每一个 AST 都对应着一个单独的Go语言文件,这个抽象语法树中包括当前文件属于的包名、定义的常量、结构体和函数等。

如果在语法解析的过程中发生了任何语法错误,都会被语法解析器发现并将消息打印到标准输出上,整个编译过程也会随着错误的出现而被中止。

2) 类型检查

当拿到一组文件的抽象语法树 AST 之后,Go语言的编译器会对语法树中定义和使用的类型进行检查,类型检查分别会按照顺序对不同类型的节点进行验证,按照以下的顺序进行处理:

通过对每一棵抽象节点树的遍历,我们在每一个节点上都会对当前子树的类型进行验证保证当前节点上不会出现类型错误的问题,所有的类型错误和不匹配都会在这一个阶段被发现和暴露出来。

类型检查的阶段不止会对树状结构的节点进行验证,同时也会对一些内建的函数进行展开和改写,例如 make 关键字在这个阶段会根据子树的结构被替换成 makeslice 或者 makechan 等函数。

其实类型检查不止对类型进行了验证工作,还对 AST 进行了改写以及处理Go语言内置的关键字,所以,这一过程在整个编译流程中是非常重要的,没有这个步骤很多关键字其实就没有办法工作。

3) 中间代码生成

当我们将源文件转换成了抽象语法树,对整个语法树的语法进行解析并进行类型检查之后,就可以认为当前文件中的代码基本上不存在无法编译或者语法错误的问题了,Go语言的编译器就会将输入的 AST 转换成中间代码。

Go语言编译器的中间代码使用了 SSA(Static Single Assignment Form) 的特性,如果我们在中间代码生成的过程中使用这种特性,就能够比较容易的分析出代码中的无用变量和片段并对代码进行优化。

在类型检查之后,就会通过一个名为 compileFunctions 的函数开始对整个Go语言项目中的全部函数进行编译,这些函数会在一个编译队列中等待几个后端工作协程的消费,这些 Goroutine 会将所有函数对应的 AST 转换成使用 SSA 特性的中间代码。

4) 机器码生成

Go语言源代码的 cmd/compile/internal 目录中包含了非常多机器码生成相关的包,不同类型的 CPU 分别使用了不同的包进行生成 amd64、arm、arm64、mips、mips64、ppc64、s390x、x86 和 wasm,也就是说Go语言能够在几乎全部常见的 CPU 指令集类型上运行。

编译器入口

Go语言的编译器入口是 src/cmd/compile/internal/gc 包中的 main.go 文件,这个 600 多行的 Main 函数就是Go语言编译器的主程序,这个函数会先获取命令行传入的参数并更新编译的选项和配置,随后就会开始运行 parseFiles 函数对输入的所有文件进行词法与语法分析得到文件对应的抽象语法树:

func Main(archInit func(*Arch)) {
    // ...

    lines := parseFiles(flag.Args())

接下来就会分九个阶段对抽象语法树进行更新和编译,就像我们在上面介绍的,整个过程会经历类型检查、SSA 中间代码生成以及机器码生成三个部分:

了解了剩下的编译过程之后,我们重新回到词法和语法分析后的具体流程,在这里编译器会对生成语法树中的节点执行类型检查,除了常量、类型和函数这些顶层声明之外,它还会对变量的赋值语句、函数主体等结构进行检查:
for i := 0; i < len(xtop); i++ {
    n := xtop[i]
    if op := n.Op; op != ODCL && op != OAS && op != OAS2 && (op != ODCLTYPE || !n.Left.Name.Param.Alias) {
        xtop[i] = typecheck(n, ctxStmt)
    }
}

for i := 0; i < len(xtop); i++ {
    n := xtop[i]
    if op := n.Op; op == ODCL || op == OAS || op == OAS2 || op == ODCLTYPE && n.Left.Name.Param.Alias {
        xtop[i] = typecheck(n, ctxStmt)
    }
}

for i := 0; i < len(xtop); i++ {
    n := xtop[i]
    if op := n.Op; op == ODCLFUNC || op == OCLOSURE {
        typecheckslice(Curfn.Nbody.Slice(), ctxStmt)
    }
}

checkMapKeys()

for _, n := range xtop {
    if n.Op == ODCLFUNC && n.Func.Closure != nil {
        capturevars(n)
    }
}

escapes(xtop)

for _, n := range xtop {
    if n.Op == ODCLFUNC && n.Func.Closure != nil {
        transformclosure(n)
    }
}
类型检查会对传入节点的子节点进行遍历,这个过程会对 make 等关键字进行展开和重写,类型检查结束之后并没有输出新的数据结构,只是改变了语法树中的一些节点,同时这个过程的结束也意味着源代码中已经不存在语法错误和类型错误,中间代码和机器码也都可以正常的生成了。
    initssaconfig()

    peekitabs()

    for i := 0; i < len(xtop); i++ {
        n := xtop[i]
        if n.Op == ODCLFUNC {
            funccompile(n)
        }
    }

    compileFunctions()

    for i, n := range externdcl {
        if n.Op == ONAME {
            externdcl[i] = typecheck(externdcl[i], ctxExpr)
        }
    }

    checkMapKeys()
}
在主程序运行的最后,会将顶层的函数编译成中间代码并根据目标的 CPU 架构生成机器码,不过这里其实也可能会再次对外部依赖进行类型检查以验证正确性。

总结

Go语言的编译过程其实是非常有趣并且值得学习的,通过对Go语言四个编译阶段的分析和对编译器主函数的梳理,我们能够对 Golang 的实现有一些基本的理解,掌握编译的过程之后,Go语言对于我们来讲也不再那么神秘,所以学习其编译原理的过程还是非常有必要的。

所有教程

优秀文章