Nand2Tetris|VirtualMachine

Compliation

Basic Concept

高级编程语言大部分都是通过以下的组件配合才能进行执行

• 编译器
• OS
• VM虚拟机
• 汇编器

根据编译的层级可以分成两种

• 一级编译：高级编程语言通过编译器直接转换为机器语言
• 二级编译：高级编程语言————>VM指令（字节码）————>机器语言

比较常见的一级编译代表就是cpp，二级编译代表是java

• 一级编译
  • 生成的更高效更具有针对性的机器代码
  • 但是针对多个硬件平台就需要需要多组编译器/编译过程实现
• 二级编译
  • 一次编译，处处运行！
  • 针对每一个硬件平台就需要一个 VM Translator(但是VM Translator的实现远比编译器简单)；同时生成的机器代码也相对来说更低效（对于部分应用程序来说这个效果并不明显）

对于 Hack 机器来说，整体的执行流程如下：

这里我们也引出整个课程第二部分的目标：

• 构建编译器的后端（目前正在进行的）
• 实现一个高级编程语言Jack（类似Java，运行在Hack计算机上）
• 实现编译器的前端
• 实现Hack硬件通用的操作系统

整体的流程：

高级编程语言编写代码，组合Hack硬件操作系统系统调用————通过编译器生成VM代码————VM代码转换为机器代码————机器代码通过汇编器转为二进制指令————Hack硬件取指执行指令进行相关功能

Virtual Machine

从整体角度来说：每个高级编程语言中的算术或逻辑表达式都可以转化为在虚拟机堆栈中运行的虚拟机命令序列。

VM code：由编译器生成，在虚拟机上运行

VM Translator：将 VM code 转换为机器语言

VM Translator实现了VM code抽象

VM基本操作介绍

Hack计算机的虚拟机是基于栈结构的

基于这个基础栈结构，程序在此数据基础上进行算数操作

虚拟机栈的算数操作抽象可以看作是一个函数f，这个函数调用会从栈中pop所需要的数据作为函数入参，将函数进行计算之后再将结果push至栈中

如下面的两张图

简单来说就是：pop oprands, apply oprators on function 最后 push result

具体应用例子如下：

Virtual Mem Segments

 class Foo {
 	static int s1, s2;
 	public int bar(int x, int y) {    
          int a, b, c; 
          ...     
          c = s1 + y;
           ...
           return c; 
  }
}

对于其中的 c = s1 + y 编译器得到的 VM code 实际上是

push static 0
push argument 1
add
pop local 

对于需要生成VM code的编译器，编译器在编译阶段会将变量根据其类型用virtual memory segments来进行表示

例如上面的代码，两个静态变量 s1 和 s2，函数局部参数 x 和 y，函数内部局部参数 a b c，分别代表三种不同的类型，对应三个不同的 segement

之后编译器会生成操作虚拟机栈和虚拟内存片段的VM指令

Jack的虚拟机架构支持8中不同的虚拟内存片段种类，分别是local argument static constant this that temp pointer

具体在后续实现编译器的时候会知道他们各自的功能

一个很重要的VM抽象就是：所有操作虚拟内存片段（VM segment）对应的指令需要表现一致的行为：

• push只会更新栈顶元素
• pop只会写入虚拟内存段

VM 指令

VM code 的基本格式就是

push/pop segement_type i (i为非负整数)

除此之外还有基础的算数运算/逻辑函数

add sub neg eq gt lt and or not

从具体的实现角度而言，有三种不同实现方式：

• 原生硬件实现：在硬件基础上进行扩展，扩展专门的硬件模块来表示虚拟机的栈结构；此外还需要在计算机支持的指令集上扩展VM指令的原始版本
• 软件模拟：将虚拟机的栈和虚拟内存段视作高级编程语言中的抽象数据结构类型。在这种情况下VM指令其实就是操作这些数据结构类型的方法/函数
• 翻译：将每条VM指令翻译成在主机 RAM 上运行的机器指令；使用内存寻址的方式，将堆栈和内存段作为主机 RAM 里的专用 RAM 段来实现（需要约定内存区域的哪些位置用来维护VM指令转换所需数据，后面都会提到）

翻译的这种实现方式是比较广泛采取的方案，例如 java py, c# ruby scala 等，这里我们的 Jack 也采用第三种方案

VM指令转机器指令

实现push const i

对于VM指令中 push constant 类型的，我们根据对应的数据流向，先写出对应的汇编代码

我们约定：vm stack pointer 的地址存放于 RAM[0]，const 类型的 vm stack 的数据从 256 地址开始

当执行 push constant i 这个VM指令的时候，实际上效果是

RAM[SP] = i
SP++     

对应的 Hack 汇编就是

//D=i
@i
D=A
//RAM[SP]=D
@SP
A=M
M=D
//SP++
@SP
M=M+1     

实现push/pop local i

对于Jack编写的函数中定义的局部变量，VM需要能够支持 push/pop 操作

pop local i 的语义是：将SP的数据pop出来，设置在 local segement 的 i 位置

值得注意的是，对于函数内部的变量，地址是在RAM中不确定的，根据每一次程序的运行动态设置，我们通过LCL来表示基础地址，类似SP，LCL的地址存放于RAM[1]

pop local i的对应伪代码就是

//pop local i
addr <- LCL + i
SP--
RAM[addr] <- RAM[SP]     

对应的汇编就是

