《Go语言定制指南》:本站前置篇:《Go语言定制指南》-解析篇
一、类型检查
主流的编译器前端遵循词法解析、语法解析、语义解析等流程,然后才是基于中间表示的层层优化并最终产生目标代码。go/types
包实现对语法树的检查功能。
1.1 语法错误
1
2
3
4
5
|
package pkg
func hello() {
var _ = "a" + 1
}
|
错误类型相加
1.2 go/types包
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
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 pkg
func hello() {
var _ = "a" + 1
}
`
|
通过new(types.Config).Check
函数检查语法树中的语义错误。
1
|
func (conf *Config) Check(path string, fset *token.FileSet, files []*ast.File, info *Info) (*Package, error)
|
参数含义:检查包的路径、全部的文件集合(用于解析文件名和行列号)、该包中所有文件对应的语法树、存储产生的分析结果。返回types.Package
对象
1
2
|
$ go run .
hello.go:4:10: cannot convert "a" (untyped string constant) to untyped int
|
1.3 跨包的类型检查
1
2
3
4
5
|
package main
import "math"
func main() {
var _ = "a" + math.Pi
}
|
go/parser
包只处理当前包, new(types.Config).Check
方式因不知道如何加载math包校验得到如下错误
1
|
hello.go:3:8: could not import math (Config.Importer not installed)
|
types.Config
对象的Importer成员负责导入依赖包,对于任何一个导入包都会调用Import方法加载导入信息,可使用importer.Default()
初始化
1
2
3
4
5
6
|
type Config struct {
Importer Importer
}
type Importer interface {
Import(path string) (*Package, error)
}
|
1
2
3
4
5
6
|
// import "go/importer"
conf := types.Config{Importer: importer.Default()}
pkg, err := conf.Check("hello.go", fset, []*ast.File{f}, nil)
if err != nil {
log.Fatal(err)
}
|
自己手动构造一个Importer实现替换默认的实现(默认实现包含标准库和用户的模块代码,还可能启动了CGO特性)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
type Program struct {
fs map[string]string
ast map[string]*ast.File
pkgs map[string]*types.Package
fset *token.FileSet
}
func NewProgram(fs map[string]string) *Program {
return &Program{
fs: fs,
ast: make(map[string]*ast.File),
pkgs: make(map[string]*types.Package),
fset: token.NewFileSet(),
}
}
func (p *Program) LoadPackage(path string) (pkg *types.Package, f *ast.File, err error) {
if pkg, ok := p.pkgs[path]; ok {
return pkg, p.ast[path], nil
}
f, err = parser.ParseFile(p.fset, path, p.fs[path], parser.AllErrors)
if err != nil {
return nil, nil, err
}
conf := types.Config{Importer: p} // 用 Program 作为包导入器
pkg, err = conf.Check(path, p.fset, []*ast.File{f}, nil)
if err != nil {
return nil, nil, err
}
p.ast[path] = f
p.pkgs[path] = pkg
return pkg, f, nil
}
func (p *Program) Import(path string) (*types.Package, error) {
if pkg, ok := p.pkgs[path]; ok {
return pkg, nil
}
pkg, _, err := p.LoadPackage(path)
return pkg, err
}
|
fs
表示每个包对应的源码字符串,ast
表示每个包对应的语法树,pkgs
表示经过语义检查的包对象,fset
表示文件的位置信息
- Import方法执行时,当
pkgs
成员没有包信息时,通过LoadPackage方法加载
使用实例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
func main() {
prog := NewProgram(map[string]string{
"hello": `
package main
import "math"
func main() { var _ = 2 * math.Pi }
`,
"math": `
package math
const Pi = 3.1415926
`,
})
_, _, err := prog.LoadPackage("math")
if err != nil {
log.Fatal(err)
}
pkg, f, err := prog.LoadPackage("hello")
if err != nil {
log.Fatal(err)
}
}
|
二、语义信息
语义分析主要时根据名字确定对象的类型和值,分析表达式的类型和值。
2.1 名字空间
名字空间类似于一个容器,用于存放具名的对象。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
package main
import "fmt"
const Pi = 3.14
func main() {
for i := 2; i <= 8; i++ {
fmt.Printf("%d*Pi = %.2f\n", i, Pi*float64(i))
}
}
----
package fmt
func Printf(format string, a ...interface{}) (n int, err error) {
return
}
|
存在三个名字空间main
、fmt
和全局的宇宙空间types.Universe
,内置的println
/len
等具名对象都在宇宙空间中.
print、println、append、close、len、cap、bool、int、string
包内部的文件名字空间比较特殊,属于半封闭的名字空间。不同文件中导入包的符号时独立的,但是同一个包内的不同文件中新定义的具名对象必须在包一级是唯一的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
package main
import (
"go/ast"
"go/parser"
"go/token"
"go/types"
"log"
"os"
)
func init() {
log.SetFlags(0)
}
func main() {
prog := NewProgram(map[string]string{
"hello.go": `
package main
import "fmt"
const Pi = 3.14
func main() {
for i := 2; i <= 8; i++ {
fmt.Printf("%d*Pi = %.2f\n", i, Pi*float64(i))
}
}
`,
"fmt": `
package fmt
func Printf(format string, a ...interface{}) (n int, err error) {
return
}
`,
})
pkg, _, err := prog.LoadPackage("hello.go")
if err != nil {
log.Fatal(err)
}
pkg.Scope().WriteTo(os.Stdout, 0, true)
pkg.Scope().Parent().WriteTo(os.Stdout, 0, true)
}
type Program struct {
fs map[string]string
ast map[string]*ast.File
pkgs map[string]*types.Package
fset *token.FileSet
}
func NewProgram(fs map[string]string) *Program {
return &Program{
fs: fs,
ast: make(map[string]*ast.File),
pkgs: make(map[string]*types.Package),
fset: token.NewFileSet(),
}
}
func (p *Program) LoadPackage(path string) (pkg *types.Package, f *ast.File, err error) {
if pkg, ok := p.pkgs[path]; ok {
return pkg, p.ast[path], nil
}
f, err = parser.ParseFile(p.fset, path, p.fs[path], parser.AllErrors)
if err != nil {
return nil, nil, err
}
conf := types.Config{Importer: p}
pkg, err = conf.Check(path, p.fset, []*ast.File{f}, nil)
if err != nil {
return nil, nil, err
}
p.ast[path] = f
p.pkgs[path] = pkg
return pkg, f, nil
}
func (p *Program) Import(path string) (*types.Package, error) {
if pkg, ok := p.pkgs[path]; ok {
return pkg, nil
}
pkg, _, err := p.LoadPackage(path)
return pkg, err
}
|
pkg.Scope().WriteTo(os.Stdout, 0, true)
语句的作用时输出当前保重的名字空间信息,Go程序的每个包还有一个父名字空间可to过pkg.Scope().Parent()
获得,宇宙空间其实也是名字空间树的根名字空间,忽略的宇宙空间的输出信息
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
package "hello.go" scope 0xc0000733b0 {
. const hello.go.Pi untyped float
. func hello.go.main()
. hello.go scope 0xc0000734a0 {
. . package fmt
. . function scope 0xc000073a40 {
. . . for scope 0xc000073a90 {
. . . . var i int
. . . . block scope 0xc000073b30 {
. . . . }
. . . }
. . }
. }
}
universe scope 0xc0000720a0 {
. builtin append
. type bool
. type byte
. builtin cap
. builtin close
. builtin complex
...
}
|
2.2 整体架构
- 通过
types.Sizes
对象指定极其字的宽度和对齐大小;通过types.Importer
对象加载被导入的包
- 基于
types.Sizes
和types.Importer
对象初始化的types.Config
对象可以通过Check方法检查当前包的语义合法性。
- 检查完成之后,输出
*types.Package
和*types.Info
两个对象,前者表示经过验证的包(包路径。名字以及名字空间树等信息),后者表示当前包中的所有标识符信息和引用关系
三、静态单赋值形式
抽象语法树AST
-> 静态单赋值形式SSA
-> 解释执行
3.1 静态单赋值形式简介
SSA通过限制变量的状态变化(单次赋值约束)来简化编译器的优化工作,几乎所有主流的编译器和计时器都提供了对SSA的支持,是一种高效的代码优化技术。go/ssa
提供了SSA的支持。
3.2 生成静态单赋值
关键代码
1
2
3
4
5
|
var ssaProg = ssa.NewProgram(prog.fset, ssa.SanityCheckFunctions)
var ssaPkg = ssaProg.CreatePackage(pkg, []*ast.File{f}, info, true)
ssaPkg.Build()
ssaPkg.WriteTo(os.Stdout)
ssaPkg.Func("main").WriteTo(os.Stdout)
|
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
package main
import (
"go/ast"
"go/parser"
"go/token"
"go/types"
"log"
"os"
"golang.org/x/tools/go/ssa"
)
const src = `
package main
var s = "hello ssa"
func main() {
for i := 0; i < 3; i++ {
println(s)
}
}
`
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),
Implicits: make(map[ast.Node]types.Object),
Selections: make(map[*ast.SelectorExpr]*types.Selection),
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)
}
var ssaProg = ssa.NewProgram(fset, ssa.SanityCheckFunctions)
var ssaPkg = ssaProg.CreatePackage(pkg, []*ast.File{f}, info, true)
ssaPkg.Build()
ssaPkg.WriteTo(os.Stdout)
}
|
运行结果
1
2
3
4
5
|
package hello.go
func init func()
var init$guard bool
func main func()
var s string
|
其中init为包初始化构造,init$guard用于记录包初始化的完成状态
1
2
|
ssaPkg.Func("init").WriteTo(os.Stdout)
ssaPkg.Func("main").WriteTo(os.Stdout)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
# Name: hello.go.init
# Package: hello.go
# Synthetic: package initializer
func init():
0: entry P:0 S:2
t0 = *init$guard bool
if t0 goto 2 else 1
1: init.start P:1 S:1
*init$guard = true:bool
*s = "hello ssa":string
jump 2
2: init.done P:2 S:0
return
# Name: hello.go.main
# Package: hello.go
# Location: hello.go:6:6
func main():
0: entry P:0 S:1
jump 3
1: for.body P:1 S:1
t0 = *s string
t1 = println(t0) ()
t2 = t3 + 1:int int
jump 3
2: for.done P:1 S:0
return
3: for.loop P:2 S:2
t3 = phi [0: 0:int, 1: t2] #i int
t4 = t3 < 3:int bool
if t4 goto 1 else 2
|
3.3 静态单赋值解释执行
导入自定义runtime包,并转换为SSA形式最终生成SSA指令。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
package main
import (
"fmt"
"go/ast"
"go/parser"
"go/token"
"go/types"
"golang.org/x/tools/go/ssa"
"golang.org/x/tools/go/ssa/interp"
)
func main() {
prog := NewProgram(map[string]string{
"main": `
package main
func main() {
for i := 0; i < 3; i++ {
println(i, "hello chai2010")
}
}
`,
"runtime": `
package runtime
type errorString string
func (e errorString) RuntimeError() {}
func (e errorString) Error() string { return "runtime error: " + string(e) }
type Error interface {
error
RuntimeError()
}
`,
})
prog.LoadPackage("main")
prog.LoadPackage("runtime")
var ssaProg = ssa.NewProgram(prog.fset, ssa.SanityCheckFunctions)
var ssaMainPkg *ssa.Package
for name, pkg := range prog.pkgs {
ssaPkg := ssaProg.CreatePackage(pkg, []*ast.File{prog.ast[name]}, prog.infos[name], true)
if name == "main" {
ssaMainPkg = ssaPkg
}
}
ssaProg.Build()
exitCode := interp.Interpret(
ssaMainPkg, 0, &types.StdSizes{8, 8},
"main", []string{},
)
if exitCode != 0 {
fmt.Println("exitCode:", exitCode)
}
}
type Program struct {
fs map[string]string
ast map[string]*ast.File
pkgs map[string]*types.Package
infos map[string]*types.Info
fset *token.FileSet
}
func NewProgram(fs map[string]string) *Program {
return &Program{
fs: fs,
ast: make(map[string]*ast.File),
pkgs: make(map[string]*types.Package),
infos: make(map[string]*types.Info),
fset: token.NewFileSet(),
}
}
func (p *Program) LoadPackage(path string) (pkg *types.Package, f *ast.File, err error) {
if pkg, ok := p.pkgs[path]; ok {
return pkg, p.ast[path], nil
}
f, err = parser.ParseFile(p.fset, path, p.fs[path], parser.AllErrors)
if err != nil {
return nil, nil, 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),
Implicits: make(map[ast.Node]types.Object),
Selections: make(map[*ast.SelectorExpr]*types.Selection),
Scopes: make(map[ast.Node]*types.Scope),
}
conf := types.Config{Importer: p}
pkg, err = conf.Check(path, p.fset, []*ast.File{f}, info)
if err != nil {
return nil, nil, err
}
p.ast[path] = f
p.pkgs[path] = pkg
p.infos[path] = info
return pkg, f, nil
}
func (p *Program) Import(path string) (*types.Package, error) {
if pkg, ok := p.pkgs[path]; ok {
return pkg, nil
}
pkg, _, err := p.LoadPackage(path)
return pkg, err
}
|
1
2
3
|
0 hello chai2010
1 hello chai2010
2 hello chai2010
|
通过interp.Interpret
函数运行main包,第一个参数时SSA形式的main包,最后一个参数模拟命令行参数
四、凹语言
使用自定义的解释执行器解释执行SSA指令,暂不做解读
五、LLVM简介
5.1 背景介绍
把程序员生产的高级语言程序,翻译成硬件处理器可以识别的二进制指令流。
编译器的三段架构:
- 前端:接收程序员生产的源代码,进行词法、语法、语义分析,生成中间表示
- 中端:接收前端生成的中间表示,进行体系无关的优化
- 后端:将经过优化的中间表示生成最终的机器指令流,并可能做进一步体系相关的优化
5.2 常见LLVM指令
- 四则运算:add、sub、mul、sdiv、udiv
- 比较运算:icmp、fcmp
- 分支与循环:goto
- 基本块:_ifstart、_iftrue、_iffalse、_ifend