程序的机器级表示（CSAPP Chapter 3，COD Chapter 2）

0. 序言

我们首先回顾计算机执行机器代码的过程和目的。其目的在于处理数据、管理内存、读写数据、通信......。其过程大概可以这样描述：编译器以汇编代码的形式输出，它是机器代码的文本表示，给出程序中的每一条指令。然后 GCC 调用汇编器和链接器，生成可执行的机器代码。

0.1 我们为啥要学机器代码

阅读汇编代码能让我们理解编译器的优化能力，并分析代码中隐含的低效率
写并发的时候，我们需要在机器代码的层级看到不同的线程是如何保持部分数据共享、部分数据私有的
恶意软件经常设计系统程序中的漏洞，我们需要机器级表示的知识来防御之

0.2 历史观点

x86的发展过程是非常漫长的。一开始它是单芯片、16 位的，之后才不断地利用进步的技术来提升性能、支持更高级操作系统。

8086：第一代，29K 个晶体管，内存只有 32768 字节，地址只有 20 位长。之后的 8087 是支持浮点数运算的版本
i386：32 位的，有平坦寻址模式......

......
Core i7：1.4G 个晶体管，有更多的指令和而指令格式；有超线程、多核、也支持把数据封装进 256 位的向量。

1.1 程序编码

假设一个 \(\text{C}\) 程序，有两个文件 p1.c 和 p2.c 。我们用\(\text{Unix}\)命令行编译这些代码：

linex> gcc -O0 -o p p1.c p2.c

gcc 代表编译器，-00 代表编译选项，这是原始的优化等级，如果更高的话，机器代码和源代码的关系就很难理解了。整个过程大概是：1、预处理器插入所有 #include 的文件，并把所有宏展开。2、编译器产生两个源文件的代码，以 .s 作为后缀。3、汇编器讲汇编代码转化成二进制目标代码文件 p1.o,p2.o ，这就已经是机器代码的一种形式了，所有指令都是二进制表示，但是没有填入全局值的地址。4、链接器把两个目标代码文件和已经实现的库函数（你可以理解成内建）合并，生成最后的可执行文件 p ，这是机器代码的第二种形式，我们将在接下来的旅程中了解它们之间的关系和链接的过程。

1.2 机器级代码

两个机器级编程的抽象：

\(\text{Instruction Set Architecture}\) 指令集架构，规定了指令格式，用途等等。实际上，在处理器上，可能是并发、多发射的，但整体行为完全一致。
虚拟地址，存储器中可能是一大堆硬件存储器组成的。

汇编代码虽然相对可读性、与C 语言代码联系较紧密，但也存在一些差别：

\(\text{PC}\) 程序计数器，给出下一条指令的地址
整数寄存器文件，可能用于存储地址、整数数据、临时数据，也有可能是返回值啥的
条件码寄存器保存着最近执行的指令的状态信息。用来实现控制或数据流中的条件变化。
向量寄存器保存着一个或多个整数/浮点数值

还有一层抽象：C 语言中的聚合数据类型，在机器代码中只是一串连续的字节，然后什么指针、整数啥的都没有区分。

程序内存：包含程序的可执行机器代码，运行时栈，分配的内存块等等。操作系统负责管理虚拟地址空间，把它翻译成内存中的物理地址。

要想查看机器代码文件的内容，有一类被称为反汇编器(disassembler)的程序非常有用。它可以根据机器代码生成一种类似于汇编代码的东西。例子：

linux> objdump -d mstore.o

下图展示了一些关于机器代码和它的反汇编表示的特性：

生成可执行代码需要对一组目标代码文件运行链接器，这一组目标代码文件中必须有且仅有一个main函数。连接器会改变代码的地址，即为函数调用找到匹配的函数的可执行代码的位置。另外，我们也加入了一些没用的指令，来让函数代码变为 16 字节的整数倍，使得就存储器性能而言，能更好地放置下一个代码块。

