Go编译器定制简介

主题大纲

最简编译器
编译器后门八卦
Go和Rust的选择
Go衍生的语言
Go语法树
Go类型系统
SSA和LLVM
µGo案例
参考链接

编译器是什么

编译器是一种精确的翻译程序
编译器输入的是数据序列, 输出的也是数据序列
编译器作为可执行程序可用于 AOT 翻译, 类似 gcc 命令
编译器也可以是一个函数, 用于 JIT 运行时翻译, 或者包装为 AOT 翻译命令
编译器一般是某种编程语言的翻译程序, 因此也就包含了编程语言的外延
现代编程语言不仅仅是翻译, 还有内置的运行时调度
编译器可以很复杂, 甚至可以内置 OS ...
编译器也可以很简单...

人肉编译器

将一个整数编译为一个程序, 程序的返回值返回这个整数值

比如 42 翻译为以下的 C 语言程序:

int main() {
    return 42;
}

也可以翻译为以下的 X86 汇编程序:

.intel_syntax noprefix
.globl _main

_main:
    mov rax, 42 ;
    ret

也可以翻译为 LLVM 跨平台的汇编程序:

define i32 @main() {
    ret i32 42 ;
}

Go程序替代人肉编译器

Go语言重新实现如下人肉编译器:

func main() {
    code, _ := io.ReadAll(os.Stdin)
    compile(string(code))
}

func compile(code string) {
    output := fmt.Sprintf(tmpl, code)
    os.WriteFile("a.out.ll", []byte(output), 0666)
    exec.Command("clang", "-o", "a.out", "a.out.ll").Run()
}

const tmpl = `
define i32 @main() {
    ret i32 %v
}
`

编译 echo 123 | go run main.go, 执行 ./a.out, 看结果 echo $?

挑战: 继续前进一小步

输入的数字变为支持加/减/乘/除法和小括弧的表达式(词法+语法解析)
输出 X86 汇编时如何处理多个中间结果?
如何简化优先级的处理?

Reflections on Trusting Trust - 01 - 自重写程序

s 是从最后一个 0 到结尾的内容, 第1个 printf 打印 s 数组, 第2个打印后面部分

Reflections on Trusting Trust - 02 - 鸡和蛋问题

C编译器为了支持转义的自举过程

Reflections on Trusting Trust - 03 - 潜伏的后门

Ken 在C编译器植入后门后擦除记录, 同时在UNIX保留伪装的后门代码

Go 开发的编译器

https://github.com/topics/compiler?l=Go

Go语法衍生: TinyGo 9.1K, Go+ 7.9K, CUE 3.2K

Terraform 30.6K Star
esbuild 29.5K Star

Google/Grumpy 10.4K Star: Python 翻译到 Go
Google/SkyLark 1.2K Star: Python 子集
Google/Jsonnet 1.1K Star
Google/CEL 1K Star: 表达式语言

OPA/Rego 6K Star: 策略语言
GopherLua 4.5K Star: Lua实现

Rust 开发的编译器

https://github.com/topics/compiler?l=rust

SWC 19K Star: TypeScript 编译器
Facebook/Move 16.3K Star: 区块链语言
RustPython 10.3K Star
solang 500 Star: Solidity 编译器
ulisp 50 Star

目前 Rust 社区对 VM 和 Compiler 的开发比较活跃

Go和Rust的选择

Go编译快, GC简化开发, 运行较快, 非常适合写编译器
Rust编译慢, 开发繁琐, 运行时稍快(但过早释放内存影响性能), 不是编译器的最佳选择
如果真有死磕 Rust 语言的毅力/能力/精力, 建议去写 Rust 编译器本身

Rust 比较适合开发长时间稳定运行的 VM 系统, 比如各种 WASM 虚拟机
Go 比较适合开发快速迭代, 一次完成 AOT 编译的编译器, GC 一次回收效率更高

Go衍生的语言

TinyGo 9.1K Star: 单片机环境的Go
Go+ 7.9K Star: Go之上增加了新的特性
CUE 3.2K Star: 配置语言
Tengo 2.5K Star: Go类似语法的脚本语言
Emgo 950 Star: 面向嵌入式环境的Go
µGo 700 Star: 如何从头定制Go子集

CUE 在配置语言领域已经形成影响力, 作者是Go团队成员, 前BCL成员
阿里开源的 KubeVela 基于 CUE 构建

FileSet 文件集模型

全部Go文件根据文件名排序
全部Go文件映射到连续的抽象内存, 每个文件对应一个区间
token.Pos 表示一个指针, 0 对应 token.NoPos 空指针
这样设计的目的是为了压缩和性能, 通过一个 uint32 可以映射到文件位置

语法解析器接口

parser.ParseDir, parser.ParseFile

方法声明的语法树结构

func (p *xType) Hello(arg1, arg2 int) (bool, error)

Scope 词法域 - 01

builtin -> package -> file -> func

Scope 词法域 - 02

func -> args -> block

Scope 词法域 - 03

特殊的地方: Pkg 内 File 之间的命名实体可见(但不包含 import)

Go类型检查

bool/int/float/string/slice/struct/interface 排序
遍历AST, 判断赋值/函数参数/返回值/表达式类型匹配

func main() {
    fset := token.NewFileSet()
    f, err := parser.ParseFile(fset, "hello.go", src, parser.AllErrors)
    if err != nil {
        log.Fatal(err)
    }
    pkg, err := new(types.Config).Check("hello.go", fset, []*ast.File{f}, nil)
    if err != nil {
        log.Fatal(err)
    }
    _ = pkg
}

