听说你想写个虚拟机（三）？

大家好，我是微微笑的蜗牛，🐌。

在上两篇文章中，我们实现了一个最小的虚拟机。如果没看过的同学，可以回过头先去看看。

• 听说你想写个虚拟机（一）？
• 听说你想写个虚拟机（二）？

今天，继续升级打怪，不过难度有所提高，将会模拟一个更加真实的环境，Little Computer-3 的实现，简称 LC-3。

LC-3 是用于教学的汇编语言，它有着相比于 x86 更为简洁的指令集，同时包含了主流 CPU 的经典思想。有关 LC-3 的介绍可点此查看。

LC-3 麻雀虽小，五脏俱全。不过它的规范不算太多，我们模拟它的实现还是比较合适的。

LC-3 基础

首先，介绍一些 LC-3 的前置知识：

• 内存地址空间 16 位，也就是最多可访问 0x0000~0xffff 的范围。
• 通用寄存器 8 个，16 位。编号从 000~111，R0 ~ R7。
• 三个标志寄存器，N（Negative）、P（Postive）、Z（Zero），每个 1 位。
• PC 寄存器。
• 指令长度 16 位，操作码 op 固定高 4 位。
• 采用大端字节序。
• 系统调用表。
• 中断向量表。
• ...

另外，还有一些没有列出来。但我们只打算实现它的一个子集，其他可以不用关注。

内存空间

由于 LC-3 工作在 16 位下，内存最大可访问空间是 2^16-1。

这里我们仍然用数组来模拟，给它分配最大空间 UINT16_MAX 即可。

uint16_t mem[UINT16_MAX];

寄存器

这里我们定义 10 个寄存器，分别是：

• 8 个通用寄存器
• PC 寄存器
• COND 标志寄存器，用于表示 N/P/Z 状态

// 寄存器定义
typedef enum
{
  R_R0,
  R_R1,
  R_R2,
  R_R3,
  R_R4,
  R_R5,
  R_R6,
  R_R7,
  R_PC,
  R_COND,
  R_COUNT
} Registers;

// 寄存器数组
uint16_t reg[R_COUNT];

R_COUNT 用于快速得到寄存器数量，reg[x] 可得到寄存器的值。

标志寄存器

标志寄存器用来标识 N/P/Z 的状态。取值定义如下：

// 标志定义
typedef enum
{
  FL_POS = 1 << 0, // 正数
  FL_ZRO = 1 << 1, // 0
  FL_NEG = 1 << 2  //负数
} ConditionFlags;

指令格式

指定包括操作码和操作数，有着如下标准格式：

• 指令长度为 16 位，高 4 位为操作码，最多可表示 16 种指令。操作码范围 0000~1111。
• 低 12 位用于表示参数。不同的指令，有着不同的参数，占用长度和布局也不一样。

指令的大体布局如下：

指令布局

注意：指令的参数中可能会包含寄存器、立即数等等。寄存器统一用 3 位来标识，因为总共只有 8 个通用寄存器。

指令定义

这次，我们打算实现如下指令。

// 指令定义
typedef enum
{
  OP_BR = 0,    // 条件分支
  OP_ADD = 1,   // 加法
  OP_LD = 2,    // 取内存地址的值到寄存器
  OP_ST = 3,    // 存寄存器的值到内存地址
  OP_JSR = 4,   // 跳转函数
  OP_AND = 5,   // 与运算
  OP_LDR = 6,   // 取值到寄存器
  OP_STR = 7,   // 存储寄存器的值
  OP_RTI = 8,   // unused
  OP_NOT = 9,   // 取反
  OP_LDI = 10,  // 间接取值
  OP_STI = 11,  // 间接存值
  OP_JMP = 12,  // 跳转
  OP_RES = 13,  // reserved
  OP_LEA = 14,  // 加载地址到寄存器
  OP_TRAP = 15, // 系统调用
} InstructionSet;

主要分为如下几类：

• 运算
• 数据存取
• 跳转
• 系统调用
• 保留指令，暂时为使用，可用于占位

由于指令有点多，且实现更复杂。全部写完文章会拖的太长，因此打算分为 3 篇来讲。这篇主要介绍运算、跳转和保留指令，使用汇编的方式说明用法（🤩 0101.. 看着头大）。

指令实现

ADD

加法指令，操作码为 0001，总共三个参数。指令执行之后，会更新标志寄存器的值。

它有两种模式，不同的模式通过指令第 6 位标志位来区分。主要区别在于第三个参数。

• 若标志位为 1，则为立即数模式；
• 若标志位为 0，则为寄存器模式。