//SP--
@SP
M=M-1
//D = RAM[SP]     
A=M
D=M
//addr <- LCL + i
@LCL
D=M
@i
A=D+A     
//RAM[addr] = RAM[SP]
M=D     

类似的 push 操作语义为 将i地址偏移后的数据写入到当前栈顶：

addr <- LCL + i
RAM[SP] <- RAM[addr]
SP++     

对应的汇编就是

//addr <- LCL + i
@LCL
D=M
@i
D=D+A
//RAM[SP] <- RAM[addr]     
A=D
D=M
@SP
A=M
M=D
//SP++
@SP
M=M+1     

类似local segement的VM操作

对于local argument this that 的 segement，他们的转换实现其实都是一样的，都可以参照上述的汇编转换，对应的逻辑是完全一致的

只是 segmentPointer 是不一样的，也就是程序运行时分配的基础地址不同，分别用 LCL ARG THIS THAT 来进行区分

实现push/pop static i

When the compiler compiles classes, it maps all their static variables onto one VM segment, named static

当编译器编译类时，它将所有静态变量映射到一个名为static的VM segment上

我们约定：static 类型的 VM segment 从地址16开始，到255停止

想要实现push/pop static i的VM指令，只需要生成实现push/pop Xxx.i的汇编代码即可，其中 Xxx.i 是汇编符号名称

（因为Hack汇编器处理定义的变量的时候，符号表的映射起始地址就是从16开始）

实现push/pop temp i

这里的temp类型是指汇编器在针对高级编程语言代码时，在生成VM指令的过程中可能需要一些临时的变量，这些变量本身并不是源代码中定义的

因此temp类型的segment是一个定长的8长度的片段，从5开始，12结束

所以实现push/pop temp i本质上就是在实现push/pop RAM[5+i]的语义

实现push/pop pointer i

pointer类型的segment主要是用于在汇编器处理代码中针对对象/数组的引用，具体更多的内容我们会在后面实现编译器的时候提到

现在只需要知道他是一个定长的两格长度的segment即可

pointer 是真正意义上虚拟的segment，不存储在任何地方，仅仅包含 this 和 that 的基础地址

实际上i只能是0或者是1，对应this和that

pop pointer 0/1 等价于将栈顶元素写入RAM[3]/RAM[4]里

push pointer 0/1 等价于将RAM[3]/RAM[4]元素压入栈顶

综上，我们描述了如何生成实现VM操作的汇编代码片段

实现VM算数逻辑指令

对于任何一个VM算数指令，本质上就是将VM栈中的数据pop出来作为操作数，之后将操作数应用到计算函数中进行计算，最终将结果push入栈的过程

pop和push的汇编指令我们之前已经实现了，而计算函数其实本质上也就是加减乘除等，汇编本身支持

VM emulator

VM的实现之前也提到了，主要分为两种：

• VM Emulator：通过高级编程语言编写，执行对应的VM指令（课程已经提供了）
• VM translator：通过将VM指令等效替换为对应平台的汇编指令（实验7和8需要实现）

这里简单提一下课程提供的VM模拟器，它可以可视化观看VM指令的执行过程，VM stack和对应的虚拟segment在主机RAM中是如何被模拟已经动态变化的

Standard Mapping

这里的Standard Mapping的意思针对某些目标平台，提供的一套标准的内存映射约定（vm stack从何处开始存储，segment pointers有哪些，分别从哪里开始等），也就是将抽象的VM栈内存映射到物理内存区域的约定

其实我们上面说到现在一直在说的，其实都是针对 Hack Computer 的 Standard Mapping，这边顺带做一个总结

VM Tanslator实现

先来梳理一下整体的逻辑：

• 用户编写高级编程语言（例如Jack或者Java）
• 编译器编译阶段生成VM指令（此过程与平台无关，跨平台的核心本质上是套了一层）
• VM Translator通过不同目的平台的实现，将VM指令转换为对应平台的汇编
• 汇编代码根据汇编器转换为对应硬件可直接执行的二进制代码

基本架构

主要可以包含三个部分：

• VMTranslator核心驱动程序，读取文件控制整体流程
• Parser：读取文件中单行的VM command并解析
• CodeWritter：Parser的解析结果，生成对应实现VM指令效果的Hack汇编代码

Parser实现

首先一个原始VM指令代码文件就对应一个Parser，这个Parser会读取所有内容并维护在内存中

同样类似于之前实现的汇编器，Parser中还是需要有判断是否还有下一行hasMoreLines()，以及维护一个隐式的游标在内存中维护当前的指令advance()

针对核心的解析逻辑，需要对当前指令执行如下函数：

• commandType()返回当前VM指令的类型：C_ARITHMETIC或者是C_PUSH/C_POP（这个其实没什么好的办法，只能根据指令内容来判断，暴力枚举即可）
• arg1 返回当前VM指令的第一个参数，也就是push/pop，对于算数运算VM指令，直接返回指令本身
• arg2 返回当前VM指令的第二个参数，也是就是segment的类型（仅C_PUSH/C_POP类型调用）

Code Writer实现

类似Parser，一个CodeWriter实例对应一个输出文件，核心实现函数包括：

• writeArithmetic根据当前VM算数指令，在输出文件流中写入汇编内容
• writePushPop根据当前VM指令，在输出文件流中写入汇编内容
• close提供关闭输出流的接口防止内存泄露