III. Instructions

本篇笔记围绕 RISC-V 架构介绍了计算机指令系统的基本概念。首先介绍了 RISC-V 的 32 个通用寄存器及其约定用途，包括零寄存器、返回地址寄存器、堆栈指针等。接着讨论了内存系统的特点，包括字节寻址、小端存储等概念。重点阐述了 RISC-V 的指令格式(R/I/S/B/U/J 型)及其编码方式，详细介绍了分支指令、过程调用指令、数据加载存储指令、跳转指令等常用指令的使用方法和实现细节。（由 claude-3.5-sonnet 生成摘要）

我们的课程和教材围绕 RISC-V 架构编写，因而本章也将围绕 RISC-V 中的设计展开。

Why RISC-V Architecture?

开放。
具有现代 指令集架构(Instruction Set Architecture, ISA) 的特征。
类似的 ISA 在市场上占据很大份额。

1. Register

RISC-V 架构提供 32 个数据寄存器，每个寄存器的大小是 64 位。（设计原则：smaller is faster，寄存器的空间远小于内存）

RISC-V 中对寄存器的约定如下（不过，对于其中的一些寄存器，我们在自己做题的时候也不是不能混用）：

$\texttt{x0}$ ( $\texttt{zero}$ ) 常量 0。这一寄存器的值一直是 0。
$\texttt{x1}$ ( $\texttt{ra}$ ) 保存 返回地址(return address)，即完成过程调用后 PC 需要回到的位置。
- 所以说伪指令 ret 其实就是 jalr x0, 0(x1)。
$\texttt{x2}$ ( $\texttt{sp}$ ) 是 堆栈指针(stack pointer)，始终指向栈顶元素。
- 栈从高地址向低地址增长，例：addi sp, sp, -24 , sd x5, 16(sp) , sd x6, 8(sp) , sd x20, 0(sp) 可以实现将 x5, x6, x20 压栈。
$\texttt{x5} \sim \texttt{x7}$ ( $\texttt{t0} \sim \texttt{t2}$ ) - $\texttt{x7}$ ( $\texttt{t2}$ ) 和 $\texttt{x28} \sim \texttt{x31}$ ( $\texttt{t3} \sim \texttt{t6}$ ) 是 临时寄存器(temporary register)，不保证在经过过程调用之后临时寄存器的值不变，需要的话应由 caller 保存。
$\texttt{x8} \sim \texttt{x9}$ ( $\texttt{s0} \sim \texttt{s1}$ ) 和 $\texttt{x18} \sim \texttt{x27}$ ( $\texttt{s2} \sim \texttt{s11}$ ) 是 保留寄存器(saved register)，保证过程调用前后这些寄存器的值不变。如果 callee 需要修改这些寄存器，就需要再堆栈中保存一份，以便在返回前恢复。
$\texttt{x10} \sim \texttt{x17}$ ( $\texttt{a0} \sim \texttt{a7}$ ) 用于存储过程参数或者数返回值。
- 函数调用的前 8 个参数会放在这些寄存器中；如果参数超过 8 个则需要放到栈上（例：放在 $\texttt{fp}$ 上方， $\texttt{fp} + 8$ 是第 9 个参数， $\texttt{fp} + 16$ 的第 10 个……）。
- 在过程调用结束后，过程的返回值也应被放在这些寄存器中。像 C 语言一般来说只有一个，就放在 $\texttt{x10}$ ( $\texttt{a0}$ ) 寄存器中。

一些 RISC-V 编译器保留寄存器 x3 用来指向静态变量区，称为 global pointer gp 。
一些 RISC-V 编译器使用 x8 指向 activation record 的第一个 dword，方便访问局部变量；因此 x8 也称为 frame pointer fp 。在进入函数时，用 sp 将 fp 初始化。
- fp 的方便性在于在整个程中对局部变量过的所有引用相对于 fp 的偏移都是固定的，但是对 sp 不一定。当然，如果过程中没有什么栈的变化或者根本没有局部变量，那就没有必要用 fp 了。
RISC-V 架构还提供一系列浮点数寄存器 f0 ~ f31，不过这并不是这里我们讨论的重点。

Cheetsheet

2. Memory

