4.3.1 将处理组织成阶段

通常，处理一条指令包括很多操作。将它们组织成某个特殊的阶段序列，即使指令的动作差异很大，但所有的指令都遵循统一的序列。每一步的具体处理取决于正在执行的指令。创建这样一个框架，我们就能够设计一个充分利用硬件的处理器。下面是关于各个阶段以及各阶段内执行操作的简略描述：

• 取指（fetch）： 取指阶段从内存读取指令字节，地址为程序计数器（PC）的值。从指令中抽取出指令指示符字节的两个四位部分，称为 icode（指令代码）和 ifun（指令功能）。它可能取出一个寄存器指示符字节，指明一个或两个寄存器操作数指示符 rA 和 rB。它还可能取出一个八字节常数字 valC。它按顺序方式计算当前指令的下一条指令的地址 valP。也就是说，valP 等于 PC 的值加上已取出指令的长度。
• 译码（decode）： 译码阶段从寄存器文件读入最多两个操作数，得到值 valA 和/或 valB。通常，它读入指令 rA 和 rB 字段指明的寄存器，不过有些指令是读寄存器 %rsp 的。
• 执行（execute）： 在执行阶段，算术/逻辑单元（ALU）要么执行指令指明的操作（根据 ifun 的值），计算内存引用的有效地址，要么增加或减少栈指针。得到的值我们称为 valE。在此，也可能设置条件码。对一条条件传送指令来说，这个阶段会检验条件码和传送条件（由 ifun 给出），如果条件成立，则更新目标寄存器。同样，对一条跳转指令来说，这个阶段会决定是不是应该选择分支。
• 访存（memory）： 访存阶段可以将数据写入内存，或者从内存读出数据。读出的值为 valM。
• 写回（write back）： 写回阶段最多可以写两个结果到寄存器文件。
• 更新 PC（PC update）： 将 PC 设置成下一条指令的地址。

处理器无限循环，执行这些阶段。在我们简化的实现中，发生任何异常时，处理器就会停止：它执行 halt 指令或非法指令，或它试图读或者写非法地址。在更完整的设计中，处理器会进入异常处理模式，开始执行由异常的类型决定的特殊代码。

从前面的讲述可以看出，执行一条指令是需要进行很多处理的。我们不仅必须执行指令所表明的操作，还必须计算地址、更新栈指针，以及确定下一条指令的地址。幸好每条指令的整个流程都比较相似。因为我们想使硬件数量尽可能少，并且最终将把它映射到一个二维的集成电路芯片的表面，在设计硬件时，一个非常简单而一致的结构是非常重要的。降低复杂度的一种方法是让不同的指令共享尽量多的硬件。例如，我们的每个处理器设计都只含有一个算术/逻辑单元，根据所执行的指令类型的不同，它的使用方式也不同。在硬件上复制逻辑块的成本比软件中有重复代码的成本大得多。而且在硬件系统中处理许多特殊情况和特性要比用软件来处理困难得多。

我们面临的一个挑战是将每条不同指令所需要的计算放入到上述那个通用框架中。我们会使用图 4-17 中所示的代码来描述不同 Y86-64 指令的处理。图 4-18～图 4-21 中的表描述了不同 Y86-64 指令在各个阶段是怎样处理的。很值得仔细研究一下这些表。表中的这种格式很容易映射到硬件。表中的每一行都描述了一个信号或存储状态的分配（用分配操作 ← 来表示）。阅读时可以把它看成是从上至下的顺序求值。当我们将这些计算映射到硬件时，会发现其实并不需要严格按照顺序来执行这些求值。

1   0x000: 30f20900000000000000 | irmovq $9, %rdx
2   0x00a: 30f31500000000000000 | irmovq $21, %rbx
3   0x014: 6123                 | subq %rdx, %rbx       # subtract
4   0x016: 30f48000000000000000 | irmovq $128, %rsp     # Problem 4.13
5   0x020: 40436400000000000000 | rmmovq %rsp, 100(%rbx) # store
6   0x02a: a02f                 | pushq %rdx            # push
7   0x02c: b00f                 | popq %rax             # Problem 4.14
8   0x02e: 734000000000000000   | je done               # Not taken
9   0x037: 804100000000000000   | call proc             # Problem 4.18
10  0x040:                      | done:
11  0x040: 00                   |     halt
12  0x041:                      | proc:
13  0x041: 90                   |     ret               # Return
14                              |

图 4-17　Y86-64 指令序列示例。我们会跟踪这些指令通过各个阶段的处理

