golang compiler

May 1, 2021 · 3152 words · 7 minute read

实际编译器 🔗

编译器入口： src/cmd/compile/internal/gc/main.go#Main

cmd/compile/internal/syntax 词法和语法分析
cmd/compile/internal/gc 类型检查，处理语法糖，改写关键字。
后端转为为 SSA。生成中间代码 cmd/compile/internal/gc.compileFunctions ，cmd/compile/internal/gc, cmd/compile/internal/ssa 将函数放入队列，协程并发生成中间代码。
生成机器代码。 cmd/compile/internal/ssa , cmd/internal/obj src/cmd/compile/internal 链接不同的指令集生成平台的机器码。

词法分析和语法分析 🔗

词法分析器的主要结构src/cmd/compile/internal/syntax/scanner.go#scanner struct。词法分析器的主要方法next。
《Lexical Scanning in Go》 Rob Pike 给出他认为比较好的实现。

语法分析 src/cmd/compile/internal/syntax/parser.go。

回到编译原理的课程上... 语法分析有两种分析方法。

Lookahead。自然的想法，预读后续的 token 确定有什么文法进行向下推导，或者进行向上归约。
自顶向下选择一条文法规则，匹配规则产生式的左边时用右边的字符串替换左边的非终结符
- 从抽象到具体
- LL 文法
自底向上从终结符开始推导，规约到某一条文法规则上
- 从具体到抽象
- LR(0)
  - 用栈存储没有被归约的字符。入栈 shift。归约 reduce，新字符进来时按照规则进行合并入栈。

syntax.Parse() -> syntax.fileOrNil()对当前文件的词法和语法进行解析。
fileOrNil返回AST root， AST 的子节点由parser.importDecl, parser.constDecl等方法构建。

fileOrNil
- constDecl
- importDecl
- typeDecl
- varDecl
- funcDeclOrNil

got, want, appendGroup 方法处理批量定义。

FuncDecl:Name, FuncType, BlockStmt。
函数体是BlockStmt，由Stmt数组组成。
Stmt是一个接口。14 种声明。EmptyStmt, BlockStmt, SendStmt, LabeledStmt, ExprStmt, DeclStmt, AssignStmt, CallStmt, IfStmt, BranchStmt, ReturnStmt, ForStmt, SelectStmt。

go 抽象语法树 AST 🔗

抽象语法树 AST 是基于每个文件独立进行生成。 golang 程序的另一种语义等价-->go 的抽象语法树。

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

"main.go": SourceFile {
    PackageName: "main",
    ImportDecl: []Import{
        "fmt",
    }
    TopLevelDecl: ...
}

基础字面值的语法树结构 🔗

基本类型字面量的语法树结构

// go/ast#BasicLit
type BasicLit struct {
    ValuePos    token.Pos    // int类型， FileSet中的全局Pos
    Kind        token.Token  // token的类型
    Value       string       // 字面值
}
expr, err := parser.ParseExpr(`"1587"`)
// print ast.BasicLit
ast.print(nil, expr)

标识符字面量的语法树结构

// go/ast#Ident
type Ident struct {
    NamePost token.Pos    // 标识符在FileSet中的全局int Pos
    Nanme    string       // 标识符的名字
    Obj      *Object      // 标识符的类型
}
ast.Print(nil, ast.NewIdent(`x`))
expr, _ := parser.ParserExpr(`x`)
ast.Print(nil, expr)
/*
*ast.Ident{
    NamePos: 1
    name: "x"
    Obj: *ast.Object {
        Kind: bad
        Name: ""
    }
}
*/

基础表达式的递归结构 🔗

go 程序中运算主要是一元运算（Unary）和二元运算，运算的操作树是数值字面量 or 标识符。

// 表达式文法
Expression := UnaryExpr | Expression binary_op Expression
UnaryExpr := Operand | Unary_op UnaryExpr
Operand := Literal | identifier | "(" Expression ")"
binary_op := "||" | "&&" | rel_op | add_op | mul_op

rel_op := "==" | "!=" | "<" | "<=" | ">" | ">="
add_op := "+" | "-" | "|" | "^"
mul_op := "*" | "/" | "%" | "<<" | ">>" | "&" | "&^"
unary_op := "+" | "-" | "!" | "^" | "*" | "&" | "<-"

parser.ParseExpr 用于解析单个表达式并返回ast.Expr。

type Expr interface {
    Node
}
type Node interface {
    Pos() token.Pos    // position of first character belonging to the node
    End() token.Pos    // position of first character immediately after the node
}

利用 interface 的多态实现类型擦除。
由于 ast.Expr 是一个接口类型，所以会存在很多实现了 Expr 接口的具体类型存在。
go doc go/ast | grep Expr --color。例如 BinaryExpr, UnaryExpr, CallExpr, IndexExpr, KeyValueExpr 等等。

type BinaryExpr struct {
    X Expr             // 左操作数         可以实现递归
    OpPos token.Pos    // 操作符op的位置
    Op token.Token     // 操作符token的类型
    Y Expr             // 右操作数
}
expr, _ := parser.ParseExpr(`2 + 3 * 5`)
ast.Print(nil, expr)