RISC-V 结构的内存按照 8 位为一个 字节(byte) 存储，地址宽度为 64 位。此外，一个 word 为 32 位，一个 双字(doubleword) 为 64 位。也就是说，RISC-V 架构的指令总共可以寻址 $2^{64}$ 个字节，也即 $2^{67}$ 个 bit 或者 $2^{61}$ 个 dword。

RISC-V 架构使用 小端存储(Little Endian)，即最低有效位放在内存最低处。按照小端存储的方式存储 0x12345678 得：(low) 78 56 34 12 (high)（如果按照一般逻辑，从左到右进行书写，实际上是是对应 大端存储(Big Endian)）。

Memort Alignment

CPU 一次只能读出 4 字节内存中的一行，所以为了一次性读出下图结构体中的 float e，需要使用 内存对齐(memory alignment) 的技术。

Constant vs Immediate Operands？

编译器可以通过从指定地址取值的方式来实现 常量(constant)，为了让操作更快，我们希望引入 立即数(immediate operands)，从而省掉寻址的时间。（设计原则：make common case fast）

RISC-V 支持四种 寻址(addressing) 方式：

立即数寻址(immediate addressing)
寄存器寻址(register addressing)
基址寻址(base addressing)：例：8(sp)
PC-relative 寻址(PC-relative addressing)

Memory Layout

3. Instructions

根据存储程序原理，我们二进制对每一条指令编码表示，叫作 机器码(machine code)。

Note

（精简指令集的）一条指令只用来实现一个运算。（设计原则：Simplicity favors regularity）

3.1. Instruction Formats

在 RISC-V 架构中，所有指令的长度都固定为 32 位。（设计原则：good design demands good compromises）

这里每种指令 format 的空间分布需要记忆，部分需要用到的指令的 opcode 和 funct 会在考试时给出。

缩写解释：

rs：源寄存器(register source)
rd：目标寄存器(register destination)
imm：立即数(immediate operands)
opcode：操作编码(operation code)
funct：函数编码(function code)，用来和 opcode 共同表示运算。

指令类型：

R-type：使用寄存器进行数字逻辑运算的指令格式，具体运算 op 由 opcode funct3 funct7 共同决定，功能为：rd = rs1 op rs2。
I-type：寄存器与立即数的运算，或者 load 类指令等只需要用到一个源寄存器的指令，功能为：rd = rs1 op imm。这里虽然立即数 imm 只有 12 位，但会先符号扩充到 64 位再参与运算，故立即数实际上为：{{52{inst[31]}}, inst[31:20]}。
- 立即数 移位(shift) 操作（slli、srai 等）是一类特殊的 I 型指令，因为对一个 64 位数进行 $\ge 64$ 位的移位操作没有意义，所以将其 imm 的 12 位分成 6 位的 funct6 和 6 位的立即数 immed，其中 immed 用来表示移位位数。
S-type：store 类指令。这里 rs1 存储 基址(base address) 寄存器编号，rs2 存储源操作数寄存器编号。
- sd 指令例：sd x9, 64(x22)，则 rs1 为 22、rs2 为 9、imm 为 64。
U-type：

为什么 SB 和 UJ 类型指令都不存储立即数的最低位（imm[0]）呢？

因为这两种指令的立即数都是指偏移，而我们的地址是 2 字节对齐的，因此最后一位一定是 $0$ ，不需要存储。

Cheatsheet

Pesudo Instructions

3.2. Branch & Loop

基于相等的跳转语句：

$\texttt{\color{blue}beq {\color{blue}rs1}, {\color{blue}rs2}, {\color{blue}label}}$ (B-type)：相等则跳转。
$\texttt{\color{blue}bne {\color{blue}rs1}, {\color{blue}rs2}, {\color{blue}label}}$ (B-type)：不相等则跳转。

基于比较的跳转语句：注意这里的比较都是有符号数的比较，如果需要无符号数的比较，请使用 bltu、bgeu 等指令。

$\texttt{\color{blue}blt rs1, rs2, label}$ (B-type)： $\text{if (}\texttt{rs1} < \texttt{rs2}\text{) branch to instruction labeled }\texttt{label}\text{.}$
$\texttt{\color{blue}bgt rs1, rs2, label}$ (B-type)： $\text{if (}\texttt{rs1} > \texttt{rs2}\text{) branch to instruction labeled }\texttt{label}\text{.}$
$\texttt{\color{blue}ble rs1, rs2, label}$ (B-type)： $\text{if (}\texttt{rs1} \leq \texttt{rs2}\text{) branch to instruction labeled }\texttt{label}\text{.}$
$\texttt{\color{blue}bge rs1, rs2, label}$ (B-type)： $\text{if (}\texttt{rs1} \geq \texttt{rs2}\text{) branch to instruction labeled }\texttt{label}\text{.}$