note: q的意思是大小指示符， \(\text{Intel}\) 将其省略，同时，它还省略 \(\%\) 符号，用不同的方式描述内存中的位置

毕竟之前的 toy-tomasulo 和 compiler 都是基于 RISC-V 指令集的，接下来的内容我还是按照 COD 来吧。

2. 计算机硬件的操作数

设计原则1：简单源于规整（指代指令集的形式）

这里有一个和高级语言程序不同的特性：算数指令的操作数会有限制：必须取自寄存器，而寄存器是一种内建于硬件的数量有限的特殊部件。在\(\text{RISC-V}\)架构中，其大小为 64 位；成组的 64 位频繁出现，被称为双字（例如我们将相邻的两个 64 位放在一起，再把相邻的两个 128 位放在一起.......）

设计原则2：更少则更快

更多的寄存器可能会增加时钟周期（因为电信号传输的距离越远，花费的时间越长）

寄存器数量：在更多寄存器、更短时间周期、指令位数限制之间权衡。

2.1 存储器操作数

程序语言中，比较复杂的数据结构（数组、结构体）被放在内存中。但我们的算数运算已经只作用于寄存器了，那么就必须得有在两者之间传输的指令，即数据传输指令。数据传输指令之间其实就是包括内存地址（ rd+offset ），和待存/取的寄存器。

晚上，我跟尹良升学长讨论了这种寻址方式的意图，他的想法是这样的：

在我们写的 asm 架构中，每个 spill 在栈上的局部变量的 offset 都是可以提前预知的（在编译期确定）。这时候 offset 可以直接用来表示变量的序号。
另外，加上 offset 可以有更大的访存范围。
其实，用 rd+offset 还是 imm 本质上是空间（指令中占位）和计算速度（到底还要不要再加一次...）

编址：\(\text{RISC-V}\) 属于小端编址，即右边的地址是双字地址。

另外几个注意事项：取int []A, A[8]的时候，偏移量是8*sizeof(int)。且字的起始地址必须是 4 的倍数，双字的起始地址必须是 8 的倍数。

2.2 常数/立即数

程序经常会在一次操作中用到常数，例如把一个常数和某个寄存器的和放到另一个寄存器中。这样比从存储器的某个位置取出常数相比，操作速度更快，能耗也更低。

同时，在\(\text{RISC-V}\)指令集中，常数 0 很重要。例如，你可以使用常数 0 寄存器来求相反数，或者弄点比较什么的。因此，我们的专用寄存器 x0 硬连线到常数 0 。根据使用频率来确定要定义的常数，这是加速经常性事件的另一个实例。

2.3 有符号/无符号数

补码确实挺好的（sigh），但是请注意最小的数是没有相反数表示的。另外，\(\text{RISC-V}\) 中也提供了 lbu,lb 两种指令， lbu 使用 0 向左填充，lb 则是做符号位拓展。

反码：字面意思。但是很明显，做减法需要多一步。

补码求相反数：按位取反再加 1 ，毕竟 \(x+\bar x=-1\)

2.4 计算机中的指令表示

翻译成字段也好理解。funct3 也代表指令的功能码。

以上是\(\text{RISC-V}\)各字段的含义分析。但你会注意到，有的时候指令需要更长的字段，比如当加载立即数的时候，这时候地址竟然被限制在了\(2^5\)以内！这时候，我们称”定长需求和单一指令需求有了矛盾“。

这时候，我们就有折中了：以下是load/store的设计

由此我们就已经得到了几种 \(\text{RISC-V}\) 指令。

2.5 逻辑操作

尽管一开始，计算机只对整字进行操作，但人们很快发现，在一个字内对其中几个位操作也是非常有用的。因而我们添加了一些操作，也就是逻辑操作。

移位操作：它使用 \(\text{I}\) 型格式。然而，事实上我们对一个寄存器的移位至多只有32位，只有 \(\text{I}\) 型指令 imm 字段的低 6 位被实际占用，剩下的 6 位是额外的操作码字段，记为 funct6 。

