# 09｜基于TypeScript的虚拟机（二）：丰富特性，支持跳转语句 你好，我是宫文学。 在上一节课里，我们已经实现了一个简单的虚拟机。不过，这个虚拟机也太简单了，实在是不够实用啊。 那么，今天这节课，我们就来增强一下当前的虚拟机，让它的特性更丰富一些，也为我们后续的工作做好铺垫，比如用C语言实现一个更强的虚拟机。 我们在这一节课有两项任务要完成： 首先，要支持if语句和for循环语句。这样，我们就能熟悉与程序分支有关的指令，并且还能让虚拟机支持复杂一点的程序，比如我们之前写过的生成斐波那契数列的程序。 第二，做一下性能比拼。既然我们已经完成了字节码虚拟机的开发，那就跟AST解释器做一些性能测试，看看性能到底差多少。 话不多说，开干！首先，我们来实现一下if语句和for循环语句。而实现这两个语句的核心，就是要支持跳转指令。 ## 了解跳转指令 if语句和for循环语句，有一个特点，就是让程序根据一定的条件执行不同的代码。这样一个语法，比较适合我们人类阅读，但是对于机器执行并不方便。机器执行的代码，都是一条条指令排成的直线型的代码，但是可以根据需要跳转到不同的指令去执行。 针对这样的差异，编译器就需要把if和for这样结构化编程的代码，转变成通过跳转指令跳转的代码，其中的关键是**计算出正确的跳转地址**。 我们举个例子来说明一下，下面是我用Java写的一个示例程序，它有一个if语句。 ```plain public static int foo3(int a){ int b; if (a > 10){ b = a + 8; } else{ b = a - 8; } return b; } ``` 我们先用javac命令编译成.class文件，然后再用javap命令以文本方式显示生成的字节码： ![图片](https://static001.geekbang.org/resource/image/31/5c/312670050f96b2663750b184f9bc095c.jpg?wh=1310x978) 我主要是想通过这个示例程序，给你展现两条跳转指令。 **一条是if\_icmple，它是一条有条件的跳转指令。**它给栈顶的两个元素做<=（less equal，缩写为le）运算。如果计算结果为真，那么就跳转到分支地址14。 ![图片](https://static001.geekbang.org/resource/image/ed/1d/edb202fcbb86e454362b369c21da411d.png?wh=808x286) 你可能会发现一个问题，为什么我们的源代码是>号，翻译成字节码却变成了<=号了呢？没错，虽然符号变了，但其实我们的语义并没有发生变化。 我给你分析一下，在源代码里面，程序用>号计算为真，就执行if下面的块；那就意味着如果>号计算为假，或者说<=号为真，则跳转到else下面的那个块，这两种说法是等价的。 但现在我们要生成的是跳转指令，所以用<=做判断，然后再跳转，就是比较自然了。具体你可以看看我们下文中为if语句生成代码的逻辑和相关的图，就更容易理解了。 **你在字节码中还会看到另一个跳转指令，是goto指令，它是一个无条件跳转指令。** 在计算机语言发展的早期，人们用高级语言写程序的时候，也会用很多goto语句，导致程序非常难以阅读，程序的控制流理解起来困难。虽然直到今天，C和C++语言里还保留了goto语句。不过，一般不到迫不得已，你不应该使用goto语句。 这种迫不得已的情况，我指的是使用goto语句实现一些奇特的效果，这些效果是用结构化编程方式（也就是不用goto语句，而是用条件语句和循环语句表达程序分支）无法完成的。比如，采用goto语句能够从一个嵌套很深的语句块，一下子跳到外面，然后还能再跳进去，接着继续执行！这相当于能够暂停一个执行到一半的程序，然后需要时再恢复上下文，接着执行。 我在说什么呢？这可以跟协程的实现机制关联起来，协程要求在应用层把一个程序停止下来，然后在需要的时候再继续执行。那么利用C/C++的goto语句的无条件跳转能力，你其实就可以实现一个协程库，如果你想了解得更具体一些，可以看看我之前的《编译原理实战课》。 总结起来，goto的这种跳转方式，是更加底层的一种机制。所以，在编译程序的过程中，我们会多次变换程序的表达方式，让它越来越接近计算机容易理解的形式，这个过程叫做**Lower过程**。而Lower到一定程度，就会形成线性代码加跳转语句的代码格式，我们有时候就会把这种格式的IR叫做“**goto格式（goto form）**”。 好了，刚才聊的关于goto语句的这些知识点，是为了加深大家对它的认识，希望能够对你的编程思想有所启发。 回到正题，现在我们已经对跳转指令有了基本的认识，那么我就把接下来要用到的跳转指令列出来，你可以看看下面这两张表： ![](https://static001.geekbang.org/resource/image/ac/3d/ac7395bba02f6acf0ed1fbb3e8b0c63d.jpg?wh=2248x1238)![](https://static001.geekbang.org/resource/image/1a/66/1ab23f48b04952b01594d7ec466a7b66.jpg?wh=2248x1391) 如果后面要增加对浮点数和对象引用的比较功能，我们可以再增加一些指令。但由于目前我们还是只处理整数，所以这些指令就够了。 接着，我们就修改一下字节码生成程序和虚拟机中的执行引擎，让它们能够支持if语句和for语句。 ## 为if语句和for循环语句生成字节码 让if语句生成字节码的代码你可以参考[visitIfStatement方法](https://gitee.com/richard-gong/craft-a-language/blob/master/08-09/vm.ts#L253)。在这个方法里，我们首先为if条件、if后面的块、else块分别生成了字节码。 ```plain //条件表达式的代码 let code_condition:number[] = this.visit(ifstmt.condition); //if块的代码 let code_ifBlock:number[] = this.visit(ifstmt.stmt); //else块的代码 let code_elseBlock:number[] = (ifstmt.elseStmt == null) ? []: this.visit(ifstmt.elseStmt); ``` 接下来，我们要把这三块块代码拼接到一起，这就需要计算出每块代码的起始地址，以便跳转语句能够做出正确地跳转。比如，if块的起始位置是代码条件块的长度加3，这个3是我们生成的跳转指令的长度。 ```plain let offset_ifBlock:number = code_condition.length + 3; //if语句块的地址 let offset_elseBlock:number = code_condition.length + code_ifBlock.length + 6; //else语句块的地址 let offset_nextStmt:number = offset_elseBlock + code_elseBlock.length; //if语句后面跟着下一个语句的地址 ``` 计算出每块代码的起始地址后，接下来我们就说说如何生成跳转指令。 在前面Java生成的字节码中，我们看到编译器对于“a>10”生成了一条“if\_icmple”指令。但我为了生成代码的逻辑更简单，采用了另一个实现思路。也就是先对a>10做计算，如果结果为真，就在栈顶放一个1，否则就放一个0。 接下来，我们再生成一条ifeq指令，根据栈顶的值是1还是0来做跳转。那么这个ifeq指令就要占据3个字节，其中操作码占1个字节，操作数占两个字节。我的算法生成了两条指令，你也可以思考一下如何能够像Java编译器那样只生成一条指令。 计算好偏移量以后，我们就可以把condition块、if块和else块的代码拼接成完整的if语句的代码了： ```plain //条件 code = code.concat(code_condition); //跳转:去执行else语句块 code.push(OpCode.ifeq); code.push(offset_elseBlock>>8); code.push(offset_elseBlock); //条件为true时执行的语句 code = code.concat(code_ifBlock); //跳转：到整个if语句之后的语句 code.push(OpCode.goto); code.push(offset_nextStmt>>8); code.push(offset_nextStmt); //条件为false时执行的语句 code = code.concat(code_elseBlock); ``` 你也看到了，在示例代码中，我们生成了两个跳转指令，分别是ifeq指令和goto指令，这样就能保证所有语句块之间正确的跳转关系。 那到这里，是不是就大功告成了，为if语句生成了正确的字节码了呢？ ![](https://static001.geekbang.org/resource/image/1f/86/1f98b2f8fa412e54b65df6f15053ba86.jpg?wh=1265x1866) 不是的。你仔细体会一下，是不是有点什么不对劲？哪里不对劲呢？ 你看，在我们生成的跳转指令中，一定要设置好正确的跳转地址，否则代码就错误了。可是，在if块和else块的代码中可能也包含了跳转指令呀。现在你把if语句中的各个块拼成了一个整体的字节码数组，那么各个块中包含的跳转指令的地址就错了呀。原来的跳转地址，都是基于各自的字节码数组中的位置，现在拼成一个新数组，这个位置也就变了。 ![](https://static001.geekbang.org/resource/image/7c/9a/7c4082aed6f36c05d4960d4c4567yy9a.jpg?wh=1265x1262) 所以，这些跳转指令的跳转地址，都需要做一下调整，加上我们计算出来的偏移量，来保证整体的跳转不出问题。 ```plain this.addOffsetToJumpOp(code_ifBlock, offset_ifBlock); this.addOffsetToJumpOp(code_elseBlock, offset_elseBlock); ``` 其实，这个调整跳转指令地址的过程，是每次做代码拼接的时候都会被调用的。比如，当前if语句生成的代码，在上一级的AST节点中做拼接的时候，也需要做地址的调整，这样就会保证为函数最终生成的字节码中，每个跳转指令的地址都是正确的。 实现完了If语句，你可以再实现一下[for循环语句](https://gitee.com/richard-gong/craft-a-language/blob/master/08-09/vm.ts#L298)。for循环语句的实现思路也是差不多的，都是先生成各个部分的代码，然后再正确地拼接到一起。 好了，到目前为止，我们已经扩展了字节码编译器的功能，让它能够为if语句和for循环语句正确地生成字节码了。接下来，我们再扩展一下字节码解释器的功能，让它能够正确地运行这些跳转指令就行了。 ## 升级字节码虚拟机 对于ifeq、ifneq、if\_cmplt等跳转指令，解释器的处理逻辑差不多都是一样的。它在遇到这些指令的时候，都会计算一下栈顶的值是否符合跳转条件。如果符合，就计算出一个新的指令地址并跳转过去。否则，就顺序执行下一条指令就可以了。 ```plain case OpCode.ifeq: byte1 = code[++codeIndex]; byte2 = code[++codeIndex]; //如果栈顶的值是0，那么就计算一个新的指令地址，以便跳转过去 if(frame.oprandStack.pop() == 0){     codeIndex = byte1<<8|byte2;     opCode = code[codeIndex]; } //否则，就继续执行下一条指令 else{     opCode = code[++codeIndex]; } ``` 在增加了对跳转指令的支持以后，我们就完成了对虚拟机的升级工作。**现在，我们已经拥有两个运行时了，一个是AST解释器，一个是字节码虚拟机。**在我们启动字节码虚拟机的设计之前，我们曾经希望它能提升程序运行的性能。那现在是否达到了这个目标呢？让我们测试一下吧！ ## 做一下性能比拼 我们仍然采用斐波那契数列的例子来做性能测试。这个例子的好处，就是随着数列的变大，所需要的计算量会指数级地上升，所以更容易比较出性能差异来。现在，我们用AST解释器和字节码虚拟机都来执行下面的代码： ```plain function fibonacci(n:number):number{ if (n <= 1){ return n; } else{ return fibonacci(n-1) + fibonacci(n-2); } } for (let i:number = 0; i< 26; i++){ println(fibonacci(i)); } ``` 我让n依次取不同的数值，分别测量出两个运行时所花费的时间，做成了一个表格。 ![](https://static001.geekbang.org/resource/image/d1/45/d19ba51ba1d615975dd368e2b5fe1845.jpg?wh=2248x1668) 你可以从表格中看到，TypeScript栈机所花费的计算时间，基本上只是AST解释器的一半。所以，我们确实按照预期获得了性能上的提升。 如果把表格画成图表，就能更清晰地显示出运行速度变化的趋势。你能看出，这两条线都是指数上升的，并且栈机花费的时间始终只有AST解释器的一半。 ![图片](https://static001.geekbang.org/resource/image/2f/11/2fb90592ca2b2e4b639644f5d1d9ee11.png?wh=1695x756) 好了，我们的第一个版本的虚拟机已经完成了。在性能方面，也确实如我们所愿，获得了重大的提升，可以说比较圆满地完成了我们这节课的目标！ ## 课程小结 这节课，我们主要实现了对if语句和for循环语句的支持。在这个过程中，我们学习了一类新的指令，也就是跳转指令。你如果多接触几种指令集就会发现，包括物理CPU的指令集在内的各种指令集，都有跳转指令，并且名称也都差不多。所以，我们这里学到的知识，也有助于后面降低你学习汇编语言的难度。 在为跳转指令生成代码的时候，关键点是**要正确地计算跳转地址，**地址是相对于这个函数的字节码数组的开头位置的偏移量。只有在为整个函数都生成了字节码以后，我们才能计算出所有的基本块的准确起始地址。 最后，我们还对虚拟机的性能做了测试。现在的性能只提高了一倍，当生成的斐波那契数列比较大的时候，我还是觉得挺慢的。那么，我们能否有办法进一步提升虚拟机的性能呢？像JVM和V8这样的虚拟机，都是用C++写的。那么，如果采用C/C++这样的系统级语言写一个新版本的虚拟机，会不会获得性能上更大的提升呢？那么在下一节课，我们就动手实现一个C语言版本的虚拟机吧。 ## 思考题 又来到了我们例行的思考题环节，我想问下，现在你对我们虚拟机的性能测试结果满意吗？你觉得我们还可以做哪些改进，来提升TypeScript版本的虚拟机的性能呢？欢迎在留言区留言。 感谢你和我一起学习，也欢迎你把这节课分享给更多对字节码虚拟机感兴趣的朋友。我是宫文学，我们下节课见。 ## 资源链接 [这节课的示例代码在这里！](https://gitee.com/richard-gong/craft-a-language/tree/master/08-09)