最热门的比较运算

$\texttt{\color{blue}slt {\color{blue}rd}, {\color{blue}rs1}, {\color{blue}rs2}}$ ：set on less then，当 $\texttt{rs1} < \texttt{rs2}$ 时令 $\texttt{rd}=1$ 。
- 可以将比较结果搭配 beq 或 bne 语句使用。

如果分支体/循环体比较长，我们可能需要 branching 到一个比较远的位置，这时需要使用 jal 或 jalr 指令，必要时可以反转条件，如下面这个例子：

3.3. Procedure

一些约定：

用 $\texttt{a0} \sim \texttt{a7}\text{ }(\texttt{x10} \sim \texttt{x17})$ 这八个参数寄存器保存 过程参数(procedure parameter) 和 返回值(return value)。
用 $\texttt{ra}\text{ }(\texttt{x1})$ 来存储返回地址。
- 通过 $\texttt{jal x1, label}$ 指令进入函数体；在过程最后用 $\texttt{jalr x0, 0(x1)}$ 指令（等价于伪指令 ret）返回。
- 如果过程体中还需要调用其他过程，记得把 $\texttt{ra}$ 保存到堆栈中。
在过程体中，最好使用 $\texttt{t0} \sim \texttt{t6}$ 这 7 个临时寄存器；尽量不要使用 $\texttt{s0} \sim \texttt{s11}$ 这些保留寄存器。如果非要使用，需要手动压栈出栈保证保留寄存器的值在过程调用前后保持不变。

我们可以通过对栈指针寄存器 $\texttt{sp}$ 的控制实现 push 和 pop 功能。

push： $\texttt{addi sp, sp, -8; sd ..., 8(sp)}$
pop： $\texttt{ld ..., 8(sp); addi sp, sp, 8}$

而帧指针寄存器 $\texttt{fp}$ 则始终指向栈顶，其在函数调用过程中保持不变（一些 RISC-V 编译器在进入过程时会自动用 $\texttt{sp}$ 初始化 $\texttt{fp}$ ），可以通过 $\texttt{fp}$ 寄存器方便地访问局部变量、保存的参数等。

Example: Compile a recursive factorial function

3.4. Load & Store Instructions

load 和 store 是唯二两个在寄存器和内存之间进行 数据传输(data transfer) 的指令。

我们的寄存器是 64 位的（dword），但有时我们需要从内存/堆栈中读取小于 64 位的（byte/halfword/word）数据，这时候就会涉及到扩充的问题，以下 load 指令都是 符号扩充(sign extend) 的，

$\texttt{\color{blue}lb rd, offset(rs1)}$ ：load byte，从 $\texttt{offset(rs1)}$ 地址开始读取 8 位并符号扩充到 64 位后保存到 $\texttt{rd}$ 中。
$\texttt{\color{blue}lh rd, offset(rs1)}$ ：load halfword，从 $\texttt{offset(rs1)}$ 地址开始读取 16 位并符号扩充到 64 位后保存到 $\texttt{rd}$ 中。
$\texttt{\color{blue}lw rd, offset(rs1)}$ ：load word，从 $\texttt{offset(rs1)}$ 地址开始读取 32 位并符号扩充到 64 位后保存到 $\texttt{rd}$ 中。
$\texttt{\color{blue}ld rd, offset(rs1)}$ ：load dword，从 $\texttt{offset(rs1)}$ 地址开始读取 64 位并保存到 $\texttt{rd}$ 中。

下面这些 load 指令则是遵循 零扩充(0 extend) 的：