表达式的求值（后序遍历表达式的 ast） 🔗

func main() {
    expr, _ := parser.ParseExpr(`2 + 3 * 4`)
    fmt.Println(Eval(expr))
}
func Eval(expr *ast.Expr) float64 {
    switch exprSpec = exp.(type) {
    case *ast.BinaryExpr:
        return BinaryExpr(exprSpec)
    case *ast.BasicLit:
        f, _ := strconv.ParseFloat(exprSpec.Value, 64)
        return f
    }
    return math.NaN()
}
func BinaryExpr(expr *ast.BinaryExpr) float64 {
    switch expr.Op {
    case token.ADD:
        return Eval(expr.X) + Eval(expr.Y)
    cae token.MUL:
        return Eval(expr.X) * Eval(expr.Y)
    }
    return math.NaN()
}

给表达式引入环境变量。

expr, _ := parser.ParseExpr(`1 + 2 * 3 + x`)
fmt.Println(Eval(expr, map[string]float64{
    "x": 11,
}))
func Eval(expr ast.Expr, vars map[string]float64) float64 {
    switch exprSpec := exp.(type) {
    case *ast.BinaryExpr:
        return EvalBinary(exprSpec, vars
    case *ast.BasicLit:
        ...
    case *ast.Ident:
        return vars[exprSpec.Name]
    }
}

go 源代码文件的语法结构 🔗

go 源文件只包含 6 种语法声明元素： package, import, type, const, var, func 。
并且，通过每行开头的不同关键词能够区分开来不同的声明类型。

type File struct {
    Doc *CommentGroup
    Package token.Pos
    Name *Ident
    Decls []Decl                    // top-level declarations;
    Scope *Scope
    Imports []*ImportSpec
    Unresolved []*Ident            //
    Comments []*CommentGroup       //
}

go 中的 import, type, const , var 的声明结构 🔗

type TypeSpec struct {
    Doc *CommentGroup       //
    Name *Ident             // type name, 新声明类型的名称 MyInt
    Assign token.Pos        // 可有可没有
    Type Expr               // any of the *XxxTypes， int
    Comment *CommentGroup   //
}

// var Pi = 3.1415926 与 常量声明的语法规则一样，共用ValueSpec。
type ValueSpec struct {
    Doc *CommentGroup       //
    Names []*Ident          // value names
    Type Expr               // value type or nil
    Values []Expr           // initial values; or nil
    Comment *CommentGroup   //
}

函数的语法树结构 🔗

go 中的概念：方法和函数。从语法规则可以看出区别是没有接受者参数。

FunctionDecl := "func" MethodName Signature [FunctionBody]
MethodDecl := "func" Recevier MethodName Signature [FunctionBody]

type FuncDecl struct {
    Doc *CommentGroup
    Recv *FieldList    // receiver or nil
    Name *Ident        // func/method name
    Type *FuncType     // function signature
    Body *BlockStmt    // function body
}

复杂的字面值 🔗

FunctionLit 是指匿名函数或者闭包。

expr, _ := parser.ParseExpr(`func() {}`)
ast.Print(nil, expr)

type FuncLit Struct {
    Type *FuncType     // functino type
    Body *BlockStmt    //function body
}

对 AST 进行类型检查 🔗

go/types 包。
类型检查的 tasklist

检查常量、类型、函数的类型
变量的赋值，初始化
函数和闭包，如何捕获变量，内敛函数的类型
哈希键值对的类型
导入函数体
检查外部依赖的声明

结构体对接口的实现。

在类型检查阶段除了对节点的类型进行检查外，还会对 make、chan 关键词进行改写为 runtime.makeslice、runtime.makechan、makemap。

类型检查的主要逻辑 cmd/compile/internal/gc.typecheck，主要在 gc.typecheck1 中。很大的 switch。弱水三千，只取一瓢饮。看其中的 OMake, OTARRAY, OTMAP 既可以了。

完成 typecheck 之后，通过 src/cmd/compile/internal/gc.compileFunctions 编译 go 项目中的所有函数。
所有函数会在一个编译队列上被并发编译goroutine 进行消费处理。 Functions -> Queue -> Goroutine consume。

AST 转换成 SSA 🔗

go/ssa 包。
ast 经过 go/types 包完成语义分析生成 types.Package 对象后，进行 ssa 格式的转换。
SSA 主要用于表示函数内的指令。

func Main(archInit func(*Arch)) {
    initssaconfig() //初始化生成SSA的配置
    for i := 0; i < len(xtop); i++ {
        n := xtop[i]
        if n.Op == ODCLFUNC {
            funccompile(n) //生成SSA
        }
    }
    compileFunctions()
}

初始化 SSA 配置 initssaconfig 🔗

1 ssa.NewTypes()初始化 Types 结构体。
2 func NewPtr(elem *Type) *Type
3 cmd/compile/internal/ssa.NewConfig 根据传入的 arch 设置生成中间代码和机器代码的函数，当前编译器使用的指针寄存器大小，可用寄存器列表，等编译选项。

处理 runtime.deferproc, runtime.newproc, runtime.growslice。初始化特定的 ABI

遍历和替换 🔗

cmd/compile/internal/gc.walk 用于遍历 AST 将一些关键字和内建函数转换为函数调用。
例如 panic, recover 转换为 runtime.gopanic , runtime.gorecover。new 替换为 runtime.newobject 函数。
在 src/cmd/compile/internal/gc/builtin/runtime.go 中找到函数的签名。

例如 channel 的转换过程。发送和接收，OSEND， ORECV。在 cmd/compile/internal/gc.walkexpr 根据节点类型进入不同分支，OSEND 时改写 OSEND 子树，cmd/compile/internal/gc.mkcall1 创建 OCALL 节点（包含了 runtime.chansend1）。

所以 channel 的底层实现，发送，接受，关闭的实现在 runtime.chansend1, runtime.chanrecv1, runtime.closechan 中。

SSA 的生成 🔗

func compileSSA(fn *Node, worker int) {
    // inner: cmd/compile/internal/gc.state.stmtList将ast转为ssa
    // cmd/compile/internal/ssa.Compile 经历多次更新ssa中间代码
    f := buildssa(fn, worker)
    pp := newProgs(fn, worker)
    genssa(f, pp) //生成cm/compile/internal/gc.Progs结构
    ...
    pp.Flush() // 调用cmd/internal/obj包中的汇编器将ssa转为汇编代码
}

多次转换。编译器需要优化中间代码。 cmd/compile/internal/ssa.Compile 函数执行。

var passes = [...]pass {
    ...
    {name: "loop rotate", fn: loopRotate},
    {name: "stackframe", fn: stackFrame, required: true},
    {name: "trim", fn: trim},
    ...
}
func Compile(f *Func) {
    ...
    for _, p := range passes {
        f.pass = &p
        p.fn(f)
    }
    ...
}

机器代码的生成 🔗

ssa 中间代码的最后阶段，Go 函数体的代码转换成 cmd/compile/internal/obj.Prog 结构。

cmd/compile/internal/ssa 包
- 负责对 ssa 中间代码进行降级，执行特定架构的优化，生成 cmd/compile/internal/obj.Prog 指令。
cmd/internal/obj 包
- 作为汇编器将 Prog 指令转换为机器码。

如果是 x86 架构，调用 cmd/compile/internal/ssa.rewriteBlock386()。

机器代码的生成。 src/cmd/compile/internal 目录下有很多 amd64, arm64, x86, wasm。

GOARCH=wasm GOOS=js go build -o lib.wasm main.go

LLVM 的基础知识 🔗

wangcong15
http://llvm.org/docs/WritingAnLLVMPass.html
http://llvm.org/docs/tutorial/index.html
llvm 中文资料白马负金羁梦在哪里
http://www.aosabook.org/en/index.html, http://www.aosabook.org/en/llvm.html
MIT Computer Systems Security https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-858-computer-systems-security-fall-2014/index.htm
https://sitano.github.io/2018/03/18/howto-read-gossa/

源伞科技

go 汇编 (劝退) 🔗

go 的汇编中寄存器的定义与 x86 汇编上容易混淆。
汇编风格分为 2 类

intel 风格(move dest, source)
AT&T 风格(左 --> 右) go 是 plan9，属于此类

go tool compile -S main.go > main.S

plan 9
- https://lrita.github.io/2017/12/12/golang-asm/#go%E5%87%BD%E6%95%B0%E8%B0%83%E7%94%A8
- https://lrita.github.io/images/posts/go/GoFunctionsInAssembly.pdf
- https://github.com/buptbill220/gotls/tree/master/interesting
- 查看当前 cpu 架构的指令集合 cat /proc/cpuinfo | grep flags | head -1
- 指令查询： http://68k.hax.com/
- 命令查询：https://9p.io/magic/man2html/1/8a
- plan9 文档： https://9p.io/sys/doc/

golang 的编译器版本 🔗

golang 1.25 🔗

golang 1.24 🔗

golang

golang compiler

实际编译器 🔗

词法分析 和 语法分析 🔗

go 抽象语法树 AST 🔗

基础字面值的语法树结构 🔗

基础表达式的递归结构 🔗

表达式的求值（后序遍历表达式的 ast） 🔗

go 源代码文件的语法结构 🔗

go 中的 import, type, const , var 的声明结构 🔗

函数的语法树结构 🔗

复杂的字面值 🔗

对 AST 进行类型检查 🔗

AST 转换成 SSA 🔗

初始化 SSA 配置 initssaconfig 🔗

遍历和替换 🔗

SSA 的生成 🔗

机器代码的生成 🔗

LLVM 的基础知识 🔗

go 汇编 (劝退) 🔗

golang 的编译器版本 🔗

golang 1.25 🔗

golang 1.24 🔗

词法分析和语法分析 🔗