252 lines
15 KiB
Markdown
252 lines
15 KiB
Markdown
# 18｜生成本地代码第3关：实现完整的功能
|
||
|
||
你好，我是宫文学。
|
||
|
||
到目前为止，我们已经把挑战生成本地代码的过程中会遇到的各种难点都解决了，也就是说，我们已经实现基本的寄存器分配算法，并维护好了栈桢。在这个基础上，我们只需要再实现其他的语法特性就行了。
|
||
|
||
所以，在今天这节课，我们要让编译器支持条件语句和循环语句。这样的话，我们就可以为前面一直在使用的一些例子，比如生成斐波那契数列的程序，生成本地代码了。然后，我们可以再比较一次不同运行时机制下的性能表现。
|
||
|
||
还记得吗？我们在前面已经分别使用了AST解释器、基于JavaScript的虚拟机和基于C语言的虚拟机来生成斐波那契数列。现在我们就看看用我们自己生成的本地代码，性能上是否会有巨大的变化。
|
||
|
||
在这个过程中，我们还会再次认识CFG这种数据结构，也会考察一下如何支持一元运算，让我们的语言特性更加丰富。
|
||
|
||
那首先我们来看一下，如何实现if语句和for循环语句。
|
||
|
||
## 支持if语句和for循环语句
|
||
|
||
在前面的课程中，我们曾经练习过为if语句和for循环语句生成字节码。不知道你还记不记得，其中的难点就是生成跳转指令。在今天这节课，我们会完成类似的任务，但采用的是一个稍微不同的方法。
|
||
|
||
我们还是先来研究一下if语句，看看针对if语句，编译器需要生成什么代码。我们采用下面一个C语言的示例程序，更详细的代码你可以参见代码库中的[if.c](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/if.c)：
|
||
|
||
```plain
|
||
int foo(int a){
|
||
if (a > 10)
|
||
return a + 8;
|
||
else
|
||
return a - 8;
|
||
}
|
||
|
||
```
|
||
|
||
C语言的编译器针对这段示例程序，会生成下面的汇编代码（参见代码库中的[if.s](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/if.s)），我对汇编代码进行了整理，并添加了注释。
|
||
|
||
这段汇编代码是未经优化的。不过，我相信你经过前面课程的训练，应该可以看出来很多可以用手工优化的地方。不过现在我们关注的重点是跳转指令，所以你可以重点看一下代码中的cmpl指令、jle指令和jmp指令。
|
||
|
||
|
||
|
||
我们现在来分析一下。第一个cmpl指令的作用是比较两个整数的大小。在这个例子中，是比较a和10的大小，计算结果会设置到eflags寄存器中相应的标志位。
|
||
|
||
第二个jle指令，它的作用是根据eflags寄存器中标志位决定是否进行跳转，如果发现是小于等于的结果，那么就进行跳转，这里是跳转到else块。如果是大于呢，就会顺着执行下面的指令，也就是if块的内容。
|
||
|
||
最后我们来看jmp指令，这是无条件跳转指令，相当于我们前面学过的字节码中的goto指令。
|
||
|
||
认识了这三个指令以后，我们就知道程序的跳转逻辑了。在这个C语言的示例程序中，一共有四个基本块，我把它们之间的跳转关系画成了图，可以更加直观一些：
|
||
|
||
|
||
|
||
在分析清楚了整个思路以后，为if语句生成本地代码的逻辑也就很清楚了，我们现在就动手吧。完整的代码你可以查看代码库里的[visitIfStmt方法](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/asm_x86-64.ts#L488)，我这里挑重点和你分析一下。
|
||
|
||
首先，我们要生成4个基本块：
|
||
|
||
```plain
|
||
//条件
|
||
let bbCondition = this.getCurrentBB();
|
||
let compOprand = this.visit(ifStmt.condition) as Oprand;
|
||
|
||
//if块
|
||
let bbIfBlcok = this.newBlock();
|
||
this.visit(ifStmt.stmt);
|
||
|
||
//else块
|
||
let bbElseBlock:BasicBlock|null = null
|
||
if (ifStmt.elseStmt != null){
|
||
bbElseBlock = this.newBlock();
|
||
this.visit(ifStmt.elseStmt);
|
||
}
|
||
|
||
//最后，要新建一个基本块,用于If后面的语句。
|
||
let bbFollowing = this.newBlock();
|
||
|
||
```
|
||
|
||
接着，我们要添加跳转指令，在4个基本块之间建立正确的跳转关系。这其中，最关键的就是我们怎么来为基本块0，也就是if条件所在的基本块生成跳转指令。
|
||
|
||
你会看到，在[visitBinary](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/asm_x86-64.ts#L624)函数中，我们为if条件中的比较表达式生成了一条cmpl指令。那这个时候，visitBinary为上级调用者返回什么操作数呢？
|
||
|
||
回忆一下，在上一节课，当我们为其他表达式生成指令之后，会返回一个操作数，代表该指令的执行结果会放在该操作数中，这个操作数通常会是一个逻辑寄存器。不过，cmpl指令跟加减乘除等指令不同，该指令不会改变目标寄存器的值，而是改变eflags寄存器的值。
|
||
|
||
为了体现这个逻辑，我就使用了一种新的操作数类型，也就是flag类型。这样的话，比较运算就返回一个flag类型的操作数就好了，而且这个操作数里也会记录下比较运算符。
|
||
|
||
```plain
|
||
case Op.G:
|
||
case Op.L:
|
||
case Op.GE:
|
||
case Op.LE:
|
||
case Op.EQ:
|
||
case Op.NE:
|
||
insts.push(new Inst_2(OpCode.cmpl, right, dest));
|
||
dest = new Oprand(OprandKind.flag, this.getOpsiteOp(bi.op));
|
||
break;
|
||
|
||
```
|
||
|
||
现在，根据这个操作数中记录的比较运算符，我们可以生成正确的跳转指令了。比如，如果比较运算符是大于，那么生成的跳转指令就是小于等于，也就是jle。跳转到哪里呢？跳转到基本块2，对应的指令是“jle LBB0\_2”。其中，0\_2代表第0个函数的第2个基本块。
|
||
|
||
不过，在这个阶段，我并没有基于计算出这个标签值来，而是采用了类型为“bb”的一个操作数，指向目标基本块即可。接下来，我们会再通过一个[Lower过程](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/asm_x86-64.ts#L1329)，计算出每个基本块准确的标签值。在这里，我们又一次使用了抽象类型的操作数，这会使指令生成过程得到简化。
|
||
|
||
这里你要注意，在编译器生成基本块的过程中，有些基本块可能是空的块，也就是块中没有代码。这也很容易理解，因为有些Block可能就是空的。那么在Lower的过程中，这些空块也会被去除掉。
|
||
|
||
好了，到目前为止，我们已经能够为if语句正确的生成指令了。
|
||
|
||
**那接下来，我们为for循环语句生成指令的要点也是类似的，都是生成多个基本块，并且用跳转指令进行正确的拼接。**你可以参考一下代码库里的[example\_for.ts](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/example_for.ts)。
|
||
|
||
我这里也摘取了一个关键的示例程序，我们来简单分析一下：
|
||
|
||
```plain
|
||
let sum:number = 0;
|
||
|
||
for (let i:number =0; i<10; i++){
|
||
sum = sum + i;
|
||
}
|
||
|
||
println(sum);
|
||
|
||
```
|
||
|
||
这个示例程序的CFG是这样的（基于[for.s](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/for.s)生成）：
|
||
|
||
|
||
|
||
你可以多熟悉一下这些if和for循环结构所对应的CFG图，因为我们后面在学习寄存器分配算法的时候，还要跟这样的CFG打交道。
|
||
|
||
在实现for循环语句的过程中，我们还会碰到一个小的技术点，也就是一元运算。一元运算，特别是++和- -这样的运算符，实现起来有点特殊，也值得我们稍微探讨一下。
|
||
|
||
## 实现一元运算
|
||
|
||
在for循环语句中，我们通常都会使用一个递增变量。比如在[example\_for.ts](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/example_for.ts)中，你就会看到i++这种表达式。
|
||
|
||
对于i++来说，我们需要返回i的当前值，然后再让i的值加1。但对于++i来说，则是先让i的值加1，然后返回增加后的值。
|
||
|
||
这里的具体实现你可以参照代码库里[visitUnary](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/asm_x86-64.ts#L744)方法，下面我摘取了其中处理++和- -的代码片段，我们来分析一下。
|
||
|
||
```plain
|
||
let oprand = this.visit(u.exp) as Oprand;
|
||
|
||
//用作返回值的Oprand
|
||
let result:Oprand = oprand;
|
||
|
||
//++和--
|
||
if(u.op == Op.Inc || u.op == Op.Dec){
|
||
let tempVar = new Oprand(OprandKind.varIndex, this.allocateTempVar());
|
||
insts.push(new Inst_2(OpCode.movl, oprand, tempVar));
|
||
if(u.isPrefix){ //前缀运算符
|
||
result = tempVar;
|
||
}
|
||
else{ //后缀运算符
|
||
//把当前操作数放入一个临时变量作为返回值
|
||
result = new Oprand(OprandKind.varIndex, this.allocateTempVar());
|
||
insts.push(new Inst_2(OpCode.movl, oprand, result));
|
||
this.s.deadTempVars.push(tempVar.value);
|
||
}
|
||
//做+1或-1的运算
|
||
let opCode = u.op == Op.Inc ? OpCode.addl : OpCode.subl;
|
||
insts.push(new Inst_2(opCode, new Oprand(OprandKind.immediate,1), tempVar));
|
||
insts.push(new Inst_2(OpCode.movl, tempVar, oprand));
|
||
}
|
||
|
||
```
|
||
|
||
对于++i来说，计算逻辑大致如下面的伪代码。也就是我们先申请一个临时变量t1，把t1加1，再赋给i，最后返回t1。这个时候返回值就是i+1。
|
||
|
||
```plain
|
||
t1 = i
|
||
t1 = t1+1
|
||
i = t1
|
||
return t1
|
||
|
||
```
|
||
|
||
但对于i++来说，它的计算逻辑就要多引入一个临时变量t2了，并且一开始要让t1和t2都等于i。t1的作用，仍然是i增加了1，但返回值却是t2，也就是i原来的值。
|
||
|
||
```plain
|
||
t1 = i
|
||
t2 = i
|
||
t1 = t+1
|
||
i = t1
|
||
return t2;
|
||
|
||
```
|
||
|
||
除了++和- -外，还有其他的一元运算符，如+和-。
|
||
|
||
对+号的处理比较简单，实际上我们直接忽略就行了。其实，忽略+号的这个动作甚至不用等到生成汇编代码的环节，我们应该在代码优化的环节就把它去掉。
|
||
|
||
对于-号，它的计算逻辑则是用0去减当前的值。在这个过程中，我们仍然需要用到临时变量，你可以看看下面这个代码：
|
||
|
||
```plain
|
||
//-
|
||
else if (u.op == Op.Minus){
|
||
let tempVar = new Oprand(OprandKind.varIndex, this.allocateTempVar());
|
||
//用0减去当前值
|
||
insts.push(new Inst_2(OpCode.movl, new Oprand(OprandKind.immediate,0), tempVar));
|
||
insts.push(new Inst_2(OpCode.subl, oprand, tempVar));
|
||
result = tempVar;
|
||
if (this.isTempVar(oprand)){
|
||
this.s.deadTempVars.push(oprand.value);
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
好了，在实现了if语句和for循环语句以后，我们几乎已经完成生成本地代码的所有工作了。那现在又到了检验我们工作成果的时候了，我们再做一次性能比拼，看看这一次，我们的程序性能有多高。
|
||
|
||
## 再一次进行性能比拼
|
||
|
||
我们还是用斐波那契数列的例子来做测试，你用make example\_fibo命令就可以编译并生成汇编代码和可执行文件，并且能够打印出每次执行所花费的时间。你还可以用make fibo命令编译C语言版本的示例程序，用来做性能比较。
|
||
|
||
我把比较结果放在下面的表格中，这次，我们只比较C语言的栈机和本地代码版就可以了，因为本地代码版速度实在是快太多了，以至于跟AST解释器和TypeScript版的栈机做比较已经没有太大意义了。
|
||
|
||
|
||
|
||
从表格可以看出，本地代码版的速度基本上是栈机版的20多倍，可以说性能有了极大的提升。
|
||
|
||
另外，我们还把用纯C语言写的版本（[fibo.c](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/fibo.c)）的性能加到了表格里，作为比较。我还绘制了曲线图。
|
||
|
||
|
||
|
||
你可能不放大这张图仔细观察，还注意不到本地代码的曲线在哪里。因为我们生成的本地代码和C语言生成的本地代码，性能上的差异已经比较小了，不过也还是有一小点差异的。我把它俩的对比又单独画了一张图，你再看一下。
|
||
|
||
|
||
|
||
那这种差异来自于哪里呢？我们不是都用了相同的寄存器分配算法吗？
|
||
|
||
如果你比较一下二者的汇编代码，还是能看出一小点差别来的。**最主要的差别，就在于如何处理Caller需要保护的寄存器。**
|
||
|
||
在我们这门课当前使用的算法里，我们记录了在一个函数中，如果有Caller保护的寄存器被使用了，那么我们在每次调用函数的时候，要把所有被使用的这些寄存器都保存到内存里。
|
||
|
||
这里有一些浪费。因为其实有些寄存器不再用了，也就意味着它不再需要保护了。如果我们进一步优化一下的话，这里其实需要一个算法，来检测哪些临时变量仍然是在使用中的，然后保护它们正在使用的寄存器就可以了。
|
||
|
||
我们在下节课里，在实现升级版的寄存器分配算法的时候，就会做变量活跃性的检测。所以，这种优化我们会在下一节课一并实现。
|
||
|
||
## 课程小结
|
||
|
||
这就是今天这节课的所有内容了。这节课的内容相对简单，你只需要记住以下几个知识点就可以了：
|
||
|
||
首先，我们又重温了一下如何生成跳转指令。对于条件跳转来说，首先要把两个操作数做比较，比较结果会被设置到eflags寄存器中。这样，我们后面的条件跳转指令就可以根据eflags寄存器的内容来做跳转了。并且，对于条件跳转，我们再一次看到了一个现象，就是生成的跳转指令跟比较操作符恰好是相反的。对于>号的比较运算符，生成的反倒是jle指令，也就是如果小于等于，则跳转。
|
||
|
||
不过，我们目前的if条件仍然只支持一个简单的条件表达式，还不支持把多个条件表达式组合成一个逻辑表达式的情况。你有兴趣的话，可以研究一下怎么扩展这方面的特性。
|
||
|
||
另外，对于一元运算，我们也稍微展开讲了一下。你要注意，特别是针对i++这样的表达式，怎样实现不同的当前值和返回值
|
||
|
||
最后，我们又一次用斐波那契数列做了一下性能的对比测试。相比C语言的栈机版本，这次我们的性能提高了20多倍。看来，我们这好几节课努力学习底层架构和汇编代码的相关技术，还是很值得的。
|
||
|
||
掌握了我们当前的生成汇编代码的技术，其实你已经可以去实现很多有用的底层功能了，比如做一个图形化的开发工具，用来生成能够在物联网设备、自动设备上运行的机器码。
|
||
|
||
不过，我们当然不会满足于现在的成绩。下节课，我们将升级寄存器分配算法，继续提升程序的性能！
|
||
|
||
## 思考题
|
||
|
||
今天这节课里，我们画了两个CFG的图。CFG是一种图的数据结构。那么，我们例子中的两个图有什么特点呢？这个特点对于图的处理有什么好处呢？
|
||
|
||
欢迎在留言区分享你的看法。由于我们后面会经常用到图的数据结构，所以你现在要开始把有关图的算法熟悉起来了！我是宫文学，我们下节课见。
|
||
|