$\texttt{\color{blue}lbu rd, offset(rs1)}$ ：load byte unsigned，从 $\texttt{offset(rs1)}$ 地址开始读取 8 位并零扩充到 64 位后保存到 $\texttt{rd}$ 中，常用于读取 ASCII 字符。
$\texttt{\color{blue}lhu rd, offset(rs1)}$ ：load halfword unsigned，从 $\texttt{offset(rs1)}$ 地址开始读取 16 位并零扩充到 64 位后保存到 $\texttt{rd}$ 中。
$\texttt{\color{blue}lwu rd, offset(rs1)}$ ：load word unsigned，从 $\texttt{offset(rs1)}$ 地址开始读取 32 位并零扩充到 64 位后保存到 $\texttt{rd}$ 中。

store 指令的话就是保存寄存器最右边的（最低的）若干位。

$\texttt{\color{blue}sb rs2, offset(rs1)}$ ：store byte，保存 $\texttt{rs2}$ 寄存器的最右 8 位到 $\texttt{offset(rs1)}$ 地址。
$\texttt{\color{blue}sh rs2, offset(rs1)}$ ：store halfword，保存 $\texttt{rs2}$ 寄存器的最右 16 位到 $\texttt{offset(rs1)}$ 地址。
$\texttt{\color{blue}sw rs2, offset(rs1)}$ ：store word，保存 $\texttt{rs2}$ 寄存器的最右 32 位到 $\texttt{offset(rs1)}$ 地址。
$\texttt{\color{blue}sd rs2, offset(rs1)}$ ：store dword，保存 $\texttt{rs2}$ 寄存器的最右 64 位到 $\texttt{offset(rs1)}$ 地址。

Example: String copy

3.5. Jump Instructions

$\texttt{\color{blue}jal rd, label}$ (UJ-type)：jump and link，保存下一语句地址（ $\texttt{pc + 4}$ ）到寄存器 $\texttt{rd}$ 并跳转到 $\texttt{label}$ 处。
- 实现： $\texttt{rd = pc + 4, pc = pc + imm}$ 。
$\texttt{\color{blue}jalr rd, imm(rs1)}$ (I-type)：jump and link register，保存下一语句地址到寄存器 $\texttt{rd}$ 并跳转到 $\texttt{imm + rs1}$ 地址的指令。
- 实现：rd = pc + 4, pc = (imm + rs1) & 0xFFFFFFFE，注意 $\texttt{pc}$ 的最低位一定会被设为 $0$ 。

Example: Jump address table

C code:

switch (k) {
    case 0: f = i + j; break;
    case 1: f = g + h; break;
    case 2: f = g - h; break;
    case 3: f = i - j; break;
}

assembly:

Conception: Basic Blocks

一段（除了开头外）没有分支标签且（除了结尾外）没有跳转语句的指令称为一个 基本块(basic block)，编辑器可以识别基本块并进行优化。

我们的 label 在转化为机器码时需要换算成具体的 offset。考虑一条指令的长度为 32 位 / 4 字节，故 offset 即目标地址减当前地址应刚好是相差指令数的 4 倍，但是注意 PC-relative 寻址是根据半字长（16 位 / 2 字节）为单位的，所以我们强制 offset 的最低位为 0，且这一最低位也不会表示到机器码中（SB 类型和 UJ 类型指令的特性）。

Example: Calculate offset

C language:
```
while (save[i] == k) i = i + 1;
```
RISC-V assembler code:
Machine code:

$\texttt{\color{blue}lui rd, imm}$ (U-type)：load upper immediate
- 实现：rd = imm << 12。

大立即数的获取：通过 lui 指令设置立即数的高 20 位，然后用 addi 指令设置立即数的低 12 位。注意：由于 addi 指令是 signed 的，第 12 位会被当作符号位；如果我们需要将这一位也置成 $1$ 的话，使用 lui 设置高 20 位的值时需先 $+1$ 。

任意 32 位地址跳转：可以通过 $\texttt{lui t0, address[31:12]; jalr x0, address[11:0](t0)}$ 实现任意位置跳转，如果不需要保存下一条语句地址则使用 $\texttt{x0}$ 作为 $\texttt{rd}$ 即可。

4. Useful Links

TABLE OF CONTENTS

1. Register

2. Memory

3. Instructions

3.1. Instruction Formats

3.2. Branch & Loop

3.3. Procedure

3.4. Load & Store Instructions

3.5. Jump Instructions

4. Useful Links

1. Register

2. Memory

3. Instructions

3.1. Instruction Formats

3.2. Branch & Loop

3.3. Procedure

3.4. Load & Store Instructions

3.5. Jump Instructions

4. Useful Links

评论