图 4-18 给出了对 OPq（整数和逻辑运算）、rrmovq（寄存器-寄存器传送）和 irmovq（立即数-寄存器传送）类型的指令所需的处理。让我们先来考虑一下整数操作。回顾图 4-2，可以看到我们小心地选择了指令编码，这样四个整数操作（addq、subq、andq 和 xorq）都有相同的 icode 值。我们可以以相同的步骤顺序来处理它们，除了 ALU 计算必须根据 ifun 中编码的具体的指令操作来设定。

阶段	OPq rA, rB	rrmovq rA, rB	irmovq V, rB
取指	icode:ifun ← M₁[PC]；rA:rB ← M₁[PC+1]；valP ← PC+2	icode:ifun ← M₁[PC]；rA:rB ← M₁[PC+1]；valP ← PC+2	icode:ifun ← M₁[PC]；rA:rB ← M₁[PC+1]；valC ← M₈[PC+2]；valP ← PC+10
译码	valA ← R[rA]；valB ← R[rB]	valA ← R[rA]
执行	valE ← valB OP valA；Set CC	valE ← 0+valA	valE ← 0+valC
访存
写回	R[rB] ← valE	R[rB] ← valE	R[rB] ← valE
更新 PC	PC ← valP	PC ← valP	PC ← valP

图 4-18　Y86-64 指令 OPq、rrmovq 和 irmovq 在顺序实现中的计算。这些指令计算了一个值，并将结果存放在寄存器中。符号 icode:ifun 表明指令字节的两个组成部分，而 rA:rB 表明寄存器指示符字节的两个组成部分。符号 M₁[x] 表示访问（读或者写）内存位置 x 处的一个字节，而 M₈[x] 表示访问八个字节

整数操作指令的处理遵循上面列出的通用模式。在取指阶段，我们不需要常数字，所以 valP 就计算为 PC+2。在译码阶段，我们要读两个操作数。在执行阶段，它们和功能指示符 ifun 一起再提供给 ALU，这样一来 valE 就成为了指令结果。这个计算是用表达式 valB OP valA 来表达的，这里 OP 代表 ifun 指定的操作。要注意两个参数的顺序——这个顺序与 Y86-64（和 x86-64）的习惯是一致的。例如，指令 subq %rax, %rdx 计算的是 R[%rdx]-R[%rax] 的值。这些指令在访存阶段什么也不做，而在写回阶段，valE 被写入寄存器 rB，然后 PC 设为 valP，整个指令的执行就结束了。

旁注　跟踪 subq 指令的执行

作为一个例子，让我们来看看一条 subq 指令的处理过程，这条指令是图 4-17 所示目标代码的第 3 行中的 subq 指令。可以看到前面两条指令分别将寄存器 %rdx 和 %rbx 初始化成 9 和 21。我们还能看到指令位于地址 0x014，由两个字节组成，值分别为 0x61 和 0x23。这条指令处理的各个阶段如下表所示，左边列出了处理一个 OPq 指令的通用的规则（图 4-18），而右边列出的是对这条具体指令的计算。

阶段	通用：OPq rA, rB	具体：subq %rdx, %rbx
取指	icode:ifun ← M₁[PC]；rA:rB ← M₁[PC+1]；valP ← PC+2	icode:ifun ← M₁[0x014] = 6:1；rA:rB ← M₁[0x015] = 2:3；valP ← 0x014+2 = 0x016
译码	valA ← R[rA]；valB ← R[rB]	valA ← R[%rdx] = 9；valB ← R[%rbx] = 21
执行	valE ← valB OP valA；Set CC	valE ← 21-9 = 12；ZF ← 0, SF ← 0, OF ← 0
访存
写回	R[rB] ← valE	R[%rbx] ← valE = 12
更新 PC	PC ← valP	PC ← valP = 0x016

这个跟踪表明我们达到了理想的效果，寄存器 %rbx 设成了 12，三个条件码都设成了 0，而 PC 加了 2。

执行 rrmovq 指令和执行算术运算类似。不过，不需要取第二个寄存器操作数。我们将 ALU 的第二个输入设为 0，先把它和第一个操作数相加，得到 valE=valA，然后再把这个值写到寄存器文件。对 irmovq 的处理与此类似，除了 ALU 的第一个输入为常数值 valC。另外，因为是长指令格式，对于 irmovq，程序计数器必须加 10。所有这些指令都不改变条件码。

