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

5.3 if和for到LLIR汇编

本节将新的if和for语法树节点翻译到LLVM-IR，这样uGo就可以达到和图灵机等价的能力，可以实现素数列表的打印程序。

5.3.1 改进Scope处理

在之前的后端翻译程序中，enterScope和leaveScope分别对应Scope的进入和退出：

func (p *Compiler) enterScope() {
	p.scope = NewScope(p.scope)
}

func (p *Compiler) leaveScope() {
	p.scope = p.scope.Outer
}

在翻译可能产生新Scope的节点时，在翻译函数开始位置加入以下的代码处理Scope：

 func (p *Compiler) compileFunc(w io.Writer, file *ast.File, fn *ast.Func) {
 	p.enterScope()
	defer p.leaveScope()
	...
}

这样处理需要确保Scope的进入和退出次数完全匹配，对于从多层嵌套的内部Scope直接返回时，处理会显得繁琐。因此我们新增一个restoreScope辅助方法用于恢复前上下文环境的Scope：

func (p *Compiler) restoreScope(scope *Scope) {
	p.scope = scope
}

翻译函数的第一个语句就是通过defer确保函数退出时恢复到之前到Scope状态：

 func (p *Compiler) compileFunc(w io.Writer, file *ast.File, fn *ast.Func) {
 	defer p.restoreScope(p.scope)
 	p.enterScope()
	...
}

对于一些内部简单的Scope可以简化处理。

5.3.2 重构语句翻译

Compiler.compileStmt方法用于翻译语句，我们将每种语句翻译封装到一个独立的函数中。比如前一章已经支持的赋值语句：

func (p *Compiler) compileStmt(w io.Writer, stmt ast.Stmt) {
	switch stmt := stmt.(type) {
	...
	case *ast.AssignStmt:
		p.compileStmt_assign(w, stmt)
	...
	}
}

赋值语句的翻译代码和之前的处理思路一样：

func (p *Compiler) compileStmt_assign(w io.Writer, stmt *ast.AssignStmt) {
	...
	if stmt.Op == token.DEFINE {
		...
	}
	...
}

采用类似的结构我们就可以轻松增加if和for语句的翻译：

func (p *Compiler) compileStmt(w io.Writer, stmt ast.Stmt) {
	switch stmt := stmt.(type) {
	...
	case *ast.IfStmt:
		p.compileStmt_if(w, stmt)

	case *ast.ForStmt:
		p.compileStmt_for(w, stmt)
	...
	}
}

需要注意的是，compileStmt方法本身只翻译语句，并不直接关联Scope处理。

5.3.3 新运算符的翻译

在翻译if语句之前我们还需要先完成比较运算等新运算符的翻译，否则无法处理if的条件部分的表达式。

首先发言取模运算符：

func (p *Compiler) compileExpr(w io.Writer, expr ast.Expr) (localName string) {
	switch expr := expr.(type) {
	...
	case *ast.BinaryExpr:
		localName = p.genId()
		switch expr.Op {
		case token.MOD:
			fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
				localName, "srem", p.compileExpr(w, expr.X), p.compileExpr(w, expr.Y),
			)
			return localName

比如a%b对于LLVM的srem i32 %a, %b指令。

然后是比较运算符，比较指令可以参考 LLVM 的官方文档 https://llvm.org/docs/LangRef.html#icmp-instruction。比较运算符翻译如下：

		// https://llvm.org/docs/LangRef.html#icmp-instruction

		case token.EQL: // ==
			fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
				localName, "icmp eq", p.compileExpr(w, expr.X), p.compileExpr(w, expr.Y),
			)
			return localName
		case token.NEQ: // !=
			fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
				localName, "icmp ne", p.compileExpr(w, expr.X), p.compileExpr(w, expr.Y),
			)
			return localName
		case token.LSS: // <
			fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
				localName, "icmp slt", p.compileExpr(w, expr.X), p.compileExpr(w, expr.Y),
			)
			return localName
		case token.LEQ: // <=
			fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
				localName, "icmp sle", p.compileExpr(w, expr.X), p.compileExpr(w, expr.Y),
			)
			return localName
		case token.GTR: // >
			fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
				localName, "icmp sgt", p.compileExpr(w, expr.X), p.compileExpr(w, expr.Y),
			)
			return localName
		case token.GEQ: // >=
			fmt.Fprintf(w, "\t%s = %s i32 %v, %v\n",
				localName, "icmp sge", p.compileExpr(w, expr.X), p.compileExpr(w, expr.Y),
			)
			return localName
		}
		...
	}
}