算术右移：这个操作和 srli 很相似，但是它不是用 0 来填充空出来的位，而是用原来的符号位。另外，你也可以从寄存器中取出移位的位数：对应 sll, srl, sra

且、或、非：分别用 and, or, xor (为了保持三操作数格式，写作异或 1...1) 表示，也有立即数形式。

2.6 用于决策的指令

典型的例子是 beq rs1, rs2, L1 。这代表了相等则分支

关于分支循环如何设计的部分略过，这个同编译器。

值得注意的是，\(\text{ARM}\) 指令系统使用的另一种方法是，保留额外的位来记录指令执行期间发生的情况。这些额外的位被称为条件代码/标志位，例如表达结果是否为0 / 负数 / 溢出。

2.6.1 边界检查的简便方法

其实就是检查是否有 0 <= x <= y ，常用于判断下标是否越界。这个时候只需要无符号比较 x <= y 就行了。

2.6.2 case/switch 语句

实现 switch 的最简单的方法，是将其翻译成一系列的 if-then-else 语句。但其实，有时候更有效的方法是编码形成指令序列的地址表，称为分支表。程序只需要索引到表中，然后跳转到合适的指令序列。因此，它是一个双字数组，包含于代码中的标签对应的地址。为了支持这种情况，\(\text{RISC-V}\) 中提供了 jalr 指令。

2.7 计算机硬件对过程的支持

过程 (procedure) 或函数是一种结构化编程的工具，它们可以提高程序的可读性和代码的可复用性。相信读到这里的你对它应该并不陌生，这里我们给出执行过程时，程序必须遵循的步骤：

将参数放在过程可以访问到的位置
将控制转交给过程
获取过程所需要的调用资源
执行过程
把结果值放在调用程序可以访问到的位置
将控制返回到初始点

如我们所认识的，计算机中访问数据最快的地方就是寄存器，因而我们希望能尽可能多地使用它们：我们为过程调用分配了这些寄存器：

x10 ~ x17 ：八个参数寄存器，用来传递参数和返回值 (a0)
x1: 一个返回地址寄存器，用于返回到起始点

除了分配这些寄存器之外，\(\text{RISC-V}\) 中还有一个仅用于过程的指令：跳转到某个地址的同时，将下一条指令的地址保存到目标寄存器 rd。 **跳转-链接指令 (jal) **写作：

jal x1, ProcedureAddress // jump to Procedure Address and write return address to x1

这条指令（包括 jalr ) 能很方便地帮我们完成调用函数的过程。

2.7.1 使用更多的寄存器

考虑一个过程需要比 8 个更多的参数，那么我们需要把寄存器换出到存储器中。

我们考虑栈。栈需要一个指向其中最新分配地址的指针，来指示下一个过程应该放置换出寄存器的位置。将数据放入栈中称为压栈，从栈中移除数据叫做弹栈。按照历史惯例，栈按照从高到低的顺序"增长"，因而减小栈指针就是一种压栈的方法。

这里我们假设使用的临时寄存器的旧值必须被保存和回复。为了避免一个其值从未被使用过的寄存器（通常称为临时寄存器），\(\text{RISC-V}\) 软件将寄存器分成了两组，其中一些是临时寄存器（调用者不对其进行保存），另一些是调用寄存器，一旦使用，被调用者应当保存并回复之。

2.7.2 嵌套过程

在调用非叶子过程中，我们需要注意寄存器的使用。

一种简单的解决方法是将所有需要保存的寄存器压栈。调用者保存所有的参数寄存器和临时寄存器，而被调用者保存返回地址寄存器和它会使用的保存寄存器。返回时，从存储器中恢复寄存器，并重新调整栈指针。

2.7.3 在栈中为新数据分配空间

这些变量是局部变量，也被称为过程帧。

2.7.4 在堆中为新数据分配空间

\(\text{C}\) 程序员还要为静态变量和动态数据结构分配内存空间（例如链表，数组）。