const src = `package main
func main() {
    var _ = "a" + 1
}
`

Go类型信息

go/types.Config.Check 可为 AST 每个表达式节点标注类型信息

func main() {
    fset := token.NewFileSet()
    f, err := parser.ParseFile(fset, "hello.go", src, parser.AllErrors)
    if err != nil {
        log.Fatal(err)
    }
    info := &types.Info{
        Types:  make(map[ast.Expr]types.TypeAndValue),
        Defs:   make(map[*ast.Ident]types.Object),
        Uses:   make(map[*ast.Ident]types.Object),
        Scopes: make(map[ast.Node]*types.Scope),
    }
    conf := types.Config{Importer: nil}
    pkg, err := conf.Check("hello.go", fset, []*ast.File{f}, info)
    if err != nil {
        log.Fatal(err)
    }
    _ = pkg
}

SSA 基本结构

模块内部有全局变量和全局函数
函数内部有单层的 Block 列表组成(由一个Label定义)
每个 Block 内由单层的指令列表组成
每个 Block 结尾必须跳转到其他 Block, 最后一个 Block 返回
每个虚拟寄存器只能被初始化一次

Go AST 到 Go SSA - 01

Go SSA 和 LLVM-IR 并不完全等价
Go SSA 抽象层次更高, 同时 SSA 只涉及语句, 不含类型和结构拆分

func main() {
    fset := token.NewFileSet()
    f, _ := parser.ParseFile(fset, "hello.go", src, parser.AllErrors)

    info := &types.Info{}
    conf := types.Config{Importer: nil}
    pkg, _ := conf.Check("hello.go", fset, []*ast.File{f}, info)

    var ssaProg = ssa.NewProgram(fset, ssa.SanityCheckFunctions)
    var ssaPkg = ssaProg.CreatePackage(pkg, []*ast.File{f}, info, true)

    ssaPkg.Build()

    ssaPkg.WriteTo(os.Stdout)
    ssaPkg.Func("init").WriteTo(os.Stdout)
    ssaPkg.Func("main").WriteTo(os.Stdout)
}

Go AST 到 Go SSA - 02

const src = `
package main

var s = "hello ssa"

func main() {
    for i := 0; i < 3; i++ {
        println(s)
    }
}
`

Go AST 到 Go SSA - 03

package hello.go:
  func  init       func()
  var   init$guard bool
  func  main       func()
# Name: hello.go.main
# Package: hello.go
# Location: hello.go:4:6
func main():
0:                                                                entry P:0 S:1
        jump 3
1:                                                             for.body P:1 S:1
        t0 = println("hello ssa -- chai...":string)                          ()
        t1 = t2 + 1:int                                                     int
        jump 3
2:                                                             for.done P:1 S:0
        return
3:                                                             for.loop P:2 S:2
        t2 = phi [0: 0:int, 1: t1] #i                                       int
        t3 = t2 < 3:int                                                    bool
        if t3 goto 1 else 2

Go SSA 的执行和再编译

SSA 可以被解释执行: go/ssa/interp/interp.go
SSA 可以被翻译到 LLVM-IR: tinygo/compiler/compiler.go

为什么是 Go ?

有人曾说 Shell 也能开发 Docker, 因此 Go 语言也不怎么样...

Go 语言够简单, 25 个关键字
Go 语言的 go/* 包太好用
少是指数级的多 (Less is exponentially more)
因此 Go 社区诞生了很多衍生的定制语言
uGo 也是凹语言的起点

未来 10 年, 国内的 Gopher 可以 Go 的更远

µGo 例子

µGo 是 Go 语言的子集(不含标准库部分), 可以直接作为Go代码编译执行.

func main() {
    for n := 2; n <= 30; n = n + 1 {
        var isPrime int = 1
        for i := 2; i*i <= n; i = i + 1 {
            if x := n % i; x == 0 {
                isPrime = 0
            }
        }
        if isPrime != 0 {
            println(n)
        }
    }
}

安装: go get github.com/wa-lang/ugo
执行: ugo run hello.ugo

Go编译器定制简介

自我介绍(chai2010)

主题大纲

主题大纲

最简编译器

编译器是什么

人肉编译器

Go程序替代人肉编译器

挑战: 继续前进一小步

编译器后门八卦

Reflections on Trusting Trust - 01 - 自重写程序

Reflections on Trusting Trust - 02 - 鸡和蛋问题

Reflections on Trusting Trust - 03 - 潜伏的后门

更多的自重写代码

Go和Rust的选择

Go 开发的编译器

Rust 开发的编译器

Go和Rust的选择

Go衍生的语言

Go衍生的语言

TinyGo的编译器架构

Go语法树

FileSet 文件集模型

全部的 Token 类型

表达式的语法树

语法解析器接口

方法声明的语法树结构

Go类型系统

Scope 词法域 - 01

Scope 词法域 - 02

Scope 词法域 - 03

Go类型检查

Go类型信息

SSA和LLVM

SSA 基本结构

Go AST 到 Go SSA - 01

Go AST 到 Go SSA - 02

Go AST 到 Go SSA - 03

Go SSA 的执行和再编译

µGo案例

为什么是 Go ?

µGo 例子

µGo 架构

参考链接

参考链接

感谢 Ian 推荐序

感谢 Ian 推荐序

Q&A

Thank you