Golang编译器源码分析(1)

微信扫一扫,分享到朋友圈

Golang编译器源码分析(1)

一、Golang源码下载及安装

官网地址:
https://golang.google.cn/dl/
下载安装包或源码包均可
wget https://golang.google.cn/dl/go1.15.4.src.tar.gz
安装包下载很简单 设置好环境变量。。
源码安装
cd go/src
./all.bash
安装报错
# ./all.bash
./make.bash: line 165: /root/go1.4/bin/go: No such file or directory
Building Go cmd/dist using /root/go1.4. ()
ERROR: Cannot find /root/go1.4/bin/go.
Set $GOROOT_BOOTSTRAP to a working Go tree >= Go 1.4.
# GOROOT_BOOTSTRAP 设置go1.4版本地址 实现了自举,编译后续版本

我们学习的对象就是Go语言版本的编译源码。

二、调试方法

1、DLV调试编译过程

调试编译器执行过程,必须调试go安装目录下的源码,即GOROOT下源码,否则报内部包冲突错误。

编译器目录为go/src/cmd/compile,调试命令如下:

#同样必须是GOROOT下源码
dlv debug /usr/local/go/src/cmd/compile/main.go
#设置断点 通过包名及方法设置断点
b main.main
#设置编译器编译目标文件
r /Users/xxx/go/src/test/debug1/main.go
#开始调试 continue
c
#执行下一行代码
n
# 打印关心的变量
p archInit
cmd/compile/internal/amd64.Init
# 通过代码文件及行数设置断点
b /usr/local/go/src/cmd/compile/internal/gc/main.go:345
p outfile
#直接通过函数名设置断点
b parseFiles
b funccompile

2、Goland调试编译过程

同理 goland调试编译器 调试的源码也必须位于go安装目录

首先需要通过Goland新建项目go 项目目录位于GOROOT,例如/user/local/go

Goland Debug配置方法如下 和dlv类似

打开 /usr/local/go/src/cmd/compile/main.go
点击main函数左侧绿色小三角形,执行 debug go build main.go
(未设置则自动)弹出go build配置框或点击右上方Edit Debug Configurations 菜单按钮重新设置
Files /usr/local/go/src/cmd/compile/main.go
# 设置有权限的工作目录
Working Directory /Users/xxx/golang/compile/w
# 设置编译目标文件
Program arguments /Users/xxx/go/src/test/debug1/main.go

以上是Goland debug编译器的关键配置,具体使用方法,自行百度,和普通程序debug调试用法一致。

三、编译过程概述

编译过程

1、Go 的编译器在逻辑上可以被分成四个阶段:词法与语法分析、类型检查和 AST 转换、通用 SSA 生成和最后的机器代码生成

编译前端     编译后端
---------- | ---------- |
| 词法分析 | 中间码生成 |
|---------------------- |
| 语法分析 | 代码优化 |
|---------------------- |
| 语义分析 | 机器码生成 |
|--------- | ---------- |
  1. 词法分析生成token [scanner.next()];
  2. 语法分析生成抽象语法树AST,每一个 AST 都对应着一个单独的 Go 语言文件 [parse.decls()];
  3. 语义分析进行类型检查,优化改写ast [checktype1()];
  4. 中间码生成将抽象语法树会经过多轮处理转变成最后的拥有 静态单赋值(SSA)特性的中间码,分析出代码中的无用变量和片段并对代码进行优化;
  5. 高效代码替换低效的代码,力所能及的进行优化;
  6. 生成汇编代码(Plan9),进而生成机器码。

词法与语法分析

词法分析是计算机科学中将字符序列转换为标记(token)序列的过程,词法分析就是解析源代码文件,它将文件中的字符串序列转换成Token序列,方便后面的处理和解析。

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

词法分析会返回一个不包含空格、换行等字符的 Token 序列,例如: package , import , ( , io , ) , …,而语法分析会把 Token 序列转换成有意义的结构体,也就是抽象语法树(AST)。

每一个 AST 都对应着一个单独的 Go 语言文件,这个抽象语法树中包括当前文件属于的包名、定义的常量、结构体和函数等。

