【计组】第二章整理 - Study & Coding Just Fun!

笔记说明：自己对上课PPT的摘要+zju大佬笔记的补充。有些地方写的不是很严谨或顺序乱，后面会整理。

感谢-笔记参考：https://xuan-insr.github.io/computer_organization/2_instructions/ （咸鱼暄的代码空间）

目录#

待整理](#%E5%BE%85%- 章节理解维度

Outline
Introduction
Arithmetic Operations
Oprands
Representing Instructions
Logic Operations
C和汇编转换
- 常见Branch举例
- Jump register & jump address table（switch逻辑）
Supporting Procedures 过程调用
竞争与同步
Linker && Loader
待整理

章节理解维度#

三种语言：高级语言、汇编语言、机器语言

高级语言（C语言）————汇编语言
汇编语言（汇编指令）————机器语言（机器码）

Outline#

Introduction
Operations of the computer hardware
Operands of the computer hardware
Signed and a numbers
Representing instructions in the computer
Logical operations
Instructions for making decision
Supporting procedures in computer hardware
Instruction addressing

Introduction#

instruction set: RISC-V P6 RISC VS CISC 对比表格 P9 Stored-program concept P12

Arithmetic Operations#

Oprands#

RISC-V has a 32 × 64-bit register file
- Use for frequently accessed data
- 64-bit data is called a “doubleword”
  - 32 x 64-bit general purpose registers x0 to x31
- 32-bit data is called a “word” 4个字节一个”字“ 在函数调用中，寄存器 x0 是否被保留取决于调用约定。
RISC-V does not require words to be aligned in memory

alignment restriction#

在一些 architecture 中，word 的起始地址必须是 word 大小的整倍数，dword 同样。 RISC-V 允许不对齐的寻址，但是效率会低。截屏2024-10-17 16.24.54 RISC-V 使用 little endian 小端编址：当我们从 0x1000 这个地址读出一个 dword 时，我们读到的实际上是 0x1000~0x1007 这 8 个字节，并将 0x1000 存入寄存器低位，0x1007 存入高位。（举例：一个2进制整数，低8位存入memory低地址，高八位存入更高地址memory）

Signed and unsigned numbers#

Unsigned Binary Integers:
2s-Complement Signed Integers: Signed Negationand add 1

P29 Sign Extension 截屏2024-10-17 17.13.15

补码 2’s complement#

前导 0 表示正数，前导 1 表示负数。

因此在将不足 64 位的数据载入寄存器时，如果数据是无符号数，只需要使用 0 将寄存器的其他部分填充 (zero extension)；而如果是符号数，则需要用最高位即符号位填充剩余部分，称为符号扩展 (sign extension)。

在指令中的lw , lh , lb使用 sign extension，而lwu , lhu , lbu使用 zero extension。（反码：1’s complement）

P19 base register & offset 截屏2024-10-17 16.53.38 P22 constant representation:

constant oprands
immediate operands

P23 Summary 截屏2024-10-17 17.00.00

Representing Instructions#

指令总表#

指令表

在 RISC 指令集中，只有 load 系列和 store 系列指令能够访问内存。
RISC-V 的跳转指令的 offset 是基于当前指令的地址的偏移；这不同于其他一些汇编是基于下一条指令的偏移的。即如果是跳转语句 PC 就不 +4 了，而是直接 +offset。
lw , lwu 等操作都会清零高位：因为RISC-V的寄存器是64位的，当执行lw/lwu操作时，它会将32位的有符号数据加载到寄存器的低32位，同时自动清零高32位，以避免寄存器中残留的高位数据干扰新的32位数据。

RISC-V 指令格式表#

指令表截屏2024-10-17 18.33.41

重点：寄存器的纯数字映射，RISC-V指令位宽，opcode即为operation code（操作码）

其中 I 型指令有两个条目；这是因为立即数移位操作 slli , srli , srai 并不可能对一个 64 位寄存器进行大于 63 位的移位操作，因此 12 位 imm 中只有后 6 位能实际被用到，因此前面 6 位被用来作为一个额外的操作码字段，如上图中第二个 I 条目那样。其他 I 型指令适用第一个 I 条目。
另外，为什么 SB 和 UJ 不存立即数（也就是偏移）的最低位呢？（关注表格，可以发现只包括 i[12:1] 或者 i[20:1]，缺失 i[0]）因为，偏移的最后一位一定是 0，即地址一定是 2 字节对齐的，因此没有必要保存

四种RISC-V指令格式#

截屏2024-10-17 18.40.33

Instruction fields
- opcode: operation code
- rd: destination register number
- funct3: 3-bit function code (additional opcode)
- rs1: the first source register number
- rs2: the second source register number
- funct7: 7-bit function code (additional opcode)

R型指令#

I型指令#

截屏2024-10-17 18.49.16

S型指令#

截屏2024-10-17 18.50.02

P40 : UJ 和 SB type 地址是双数的，舍去第一位（没有零位），加上第十二位，扩大范围。

Logic Operations#

shift left & right都是立即数指令？

· 基址寻址：ld x19, 0(x10) # temp reg x19 = A[i] 其中的0（x10）就是基址寻址 · 常见强制跳转：beq x0, x0, Loop 或 beq x0, x0, Exit

jalr（Jump And Link Register）指令：
PC：当前正在执行的指令地址。一般情况下会自动递增4。当遇到跳转（如 JAL、JALR）、分支或函数调用等指令时，PC 会被显式修改以跳转到其他位置执行。
关于Address table:（以x6为table基地址为例）

C和汇编转换#

常见Branch举例#

beq x21, x22, L1  # go to L1 if i equals j

if-then-else

bne x22, x23, Else # go to Else if i != j
...
beq x0, x0, EXIT # go to Exit
Else: sub x19, x20, x21 # f = g - h ( Executed if i ≠ j else) 
Exit: # the first instruction of the next C

LOOPs

Loop: ...
    add x22, x22, x23 # i = i + j
    bne x22, x21, Loop # 开头loop, 末尾 go to Loop if i != h

while

Loop: ...
    bne x9, x24, Exit # go to Exit if save[i] != k
      ...
    addi x22, x22, 1 # i += 1
      ...
    beq x0, x0, Loop # go to Loop 强制循环
Exit

其他

blt rs1, rs2, L1

if (rs1 < rs2) branch to instruction labeled L1

bge rs1, rs2, L1

if (rs1 >= rs2) branch to instruction labeled L1

Jump register & jump address table（switch逻辑）#

jalr和jal语法(无条件跳转)#

jalr: 基本格式为 jalr rd, offset(rs1)

rd：目标寄存器，用于存储返回地址。如果目标寄存器是x0，则不保存返回地址。
offset：一个立即数偏移量（通常是0或小的整数），用于相对于rs1的跳转。
rs1：源寄存器，包含跳转的基地址
jalr指令通常用于实现函数调用的返回，而不是作为调用者（caller）来进行函数调用（jal）

使用示例：

# 假设要调用一个函数并返回
# 函数地址在x1寄存器中，返回地址保存到x2寄存器
jalr x2, 0(x1)   # 跳转到x1寄存器中的地址，返回地址存储在x2
... # 函数代码
# 函数结束后返回
jalr x0, 0(x2)   # 使用jalr指令返回到之前调用的位置

jal: 基本格式为 jal rd, offset

rd：目标寄存器，通常用于保存返回地址。返回地址是下一条指令的地址，供后续返回使用。
offset：一个立即数偏移量，表示相对于当前指令地址的跳转距离。这个值可以是正数（向前跳转）或负数（向后跳转）

使用示例：

# 假设我们有一个名为function的函数
function:
    ... # 函数代码  
    jalr x0, 0(x1)   # 返回到调用点
main:
    jal x1, function  
        # 跳转到function，返回地址保存在x1
    # 继续执行main的后续代码

switch逻辑（汇编语言）#

其中第一行相当于switch的default语句，L0-L3相当于switch的case跳转语句。被case的是k的值。转写C：

switch (k) {
        case 0:
            *f = i + j;  // k = 0，执行 f = i + j
            break;
        case 1:
            *f = g + h;  // k = 1，执行 f = g + h
            break;
        case 2:
            *f = g - h;  // k = 2，执行 f = g - h
            break;
        case 3:
            *f = i - j;  // k = 3，执行 f = i - j
            break;
        default:
            break; 
    }

汇编&C 转换提醒：

slli x7, x25, 3 # temp reg x7 = 8 * k (0<=k<=3) 
add x7, x7, x6 # x7 = address of JumpTable[k]

如果是自己把C转写汇编，注意基址偏移量为8bit倍数，如第一行代码所示处理。

Basic Blocks（基本块）#

p58

定义：一组没有分支（跳转）指令的连续指令序列

Supporting Procedures 过程调用#

P59 程序/函数被用来构建程序结构

一个存储的子程序，根据提供的参数执行特定任务，使程序更易于理解，允许代码重用
六个步骤：

将参数放置在程序可以访问的地方
将控制权转移给程序：跳转到(jump to)
获取程序所需的存储资源
执行所需的任务
将结果值放置在调用程序可以访问的地方
将控制权返回到原始点

Procedure Call Instructions#

Instruction for procedures: jal ( jump-and-link )
- Caller jal x1, ProcedureAddress
  - x1是目标寄存器，通常在RISC-V中被称为ra（Return Address）。
  - 在跳转之前，jal指令会将当前指令的下一条指令的地址（即返回地址）存储在x1寄存器中。这意味着当ProcedureAddress执行完后，可以通过jalr（Jump and Link Register）指令从x1寄存器返回（见下面的jalr指令）
Procedure return: jalr ( jump and link register )
- Callee jalr x0, 0(x1)
  - 不保存返回地址：x0 为0，不会保存返回地址。因此在完成这个跳转后，无法返回到跳转之前的位置

过程调用和栈#

RISC-V 约定：

x5 - x7 和 x28 - x31 ：temp reg
- 这些寄存器在调用过程中可以自由使用，不要求被调用者（callee）在使用它们后恢复原值。所以调用者（caller）必须承担这些寄存器值可能在函数调用后被改变的风险。
- 如果希望调用后，仍保留这些数据，就需要在调用函数前将这些数据保存到内存或其他保存寄存器中。
x8 - x9 和 x18 - x27 ： saved reg
- 调用约定要求被调用者（callee）在使用这些寄存器之前保存它们的值，并在函数返回前恢复。
- 因此，调用者不需要自己保存这些寄存器的值，被调用者在使用这些寄存器时必须先将它们保存到栈中，在函数返回前再将保存的数据恢复到寄存器。
x10 - x17 是 8 个参数寄存器，函数调用的前 8 个参数会放在这些寄存器中
- 如果参数超过 8 个的话就需要放到栈上（放在 fp 上方， fp + 8 是第 9 个参数， fp + 16 的第 10 个，以此类推）。
- 同时，调用过程的返回值也会放到这些寄存器中（当然，对于 C 语言这种只能有一个返回值的语言，可能只会用到 x10 ）。
x1 ：保存返回地址，所以也叫 ra
栈指针（sp）是 x2 ；始终指向栈顶元素。栈从高地址向低地址增长。
- 堆栈：从高地址往低地址建设——>push:指针下移地址减小，pop:指针上移地址增加——>进栈减，入栈加
- addi sp, sp, -24 , sd x5, 16(sp) , sd x6, 8(sp) , sd x20, 0(sp) 可以实现将 x5, x6, x20 压栈。
- 64位RISC-V架构中，sp 的偏移量是以8字节为单位的，即栈中一个元素的大小为 8 字节（64位）
一些编译器中 x3 用来指向静态变量区，称为 global pointer （gp） 。
一些编译器中 x8 指向 activation record 的第一个 dword，方便访问局部变量；因此 x8 也称为 frame pointer （fp） 。在进入函数时，用 sp 将 fp 初始化。
- fp 的方便性在于在整个过程中对局部变量的所有引用相对于 fp 的偏移都是固定的，但是对 sp 不一定。当然，如果过程中没有什么栈的变化或者根本没有局部变量，那就没有必要用 fp 了。以下为总结：

寄存器用途总结表#

截屏2024-10-17 14.52.43 其中 “preserved on call” 的意思是，是否保证调用前后这些寄存器的值不变。

leaf procedure：没有进一步的函数调用

理解🌰：截屏2024-10-17 14.25.44 建议学习从例子入手，从具象到理论更容易接受

四种寻址方式#

p82 PC相对寻址机器码：2000/2（去零位） 32位数对，考试错一位扣分，不要写漏数字！
P88 四种寻址方式

RISC-V 支持 PC relative 寻址、立即数寻址 ( lui )、间接寻址 ( jalr )、基址寻址 ( 8(sp) )等

总结：

立即寻址（Immediate Addressing）： • 指令中包含一个立即数，该数值直接作为操作数使用。 • 例如，addi x1, x0, 10，将10直接加到寄存器x0的值上并存储到x1中。
寄存器寻址（Register Addressing）： • 操作数直接从寄存器中读取，指令中指定寄存器。 • 例如，add x1, x2, x3，将x2和x3的值相加，结果存储到x1中。
基址寻址（Base Addressing）： • 使用一个寄存器作为基地址，加上一个偏移量来计算有效地址。 • 例如，lw x1, 4(x2)，从寄存器x2中读取基址，加上4作为偏移量，从内存中加载数据到x1。
偏移寻址（Offset Addressing）： • 类似于基址寻址，使用一个寄存器和一个立即数（偏移量）来计算地址。 • 例如，sw x1, 8(x2)，将x1的值存储到内存地址x2 + 8。
相对寻址（PC-Relative Addressing）： • 使用当前程序计数器（PC）的值加上一个偏移量来计算有效地址，通常用于控制流指令。 • 例如，beq x1, x2, label，如果x1等于x2，则跳转到label位置，label的地址是PC加上指令中的偏移量。
直接寻址（Direct Addressing）： • 直接指定一个内存地址，通常用于特定的I/O操作。 • 这种方式在RISC-V中不常见，主要用于特定的指令。
间接寻址（Indirect Addressing）： • 寻址模式通过一个寄存器中存储的地址来确定操作数的实际地址。 • 例如，先将地址存入寄存器，然后通过该寄存器访问内存。

P89 查表判断指令是加法 rs2,rs1在汇编语言：不要写反！

竞争与同步#

P93 （数据）竞争——>解决：同步机制原子操作（硬件支持） atomic swap of register：一次读写打包

P94 load reserved：预约 rd：用于确认操作是否成功（不成功可能是因为数据改变/有其他进程在操作）解决竞争的方法：

注意理解两种方法的区别。

Linker && Loader#

P96 linker链接器 loader 程序由很多头文件组成，用链接器链接根据object file header就能完成链接，而不需要扫描整个程序。

image file：镜像文件动态链接：运行更多开销动态静态：看需求 Lazy Linkage：也是动态链接 P102 右边是第二次（已经链接过了），左边是第一次（动态链接）

间接跳转方式：不用修改主程序，跳转对应的表储存在内存里√ P103 Java虚拟机 P108 四个连续的mv意义？相当于堆栈。前两个mv：放进寄存器保护，避免被覆盖。后两个：拿出下一个交换的两个参数。寄存器存储可以代替堆栈，除非寄存器spilling bug：其实n没有被保护好，x11会被下一次循环改变。mv应该放在sort一开始（循环外面）怎么改？

Smaller is faster：寄存器数量少，访问快

待整理#

分支和循环过程调用和栈