从零开始设计指令集的过程

2019/04/10 10:10
阅读数 24

前一篇文章简单介绍了我的指令集和虚拟机,这篇文章介绍指令集的设计过程。

设计指令集

这里我一步步说明目前指令的设计过程,这些指令大多已经确定,也有一些是临时加入,还没有验证实用性。

希望看到这篇文章的读者能多多给我提建议,让我的虚拟指令能从玩具变成实用品。

针对软件设计的虚拟指令集

在设计指令前,我就确定了设计的原则:

  1. 首先,我的指令不是用来做硬件电路,而是用C语言和汇编解释执行的,所以指令要设计得使软件虚拟机能尽可能快地运行。
  2. 对于虚拟机,运行的最小单位是每条指令,每条指令前要取指和翻译,指令后要更改PC(程序计数器)的值,这也是虚拟指令相比原生代码的一部分累赘。因此一条虚拟指令内执行的事越多,性能就可以越接近原生代码。所以指令并非越简单越好,复杂是有必要也有收益的。反过来说就是要减少一个操作所需要的指令数
  3. 指令越短越好。这不仅能减小程序大小,也使虚拟机取指令更快。
  4. 固定的东西越多,运行越快。这是因为变量需要读取内存。例如在指令中取虚拟机寄存器R[rx]和固定的R[3]是不同的,因为rx需要再读一次值才能确定。然而为了更灵活的功能,变量常常是必须,只能自行权衡。

省着分配opcode

在增加指令前,还要考虑指令的数量,由此确定操作码(opcode)需要的位数。为了加快指令译码,我将操作码定为1字节,因此可以表示256种不同的指令。

但这256个位置不是都用来表示指令,我将操作码 0 认定为空异常,而255是程序结束符。这是因为0x00和0xFF经常出现在程序中,可以检测程序是否运行到非法的地方。

这样还剩254个指令,这里我按设计顺序列为

  1. 立即数指令
  2. 移动指令
  3. 加减运算
  4. 跳转、分支
  5. 函数调用
  6. 内存读取储存
  7. 移位、位运算
  8. 系统指令
  9. 寄存器窗口操作
  10. 结束符

指令说明

在介绍指令前我先解释文中表示指令的格式,表格里靠左的是低地址字节,每格里靠左是低位。

第一大格为操作码,占1byte即8bit,中格一般是“r”开头的寄存器占4bit,一小格代表1bit。

蓝色的代表立即数,也就是在指令中的常数;橙色的代表偏移或地址,用于跳转指令。

opcode


 

空指令

首先加入的是最简单的空操作指令,只需一个opcode。

nop

nop代表什么都不做,这条指令在硬件系统中可能会用来调节流水线,但在我的虚拟机中,应该是没用的。

立即数指令

之后设计的是向寄存器写入立即数的指令,因为这是一台机器基本功能的“输入-运行-输出”中开头的部分,对应程序中的常数量。

因为很多时候时候都需要设定像-1,0,1,2这样不大的常数,所以这种常用指令应该比较短。

此外也要考虑使用使用大常数的情况。在x86,JAVA等大多数程序中都设定一块常数池,运行时查表取数。

我没有采用常量池的方法,因为我不想多查表,所以考虑后的结果是把立即数都存指令里,分别设计了4条获取立即数的指令:

表示立即数时,我用s代表有符号(signed),u为无符号(unsigned),后接数字代表位长。s8就对应char,s16为short。

暂时没有set rd,u32,因此没办法表示u32。这不一定是问题,如果虚拟机是32位,那么s32和u32在数据上没有差别。如果是64位还要再考虑要不要加。

rd表示目标寄存器,rd后面是空的,因为我为了读取和译码效率,尽量对齐立即数,这里空出的4位未来也可能用上。

移动寄存器指令

之后加入的是移动寄存器指令。

move

非常简单,rd目标寄存器,rs来源寄存器。

加减运算指令

加减是机器功能的基础,所以也在一开始就加入了。