以下代码中用于取出标志位，instr 表示指令。

// 取出 flag，在第 6 位。
uint16_t flag = (instr >> 5) & 0x1;

1. 立即数模式

ADD R0, R1, #5 → RO = R1 + 5

第三个参数为数字，可直接使用，所以称之为立即数。

指令布局如下，标志位为 1。

image

低 5 位为立即数。由于寄存器是 16 位，与立即数相加时，需将立即数以有符号的方式扩展到 16 位。

扩展方式比较简单，若最高位为 1，则全部填 1；若最高位为 0，则全部填 0。如下图所示：

image

由于符号扩展在很多指令中都会用到。因此，我们写个通用的函数，专用于处理符号扩展。

// 符号扩展
uint16_t sign_extend(uint16_t x, int bit_count)
{
  // 最高位 1
  if ((x >> (bit_count - 1)) & 0x1)
  {
        // 全部补 1
    x |= 0xFFFF << bit_count;
  }

  return x;
}

搞清楚指令布局和符号扩展后，实现就比较简单了。

1. 取出「目的寄存器 r0」，注意寄存器相关的值都是寄存器下标。
2. 取出「源寄存器 r1」。
3. 取出「立即数 imm」，并进行符号扩展。
4. 相加求和，将结果放入「目的寄存器 r0」。

// 取出目的寄存器 r0，9~11，占 3 位，与上 111
uint16_t r0 = (instr >> 9) & 0x7;

// 源寄存器 r1，6~8 位
uint16_t r1 = (instr >> 6) & 0x7;

// 低五位，取出立即数。
uint16_t data = instr & 0x1F;

// 符号扩展，若高位是 1，则全部补 1
uint16_t value = sign_extend(data, 5);

// 求和
reg[r0] = reg[r1] + value;

// 更新标志寄存器
update_flags(r0);

最后，还剩一步，lc-3 规范中要求更新标志寄存器。根据当前操作寄存器的符号位，设定不同的状态。如下所示：

// 更新标志寄存器
void update_flags(uint16_t r)
{
  uint16_t value = reg[r];
  if (value == 0)
  {
    COND = FL_ZRO;
  }
  else if ((value >> 15) & 0x1)
  {
    // 最高位 1，负数
    COND = FL_NEG;
  }
  else
  {
    COND = FL_POS;
  }
}

这样，立即数模式的实现就完成了。

下面再来举个实际的 🌰，说明下指令的布局。

假设我们想做这样的操作：ADD R1,R2,#6，那么指令数据如下图所示：

image

其中 操作码=0001；第一个参数=001；第二个参数=010；第三个参数=00110，最终的十六进制表示为：0x12A6。

2. 寄存器模式

ADD RO, R1, R2 → RO = R1 + R2

第三个参数为寄存器，需从寄存器中取值。

指令布局如下，标志位为 0。

image

寄存器模式的实现更加简单，取出「源寄存器 2」的值，与「源寄存器 1」相加，结果放入「目的寄存器」。

// 取出源寄存器 2，低 3 位
uint16_t r2 = instr & 0x7;

// 相加
reg[r0] = reg[r1] + reg[r2];

// 更新标志寄存器
update_flags(r0);

寄存器模式下的指令，你也可以试着举个实例栗子，动手写写看。

AND

与运算，操作码 0101。和 ADD 一样，有两种模式，指令格式一模一样。把求和改成求与就好，就不重复了。

两种模式的指令布局如下图所示：

image

NOT

NOT R0, R1; R0 = ~R1

取反指令，操作码 1001。取反之后同时更新标志寄存器。

指令布局如下所示，低六位没有使用，全是 1。

image

目的寄存器和源寄存器的取法跟 ADD 指令是一样，代码实现如下：

// 取出目的寄存器 r0，9~11，占 3 位，与上 111
uint16_t r0 = (instr >> 9) & 0x7;

// 源寄存器 r1，6~8 位，
uint16_t r1 = (instr >> 6) & 0x7;

reg[r0] = ~reg[r1];

// 更新标志寄存器
update_flags(r0);

JMP

JMP R1

跳转指令，操作码 1100，只有一个寄存器参数，在 6~8 位。作用是更新 PC 为寄存器的值。

指令布局如下：

image

代码实现如下：

// 取出寄存器
uint16_t r1 = (instr >> 6) & 0x7;

// 更新 PC
PC = reg[r1];

RET

RET 并不在我们要实现的指令列表中。这里之所以单独拎出来讲，是因为 RET 是 JMP 指令的特例。