练习题 4.13 填写下表的右边一栏，这个表描述的是图 4-17 中目标代码第 4 行上的 irmovq 指令的处理情况：

阶段	通用：irmovq V, rB	具体：irmovq $128, %rsp
取指	icode:ifun ← M₁[PC]；rA:rB ← M₁[PC+1]；valC ← M₈[PC+2]；valP ← PC+10
译码
执行	valE ← 0+valC
访存
写回	R[rB] ← valE
更新 PC	PC ← valP

这条指令的执行会怎样改变寄存器和 PC 呢？

图 4-19 给出了内存读写指令 rmmovq 和 mrmovq 所需要的处理。基本流程也和前面的一样，不过是用 ALU 来加 valC 和 valB，得到内存操作的有效地址（偏移量与基址寄存器值之和）。在访存阶段，会将寄存器值 valA 写到内存，或者从内存中读出 valM。

阶段	rmmovq rA, D(rB)	mrmovq D(rB), rA
取指	icode:ifun ← M₁[PC]；rA:rB ← M₁[PC+1]；valC ← M₈[PC+2]；valP ← PC+10	icode:ifun ← M₁[PC]；rA:rB ← M₁[PC+1]；valC ← M₈[PC+2]；valP ← PC+10
译码	valA ← R[rA]；valB ← R[rB]	valB ← R[rB]
执行	valE ← valB+valC	valE ← valB+valC
访存	M₈[valE] ← valA	valM ← M₈[valE]
写回		R[rA] ← valM
更新 PC	PC ← valP	PC ← valP

图 4-19　Y86-64 指令 rmmovq 和 mrmovq 在顺序实现中的计算。这些指令读或者写内存

旁注　跟踪 rmmovq 指令的执行

让我们来看看图 4-17 中目标代码的第 5 行 rmmovq 指令的处理情况。可以看到，前面的指令已将寄存器 %rsp 初始化成了 128，而 %rbx 仍然是 subq 指令（第 3 行）算出来的结果 12。我们还可以看到，指令位于地址 0x020，有 10 个字节。前两个的值为 0x40 和 0x43，后 8 个是数字 0x0000000000000064（十进制数 100）按字节反过来得到的数。各个阶段的处理如下：

阶段	通用：rmmovq rA, D(rB)	具体：rmmovq %rsp, 100(%rbx)
取指	icode:ifun ← M₁[PC]；rA:rB ← M₁[PC+1]；valC ← M₈[PC+2]；valP ← PC+10	icode:ifun ← M₁[0x020] = 4:0；rA:rB ← M₁[0x021] = 4:3；valC ← M₈[0x022] = 100；valP ← 0x020+10 = 0x02a
译码	valA ← R[rA]；valB ← R[rB]	valA ← R[%rsp] = 128；valB ← R[%rbx] = 12
执行	valE ← valB+valC	valE ← 12+100 = 112
访存	M₈[valE] ← valA	M₈[112] ← 128
写回
更新 PC	PC ← valP	PC ← 0x02a

跟踪记录表明这条指令的效果就是将 128 写入内存地址 112，并将 PC 加 10。

图 4-20 给出了处理 pushq 和 popq 指令所需的步骤。它们可以算是最难实现的 Y86-64 指令了，因为它们既涉及访问内存，又要增加或减少栈指针。虽然这两条指令的流程比较相似，但是它们还是有很重要的区别。

阶段	pushq rA	popq rA
取指	icode:ifun ← M₁[PC]；rA:rB ← M₁[PC+1]；valP ← PC+2	icode:ifun ← M₁[PC]；rA:rB ← M₁[PC+1]；valP ← PC+2
译码	valA ← R[rA]；valB ← R[%rsp]	valA ← R[%rsp]；valB ← R[%rsp]
执行	valE ← valB+(-8)	valE ← valB+8
访存	M₈[valE] ← valA	valM ← M₈[valA]
写回	R[%rsp] ← valE	R[%rsp] ← valE；R[rA] ← valM
更新 PC	PC ← valP	PC ← valP

图 4-20　Y86-64 指令 pushq 和 popq 在顺序实现中的计算。这些指令将值压入或弹出栈

pushq 指令开始时很像我们前面讲过的指令，但是在译码阶段，用 %rsp 作为第二个寄存器操作数的标识符，将栈指针赋值为 valB。在执行阶段，用 ALU 将栈指针减 8。减过 8 的值就是内存写的地址，在写回阶段还会存回到 %rsp 中。将 valE 作为写操作的地址，是遵循 Y86-64（和 x86-64）的惯例，也就是在写之前，pushq 应该先将栈指针减去 8，即使栈指针的更新实际上是在内存操作完成之后才进行的。