先加入的有自增,立即数加法和寄存器加法。

inc指令虽然叫自增,事实上可以运算[-8,7]的范围。

add是一个只有两个操作寄存器的运算指令,相当于rd+=rs。因为这种运算经常出现,所以添加了这条指令,可以缩小指令大小。

add2中的2代表"To",rs1和rs2加到rd的意思。

而sub和sub2是最后才加入的。

跳转指令

跳转也是计算机功能中的基础,我设了两条相对跳转和一条绝对跳转指令。

计划将jump_32也改成相对跳转。

在VL指令集中,跳转代表无条件跳转,分支代表有条件跳转。

分支指令

在x86中,分支是通过先测试寄存器值,设定标志位,然后根据标志位跳转。

我的虚拟机没有采用标志位的方法,是类似于MIPS的无标志位跳转。

这会导致分支指令占据指令总量的一大部分,为了让分支少一两句代码,我觉得值。

目前只有和0、整数、寄存器的比较分支,各分为相等分支,不相等分支,大于分支,大于等于分支。这部分还在变动阶段,后续会大量改动。

指令格式如下(长度分别为 4,4,6字节):

这些指令分别有beq/bne/bgt/bgeq共四组。

这里offset20并没有遵循对齐的原则,因为我受到4位空间的诱惑,选择了将16位向前拓展4位而不是向后拓展16位。因此也意味着offset20分支最大只能跳转前后512KB的程序大小,而offset16只能前后跳转32KB。

虽然似乎非常受限,但是因为分支指令在程序中经常出现且一般范围不大,所以我尽量压缩它们的大小。

除了这个原因,远距离分支的问题也可以通过反转分支条件并在分支后接一条远跳转指令的方法来解决。

 

函数指令

到函数这部分可以说指令设计已经到了高级阶段。

首先是函数调用,通常函数调用就是保存PC,然后跳转。因为我的虚拟机是基于寄存器窗口的,所以我的调用还要移动窗口。

函数调用指令会使虚拟机执行一系列操作:

  1. 将窗口后移。
  2. 把PC保存到窗口前一个寄存器。(移动窗口和保存PC的顺序可以调换)
  3. 将PC跳转到函数地址。

参考上一篇文章中的这张图:

所以,调用指令中需要指定窗口移动量,还要包含函数的地址。

我设计了两条指令,xcall是可控制窗口移动量的超级调用;call则是固定移动14个寄存器的普通调用,用这条指令来节约程序大小并减少取码加快运行。

我也在考虑将address32改为offset32。

函数返回

返回指令的功能是和调用正相反:

  1. 将之前的PC从窗口前一个寄存器取出。
  2. 将窗口移回。
  3. PC跳回之前的PC。

其实,如果在调用时,将窗口移动量也保存在窗口前,那么返回时就可以不用设定移动量,而是像PC一样读取。但考虑到寄存器占用问题,我还没有加入这样的指令。如果有了堆栈,就可以将PC和移动量都保存到栈中了,这些就之后再说。

此外,现在移动量都是写死的值,如果可以使用寄存器值在函数调用时控制窗口移动量,程序灵活性会更高,这些也还在考虑中。

内存保存读取

内存的读写操作也是程序很重要的需求,放到现在是因为最开始不敢贸然确立。所谓内存操作就是寄存器到内存,内存到寄存器,还有内存到内存。

在精简指令集中,内存操作限定为一个load和一个store,不仅减少了指令也大大简化电路设计。

而在英特尔指令集中,有很多内存指令,可以对指针地址和内容进行运算再读写。根据上面列出的第二点原则,我希望这些指令功能往复杂方向走。

目前的指令如下:

其中每种指令都对应了8位,16位,32位这三种情况,加载指令还分有符号和无符号数。他们的汇编语法格式为:

-*读取内存
load rd,[rs].s8
load rd,[rs].u8
load rd,[rs].s16
load rd,[rs].u16
load rd,[rs].s32
load rd,[rs].u32
-*写入内存
save rd,[rs].8
save rd,[rs].16
save rd,[rs].32

