KusonStack一站式可编程配置技术栈(Go): https://github.com/KusionStack/kusion
KCL 配置编程语言(Rust): https://github.com/KusionStack/KCLVM
凹语言™: https://github.com/wa-lang/wa

3.2 AST到LLVM汇编

在前一节我们已经采用AST形式编写了一个最小µGo程序，本节我们尝试将这个AST翻译到LLVM汇编程序。

3.2.1 对应的LLVM汇编程序

我们已经了解了AST的数据结构，在翻译前我们还需要明确要输出的汇编代码的形式。只有先在大脑人肉完成翻译工作后，才真正好通过程序实现自动化的翻译。

结合第二章表达式的内容，可以想象输出以下的汇编程序：

declare i32 @ugo_builtin_exit(i32)

define i32 @ugo_main_main() {
	%t0 = add i32 0, 40    ; t0 = 40
	%t1 = add i32 0, 2     ; t1 = 2
	%t2 = add i32 %t0, %t1 ; t2 = t1 + t1
	call i32(i32) @ugo_builtin_exit(i32 %t2)
	ret i32 0
}

第一句是通过declare声明@ugo_builtin_exit内置函数（稍后通过其他工具生成），其作用是将一个整数参数作为退出码退出程序。然后@ugo_main_main是µGo的main包中的main函数输出的LLVM对应的函数，并在开头增加了ugo_前缀。函数体则是通过计算一个表达式，然后作为参数调用µGo的exit内置函数对应的代码。

要执行该程序需要在main入口函数调用@ugo_main_main函数：

define i32 @main() {
	call i32() @ugo_main_main()
	ret i32 0
}

以上这2段代码就是我们的编译器需要生成的汇编程序。

3.2.2 准备`@ugo.builtin.exit`内置函数

为了简单，我们采用C语言实现µGo内置的@ugo_builtin_exit函数：

// builtin.c
extern int exit(int);

int ugo_builtin_exit(int x) {
	exit(x);
	return 0;
}

然后用clang -S -emit-llvm builtin.c将C代码转化为LLVM汇编语言格式。输出的builtin.ll文件如下：

declare void @exit(i32)

define i32 @ugo_builtin_exit(i32) {
  %2 = alloca i32, align 4
  store i32 %0, i32* %2, align 4
  %3 = load i32, i32* %2, align 4
  %4 = call i32 @exit(i32 %3)
  unreachable
}

然后结合前面编译器将要生成的main.ll程序，用clang命令再编译连接执行：

$ clang builtin.ll main.ll
$ ./a.out
$ echo $?
42

验证一切正常之后，我们就可以开始尝试用程序生成main.ll了。

3.2.3 构造`compiler.Compiler`对象

编译器的代码放在compiler包，其中Compiler对象提供一个编译方法：

type Compiler struct{}

func (p *Compiler) Compile(f *ast.File) string {
	var buf bytes.Buffer

	p.genHeader(&buf, file)
	p.compileFile(&buf, file)
	p.genMain(&buf, file)

	return buf.String()
}

参数是输入的ast.File，对应µGo程序的AST。其中p.genHeader调用用于生成内置函数的声明，p.compileFile则将µGo程序编译为LLVM汇编，最后p.genMain将main.main函数挂到入口的main函数。

3.2.4 内置函数声明和入口代码生成

内置函数的声明和入口函数的定义均在builtin包定义：

package builtin

const Header = `
declare i32 @ugo_builtin_exit(i32)
`

const MainMain = `
define i32 @main() {
	call i32() @ugo_main_main()
	ret i32 0
}
`

对应的编译函数实现：

package compiler

import (
	"github.com/wa-lang/ugo/builtin"
)

func (p *Compiler) genHeader(w io.Writer, file *ast.File) {
	fmt.Fprintf(w, "; package %s\n", file.Pkg.Name)
	fmt.Fprintln(w, builtin.Header)
}

func (p *Compiler) genMain(w io.Writer, file *ast.File) {
	if file.Pkg.Name != "main" {
		return
	}
	for _, fn := range file.Funcs {
		if fn.Name == "main" {
			fmt.Fprintln(w, builtin.MainMain)
			return
		}
	}
}

genHeader方法首先生成注释说明当前边缘的源文件信息，然后输出内置函数的声明。genMain函数则是针对main.main输出main入口函数。

3.2.5 编译文件

因为目前的程序比较简单，AST中只有函数。compileFile实现如下：

func (p *Compiler) compileFile(w io.Writer, file *ast.File) {
	for _, fn := range file.Funcs {
		p.compileFunc(w, file, fn)
	}
}

只是简单遍历file.Funcs包含的每个函数，然后调用p.compileFunc编译函数。

p.compileFunc实现如下：