旁注　跟踪 pushq 指令的执行

让我们来看看图 4-17 中目标代码的第 6 行 pushq 指令的处理情况。此时，寄存器 %rdx 的值为 9，而寄存器 %rsp 的值为 128。我们还可以看到指令是位于地址 0x02a，有两个字节，值分别为 0xa0 和 0x2f。各个阶段的处理如下：

阶段	通用：pushq rA	具体：pushq %rdx
取指	icode:ifun ← M₁[PC]；rA:rB ← M₁[PC+1]；valP ← PC+2	icode:ifun ← M₁[0x02a] = a:0；rA:rB ← M₁[0x02b] = 2:f；valP ← 0x02a+2 = 0x02c
译码	valA ← R[rA]；valB ← R[%rsp]	valA ← R[%rdx] = 9；valB ← R[%rsp] = 128
执行	valE ← valB+(-8)	valE ← 128+(-8) = 120
访存	M₈[valE] ← valA	M₈[120] ← 9
写回	R[%rsp] ← valE	R[%rsp] ← 120
更新 PC	PC ← valP	PC ← 0x02c

跟踪记录表明这条指令的效果就是将 %rsp 设为 120，将 9 写入地址 120，并将 PC 加 2。

popq 指令的执行与 pushq 的执行类似，除了在译码阶段要读两次栈指针以外。这样做看上去很多余，但是我们会看到让 valA 和 valB 都存放栈指针的值，会使后面的流程跟其他的指令更相似，增强设计的整体一致性。在执行阶段，用 ALU 给栈指针加 8，但是用没加过 8 的原始值作为内存操作的地址。在写回阶段，要用加过 8 的栈指针更新栈指针寄存器，还要将寄存器 rA 更新为从内存中读出的值。用没加过 8 的值作为内存读地址，保持了 Y86-64（和 x86-64）的惯例，popq 应该首先读内存，然后再增加栈指针。

练习题 4.14 填写下表的右边一栏，这个表描述的是图 4-17 中目标代码第 7 行 popq 指令的处理情况：

阶段	通用：popq rA	具体：popq %rax
取指	icode:ifun ← M₁[PC]；rA:rB ← M₁[PC+1]；valP ← PC+2
译码	valA ← R[%rsp]；valB ← R[%rsp]
执行	valE ← valB+8
访存	valM ← M₈[valA]
写回	R[%rsp] ← valE；R[rA] ← valM
更新 PC	PC ← valP

这条指令的执行会怎样改变寄存器和 PC 呢？

练习题 4.15 根据图 4-20 中列出的步骤，指令 pushq %rsp 会有什么样的效果？这与练习题 4.7 中确定的 Y86-64 期望的行为一致吗？

练习题 4.16 假设 popq 在写回阶段中的两个寄存器写操作按照图 4-20 列出的顺序进行。popq %rsp 执行的效果会是怎样的？这与练习题 4.8 中确定的 Y86-64 期望的行为一致吗？

图 4-21 表明了三类控制转移指令的处理：各种跳转、call 和 ret。可以看到，我们能用同前面指令一样的整体流程来实现这些指令。

阶段	jXX Dest	call Dest	ret
取指	icode:ifun ← M₁[PC]；valC ← M₈[PC+1]；valP ← PC+9	icode:ifun ← M₁[PC]；valC ← M₈[PC+1]；valP ← PC+9	icode:ifun ← M₁[PC]；valP ← PC+1
译码		valB ← R[%rsp]	valA ← R[%rsp]；valB ← R[%rsp]
执行	Cnd ← Cond(CC, ifun)	valE ← valB+(-8)	valE ← valB+8
访存		M₈[valE] ← valP	valM ← M₈[valA]
写回		R[%rsp] ← valE	R[%rsp] ← valE
更新 PC	PC ← Cnd ? valC : valP	PC ← valC	PC ← valM

图 4-21　Y86-64 指令 jXX、call 和 ret 在顺序实现中的计算。这些指令导致控制转移