-*读取内存 自增
load rd,[rs+s8].s8
load rd,[rs+s8].u8
load rd,[rs+s8].s16
load rd,[rs+s8].u16
load rd,[rs+s8].s32
-*写入内存 自增
save rd,[rs+s8].8
save rd,[rs+s8].16
save rd,[rs+s8].32

其中savef/loadf都会对源寄存器的地址进行自增,这样的指令在顺序读取中可以减少指令数。

为了复杂的目标,我还准备加入load rd,[rs+rx].s8这样的三寄存器指令,还有从内存到内存的copy指令 copy [rd],[rs]。

在那之前,大家已经可以看到其代价也非常大,在现在不支持浮点数的情况下,内存指令就已经有18条,如果加上[rs+rx](9条)和copy(6条)等指令,起码会有33条指令。若再加上浮点数那真是爆炸了,所以我也在考虑是否有必要,还要看后续指令空间是否有剩余。

为什么将寄存器存到内存指令叫save不叫store? 因为load和save都是四个字母,对齐好看。

系统指令

系统指令是虚拟机的魔法,也是促使我一直做到现在的动力。

虚拟机特点就在“虚拟”二字,在虚拟机中宛如隔世,对真实世界一无所知。而系统指令,让虚拟机可以访问真实系统里的信息,建起了真实与虚拟间的桥。

此外,虚拟机对虚拟机中运行程序而言也是“系统”,因此系统指令也包括程序对虚拟机的访问指令,例如读取虚拟机的寄存器窗口指针(RP),PC,SP,error等特殊寄存器:

其中vreg是指虚拟机的特殊寄存器。

addvi指令的用途在于,由于程序文件是加载到内存中的随机地址中,所以要读取储存在程序文件中的数据块data,只能通过相对程序头部或相对某指令偏移的方法,通过addvi指令就可以rd=pc+offset,从而获取到数据块的地址。

而真正赋予虚拟机能力的是系统调用指令,让虚拟机站在巨人的肩膀上。

系统调用是调用C函数执行操作,例如分配内存,输出文字到控制台,从控制台获取输入等,这些函数使虚拟机连接到了真实世界中。

系统调用不同于虚拟机内函数调用,它运行在C环境中,所以不用移动寄存器窗口,系统函数直接从窗口内获取参数并将结果写入窗口内。

目前function是8位的空间,所以可以容纳256种系统调用。

目前的系统函数简单封装了malloc/free/resize/printf/scanf,后续会继续完善。

移位操作指令

移位共有左移位(shl)、右算术移位(shr)和右逻辑移位(ushr)三种类型。

我认为移位是很常用的功能,所以每种移位我都给了4条指令。总共12条指令。

位运算指令

 位运算有“与”、“或”、“异或”和一个还未添加的“非”指令。

如果加上一条非指令not rd,共有10条指令。

乘除法指令

乘数法指令格式类似于加减法。但立即数乘除法都只设计了8位的立即数,而没有16位和32位,我还在考虑他们的实用性。

除法格式相同。

程序结束指令

 这个放在最后写,有始有终。与真实系统不同,真实系统从开机开始就一直在运行指令,不需要停止,而虚拟机就像一个程序,通常都会有运行结束的时候。

所以我使用END符代表结束,opcode=0xFF,虚拟机碰到这个指令就会正常的结束退出。

 


 

接下来

至此,我已经介绍完所有已确定的和未列入集的指令,总共有73条。之后,我打算先测试目前指令的实用性,然后谨慎添加需要的指令。

计划加入浮点数和可能增加的栈指令后,指令总数在180之内,最后考虑添加向量指令。

指令集大致确定之后,我就开始编写虚拟机代码,下一篇文章将会记录LVM虚拟机的实现过程和优化心得。

 

 

原文出处:https://www.cnblogs.com/h5l0/p/design_hl_instruction_set.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部