Compiler stage-1
7.1Background
7.1.1The Virtual Machine Paradigm7.1.2Stack Machine Model 7.2VM Specification Part-1
7.2.1General7.2.2 Arithmetic and Logical Commands7.2.3 Memory Access Commands7.2.4 Program Flow and Function Calling Command 7.3Implementation
7.3.1 Standard VM Mapping on the Hack Platform, Part 1
VM to Hack TranslateRAM UsageMemory Segments MappingAssembly Language Symbol 8.2VM Specification Part-2
8.2.1 Program Flow Commands8.2.2 Function Calling Commands8.3.3 The Function Calling Protocol8.2.4 Initialization 8.3 Implementation
8.3.1 Standard VM Mapping on the Hack Platform, Part Ⅱ
The Global StackFunction Calling Protocol ImplementationAssembly Language SymbolsBootstrap Code 8.3.2 Example Implementation In Python
Compiler stage-1为简化编译工作，并提高可移植性，设计一种intermediate code运行于虚拟机（virtual machine）中。VM是虚构出来的计算机，但是可以移植并运行于各种架构的真实计算机中。
本章所涉及的VM语言包括四种命令：arithmetic、memory access、program flow、subroutine calling commands。
高级语言的运行需要依赖编译器将其编译为目标平台支持的机器码，通常需要一个单独的编译器为每一对高级语言-机器码进行编译工作。
通过引入运行于virtual machine的intermediate code，可以解除这种依赖关系。编译被简化为两个几乎互不影响的阶段：
parse the High-level language and translate its commands into intermediate processing stepstranslate the intermediate steps into targe machine language
这样做的好处是第一阶段的编译只依赖于高级语言，第二阶段的编译只依赖于目标平台的机器码，极大提高了可移植性和模块化编译的方便性。JRE和.NET框架都采用了这样的思想。
7.1.2Stack Machine ModelVM中的所有操作数和结果都存放在stack中，所有的计算、读取包括子进程调用操作都可以通过栈操作实现。
pushpop
具体作用：
处理所有的计算和逻辑操作方便子进程调用以及内存分配
7.2VM Specification Part-1
7.2.1General
The virtual machine is stack-based and function-based.包括四种命令：
Arithmetic commands - 在栈结构中执行运算与逻辑操作Memory access commands - 在栈结构和虚拟内存节点之间转移数据Program flow commands - facilitate conditional and unconditional branchingFunction calling commands - 调用函数并返回值
该课程所涉及的VM程序包含一个或多个.vm文件，每个文件包含一个或多个function，跟别对应高级语言中的program、class 、method概念。
7.2.2 Arithmetic and Logical Commands本课程所设计的VM语言包括9种面向栈结构的运算或逻辑命令：
七种二元命令：pop两个操作数，进行运算，然后push结果入栈；两种一元命令：pop一个操作数，进行逻辑处理之后push结果入栈；
# 注意命令（`gt`、`lt`、`eq`）返回`Boolean`类型结果： # true = -1 (0xFFFF, or 1111111111111111) # false = 0 (0x0000, or 0000000000000000)7.2.3 Memory Access Commands
VM 语言设定有8种virtual memory segments，操作指令如下：
push segment index // Push the value of segment[index] onto the stackpop segment index // Pop the top stack value and store it in segment[index]
除了上述virtual memory segments，我们还需要维护数据结构stack（push和pop操作种数据存储移动的地方）和heap（RAM） 。
7.2.4 Program Flow and Function Calling CommandProgram Flow Commands:
label symbol，Label declarationgoto symbol，Unconditional branchingif-goto symbol，Conditional branching
Function Calling Commands:
function functionName nLocalscall functionName nArgsreturnPS. functionName is a symbol, while nLocals and nArgs are non-negative integers. 7.3Implementation
在目标平台上实现设计的VM语言需要将VM数据结构映射到目标硬件平台上，再将所有的VM命令编译位硬件平台支持的指令形式。
7.3.1 Standard VM Mapping on the Hack Platform, Part 1下面讨论将VM映射至Hack硬件平台。
VM to Hack Translate一个.vm程序或许包含多个.vm文件，将该程序便编译为一份.asm汇编代码。
RAM UsageHack平台上共有32K 16-bit RAM空间，其中前16K为通用RAM，后16K用作I/O设备映射。
上述RAM地址0~15可以被任何汇编程序用作R0~R15。
同时SP、LCL、ARG、THIS、THAT也可以用来指代RAM[0~4]。此举旨在提升VM程序可读性。
- 之前讨论的8个内存段（memory segment）中，local、‘argument’、this、that都在RAM中有直接的映射（通过将该内存段的物理地址保存在制定的专用寄存器中——LCL, ARG, THIS, THAT）。
也即是所有获取某一内存段第i位数据的操作在汇编语言中可以通过操作RAM[base + i]实现，其中base是此时存储在该内存段制定的寄存器中的数值。其次，对于pointer, temp内存段，这两个内存段被分配到指定的空间。pointer被分配到RAM[3~4]（也是THIS, THAT），temp被分配到RAM[5~12]。获取pointer i和temp i可以分别通过指向3 + i以及5 + i操作实现。另外，constan是唯一的虚拟内存段，VM通过直接提供常数i来实现
VM所使用的程序控制指令：
label label ，其中label为任意非数字开头的字符串，标识了代码该处的位置，只有通过此声明才能使的程序从另一个地方跳转到代码的这个位置。goto label ，无条件跳转。if-goto label 条件跳转。执行次操作是栈顶的元素被pop出，若非零则跳转，反之不进行任何操作。跳转的位置需要实现被标识。 8.2.2 Function Calling Commands
高级语言中的子进程被编译为VM中的一个函数。函数通过随即字符串构成的名字来实现全局调用（我们希望高级语言中类Foo中的方法bar被编译为函数Foo.bar）。值得说明的是，在高级语言中一个完整的用户程序通常由若干个内含一个class的代码文件组成，在第一层编译中，每一个文件分别被编译为一个.vm文件，第二层也即是Jack to VM的最后一层编译后，这若干个.vm文件会被编译为一个.asm文件。考虑到高级语言中不同的class可能拥有相同的method，编译到.asm文件之后为了防止作用域冲突，将类Foo中的方法bar被编译为函数Foo.bar。
VM中的指令如下：
function f n ，声明函数f，拥有n个本地local variablescall f m，调用函数f，同时有m个参数被入栈。 8.3.3 The Function Calling Protocol
函数调用事件可以从函数调用进程和被调用函数两个两个视角看待。
调用者视角：
- 调用函数之前，调用者入栈相应数量的参数；用call指令激活函数；调用的函数执行完毕并返回值之后，之前入栈的参数没有了，取而代之的是函数的返回值；调用的函数执行完毕并返回值之后，调用者的内存段argument, local, static, this, that, pointer与调用函数之前完全相同，temp为未定义状态。
- 函数开始执行，他的形参列表argument被初始化为传递给他的实参的数值；预先设定的local本地变量列表初始化为0；函数的static内存段被设置为它属于的VM文件所拥有的static内存段；可操作的栈为空；this, that, pointer, temp 内存段未定义；函数返回值之前，将一个结果入栈。
一个VM程序由多个VM函数组成（由高级语言编译而成）。当VM程序运行时，首先需要执行Sys.init函数，通过该函数调用用户需要执行的Main函数。
8.3 Implementation本节主要讲述了如何完善第7章搭建的Vm Translator。8.3.1描述了如何维护关键的栈结构，以及如何将该结构映射到硬件平台。8.3.2给了一个具体的例子。
8.3.1 Standard VM Mapping on the Hack Platform, Part Ⅱ The Global StackVM语言的资源管控通过栈结构实现。每当一个函数被调用，一个新的block被添加到全局栈当中。该内存块包含
argument，已经传递数值的形参列表；pointers，VM用来函数调用者的状态；local variables，本地变量，初始化为0；working stack，空栈。
下图表示基本的函数栈结构：
值得注意的是，被调用函数中的ARG, LCL以及SP不会被调用者看到，仅可以被该函数使用。
另外，根据之前设定好的内存分配规则，全局栈结构应该从RAM[256]开始，因此VM执行的第一步应该是置SP=256。之后每当遇到pop, push, add等操作时，需要更新SP的值。当遇到call, function, return等指令时，需要执行下图所示栈操作：
上图
Assembly Language Symbols显然，VM实现program flow以及function calling需要创造并使用special symbol。如下图汇总：
在Hack平台执行编译好的.asm文件，首先需要：
将全局栈映射至RAM[256]以后第一个执行的函数应该是Sys.init
由于之前所硬件平台在上电之后会开始执行RAM[0]位置处的代码，称为bootstrap code，如上述需要执行以下操作：
SP == 256 call Sys.init
Sys.init调用用户给定的Main函数，之后进入无限循环中。
8.3.2 Example Implementation In Python#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""[two tier compile]:
Compile procedure:
High-level language --> intermediate-code --> target machine code
Usage:
> python script.py [option] [para]
Recommend os:
Unix-like
"""
__author__ = 'eric'
import getopt
import os.path
import sys
# ----------------------------------------------------------
# Description:
# Translate .vm file into .asm file
def main():
input_path = recv_opt_arg(sys.argv)
print('input_path:t' + input_path)
if os.path.isdir(input_path): # 编译文件夹中所有VM代码为一个汇编文件，输出文件和文件夹同名
print('[Log]:tis dir')
input_path = os.path.abspath(input_path) + '/' # get absolute path and make sure the last char is '/'
output_path = input_path + input_path.split('/')[-2] + '.asm' # 输出文件和文件夹同名
file_path_list = [] # a list that contain every to be processed file's full path
files = os.listdir(input_path)
for each_file in files: # 处理给定文件夹中的 .vm 文件
if each_file[-3:] == '.vm':
file_path_list.append(input_path + each_file) # 完整路径 = 文件路径 + 文件名(带后缀)
processing_dir_file(file_path_list, output_path)
elif os.path.isfile(input_path): # 编译给定文件为一个汇编文件，输出文件与编译文件同名
print('[Log]:tis file')
if input_path[-3:] == '.vm':
output_path = input_path[:-3] + '.asm'
file_path_list = [os.path.abspath(input_path)] # get absolute input path
processing_dir_file(file_path_list, output_path)
else:
print('[Log]:tError_invalid_file_type')
exit(0)
else: # path is neither directory nor file
print('[Log]:tError_invalid_input_path_type')
exit(0)
return
# ----------------------------------------------------------
# Description:
# processing each file in file_path_list, and write asm_list into output_path
# Input:
# file_path_list, output_path
def processing_dir_file(file_path_list, output_path):
print('[Log]:t---* processing file, list:', file_path_list)
print('[Log]:t---* output_path:', output_path)
asm_list = []
for each_input_path in file_path_list: # each_file_path is the full path of each file to be processed
if 'Sys.vm' in each_input_path:
print('[Log]:tAdd Bootstrap Code')
asm_list = ['//Bootstrap Code'] + VMTranslator.c_init() + asm_list
with open(each_input_path, 'r') as f: # import original jack_file into a list
vm_list = f.readlines()
file_name = each_input_path.split('/')[-1][0:-3]
vm_translator = VMTranslator(vm_list, file_name)
asm_list += vm_translator.get_asm_list()
write_asm_file(output_path, asm_list)
# ----------------------------------------------------------
# Class Description:
# Instantiate: VMTranslator(vm_list, file_name)
class VMTranslator(object):
def __init__(self, vm_list, file_name):
self.file_name = file_name
print('[Log]:t---* instantiate VMTranslator, file_name: ' + self.file_name)
self.vm_list = vm_list
# print('[Log]:tvm_list, line:', len(self.vm_list), 'n', self.vm_list)
self.no_comment_list = []
self.asm_list = ['//' + self.file_name]
self.label_flag = 0 # 多个vm文件中可能存在同名函数，标识label时在函数名前加上文件名进行标识
# ---* main process *---
self.format_file() # Remove comment and empty line
# print('[Log]:tno_comment_list, line:', len(self.no_comment_list), 'n', self.no_comment_list)
self.parse_command()
def get_asm_list(self):
return self.asm_list
# ----------------------------------------------------------
# Description:
# Remove comment and empty line
def format_file(self):
for line in self.vm_list:
if '//' in line: # remove comment
line = line[0:line.index('//')]
line = line.strip() # remove backspace on both side
if len(line) != 0: # ignore empty line
self.no_comment_list.append(line)
# ----------------------------------------------------------
# parse vm file and translate it into assembly file
# Input:
# f_lines a list that contain every line of original .vm file
def parse_command(self):
for line in self.no_comment_list:
command_list = line.split(' ') # split command with backspace
command_type = self.which_command(command_list)
if command_type == 'arithmetic':
self.asm_list += self.c_arithmetic(command_list)
elif command_type == 'push':
self.asm_list += self.c_push(command_list)
elif command_type == 'pop':
self.asm_list += self.c_pop(command_list)
elif command_type == 'label':
self.asm_list += self.c_label(command_list)
elif command_type == 'goto':
self.asm_list += self.c_goto(command_list)
elif command_type == 'if-goto':
self.asm_list += self.c_if(command_list)
elif command_type == 'function':
self.asm_list += self.c_function(command_list)
elif command_type == 'call':
self.asm_list += self.c_call(command_list)
elif command_type == 'return':
self.asm_list += self.c_return()
else: # invalid command type
print('[Log]:tError_invalid_command_type')
self.asm_list += ['Error_invalid_command_type']
# ----------------------------------------------------------
# return corresponding number of command type
@staticmethod
def which_command(command_list):
arithmetic_command = ['add', 'sub', 'neg', 'eq', 'gt', 'lt', 'and', 'or', 'not']
if command_list[0] in arithmetic_command:
return 'arithmetic'
else: # 'arithmetic', 'push', 'pop', 'label', 'goto', 'if-goto', 'function', 'call', 'return'
return command_list[0]
# ----------------------------------------------------------
# parse arithmetic command
def c_arithmetic(self, command_list):
command = command_list[0]
if command == 'add':
re_c_arithmetic = ['@SP', 'AM=M-1', 'D=M', '@SP', 'A=M-1', 'M=D+M']
elif command == 'sub':
re_c_arithmetic = ['@SP', 'AM=M-1', 'D=M', '@SP', 'A=M-1', 'M=M-D']
elif command == 'neg':
re_c_arithmetic = ['@SP', 'A=M-1', 'M=-M']
elif command == 'eq':
re_c_arithmetic = ['@SP', 'AM=M-1', 'D=M', '@SP', 'A=M-1', 'D=M-D', 'M=-1', '@eqTrue' + str(self.label_flag),
'D;JEQ',
'@SP',
'A=M-1', 'M=0', '(eqTrue' + str(self.label_flag) + ')']
self.label_flag += 1
elif command == 'gt':
re_c_arithmetic = ['@SP', 'AM=M-1', 'D=M', '@SP', 'A=M-1', 'D=M-D', 'M=-1', '@gtTrue' + str(self.label_flag),
'D;JGT',
'@SP',
'A=M-1', 'M=0', '(gtTrue' + str(self.label_flag) + ')']
self.label_flag += 1
elif command == 'lt':
re_c_arithmetic = ['@SP', 'AM=M-1', 'D=M', '@SP', 'A=M-1', 'D=M-D', 'M=-1', '@ltTrue' + str(self.label_flag),
'D;JLT',
'@SP',
'A=M-1', 'M=0', '(ltTrue' + str(self.label_flag) + ')']
self.label_flag += 1
elif command == 'and':
re_c_arithmetic = ['@SP', 'AM=M-1', 'D=M', '@SP', 'A=M-1', 'M=D&M']
elif command == 'or':
re_c_arithmetic = ['@SP', 'AM=M-1', 'D=M', '@SP', 'A=M-1', 'M=D|M']
elif command == 'not':
re_c_arithmetic = ['@SP', 'A=M-1', 'M=!M']
else:
re_c_arithmetic = []
print('[Log]:tError_unknown_arithmetic_command')
exit(0)
return re_c_arithmetic
# ----------------------------------------------------------
# parse push command
def c_push(self, command_list):
segment = command_list[1]
index = command_list[2]
if segment == 'constant':
re_c_push = ['@' + str(index), 'D=A', '@SP', 'A=M', 'M=D', '@SP', 'M=M+1']
elif segment == 'static':
re_c_push = ['@' + self.file_name + '.' + str(index), 'D=M', '@SP', 'A=M', 'M=D', '@SP', 'M=M+1']
elif segment == 'this':
re_c_push = ['@THIS', 'D=M', '@' + str(index), 'A=D+A', 'D=M', '@SP', 'A=M', 'M=D', '@SP', 'M=M+1']
elif segment == 'that':
re_c_push = ['@THAT', 'D=M', '@' + str(index), 'A=D+A', 'D=M', '@SP', 'A=M', 'M=D', '@SP', 'M=M+1']
elif segment == 'local':
re_c_push = ['@LCL', 'D=M', '@' + str(index), 'A=D+A', 'D=M', '@SP', 'A=M', 'M=D', '@SP', 'M=M+1']
elif segment == 'argument':
re_c_push = ['@ARG', 'D=M', '@' + str(index), 'A=D+A', 'D=M', '@SP', 'A=M', 'M=D', '@SP', 'M=M+1']
elif segment == 'temp':
re_c_push = ['@5', 'D=A', '@' + str(index), 'A=D+A', 'D=M', '@SP', 'A=M', 'M=D', '@SP', 'M=M+1']
elif segment == 'pointer':
re_c_push = ['@3', 'D=A', '@' + str(index), 'A=D+A', 'D=M', '@SP', 'A=M', 'M=D', '@SP', 'M=M+1']
else:
re_c_push = []
print('unknown arithmetic command!')
return re_c_push
# ----------------------------------------------------------
# parse pop command
def c_pop(self, command_list):
segment = command_list[1]
index = command_list[2]
if segment == 'static':
re_c_pop = ['@SP', 'AM=M-1', 'D=M', '@' + self.file_name + '.' + str(index), 'M=D']
elif segment == 'this':
re_c_pop = ['@THIS', 'D=M', '@' + str(index), 'D=D+A', '@R13', 'M=D', '@SP', 'AM=M-1', 'D=M', '@R13', 'A=M',
'M=D']
elif segment == 'that':
re_c_pop = ['@THAT', 'D=M', '@' + str(index), 'D=D+A', '@R13', 'M=D', '@SP', 'AM=M-1', 'D=M', '@R13', 'A=M',
'M=D']
elif segment == 'local':
re_c_pop = ['@LCL', 'D=M', '@' + str(index), 'D=D+A', '@R13', 'M=D', '@SP', 'AM=M-1', 'D=M', '@R13', 'A=M',
'M=D']
elif segment == 'argument':
re_c_pop = ['@ARG', 'D=M', '@' + str(index), 'D=D+A', '@R13', 'M=D', '@SP', 'AM=M-1', 'D=M', '@R13', 'A=M',
'M=D']
elif segment == 'temp':
re_c_pop = ['@5', 'D=A', '@' + str(index), 'D=D+A', '@R13', 'M=D', '@SP', 'AM=M-1', 'D=M', '@R13', 'A=M',
'M=D']
elif segment == 'pointer':
re_c_pop = ['@3', 'D=A', '@' + str(index), 'D=D+A', '@R13', 'M=D', '@SP', 'AM=M-1', 'D=M', '@R13', 'A=M',
'M=D']
else:
re_c_pop = []
print('unknown arithmetic command!')
return re_c_pop
# ----------------------------------------------------------
# parse label command
def c_label(self, command_list):
new_label = self.file_name + '$' + command_list[1] # mark different labels
return ['(' + new_label + ')']
# ----------------------------------------------------------
# parse goto command
def c_goto(self, command_list):
new_label = self.file_name + '$' + command_list[1]
return ['@' + new_label, '0;JMP']
# ----------------------------------------------------------
# parse if command
def c_if(self, command_list):
new_label = self.file_name + '$' + command_list[1]
return ['@SP', 'AM=M-1', 'D=M', '@' + new_label, 'D;JNE']
# ----------------------------------------------------------
# parse function command
def c_function(self, command_list):
res_push = self.c_push(['push', 'constant', '0'])
res = ['(' + command_list[1] + ')']
loop_times = int(command_list[2])
while loop_times:
res = res + res_push
loop_times = loop_times - 1
return res
# ----------------------------------------------------------
# parse return command
# ----------------------------------------------------------
@staticmethod
def c_return():
res = ['@LCL', 'D=M', '@R13', 'M=D', '@5', 'A=D-A', 'D=M', '@R14', 'M=D', '@SP', 'AM=M-1', 'D=M', '@ARG', 'A=M',
'M=D']
res += ['@ARG', 'D=M+1', '@SP', 'M=D']
res += ['@R13', 'AM=M-1', 'D=M', '@THAT', 'M=D']
res += ['@R13', 'AM=M-1', 'D=M', '@THIS', 'M=D']
res += ['@R13', 'AM=M-1', 'D=M', '@ARG', 'M=D']
res += ['@R13', 'AM=M-1', 'D=M', '@LCL', 'M=D', '@R14', 'A=M', '0;JMP']
return res
# ----------------------------------------------------------
# parse call command
@staticmethod
def c_call(command_list):
global CALL_FLAG
label = command_list[1] + '.returnAddr.' + str(CALL_FLAG)
# 此处call_flag设立是为了防止同一个vm文件中多次调用同一函数，导致出现多个相同label
# 但是对于每个文件单独维护的call_flag，到处理另一个文件时由于新建VMTranslator对象会导致该变量重置为0
# 以至于无法处理多个文件多次调用同名函数的bug
# 可选解决方案：
# 1. 将call_flag的维护调整为全局，也即是对于所有文件公共维护同一个CALL_FLAG (yes)
# 2. 通过if语句手动排除 (no)
CALL_FLAG += 1
res = ['@' + label, 'D=A', '@SP', 'A=M', 'M=D', '@SP', 'M=M+1']
res += ['@LCL', 'D=M', '@SP', 'A=M', 'M=D', '@SP', 'M=M+1']
res += ['@ARG', 'D=M', '@SP', 'A=M', 'M=D', '@SP', 'M=M+1']
res += ['@THIS', 'D=M', '@SP', 'A=M', 'M=D', '@SP', 'M=M+1']
res += ['@THAT', 'D=M', '@SP', 'A=M', 'M=D', '@SP', 'M=M+1']
res += ['@' + command_list[2], 'D=A', '@5', 'D=D+A', '@SP', 'D=M-D', '@ARG', 'M=D', '@SP', 'D=M', '@LCL',
'M=D', '@' + command_list[1], '0;JMP', '(' + label + ')']
return res
# ----------------------------------------------------------
# Description:
# return the Bootstrap Code
@staticmethod
def c_init():
res_init = ['@256', 'D=A', '@SP', 'M=D']
res_call = VMTranslator.c_call(['call', 'Sys.init', '0'])
return res_init + res_call # 将寄存器SP置为256 + 调用函数Sys.init
# ----------------------------------------------------------
# Description:
# write assembly code to .asm file
# Input:
# out_file_path, asm_list
def write_asm_file(out_file_path, asm_list):
with open(out_file_path, 'w') as f:
for line in asm_list:
f.write(line + 'n')
# ----------------------------------------------------------
# Description:
# receive command line input. return input_path or print usage
# Output:
# input_path
def recv_opt_arg(argv):
# print('sys.argv=| ', argv, ' |')
try:
opts, args = getopt.gnu_getopt(argv[1:], 'i:h?', ['input_path=', 'help'])
# 'opts' is a list of tuple ('option', 'value'), each option match one value
# 'args' is a list contains extra arguments
# print('opts=| ', opts, ' |')
# print('args=| ', args, ' |')
except getopt.GetoptError as e:
print(e)
print_usage(argv[0])
sys.exit()
input_path = os.getcwd() # default input path
for opt, value in opts: # ('option', 'value'), tuple
if opt in ['-h', '-?', '--help']: # print help information
print_usage(argv[0])
exit(0)
elif opt == '-i': # input_path
input_path = value
return input_path
# ----------------------------------------------------------
# Description:
# print usage information of this script
def print_usage(cmd):
print(('*********************************************************n' +
' --* This massage gave you some detailed information! *--n' +
'Usage: {0} [OPTION]... [PATH]...n' +
'- OPTION:n' +
' {0} -i | --input_pathtinput pathn' +
' {0} -h | -? | --helptprint help info and exit scriptn' +
'- PATH:n' +
' Provides name of the file you want to precess or directory that contain those filesn' +
' --* *-- n' +
'*********************************************************n').format(cmd))
if __name__ == '__main__':
CALL_FLAG = 0 # 一个文件中可能存在多次调用同一函数的情况，调用代码结尾的label需要加上flag标识
main()
