L02 RISC-V haskell and Binary Notation

MIT 6.004 Spring 2019 L02 RISC-V haskell，由Silvina Hanono Wachman讲述。

主要内容包括RISC-V汇编语言的继续讨论和二进制表示的深入探讨。

RISC-V汇编语言讨论

  • 介绍了RISC-V指令集架构（ISA），这是软件和硬件之间的一种契约，规定了处理器可以进行的所有操作、可用的存储空间以及如何利用这些硬件资源。
  • 讨论了存储结构，包括32位宽的寄存器文件和主存储器，以及用于访问常数和内存中数据的指令格式。
  • 详细说明了如何执行计算指令、控制流指令（条件分支和无条件跳转）以及如何进行加载和存储操作，包括使用基址加偏移量的方法来访问内存。

指令和操作

  • 通过示例详细讲解了RISC-V汇编语言中包括算术运算、逻辑运算、移位操作、加载和存储数据、以及如何实现条件分支和跳转等指令的使用。
  • 强调了汇编语言中使用的二进制和十六进制表示法，以及如何将高级语言中的表达式和控制流结构翻译成汇编指令。

课程结束部分

  • 课程的最后部分讨论了使用二进制表示负数的方法，即二进制补码表示法，并指出所有汇编指令中使用的常数都采用二进制补码形式。
  • 虽然时间有限，未能覆盖所有内容，但计划在下次课堂讨论中继续深入讲解。

分页知识点

微处理器的组件

  • 寄存器文件（Register File）：存储临时数据，可以快速访问。
  • 算术逻辑单元（ALU）：执行算术和逻辑操作。
  • 主内存（Main Memory）：存储程序和数据，由地址和数据组成，每个内存位置是 32 位宽。

RISC-V 处理器存储

  • 主内存中的每个位置是 32 位宽（4 字节）。
  • 寄存器：32 个通用寄存器，每个寄存器是 32 位宽。
  • x0 寄存器：硬编码为 0，任何写入 x0 的操作都不会改变其值。

RISC-V 指令集架构（ISA）

  • ISA 的定义：软件和硬件之间的契约，定义操作和存储位置的功能描述。
  • RISC-V ISA：一种来自伯克利的新开放 ISA，包括不同的数据宽度和指令。
  • 指令类型：
    • 计算指令：在寄存器上执行算术和逻辑操作。
    • 加载和存储指令：在寄存器和主内存之间移动数据。
    • 控制流指令：更改指令执行顺序，支持条件语句和循环。

计算指令

  • 算术、比较、逻辑和移位操作：

    • 寄存器-寄存器指令

      ：使用两个源操作数寄存器和一个目标寄存器。

      • 算术操作：加法（add）、减法（sub）
      • 比较：设置小于（slt）、设置小于无符号（sltu）
      • 逻辑：与（and）、或（or）、异或（xor）
      • 移位：逻辑左移（sll）、逻辑右移（srl）、算术右移（sra）

例子：

  • add x3, x1, x2 表示 x3 = x1 + x2。
  • slt x3, x1, x2 表示如果 x1 < x2 则 x3 = 1，否则 x3 = 0。
  • and x3, x1, x2 表示 x3 = x1 & x2。
  • sll x3, x1, x2 表示 x3 = x1 << x2。

二进制运算

  • 所有值都是二进制：
    • 例如：x1 = 00101; x2 = 00011
    • add x3, x1, x2 表示 x3 = x1 + x2。与十进制中的 5 + 3 = 8 相对应，二进制计算结果为 01000。
    • sll x3, x1, x2 表示将 x1 向左移动 x2 位，结果为 01000。

二进制模运算

  • 如果我们使用固定数量的位进行计算，加法和其他操作可能会产生超出范围的结果。这称为溢出。
  • 通常的做法是忽略额外的位，采用模运算。对于 N 位数字，等同于执行 mod 2^N。
  • 视觉上，可以看到数值在最大和最小值之间“环绕”。

十六进制表示法

  • 长二进制串手工转换容易出错，因此常用高基数（radix）表示法，十六进制是一种流行的选择。
  • 十六进制使用基数16，每4个相邻的二进制位编码为一个十六进制数字。
  • 示例：二进制串 011110100000 转换为十六进制为 0x7D0。

寄存器-立即数指令

  • 一种操作数来自寄存器，另一个是编码在指令中的小常数。
    • 格式：操作 目标寄存器，源寄存器1，常数
      • addi x3, x1, 3 // x3 = x1 + 3
      • andi x3, x1, 3 // x3 = x1 & 3
      • slli x3, x1, 3 // x3 = x1 << 3
    • 注意没有subi指令，而是使用负数常量。
      • addi x3, x1, -3 // x3 = x1 - 3

控制流指令

  • 根据条件执行不同的操作：
    • 如果 a < b，则 c = a + 1
    • 否则，c = b + 2
  • 需要条件分支指令：
    • 格式：条件 源寄存器1 比较 源寄存器2，标签
    • 如果比较结果为True，则跳转到标签处执行，否则按顺序执行程序。

复合计算

  • 执行 a = ((b+3) >> c) - 1;
    • 将复杂表达式分解为基本计算。我们的指令只能指定两个源操作数和一个目标操作数（也称为三地址指令）。
    • 假设 a, b, c 存在寄存器 x1, x2, 和 x3 中，分别使用 x4 作为 t0, x5 作为 t1。
      • t0 = b + 3;
      • t1 = t0 >> c;
      • a = t1 - 1;

