3870 字
19 分钟
【计组】第二章整理
2024-10-29

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

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


目录#

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

章节理解维度#

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

  1. 高级语言(C语言)————汇编语言
  2. 汇编语言(汇编指令)————机器语言(机器码)

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个字节一个”字“ 截屏2024-10-17 15.39.38 在函数调用中,寄存器 x0 是否被保留取决于调用约定。 截屏2024-10-17 15.46.14 截屏2024-10-17 15.46.29 截屏2024-10-17 15.46.37
  • 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#

  1. Unsigned Binary Integers: 截屏2024-10-17 17.06.03
  2. 2s-Complement Signed Integers:截屏2024-10-17 17.06.34 截屏2024-10-17 17.07.02 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举例#

  1. if
beq x21, x22, L1  # go to L1 if i equals j
  1. 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
  1. LOOPs
Loop: ...
    add x22, x22, x23 # i = i + j
    bne x22, x21, Loop # 开头loop, 末尾 go to Loop if i != h
  1. 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
  1. 其他
  • 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语法(无条件跳转)#

  1. 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指令返回到之前调用的位置
  1. 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 程序/函数被用来构建程序结构

  • 一个存储的子程序,根据提供的参数执行特定任务,使程序更易于理解,允许代码重用
  • 六个步骤:
  1. 将参数放置在程序可以访问的地方
  2. 将控制权转移给程序:跳转到(jump to)
  3. 获取程序所需的存储资源
  4. 执行所需的任务
  5. 将结果值放置在调用程序可以访问的地方
  6. 将控制权返回到原始点

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” 的意思是,是否保证调用前后这些寄存器的值不变。 截屏2024-10-17 14.52.43

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

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

四种寻址方式#

  1. p82 PC相对寻址 截屏2024-10-17 14.52.43 机器码:2000/2(去零位) 32位数对,考试错一位扣分,不要写漏数字!
  2. P88 四种寻址方式

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

总结:

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

待整理#

分支和循环 过程调用和栈

【计组】第二章整理
https://tillyendless.github.io/posts/计组第二章整理/
作者
发布于
2024-10-29
许可协议
CC BY-NC-SA 4.0