比如a>=b被翻译为icmp sge i32 %a, %b指令。icmp表示整数的比较，sge表示有符号整数的大于和等于比较。

5.3.4 翻译if语句

现在可以翻译if语句了。if语句有一个可选的初始化语句，比如if x := 0; x > 0 {}语句的x对应一个新的Scope，因此需要先处理Scope：

func (p *Compiler) compileStmt_if(w io.Writer, stmt *ast.IfStmt) {
	defer p.restoreScope(p.scope)
	p.enterScope()

在翻译前需要根据if语句的特点构造几个Label位置。我们将if x := 0; x > 0 {}语句重写为以下形式：

if_init:
x := 0

if_cond:
cond := x > 0

if_body:
{ ... }
if_end:

通过4个跳转Label分割if语句的不同部分，对应以下的翻译语句：

	ifPos := fmt.Sprintf("%d", p.posLine(stmt.If))
	ifInit := p.genLabelId("if.init.line" + ifPos)
	ifCond := p.genLabelId("if.cond.line" + ifPos)
	ifBody := p.genLabelId("if.body.line" + ifPos)
	ifEnd := p.genLabelId("if.end.line" + ifPos)

有了Label之后就可以开始翻译if语句了。

根据LLVM-IR的语法要求，每个Label对应的语句块必须有一个终结语句，是直接退出当前函数或者是跳转到其他的语句块。因此为了确保能够终结翻译if语句之前的语句块，我们在当前的指令之上添加一个br跳转指令，跳转的目标是if语句的开头。添加以下翻译代码：

	// br if.init
	fmt.Fprintf(w, "\tbr label %%%s\n", ifInit)

然后就可以开始进入if初始化语句的翻译：

	// if.init
	{
		fmt.Fprintf(w, "\n%s:\n", ifInit)
		if stmt.Init != nil {
			p.compileStmt(w, stmt.Init)
		}
	}

首先定义初始化语句对应的Label，然后如果有初始化语句则递归调用compileStmt翻译其中的赋值语句。需要注意的是compileStmt语句中如果涉及新的命名变量等对象，都是保存在当前的Scope下（但是不是if的body对应的Scope）。

然后是条件部分的翻译（条件部分不需要打开新的Scope空间）：

	// br if.cond
	fmt.Fprintf(w, "\tbr label %%%s\n", ifCond)

	// if.cond
	{
		fmt.Fprintf(w, "\n%s:\n", ifCond)
		condValue := p.compileExpr(w, stmt.Cond)
		fmt.Fprintf(w, "\tbr i1 %s , label %%%s, label %%%s\n", condValue, ifBody, ifEnd)
	}

条件部分的翻译是通过compileExpr翻译方法完成。当条件中遇到变量名时，会从当前的Scope查询变量。然后通过一个br终结前初始化语句块，跳转的目标是ifCond对应条件判断部分。

处理完条件后，就是if的body部分的翻译：

	// if.body
	func() {
		defer p.restoreScope(p.scope)
		p.enterScope()

		fmt.Fprintf(w, "\n%s:\n", ifBody)
		p.compileStmt(w, stmt.Body)
	}()

放在闭包函数处理的原因是可以方便通过defer p.restoreScope(p.scope)方式管理嵌套的Scope。然后通过compileStmt翻译函数递归翻译if的语句部分。

最后是终结if的翻译工作：

	// br if.end
	fmt.Fprintf(w, "\tbr label %%%s\n", ifEnd)

	// end
	fmt.Fprintf(w, "\n%s:\n", ifEnd)

也是通过br终结当前块，然后定义新的ifEnd用于后续正常语句翻译需要的Label。

5.3.5 翻译for语句

for语句本质上可以通过if和br语句的组合构造而来，for语句的翻译也是同样的思路。先将for x := 0; x < 10; x = x + 1 { body }改成以下形式：

for_init:
x := 0;

for_cond:
x < 10

for_post:
x = x + 1

for_body:
body

for_end:

其中for_init和for_body可能产生新的变量，因此需要处理Scope（通过闭包函数处理）。通过以下代码产生Label：

func (p *Compiler) compileStmt_for(w io.Writer, stmt *ast.ForStmt) {
	defer p.restoreScope(p.scope)
	p.enterScope()

	forPos := fmt.Sprintf("%d", p.posLine(stmt.For))
	forInit := p.genLabelId("for.init.line" + forPos)
	forCond := p.genLabelId("for.cond.line" + forPos)
	forPost := p.genLabelId("for.post.line" + forPos)
	forBody := p.genLabelId("for.body.line" + forPos)
	forEnd := p.genLabelId("for.end.line" + forPos)

	...
}

参考if语句的翻译思路，先翻译for.init部分：

	// br for.init
	fmt.Fprintf(w, "\tbr label %%%s\n", forInit)

	// for.init
	fmt.Fprintf(w, "\n%s:\n", forInit)
	if stmt.Init != nil {
		p.compileStmt(w, stmt.Init)
	}

对比可以发现翻译的代码几乎和if的init部分完全一样！然后是条件部分的翻译：

	// br for.cond
	fmt.Fprintf(w, "\tbr label %%%s\n", forCond)

	// for.cond
	fmt.Fprintf(w, "\n%s:\n", forCond)
	if stmt.Cond != nil {
		condValue := p.compileExpr(w, stmt.Cond)
		fmt.Fprintf(w, "\tbr i1 %s , label %%%s, label %%%s\n", condValue, forBody, forEnd)
	} else {
		fmt.Fprintf(w, "\tbr label %%%s\n", forBody)
	}

条件部分的翻译依然几乎和if语句的处理完全一样：如果条件满足就跳转到forBody，否则跳转到forEnd。细微的差别是for语句条件是可选的，其终结语句并不一定总是产生，因此对于缺省的真条件在else分支中处理。

然后是for语句的body部分：

	// for.body
	func() {
		defer p.restoreScope(p.scope)
		p.enterScope()

		fmt.Fprintf(w, "\n%s:\n", forBody)
		p.compileStmt(w, stmt.Body)
	}()

for语句的body和if语句的body的翻译也几乎是一样的。

下面处理for语句的post部分：

	// br for.post
	fmt.Fprintf(w, "\tbr label %%%s\n", forPost)

	// for.post
	{
		fmt.Fprintf(w, "\n%s:\n", forPost)
		if stmt.Post != nil {
			p.compileStmt(w, stmt.Post)
		}

		// br for.cond
		fmt.Fprintf(w, "\tbr label %%%s\n", forCond)
	}

for对应的LLVM的块语句的终结语句不是退出循环，而是需要跳转到post循环变量变化的部分。post语句完成之后再跳转到forCond对应到条件判断部分。

最后依然是for语句翻译的终结处理：

	// br for.end
	fmt.Fprintf(w, "\tbr label %%%s\n", forEnd)

	// end
	fmt.Fprintf(w, "\n%s:\n", forEnd)

也是通过br终结当前块，然后定义新的forEnd用于后续正常语句翻译需要的Label。

5.3.6 打印素数列表

现在已经完成了if和for的翻译工作，我们准备以下的素数列表测试代码：

package main

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 run main.go run ./_examples/prime.ugo
2
3
5
7
11
13
17
19
23

结果正常。

µGo语言实现