func (p *Compiler) compileFunc(w io.Writer, file *ast.File, fn *ast.Func) {
	if fn.Body == nil {
		fmt.Fprintf(w, "declare i32 @ugo_%s_%s() {\n", file.Pkg.Name, fn.Name)
		return
	}

	fmt.Fprintf(w, "define i32 @ugo_%s_%s() {\n", file.Pkg.Name, fn.Name)
	p.compileStmt(w, fn.Body)

	fmt.Fprintln(w, "\tret i32 0")
	fmt.Fprintln(w, "}")
}

如果函数没有Body，则产生函数的声明，否则则输出完整的函数定义。函数的定义对应一个块语句，通过p.compileStmt函数完成编译。输出的函数名字做了简单的名字修饰——增加了当前包的名字。

3.2.6 编译语句

语句是编程语言中最有价值的部分，比如if、for这些都是语句。目前的程序只有块和表达式两种语句，compileStmt实现如下：

func (p *Compiler) compileStmt(w io.Writer, stmt ast.Stmt) {
	switch stmt := stmt.(type) {
	case *ast.BlockStmt:
		for _, x := range stmt.List {
			p.compileStmt(w, x)
		}
	case *ast.ExprStmt:
		p.compileExpr(w, stmt.X)

	default:
		panic("unreachable")
	}
}

其实函数的Body就是一个*ast.BlockStmt，只要针对其中的每个语句再次递归调用p.compileStmt编译即可。如果是普通的表达式语句，则调用p.compileExpr编译表达式。

3.2.7 编译表达式

我们已经在第二章展示过如何编译加减乘除构成的表达式，现在的表达式则增加了一个函数调用，但是实现的方式依然相似。

调套表达式的特点是每个节点最多产生一个值（不返回或返回多个值的一般不会出现在前套的表达式中，只需要特化处理即可），只需要针对每个表达式节点类型分别处理：

func (p *Compiler) compileExpr(w io.Writer, expr ast.Expr) (localName string) {
	switch expr := expr.(type) {
	case *ast.Number:
		// %t1 = add i32 0, x; x
		return `%t1`
	case *ast.BinaryExpr:
		// %t1 = bin_op i32 x, y; x+y
		return `%t1`
	case *ast.UnaryExpr:
		// %t1 = sub i32 0, x; -x, or x
		return `%t1`
	case *ast.ParenExpr:
		// %t1 = %t0; (x) -> x
		return `%t1`
	case *ast.CallExpr:
		// %t1 = call i32(i32) func(i32 %x)
		return `%t1`
	}
	panic("unreachable")
}

普通的数字面值、二元、一元和小括弧和第2章产生的方式类似：

func (p *Compiler) compileExpr(w io.Writer, expr ast.Expr) (localName string) {
	switch expr := expr.(type) {
	case *ast.Number:
		localName = p.genId()
		fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
			localName, "add", `0`, expr.Value,
		)
		return localName
	case *ast.BinaryExpr:
		localName = p.genId()
		switch expr.Op.Type {
		case token.ADD:
			fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
				localName, "add", p.compileExpr(w, expr.X), p.compileExpr(w, expr.Y),
			)
			return localName
		case token.SUB:
			// ...
		case token.MUL:
			// ...
		case token.DIV:
			// ...
		}
	case *ast.UnaryExpr:
		if expr.Op.Type == token.SUB {
			localName = p.genId()
			fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
				localName, "sub", `0`, p.compileExpr(w, expr.X),
			)
			return localName
		}
		return p.compileExpr(w, expr.X)
	case *ast.ParenExpr:
		return p.compileExpr(w, expr.X)

	// ...

函数调用是新加的，实现如下：

	case *ast.CallExpr:
		// call i32(i32) @ugo_builtin_exit(i32 %t2)
		localName = p.genId()
		fmt.Fprintf(w, "\t%s = call i32(i32) @ugo_builtin_%s(i32 %v)\n",
			localName, expr.FuncName, p.compileExpr(w, expr.Args[0]),
		)
		return localName
	}

	panic("unreachable")
}

为了简化函数的返回值和参数类型目前是固定的，函数的名字增加一个@ugo_builtin_前缀。到此我们基本完成了编译器后端的基础工作。

3.2.8 组装编译器

现在我们可以构造一个测试程序，将AST和编译函数串起来：

package main

import (
	"fmt"

	"github.com/wa-lang/ugo/ast"
	"github.com/wa-lang/ugo/compiler"
)

func main() {
	ast := &ast.File{} // 用ch3.1内容填充
	ll := new(compiler.Compiler).Compile(ast)
	fmt.Print(ll)
}

输出的LL汇编程序：

; package main

declare i32 @ugo_builtin_exit(i32)

define i32 @ugo_main_main() {
	%t2 = add i32 0, 40
	%t3 = add i32 0, 2
	%t1 = add i32 %t2, %t3
	%t0 = call i32(i32) @ugo_builtin_exit(i32 %t1)
	ret i32 0
}

define i32 @main() {
	call i32() @ugo_main_main()
	ret i32 0
}

这样我们就实现了自动翻译的编译器程序。

µGo语言实现