类型检查

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

  1. 常量、类型和函数名及类型;
  2. 变量的赋值和初始化;
  3. 函数和闭包的主体;
  4. 哈希键值对的类型;
  5. 导入函数体;
  6. 外部的声明;

通过对整棵抽象语法树的遍历,我们在每一个节点上都会对当前子树的类型进行验证,以保证当前节点上不会出现类型错误的问题,所有的类型错误和不匹配都会在这一个阶段被发现和暴露出来,结构体是否实现了某些接口也会在这一阶段被检查出来。

中间代码生成

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

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

由于 Go 语言编译器的中间代码使用了 SSA 的特性,所以在这一阶段我们就能够分析出代码中的无用变量和片段并对代码进行优化。

机器码生成

Go 语言源代码的 src/cmd/compile/internal 目录中包含了很多机器码生成相关的包,不同类型的 CPU 分别使用了不同的包生成机器码,其中包括 amd64、arm、arm64、mips、mips64、ppc64、s390x、x86 和 wasm。

四、编译源代码学习

词法分析准备

通过main函数,不难追踪到文件解析入口函数parseFiles,该函数为每个文件创建了一个noder对象,noder拥有一个词法文件属性存储该源文件对应词法分析的结果。

单个源文件对应的词法树noder结构体

// noder transforms package syntax's AST into a Node tree.
type noder struct {
basemap   map[*syntax.PosBase]*src.PosBase
basecache struct {
last *syntax.PosBase
base *src.PosBase
}
file       *syntax.File //词法分析文件对象指针
linknames  []linkname
pragcgobuf [][]string
err        chan syntax.Error
scope      ScopeID
// scopeVars is a stack tracking the number of variables declared in the
// current function at the moment each open scope was opened. scopeVars []int
lastCloseScopePos syntax.Pos
}

parseFiles方法开启协程通过syntax.Parse进行文件解析.

Parse函数代码如下:

func Parse(base *PosBase, src io.Reader, errh ErrorHandler, pragh PragmaHandler, mode Mode) (_ *File, first error) {
defer func() {
if p := recover(); p != nil {
if err, ok := p.(Error); ok {
first = err
return
}
panic(p)
}
}()
var p parser
p.init(base, src, errh, pragh, mode)
p.next() //开始识别token
return p.fileOrNil(), p.first //p.fileOrNil()开始生成token词法树
}

解析过程中,创建了文件解析器parser,其中继承了扫描器sanner的方法和属性

#解析器结构体
type parser struct {
file *PosBase
errh ErrorHandler
mode Mode
scanner //继承扫描器scanner的方法属性
base   *PosBase // current position base
first  error // first error encountered
errcnt int // number of errors encountered
pragma Pragma // pragma flags
fnest  int // function nesting level (for error handling)
xnest  int // expression nesting level (for complit ambiguity resolution)
indent []byte // tracing support
}

扫描器的fileOrNil()方法返回词法文件结构体syntax.File,也就是解析完毕的词法树,结构体如下:

// package PkgName; DeclList[0], DeclList[1], ...
type File struct {
PkgName  *Name
DeclList []Decl
Lines    uint
node}

词法分析过程

Go 语言的词法解析是通过src/cmd/compile/internal/syntax/scanner.go文件中的 scanner 结构体实现的,这个结构体会持有当前扫描的数据源文件、启用的模式和当前被扫描到的Token。

#扫描器结构体
type scanner struct {
source
mode   uint
nlsemi bool // if set 'n' and EOF translate to ';'
// current token, valid after calling next() line, col uint
tok       token
lit       string // valid if tok is _Name, _Literal, or _Semi ("semicolon", "newline", or "EOF"); may be malformed if bad is true
bad       bool // valid if tok is _Literal, true if a syntax error occurred, lit may be malformed
kind      LitKind // valid if tok is _Literal
op        Operator // valid if tok is _Operator, _AssignOp, or _IncOp
prec      int // valid if tok is _Operator, _AssignOp, or _IncOp
}