\(\text{C}\) 语言通过 malloc 在堆上分配空间并返回指向它的指针，free 释放指针所指向的堆空间。忘记释放空间会导致 “内存泄漏”，最终耗尽大量内存，导致操作系统崩溃。过早释放空间会导致 “悬空指针”，这可能导致指针指向程序为曾打算访问的位置。（这点被 \(\text{Java}\) 薄纱了）

下面是一个更详细的例子。

2.8 人机交互

下面来聊聊 \(\text{Java}\) 中的字符和字符串：它使用的是 \(\text{Unicode}\) 作为字符，单个字符为 16 位。

\(\text{RISC-V}\) 指令系统也有加载/存储这种 16 位半字的指令：load half unsigned可以把这 16 位放在寄存器的最右边，并用 0 来填充左边。你可能会觉得这样会有更多没用的占用，但是好在字节型数组会把每 8 个半字压缩为“四字”。

2.9 大立即数的寻址

2.9.1 大立即数

很明显，虽然常量通常适合 12 位字段，有时候它们会更大。

好在 \(\text{RISC-V}\) 给我们提供了 load upper immediate，用于将 20 位常数加载到第 31~12 位，并让右边被 0 填充。这条指令也属于新的指令格式——U 型。

2.9.2 分支中的寻址

\(\text{RISC-V}\) 为我们提供了被称为 SB 型的寻址方式，可以表示从 -4086~4094 的偶数地址（你可以理解成这是因为立即数里面放不下第 0 位了）。并且你会看到，这种编码方式很特殊，虽然简化了数据通路设计，但却让组装变得很复杂。

另外还有一个特殊的类型——UJ型。该指令的立即数也是 20 位，唯一一个使用它的是 jal：

如果程序的地址必须适配这个 20 位字段，那么没有一个程序的跨度能大于 \(2^{20}\)。另一种方法是指定一个寄存器来和这个立即数相加，但问题是如何选择这个寄存器。

我们可以采用 \(\text{PC}\)相对寻址 ，因为大部分时候，几乎所有的循环和 if 语句都是小于 \(2^{10}\) 个字的，因而 \(\text{PC}\) 确实是个比较理想的选择。另一方面，过程调用可能需要转移超过 \(2^{18}\) 个字的距离，因此，\(\text{RISC-V}\) 允许使用双指令序列来非常长地跳到任何一个 32 位地址： lui 帮助我们将地址的第 12 位到 31 位写入临时寄存器，jalr 将地址的低 12 位加入，并跳转。

2.9.3 总结

这是寻址方式的总结。关于译码的话，这本质上也就是个字符串大模拟。

2.10 指令与并行性：同步

任务之间需要同步，即需要知道任务何时完成写入、合适能安全地读出。在本节中，我们介绍加锁和解锁的操作，它们可以用于创建只有单个处理器才可以操作的区域，称为互斥区（mutual exclusion） ，以及实现更复杂的同步机制。

同步的第一个关键是一种硬件原语（最基本的单元，例如逻辑门），能以原子方式读取/修改内存。也就是说，内存单元的读取和写入之间不能插入其他任何操作。

我们从原子交换开始，展示如何用它来构建基本同步原语，它将寄存器中的值和存储器中的值进行交换。我们假设构建一个简单的锁变量，1 代表占用，0 代表可用。处理器通过将寄存器中的 1 来和锁变量中内存地址的值进行交换来加锁。如果某个处理器已声明访问该锁变量，则交换指令的返回置为 1，否则为 0 ，代表加锁成功。

另一种方法是使用指令对，第二条指令返回一个值，代表该指令对是否被源自执行。如果处理器的其他操作都在该指令前或后，则这个操作对是原子的。这个操作在 \(\text{RISC-V}\) 中被称为保留加载双字。如果内存位置的内容在条件存储指令执行到同一个地址的时候发生了变化，则条件存储指令失败，不会将值写入内存，信息的传递是通过将是否成功写入某个寄存器。