RET 是在函数调用完成后，用于恢复 PC 寄存器的值。

只不过这时候寄存器固定是 R7，所以参数就为 111。如下图所示：

image

也就相当于：

RET = JMP R7

JSR

全称为 Jump to Subroutine，也就是函数调用，操作码 0100。

它有两种模式，通过指令第 12 位 flag = instr[11] 来区分。

两种模式的前置操作均为保存现场：将当前 PC 值保存到 R7 中，目的是为了在函数调用完成之后恢复原 PC 值。

1. 标签模式

JSR label

跳转到 label 标签处的函数执行，标签就是一个名称。

注意，实际上 JSR 的参数是「相对于 PC 的偏移量」，是个数值，其中 PC 指向要执行的下一条指令。因为最终肯定是跳转到某个地址。这里是汇编的形式说明用法。

另外，这里 PC 的含义跟前面文章中说的稍微有些区别，前面的 PC 指的是当前执行指令，这里指的是下一条指令。这对理解无大碍，只不过实现方式不一样而已。

此时，flag = 1。 指令布局如下：

image

0~10 位为相对于 PC 的偏移量，将其取出来进行符号扩展，然后与 PC 相加。

// long_pc_offset
uint16_t long_pc_offset = sign_extend(instr & 0x7ff, 11);

// 更新 pc
PC += long_pc_offset;

2. 寄存器模式

JSRR R1

跳转到 R1 寄存器中的地址，寄存器在 6~8 位。

此时，flag = 0。 指令布局如下：

image

取出寄存器，将 PC 更新为寄存器中的值即可。

// 取出寄存器
uint16_t r1 = (instr >> 6) & 0x7;

// 更新
PC = reg[r1];

BR

根据「条件标志位」进行跳转，操作码是 0000。跳转参数是相对于 PC 的偏移量，在 0~8 位。

指令布局如下：

image

condition_flag 中包含 n/z/p 的状态，只要任意一个状态与当前标志寄存器相符，则进行跳转。

// 取出标志参数
uint16_t cond_flag = (instr >> 9) & 0x7;

// 偏移量
uint16_t pc_offset = sign_extend(instr & 0x1FF, 9);

// 传入标识是否与标志寄存器的值相符，n,z,p
if (cond_flag & COND)
{
    PC += pc_offset;
}

保留指令

RTI 和 RES 未使用，不处理即可。不过它们倒是可以用作占位指令，下面会讲到。

手写指令

实现了这么些指令，还得上手操练一下，检查下正确性。可现在我们还没有定义程序退出的指令，不然运行虚拟机会进入死循环。

LC-3 中的退出指令定义在 TRAP 系统调用中，后面的文章会专门讲 TRAP 指令，操作码是 1111。

那我们先简单处理下，约定只要遇到操作码是 1111 的指令，就认为是程序退出，不用管后面的参数。所以暂且将退出指令定为 0xf000。

最后，我写了些指令，不得不说真的很麻烦😆。它的功能如下：

• 先执行两个 ADD 指令。
• 执行 JSR， 跳转到第六条指令 RES。
• 执行 RES 指令，继续执行，直至退出。

// 内存区
uint16_t mem[UINT16_MAX] = {
    // ADD R0,R1,R2
    0x1042,

    // ADD R1,R2,#6
    0x12A6,

    // JSR 2;
    // 下一条是第 4 条指令，PC=3，跳转到 PC=3+2，也就是第 6 条指令 RES。
    0x4802,

    // JMP R1;跳转到第 6 条指令
    0xC040,

    // RTI;占位
    0X8000,

    // RES;占位
    0XD000,

    // NOT R3, R1
    0x967F,

    // trap-halt
    0xf000,
};

为了方便调试，在每条指令执行时，打印了当前操作码。指令执行完成后，最后再打印出了 r0~r3 寄存器的值。

执行完上述代码后，结果如下所示：

exe op:ADD
exe op:ADD
exe op:JSR
exe op:RES
exe op:NOT
exe op:TRAP
r0,0
r1,6
r3,65529

另外，你也可以添加自己的指令试试，绝对值得体验一下效率暴跌的感觉😆。

完整代码可点此查看。

参考资料

• LC-3 介绍：https://en.wikipedia.org/wiki/Little_Computer_3#C_and_the_LC-3
• LC-3 规范：https://justinmeiners.github.io/lc3-vm/supplies/lc3-isa.pdf
• https://justinmeiners.github.io/lc3-vm/#1:8
• https://github.com/silan-liu/virtual-machine