同对整数操作一样，我们能够以一种统一的方式处理所有的跳转指令，因为它们的不同只在于判断是否要选择分支的时候。除了不需要一个寄存器指示符字节以外，跳转指令在取指和译码阶段都和前面讲的其他指令类似。在执行阶段，检查条件码和跳转条件来确定是否要选择分支，产生出一个一位信号 Cnd。在更新 PC 阶段，检查这个标志，如果这个标志为 1，就将 PC 设为 valC（跳转目标），如果为 0，就设为 valP（下一条指令的地址）。我们的表示法 x ? a : b 类似于 C 语句中的条件表达式——当 x 非零时，它等于 a，当 x 为零时，等于 b。

旁注　跟踪 je 指令的执行

让我们来看看图 4-17 中目标代码的第 8 行 je 指令的处理情况。subq 指令（第 3 行）已经将所有的条件码都置为了 0，所以不会选择分支。该指令位于地址 0x02e，有 9 个字节。第一个字节的值为 0x73，而剩下的 8 个字节是数字 0x0000000000000040 按字节反过来得到的数，也就是跳转的目标。各个阶段的处理如下：

阶段	通用：jXX Dest	具体：je 0x040
取指	icode:ifun ← M₁[PC]；valC ← M₈[PC+1]；valP ← PC+9	icode:ifun ← M₁[0x02e] = 7:3；valC ← M₈[0x02f] = 0x040；valP ← 0x02e+9 = 0x037
译码
执行	Cnd ← Cond(CC, ifun)	Cnd ← Cond(⟨0, 0, 0⟩, 3) = 0
访存
写回
更新 PC	PC ← Cnd ? valC : valP	PC ← 0 ? 0x040 : 0x037 = 0x037

就像这个跟踪记录表明的那样，这条指令的效果就是将 PC 加 9。

练习题 4.17 从指令编码（图 4-2 和图 4-3）我们可以看出，rrmovq 指令是一类更通用的、包括条件传送在内的指令的无条件版本。请给出你要如何修改下面 rrmovq 指令的步骤，使之也能处理 6 个条件传送指令。看看 jXX 指令的实现（图 4-21）是如何处理条件行为的，可能会有所帮助。

阶段	cmovXX rA, rB
取指	icode:ifun ← M₁[PC]；rA:rB ← M₁[PC+1]；valP ← PC+2
译码	valA ← R[rA]
执行	valE ← 0+valA
访存
写回	R[rB] ← valE
更新 PC	PC ← valP

指令 call 和 ret 与指令 pushq 和 popq 类似，除了我们要将程序计数器的值入栈和出栈以外。对指令 call，我们要将 valP，也就是 call 指令后紧跟着的那条指令的地址，压入栈中。在更新 PC 阶段，将 PC 设为 valC，也就是调用的目的地。对指令 ret，在更新 PC 阶段，我们将 valM，即从栈中取出的值，赋值给 PC。

练习题 4.18 填写下表的右边一栏，这个表描述的是图 4-17 中目标代码第 9 行 call 指令的处理情况：

阶段	通用：call Dest	具体：call 0x041
取指	icode:ifun ← M₁[PC]；valC ← M₈[PC+1]；valP ← PC+9
译码	valB ← R[%rsp]
执行	valE ← valB+(-8)
访存	M₈[valE] ← valP
写回	R[%rsp] ← valE
更新 PC	PC ← valC

这条指令的执行会怎样改变寄存器、PC 和内存呢？

我们创建了一个统一的框架，能处理所有不同类型的 Y86-64 指令。虽然指令的行为大不相同，但是我们可以将指令的处理组织成 6 个阶段。现在我们的任务是创建硬件设计来实现这些阶段，并把它们连接起来。

旁注　跟踪 ret 指令的执行

让我们来看看图 4-17 中目标代码的第 13 行 ret 指令的处理情况。指令的地址是 0x041，只有一个字节的编码，0x90。前面的 call 指令将 %rsp 置为了 120，并将返回地址 0x040 存放在了内存地址 120 中。各个阶段的处理如下：

阶段	通用：ret	具体：ret
取指	icode:ifun ← M₁[PC]；valP ← PC+1	icode:ifun ← M₁[0x041] = 9:0；valP ← 0x041+1 = 0x042
译码	valA ← R[%rsp]；valB ← R[%rsp]	valA ← R[%rsp] = 120；valB ← R[%rsp] = 120
执行	valE ← valB+8	valE ← 120+8 = 128
访存	valM ← M₈[valA]	valM ← M₈[120] = 0x040
写回	R[%rsp] ← valE	R[%rsp] ← 128
更新 PC	PC ← valM	PC ← 0x040

跟踪记录表明这条指令的效果就是将 PC 设为 0x040，halt 指令的地址。同时也将 %rsp 置为了 128。