src/cmd/compile/internal/syntax/tokens.go 文件中定义了 Go 语言中支持的全部 Token 类型,所有的 token 类型都是正整数,你可以在这个文件中找到一些常见 Token 的定义,例如:操作符、括号和关键字等:

const (
_ token = iota
_EOF // EOF
// names and literals _Name // name
_Literal // literal
// operators and operations // _Operator is excluding '*' (_Star) _Operator // op
_AssignOp // op=
_IncOp // opop
_Assign // =
_Define // :=
_Arrow // <-
_Star // *
// delimiters _Lparen // (
_Lbrack // [
_Lbrace // {
_Rparen // )
_Rbrack // ]
_Rbrace // }
_Comma // ,
_Semi // ;
_Colon // :
_Dot // .
_DotDotDot // ...
// keywords _Break // break
_Case // case
_Chan // chan
_Const // const
_Continue // continue
_Default // default
_Defer // defer
_Else // else
_Fallthrough // fallthrough
_For // for
_Func // func
_Go // go
_Goto // goto
_If // if
_Import // import
_Interface // interface
_Map // map
_Package // package
_Range // range
_Return // return
_Select // select
_Struct // struct
_Switch // switch
_Type // type
_Var // var
// empty line comment to exclude it from .String tokenCount //
)

最右推导加向前查看构成了Go语言词法分析器的最基本原理,主要是由 scanner 这个结构体中的 next 方法驱动来获取下一个词法token,方法代码如下:

func (s *scanner) next() {
nlsemi := s.nlsemi
s.nlsemi = false
redo:
// skip white space
c := s.getr()
for c == ' ' || c == 't' || c == 'n' && !nlsemi || c == 'r' {
c = s.getr()
}
// token start
s.line, s.col = s.source.line0, s.source.col0
if isLetter(c) || c >= utf8.RuneSelf && s.isIdentRune(c, true) {
s.ident()
return
}
switch c {
case -1:
if nlsemi {
s.lit = "EOF"
s.tok = _Semi
break
}
s.tok = _EOF
case 'n':
s.lit = "newline"
s.tok = _Semi
case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
s.number(c)
case '"':
s.stdString()
case '`':
s.rawString()
case ''':
s.rune()
case '(':
s.tok = _Lparen
case '[':
s.tok = _Lbrack
case '{':
s.tok = _Lbrace
case ',':
s.tok = _Comma
case ';':
s.lit = "semicolon"
s.tok = _Semi
case ')':
s.nlsemi = true
s.tok = _Rparen
case ']':
s.nlsemi = true
s.tok = _Rbrack
case '}':
s.nlsemi = true
s.tok = _Rbrace
case ':':
if s.getr() == '=' {
s.tok = _Define
break
}
s.ungetr()
s.tok = _Colon
case '.':
c = s.getr()
if isDecimal(c) {
s.ungetr()
s.unread(1) // correct position of '.' (needed by startLit in number)
s.number('.')
break
}
if c == '.' {
c = s.getr()
if c == '.' {
s.tok = _DotDotDot
break
}
s.unread(1)
}
s.ungetr()
s.tok = _Dot
case '+':
s.op, s.prec = Add, precAdd
c = s.getr()
if c != '+' {
goto assignop
}
s.nlsemi = true
s.tok = _IncOp
case '-':
s.op, s.prec = Sub, precAdd
c = s.getr()
if c != '-' {
goto assignop
}
s.nlsemi = true
s.tok = _IncOp
case '*':
s.op, s.prec = Mul, precMul
// don't goto assignop - want _Star token
if s.getr() == '=' {
s.tok = _AssignOp
break
}
s.ungetr()
s.tok = _Star
case '/':
c = s.getr()
if c == '/' {
s.lineComment()
goto redo
}
if c == '*' {
s.fullComment()
if s.source.line > s.line && nlsemi {
// A multi-line comment acts like a newline;
// it translates to a ';' if nlsemi is set. s.lit = "newline"
s.tok = _Semi
break
}
goto redo
}
s.op, s.prec = Div, precMul
goto assignop
case '%':
s.op, s.prec = Rem, precMul
c = s.getr()
goto assignop
case '&':
c = s.getr()
if c == '&' {
s.op, s.prec = AndAnd, precAndAnd
s.tok = _Operator
break
}
s.op, s.prec = And, precMul
if c == '^' {
s.op = AndNot
c = s.getr()
}
goto assignop
case '|':
c = s.getr()
if c == '|' {
s.op, s.prec = OrOr, precOrOr
s.tok = _Operator
break
}
s.op, s.prec = Or, precAdd
goto assignop
case '^':
s.op, s.prec = Xor, precAdd
c = s.getr()
goto assignop
case '<':
c = s.getr()
if c == '=' {
s.op, s.prec = Leq, precCmp
s.tok = _Operator
break
}
if c == '<' {
s.op, s.prec = Shl, precMul
c = s.getr()
goto assignop
}
if c == '-' {
s.tok = _Arrow
break
}
s.ungetr()
s.op, s.prec = Lss, precCmp
s.tok = _Operator
case '>':
c = s.getr()
if c == '=' {
s.op, s.prec = Geq, precCmp
s.tok = _Operator
break
}
if c == '>' {
s.op, s.prec = Shr, precMul
c = s.getr()
goto assignop
}
s.ungetr()
s.op, s.prec = Gtr, precCmp
s.tok = _Operator
case '=':
if s.getr() == '=' {
s.op, s.prec = Eql, precCmp
s.tok = _Operator
break
}
s.ungetr()
s.tok = _Assign
case '!':
if s.getr() == '=' {
s.op, s.prec = Neq, precCmp
s.tok = _Operator
break
}
s.ungetr()
s.op, s.prec = Not, 0
s.tok = _Operator
default:
s.tok = 0
s.errorf("invalid character %#U", c)
goto redo
}
return
assignop:
if c == '=' {
s.tok = _AssignOp
return
}
s.ungetr()
s.tok = _Operator
}

通过getr获取下一个字符,通过许多不同的switch/case来识别token。

而通过解析器(parser)的fileOrNil方法来将识别的token加入到词法树:

func (p *parser) fileOrNil() *File {
if trace {
defer p.trace("file")()
}
f := new(File)
f.pos = p.pos()
// PackageClause
if !p.got(_Package) {
p.syntaxError("package statement must be first")
return nil
}
f.PkgName = p.name()
p.want(_Semi)
// don't bother continuing if package clause has errors
if p.first != nil {
return nil
}
// { ImportDecl ";" }
for p.got(_Import) {
f.DeclList = p.appendGroup(f.DeclList, p.importDecl)
p.want(_Semi)
}
// { TopLevelDecl ";" }
for p.tok != _EOF {
switch p.tok {
case _Const:
p.next()
f.DeclList = p.appendGroup(f.DeclList, p.constDecl)
case _Type:
p.next()
f.DeclList = p.appendGroup(f.DeclList, p.typeDecl)
case _Var:
p.next()
f.DeclList = p.appendGroup(f.DeclList, p.varDecl)
case _Func:
p.next()
if d := p.funcDeclOrNil(); d != nil {
f.DeclList = append(f.DeclList, d)
}
default:
if p.tok == _Lbrace && len(f.DeclList) > 0 && isEmptyFuncDecl(f.DeclList[len(f.DeclList)-1]) {
// opening { of function declaration on next line
p.syntaxError("unexpected semicolon or newline before {")
} else {
p.syntaxError("non-declaration statement outside function body")
}
p.advance(_Const, _Type, _Var, _Func)
continue
}
// Reset p.pragma BEFORE advancing to the next token (consuming ';')
// since comments before may set pragmas for the next function decl. p.pragma = 0
if p.tok != _EOF && !p.got(_Semi) {
p.syntaxError("after top level declaration")
p.advance(_Const, _Type, _Var, _Func)
}
}
// p.tok == _EOF
f.Lines = p.source.line
return f
}

通过fileOrNil方法,不难看出go语言四种不同的顶级声明token(TopLevelDecl)词法节点:_Const(常量)、_Type(类型)、_Var(变量)、_Func(函数及方法)以及_Package和_Import声明token。

解析器还封装了p.want()和p.got(),进行前驱分析和意图判断。

func (p *parser) got(tok token) bool {
if p.tok == tok {
p.next()//如果当前tok和指定token相等,返回true并自动前驱获取下个token
return true
}
return false
}
func (p *parser) want(tok token) {
if !p.got(tok) {//如果不符合预期则报语法错误。
p.syntaxError("expecting " + tokstring(tok))
p.advance()
}
}

got 其实只是用于快速判断一些语句中的关键字,如果当前解析器中的 Token 是传入的 Token 就会直接跳过该 Token 并返回 true ;而 want 就是对 got 的简单封装了,如果当前的 Token 不是我们期望的,就会立刻返回语法错误并结束这次编译。

词法分析节点介绍

// 顶级声明
type (
Decl interface {
Node
aDecl()
}
//              Path
// LocalPkgName Path
ImportDecl struct {
LocalPkgName *Name // including "."; nil means no rename present
Path         *BasicLit
Group        *Group // nil means not part of a group
decl
}
// NameList
// NameList      = Values // NameList Type = Values
ConstDecl struct {
NameList []*Name
Type     Expr // nil means no type
Values   Expr // nil means no values
Group    *Group // nil means not part of a group
decl
}
// Name Type
TypeDecl struct {
Name   *Name
Alias  bool
Type   Expr
Group  *Group // nil means not part of a group
Pragma Pragma
decl }
// NameList Type
// NameList Type = Values // NameList      = Values
VarDecl struct {
NameList []*Name
Type     Expr // nil means no type
Values   Expr // nil means no values
Group    *Group // nil means not part of a group
decl
}
// func          Name Type { Body }
// func          Name Type // func Receiver Name Type { Body } // func Receiver Name Type
FuncDecl struct {
Attr   map[string]bool // go:attr map
Recv   *Field // nil means regular function
Name   *Name
Type   *FuncType
Body   *BlockStmt // nil means no body (forward declaration)
Pragma Pragma // TODO(mdempsky): Cleaner solution.
decl
}
)

以FuncDecl为例,函数体存储类型为BlockStmt指针,常见statments定义如下:

// Statements
type (
Stmt interface {
Node
aStmt()
}
SimpleStmt interface {
Stmt
aSimpleStmt()
}
EmptyStmt struct {
simpleStmt
}
LabeledStmt struct {
Label *Name
Stmt  Stmt
stmt }
BlockStmt struct {
List   []Stmt
Rbrace Pos
stmt }
ExprStmt struct {
X Expr
simpleStmt }
SendStmt struct {
Chan, Value Expr // Chan <- Value
simpleStmt
}
DeclStmt struct {
DeclList []Decl
stmt }
AssignStmt struct {
Op       Operator // 0 means no operation
Lhs,Rhs Expr // Rhs == ImplicitOne means Lhs++ (Op == Add) or Lhs-- (Op == Sub)
simpleStmt
}
BranchStmt struct {
Tok   token // Break, Continue, Fallthrough, or Goto
Label *Name
// Target is the continuation of the control flow after executing
// the branch; it is computed by the parser if CheckBranches is set. // Target is a *LabeledStmt for gotos, and a *SwitchStmt, *SelectStmt, // or *ForStmt for breaks and continues, depending on the context of // the branch. Target is not set for fallthroughs. Target Stmt
stmt }
CallStmt struct {
Tok  token // Go or Defer
Call *CallExpr
stmt }
ReturnStmt struct {
Results Expr // nil means no explicit return values
stmt
}
IfStmt struct {
Init SimpleStmt
Cond Expr
Then *BlockStmt
Else Stmt // either nil, *IfStmt, or *BlockStmt
stmt
}
ForStmt struct {
Init SimpleStmt // incl. *RangeClause
Cond Expr
Post SimpleStmt
Body *BlockStmt
stmt }
SwitchStmt struct {
Init   SimpleStmt
Tag    Expr // incl. *TypeSwitchGuard
Body   []*CaseClause
Rbrace Pos
stmt }
SelectStmt struct {
Body   []*CommClause
Rbrace Pos
stmt }
)

这些不同类型的 Stmt 构成了全部命令式的 Go 语言代码,从中我们可以看到非常多熟悉的控制结构,例如 ifforswitchselect

语法分析

因为词法分析器 scanner 作为结构体被嵌入到了 parser 中,所以这个方法中的 p.next() 实际上调用的是 scannernext 方法,它会直接获取文件中的下一个 Token,所以词法分析和语法分析其实是一起进行的。

上面parseFiles方法中扫描器和解析器(syntax.Parse)生成源文件对应的syntax.File对象后,生成语法树的过程是在p.node()执行过程中生成的

func (p *noder) node() {
types.Block = 1
imported_unsafe = false
p.setlineno(p.file.PkgName)
mkpackage(p.file.PkgName.Value)
xtop = append(xtop, p.decls(p.file.DeclList)...)//生成抽象语法树
for _, n := range p.linknames {
if !imported_unsafe {
p.yyerrorpos(n.pos, "//go:linkname only allowed in Go files that import "unsafe"")
continue
}
s := lookup(n.local)
if n.remote != "" {
s.Linkname = n.remote
} else {
// Use the default object symbol name if the
// user didn't provide one. if myimportpath == "" {
p.yyerrorpos(n.pos, "//go:linkname requires linkname argument or -p compiler flag")
} else {
s.Linkname = objabi.PathToPrefix(myimportpath) + "." + n.local
}
}
}
// The linker expects an ABI0 wrapper for all cgo-exported
// functions. for _, prag := range p.pragcgobuf {
switch prag[0] {
case "cgo_export_static", "cgo_export_dynamic":
if symabiRefs == nil {
symabiRefs = make(map[string]obj.ABI)
}
symabiRefs[prag[1]] = obj.ABI0
}
}
pragcgobuf = append(pragcgobuf, p.pragcgobuf...)
lineno = src.NoXPos
clearImports()
}
//xtop声明如下:
var xtop []*Node

语法树单个树节点定义如下:

// A Node is a single node in the syntax tree.
// Actually the syntax tree is a syntax DAG, because there is only one
// node with Op=ONAME for a given instance of a variable x.
// The same is true for Op=OTYPE and Op=OLITERAL. See Node.mayBeShared.
type Node struct {
// Tree structure.
// Generic recursive walks should follow these fields. Left  *Node
Right *Node
Ninit Nodes
Nbody Nodes
List  Nodes
Rlist Nodes
// most nodes
Type *types.Type
Orig *Node // original form, for printing, and tracking copies of ONAMEs
// func Func *Func
// ONAME, OTYPE, OPACK, OLABEL, some OLITERAL
Name *Name
Sym *types.Sym // various
E   interface{} // Opt or Val, see methods below
// Various. Usually an offset into a struct. For example: // - ONAME nodes that refer to local variables use it to identify their stack frame position. // - ODOT, ODOTPTR, and ORESULT use it to indicate offset relative to their base address. // - OSTRUCTKEY uses it to store the named field's offset. // - Named OLITERALs use it to store their ambient iota value. // - OINLMARK stores an index into the inlTree data structure. // - OCLOSURE uses it to store ambient iota value, if any. // Possibly still more uses. If you find any, document them. Xoffset int64
Pos src.XPos
flags bitset32
Esc uint16 // EscXXX
Op  Op
aux uint8
}

总结

了解 Go 语言的词法分析器 scanner 和语法分析器 parser 让我们对解析器处理源代码的过程有着比较清楚的认识,同时我们也在 Go 语言的文法和语法分析器中找到了熟悉的关键字和语法结构,加深了对 Go 语言的理解。

待续

有疑问加站长微信联系(非本文作者)

5 个我不可或缺的开源工具 | Linux 中国

上一篇

Hugo 跨版本升级(二)

下一篇

你也可能喜欢

Golang编译器源码分析(1)

长按储存图像,分享给朋友