CSAPP - 04.ISA
计算机体系结构: ISA (Instruction Set Architecture)
主要内容:
本章从使用汇编转向了设计 CPU。
- ISA (指令集架构):介绍了 ISA 作为软硬件契约的概念,以及 CISC (x86) 与 RISC (ARM/MIPS) 的设计哲学区别。
- Y86-64:为了教学目的,简化了复杂的 x86-64,定义了一个迷你的指令集 Y86-64。我们详细定义了它的寄存器、指令编码字节、以及异常处理状态。
Motivation:
真正的 x86-64 太复杂,无法在课堂上设计出它的电路。学习 Y86-64 是为了搭建一个**“麻雀虽小,五脏俱全”的模型**。它是后续章节我们亲手“造 CPU”的蓝图和需求文档。
指令集架构 (Instruction Set Architecture - ISA)
- ISA (指令集架构) 是一个抽象层,位于编译器编写者和处理器设计者之间。
- 它定义了处理器的汇编语言视图 (Assembly Language View):
- 处理器状态 (Processor state): 寄存器、内存等。
- 指令 (Instructions):
addq,pushq,ret等。 - 指令编码 (Encoding): 指令如何被编码为字节。
抽象层次:
- 对编译器编写者 (上层):
- 只需要知道允许哪些指令,以及它们是如何编码的。
- 关注机器代码优化。
- 对处理器设计者 (下层):
- 需要建造出能执行这些指令的处理器。
- 关注如何高效执行指令(例如,通过流水线并行执行)。
CISC vs. RISC
CISC (复杂指令集计算机)
- CISC = Complex Instruction Set Computer。
- IA32 (x86-32) 是一个典型的例子。
- 特性:
- 面向栈 (Stack-oriented): 使用栈来传递参数、保存程序计数器,有显式的
push和pop指令。 - 算术指令可访问内存: 例如
addq %rax, 12(%rbx,%rcx,8),一条指令就包含了复杂的地址计算以及内存读写。 - 条件码 (Condition codes): 作为算术和逻辑指令的副作用被设置。
- 面向栈 (Stack-oriented): 使用栈来传递参数、保存程序计数器,有显式的
- 哲学: 添加指令来执行“典型”的编程任务。
- 结果: x86 指令集中的指令数量随时间不断增长,到 2014 年已超过 1300 条。
RISC (精简指令集计算机)
- RISC = Reduced Instruction Set Computer。
- 由 IBM 的项目开创,后被 Hennessy (Stanford) 和 Patterson (Berkeley) 推广。
- 特性:
- 更少、更简单的指令: 完成某个任务可能需要更多条指令,但每条指令都可以用更小、更快的硬件来执行。
- 面向寄存器 (Register-oriented):
- 通常有更多(例如 32 个)寄存器。
- 使用寄存器传递参数、存储返回值和临时变量。
- Load/Store 架构:
- 只有
load(加载) 和store(存储) 指令可以访问内存(类似于 Y86-64 的mrmovq和rmmovq)。 - 算术指令(如
add)只能操作寄存器。
- 只有
- 无条件码: 测试指令(如比较)会在一个寄存器中返回 0 或 1。
MIPS 示例 (一种 RISC ISA)
- MIPS 寄存器: 有 32 个通用寄存器(
$0-$31),按用途命名(如$a0-$a3用于参数,$v0-$v1用于返回值,$t0-$t9用于临时变量,$s0-$s7用于保存的变量,$sp栈指针,$ra返回地址)。 - MIPS 指令示例:
addu $3, $2, $1(寄存器加法):$3 = $2 + $1addu $3, $2, 3145(立即数加法:$3 = $2 + 3145)lw $3, 16($2)(Load Word:$3 = M[$2 + 16])sw $3, 16($2)(Store Word:M[$2 + 16] = $3)
CISC vs. RISC 的现状
-
最初的争论:
- CISC 支持者: 对编译器友好,代码字节数更少。
- RISC 支持者: 对优化编译器友好,可以用简单的芯片设计实现高速运行。
-
目前的状态:
- 桌面处理器: ISA 的选择已不是一个关键技术问题。有足够强大的硬件,任何 ISA 都能跑得很快。代码兼容性更重要。
- x86-64 已经吸收了很多 RISC 的特性(例如,更多的寄存器,使用寄存器传参)。
- 嵌入式处理器: RISC 意义重大(更小、更便宜、功耗更低)。ARM 处理器(一种 RISC)被用于大多数手机。
-
总结: 无论是单纯的 RISC 还是 CISC 都不如结合两者思想精华的设计。Y86-64 就同时具有 CISC(如条件码、可变指令长度)和 RISC(如 Load/Store 体系结构)的属性。
Y86-64 处理器状态 (Processor State)
- RF (Program Registers): 15 个程序寄存器(省略
%r15),每个 64 位。 - CC (Condition Codes): 3 个单位标志位:
ZF: 零 (Zero)SF: 负 (Negative)OF: 溢出 (Overflow)
- PC (Program Counter): 存放下一条要执行指令的地址。
- Stat (Program Status): 指示程序是正常运行还是出现了错误。
- DMEM (Memory): 字节寻址的存储阵列。
Y86-64 指令集 (Instruction Set)
- 格式: 指令长度为 1 到 10 字节。可以从第一个字节确定指令长度。编码比 x86-64 简单。
- 字节编码的唯一解释:这是指令集的一个重要性质。
- 任意一个字节序列要么是一个唯一的指令序列的编码,要么就不是一个合法的字节序列。
- 这保证了处理器可以无二义性地执行目标代码程序。
- 第一个字节:Y86-64 每条指令的第一个字节有唯一的代码 (icode) 和功能 (ifun) 组合。
- 给定这个字节,我们就可以决定所有其他附加字节的长度和含义。
- 字节序:Y86-64 采用小端法 (little-endian),同 x86-64 一样。
寄存器编码 (Encoding Registers)
- 每个寄存器有一个 4-bit 的 ID (0-E)。
- ID
F(15) 表示 “无寄存器” (No Register)。
| 寄存器 | ID | 寄存器 | ID |
|---|---|---|---|
%rax |
0 | %r8 |
8 |
%rcx |
1 | %r9 |
9 |
%rdx |
2 | %r10 |
A |
%rbx |
3 | %r11 |
B |
%rsp |
4 | %r12 |
C |
%rbp |
5 | %r13 |
D |
%rsi |
6 | %r14 |
E |
%rdi |
7 | (无) | F |
Y86-64 指令详解
1. 算术和逻辑操作 (Arithmetic and Logical Operations)
OPq rA, rB(编码:6 fn rA rB)- 从
rA和rB读取值,计算结果,存回rB,并设置条件码。 fn(function code) 决定具体操作:addq(加法):fn = 0(编码:60)subq(减法):fn = 1(编码:61)andq(与):fn = 2(编码:62)xorq(异或):fn = 3(编码:63)
- 示例:
addq %rax, %rsirA = %rax = 0,rB = %rsi = 6- 编码:
60 06
2. 移动操作 (Move Operations)
rrmovq rA, rB(编码:20 rA rB)- 寄存器 -> 寄存器。
irmovq V, rB(编码:30 F rB V)- 立即数 -> 寄存器。
V是一个 8 字节的立即数。
- 立即数 -> 寄存器。
rmmovq rA, D(rB)(编码:40 rA rB D)- 寄存器 -> 内存。
D是一个 8 字节的位移。
- 寄存器 -> 内存。
mrmovq D(rB), rA(编码:50 rA rB D)- 内存 -> 寄存器。
D是一个 8 字节的位移。
- 内存 -> 寄存器。
- 示例:
irmovq $0xabcd, %rdxrB = %rdx = 2,V = 0x...abcd- 编码:
30 f2 cd ab 00 00 00 00 00 00(小端法)
- 示例:
rmmovq %rsi, 0x41c(%rsp)rA = %rsi = 6,rB = %rsp = 4,D = 0x...41c- 编码:
40 64 1c 04 00 00 00 00 00 00
3. 条件移动 (Conditional Move Instructions)
cmovXX rA, rB(编码:2 fn rA rB)- 这是
rrmovq的变体。只有当条件码满足fn指定的条件时,才将rA的值复制到rB。 fn(function code) 决定条件:rrmovq(无条件):fn = 0(编码:20)cmovle(小于或等于):fn = 1(编码:21)cmovl(小于):fn = 2(编码:22)cmove(等于):fn = 3(编码:23)cmovne(不等于):fn = 4(编码:24)cmovge(大于或等于):fn = 5(编码:25)cmovg(大于):fn = 6(编码:26)
4. 跳转指令 (Jump Instructions)
jXX Dest(编码:7 fn Dest)- 根据
fn指定的条件码,跳转到Dest(一个 8 字节的绝对地址)。 fn(function code) 决定条件:jmp(无条件):fn = 0(编码:70)jle(小于或等于):fn = 1(编码:71)jl(小于):fn = 2(编码:72)je(等于):fn = 3(编码:73)jne(不等于):fn = 4(编码:74)jge(大于或等于):fn = 5(编码:75)jg(大于):fn = 6(编码:76)
5. 栈操作 (Stack Operations)
- Y86-64 的栈向低地址增长。
%rsp指向栈顶元素。 pushq rA(编码:A0 rA F)%rsp减 8。- 将
rA的值存入%rsp指向的内存。
popq rA(编码:B0 rA F)- 从
%rsp指向的内存读取一个值存入rA。 %rsp加 8。
- 从
6. 子程序调用和返回 (Subroutine Call and Return)
call Dest(编码:80 Dest)- 将
call指令的下一条指令地址(返回地址)push到栈上。 - 跳转到
Dest。
- 将
ret(编码:90)- 从栈上
pop一个地址。 - 跳转到该地址。
- 从栈上
7. 杂项指令 (Miscellaneous Instructions)
nop(编码:10)- 不做任何事。
halt(编码:00)- 停止执行指令。
- 编码为
00确保了程序如果意外跳转到未初始化的内存(通常为 0)时会停止,而不是执行非法指令。
状态条件 (Status Conditions)
AOK(Code 1): 正常操作。HLT(Code 2):halt指令。ADR(Code 3): 遇到非法地址(指令或数据)。INS(Code 4): 遇到非法指令。- 如果状态不是
AOK,处理器停止执行。
| 类别 | 指令助记符 (Mnemonic) | 字节编码 (Byte Encoding)icode:ifun … |
长度 (Bytes) | 含义 / 操作描述 |
|---|---|---|---|---|
| 控制与杂项 | halt | 00 |
1 | 停止指令执行。将状态码设置为 HLT 。 |
| nop | 10 |
1 | 空操作,什么也不做 (No Operation) 。 | |
| 数据传送 | rrmovq rA, rB | 20 rA rB |
2 | 寄存器到寄存器传送:R[rB] <- R[rA]。 |
| cmovXX rA, rB | 2fn rA rB |
2 | 条件传送:根据条件码决定是否将 R[rA] 传送到 R[rB]。21: cmovle (<=)22: cmovl (<)23: cmove (=)24: cmovne (!=)25: cmovge (>=)26: cmovg (>) |
|
| irmovq V, rB | 30 F rB V |
10 | 立即数到寄存器:R[rB] <- V。注意源寄存器位固定为 F (无) 。 |
|
| rmmovq rA, D(rB) | 40 rA rB D |
10 | 寄存器到内存:M[R[rB] + D] <- R[rA] 。 |
|
| mrmovq D(rB), rA | 50 rA rB D |
10 | 内存到寄存器:R[rA] <- M[R[rB] + D]。 |
|
| 算术逻辑 | addq rA, rB | 60 rA rB |
2 | 加法:R[rB] <- R[rB] + R[rA] 。 |
| subq rA, rB | 61 rA rB |
2 | 减法:R[rB] <- R[rB] - R[rA]。 |
|
| andq rA, rB | 62 rA rB |
2 | 逻辑与:R[rB] <- R[rB] & R[rA]。 |
|
| xorq rA, rB | 63 rA rB |
2 | 逻辑异或:R[rB] <- R[rB] ^ R[rA]。 |
|
| 跳转控制 | jmp Dest | 70 Dest |
9 | 无条件跳转。 |
| jXX Dest | 7fn Dest |
9 | 条件跳转:根据条件码跳转 。71: jle (<=)72: jl (<)73: je (=)74: jne (!=)75: jge (>=)76: jg (>) |
|
| 函数调用 | call Dest | 80 Dest |
9 | 将返回地址压栈,然后跳转到 Dest。 |
| ret | 90 |
1 | 从栈中弹出返回地址,并跳转到该地址。 | |
| 栈操作 | pushq rA | A0 rA F |
2 | 将寄存器 rA 的值压入栈。注意第二个寄存器位固定为 F 。 |
| popq rA | B0 rA F |
2 | 从栈弹出值并存入寄存器 rA。注意第二个寄存器位固定为 F 。 |
Y86-64 不支持 x86-64 中的 比例变址 (scaled addressing) 寻址模式。
- x86-64 支持:
D(Rb, Ri, S),即Displacement(Base, Index, Scale)。例如(%rdi, %rax, 8)表示地址为R[%rdi] + R[%rax] * 8。这在访问数组a[i]时非常方便。 - Y86-64 仅支持:
D(Rb),即 基址 + 偏移量 (Base + Displacement)。例如8(%rbp)或(%rdi)。- 它不支持索引寄存器(Index Register)。
- 它不支持比例因子(Scale Factor, 如
*1, *2, *4, *8)。
编写 Y86-64 代码
- 方法:
- 在 C 中编写代码。
- 使用
gcc -Og -S编译为 x86-64 汇编。 - 将其“转译” (Transliterate) 为 Y86-64 汇编。
- 难点: Y86-64 没有 x86-64 的比例变址 (scaled addressing) 寻址模式(如
(%rdi, %rax, 8)),这使得数组索引a[i]变得困难。
示例:计算数组长度
- 目标: 计算一个以 0 结尾的
long数组的长度。 - C 语言 (指针版本):
1 | |
- Y86-64 汇编 (len):
1 | |
Y86-64 程序结构
Y86-64 程序是一个 “裸机” (Bare-metal) 程序。因为没有操作系统来加载程序或设置运行环境,程序员必须在代码中显式地定义内存布局、初始化栈指针,并手动停止处理器。
1. 完整代码结构示例
1 | |
2. 核心组成部分解析
2.1 程序的入口 (init)
.pos 0: Y86 处理器复位后,PC (程序计数器) 默认值为 0。因此,地址 0 处必须是可以执行的代码。irmovq Stack, %rsp: 这是程序的第一条有效指令。- 在执行
call指令时,CPU 会自动将返回地址压栈。 - 如果
%rsp没有初始化(或者是 0),压栈操作会导致内存错误或覆盖地址 0 处的代码。
- 在执行
halt: 程序结束的标志。在 Y86 模拟器中,这会让处理器停止运行并显示最终状态 (HLT)。
2.2 数据布局 (.align & .quad)
.align 8: Y86-64 是 64 位架构。虽然它不像某些硬件那样强制要求对齐,但为了模拟真实系统并避免跨字边界访问,通常对数据进行 8 字节对齐。.quad: 定义一个 64 位 (8字节) 的字。这对应于 C 语言中的long类型。- 放置位置: 数据通常放在
halt之后,Main之前。这样既不会被意外执行,离代码也比较近。
2.3 栈的设置 (Stack & .pos)
栈的设计采用了 “向后定义” 的技巧:
.pos 0x100: 这条伪指令告诉汇编器:“不要紧接着上面的代码写了,直接跳到地址0x100”。- 留白区域: 从上一个代码结束的位置到
0x100之间的内存区域,就是栈空间。 Stack:标签: 这个标签代表地址0x100。- 生长方向:
- 初始
%rsp=0x100。 - 第一次
push或call,%rsp变为0x0F8(减8)。 - 栈向低地址增长,慢慢填满
0x100之前的空白区。
- 初始
如果栈空间预留得不够大(例如 .pos 的地址太小),或者递归调用太深,栈就会一直向低地址生长,最终覆盖掉代码段或数据段,导致程序崩溃或行为异常。
3. 内存映像图解 (Memory Map)
这个程序的内存布局在模拟器中看起来是这样的:
1 | |
汇编和仿真
- 汇编 (Assembling):
yas len.ys(Y86-64 Assembler)- 生成目标文件
len.yo。
- 生成目标文件
- 仿真 (Simulating):
yis len.yo(Y86-64 Instruction Simulator)- 执行代码,报告处理器状态的改变(寄存器、内存)和最终状态。
开源指令集
- RISC-V (2016): 完全开源,架构简单,易于移植,模块化设计,低功耗。
- PowerPC (2019): 架构和指令集移交给了 Linux 基金会。
总结
- Y86-64 ISA:
- 与 x86-64 相似的状态和指令。
- 更简单的编码。
- 介于 CISC 和 RISC 之间。
- ISA 设计的重要性:
- 现在的重要性低于过去。
- 有足够强大的硬件,几乎任何 ISA 都能跑得很快。
练习
CSAPP 练习题4.1
需要用到 Y86-64 指令集的以下规则:
- 指令编码格式:
irmovq V, rB:30 F rB V(10 字节)rrmovq rA, rB:20 rA rB(2 字节)rmmovq rA, D(rB):40 rA rB D(10 字节)addq rA, rB:60 rA rB(2 字节)jmp Dest:70 Dest(9 字节)
- 寄存器 ID:
%rcx= 1,%rbx= 3
- 数据格式:
- 立即数、偏移量、跳转地址均使用 8字节、小端法 (Little-endian) 存储。
| 地址 (Address) | 字节编码 (Byte Representation) | 指令 (Instruction) |
|---|---|---|
| 0x100 | 30 F3 0F 00 00 00 00 00 00 00 |
irmovq $15, %rbx |
| 0x10A | 20 31 |
rrmovq %rbx, %rcx |
| 0x10C | 40 13 FD FF FF FF FF FF FF FF |
loop: rmmovq %rcx, -3(%rbx) |
| 0x116 | 60 31 |
addq %rbx, %rcx |
| 0x118 | 70 0C 01 00 00 00 00 00 00 |
jmp loop |
CSAPP 练习题4.2
这是一个关于 Y86-64 指令解码的练习题。我们需要根据指令编码规则,将每个字节序列翻译成汇编代码,并检查是否有非法指令。
A. 0x100: 30f3fcffffffffffffff40630008000000000000
这是一个合法的序列。
0x100: 30 f3 fcffffffffffffff30:irmovq指令。f3: 源无 (F), 目的%rbx(3)。fcffffffffffffff: 立即数-4(0xff…fc)。- 指令:
irmovq $-4, %rbx
0x10A: 40 63 000800000000000040:rmmovq指令。63: 源%rsi(6), 基址%rbx(3)。0008...: 偏移量0x800。- 指令:
rmmovq %rsi, 0x800(%rbx)
B. 0x200: a06f800c0200000000000030f30a0000000000000090
这是一个合法的序列。
0x200: a0 6fa0:pushq指令。6f: 寄存器%rsi(6), 填充位F。- 指令:
pushq %rsi
0x202: 80 0c0200000000000080:call指令。0c02...: 目标地址0x20c。- 指令:
call 0x20c
0x20B: 30 f3 0a0000000000000030:irmovq指令。f3: 目的%rbx(3)。0a...: 立即数10。- 指令:
irmovq $10, %rbx
0x215: 9090:ret指令。- 指令:
ret
C. 0x300: 5054070000000000000010f0b01f
这是一个非法的序列。
0x300: 50 54 070000000000000050:mrmovq指令。54: 目的%rbp(5), 基址%rsp(4)。07...: 偏移量7。- 指令:
mrmovq 7(%rsp), %rbp
0x30A: 1010:nop指令。- 指令:
nop
0x30B: f0- 错误: Y86-64 指令集中没有以
0xF开头的操作码。 - 结论: 地址 0x30B 处出现非法字节
f0。
- 错误: Y86-64 指令集中没有以
D. 0x400: 6113730004000000000000
这是一个合法的序列。
0x400: 61 1361:subq指令。13: 寄存器%rcx(1) 和%rbx(3)。- 指令:
subq %rcx, %rbx
0x402: 73 000400000000000073:je(相等则跳转) 指令。0004...: 目标地址0x400。- 指令:
je 0x400
0x40B: 0000:halt指令。- 指令:
halt
E. 0x500: 6362a0f0
这是一个非法的序列。
0x500: 63 6263:xorq指令。62: 寄存器%rsi(6) 和%rdx(2)。- 指令:
xorq %rsi, %rdx
0x502: a0 f0a0:pushq指令。- 错误:
pushq的寄存器字节格式必须是rA F。- 这里的第二个字节是
f0。 - 高位
f表示寄存器rA是0xF(无寄存器),这是非法的,因为push必须操作一个有效寄存器。 - 低位
0应该是F(填充位),这里却是0。
- 这里的第二个字节是
- 结论: 地址 0x503 (或者说指令
0x502) 的寄存器说明符字节f0是非法的。