无条件控制指令：跳转

  • jal：无条件跳转并链接

    • 例子：jal x3, label
    • 跳转目标指定为标签，标签被编码为当前指令的偏移量
    • 链接（在下次讲座中讨论）：存储在 x3 中

  • jalr：通过寄存器和链接进行无条件跳转

    • 例子：jalr x3, 4(x1)
    • 跳转目标指定为寄存器值加上常数偏移量
    • 例子：跳转目标 = x1 + 4
    • 可以跳转到任何 32 位地址 - 支持长跳转

以上解释中，“无条件跳转并链接”（jal）是一种跳转指令，用于无条件地将程序的执行流跳转到指定的地址，并将下一条指令的地址保存在寄存器中，通常用于函数调用。 “通过寄存器和链接进行无条件跳转”（jalr）是一种变体，允许跳转到一个基于寄存器值和常数偏移量计算的地址。这些都是 RISC-V 指令集中控制程序流的基础操作。

在内存中执行计算

当我们需要对存储在内存中的值执行计算时，我们会用到加载（load）和存储（store）指令。以计算 a = b + c 为例，我们会按以下步骤进行：

  1. 从内存地址 Mem[b] 加载 b 的值到寄存器 x1。
  2. 从内存地址 Mem[c] 加载 c 的值到寄存器 x2。
  3. 将寄存器 x1 和 x2 中的值相加，并将结果存储到寄存器 x3。
  4. 将寄存器 x3 的值存储回内存地址 Mem[a]。

例如，如果 b 和 c 分别位于内存地址 0x4 和 0x8，而我们想要将它们的和存储在地址 0x10，对应的汇编代码如下：

lw x1, 0x4(x0)
lw x2, 0x8(x0)
add x3, x1, x2
sw x3, 0x10(x0)

RISC-V 加载和存储指令

由于一些很好的技术原因，RISC-V 指令集架构不允许我们直接将内存地址写入指令。我们需要以 <基址, 偏移量> 的形式指定地址：

  • 基址始终存储在一个寄存器中。
  • 偏移量是一个小常数。
  • 格式示例：lw dest, offset(base) 或 sw src, offset(base)。

汇编示例中的行为如下：

lw x1, 0x4(x0)   // x1 <- load(Mem[x0 + 0x4])
lw x2, 0x8(x0)   // x2 <- load(Mem[x0 + 0x8])
add x3, x1, x2   // x3 <- x1 + x2
sw x3, 0x10(x0)  // store(Mem[x0 + 0x10]) <- x3

常量和指令编码限制

  • 指令被编码为 32 位。
    • 需要指定操作码（10位）。
    • 需要指定2个源寄存器（10位）或1个源寄存器加上一个小常数。
    • 需要指定1个目的寄存器（5位）。
  • 指令中的常数必须小于12位；更大的常数需要存储在内存或寄存器中并显式使用。
  • 正是由于这个限制，我们从不在指令中直接指定内存地址。

程序求和数组元素

假设我们有一个求和函数，计算数组 a 的所有元素之和，其中 a[0] 到 a[n-1]。假设基地址（地址 100）已经加载到寄存器 x10 中，对应的汇编代码如下：

lw x1, 0x0(x10)
lw x2, 0x4(x10)
lw x3, 0x8(x10)
... // 继续加载其它数组元素并求和

伪指令

  • 伪指令是简化汇编编程的别名，它们映射到实际的汇编指令。
    • 例如，mv x2, x1 伪指令等价于 addi x2, x1, 0 汇编指令。
伪指令等效汇编指令
mv x2, x1addi x2, x1, 0
ble x1, x2, labelbge x2, x1, label
bgez x1, labelbge x1, x0, label
bnez x1, labelbne x1, x0, label
j labeljal x0, label

负数的编码

  • 表达负数的方式包括符号大小表示法和二进制补码表示法。

符号大小表示法

  • 我们使用符号大小表示法来表达十进制数，用 "+" 和 "-" 分别代表正负号。
  • 例如：对于二进制数 11111110000，0 表示 "+"，1 表示 "-"，这表示 -2000。
  • 这种编码可能会有哪些问题？会有两种表示方式表示 0（+0 和 -0），而且为加减法设计电路比无符号数复杂。

寻找更好的编码方法

  • 你能否简单地重新标记一些数字，以保留模数运算的好属性？答案是肯定的。

例如：

  • -1 用 111 表示
  • -2 用 110 表示
  • -3 用 101 表示
  • -4 用 100 表示
  • 这就是所谓的二进制补码编码。

二进制补码编码

  • 在二进制补码编码中，N 位数的最高位用于表示符号（正数为 0，负数为 1）。
  • 二进制补码的形式：v = -2^N-1*b_N-1 + Σ (b_i*2^i) for i = 0 to N-2
  • 负数的最高位是“1”。
  • 最负数是 10...000 -> -2^N-1
  • 如果所有位都是 1，则是 -1。
  • 指令中编码的常量使用二进制补码编码。

Take home

  1. 用 6 位二进制补码表示 -4。
  2. 将下面的代码片段翻译成 RISC-V 汇编：
sum = 0;
for (i = 0; i < 10; i++) {
  sum = sum + i;
}
end