附录A 指令集基本原理

1. 引言

本书主要关注指令集体系结构4个主题：
        1. 提出对指令集进行分类的方法，并对各种方法的优缺点进行定性评估；
        2. 提出并分析一些在很大程度上独立于特定指令集的指令集评估数据。
        3. 讨论语言与编译器议题以及它们对指令集体系结构的影响。
        4. 展示这些思想在RISC-V指令集中是如何实现的。

桌面计算机强调涉及整数和浮点数据类型的程序性能，很少考虑程序规模。如今的服务器主要用于数据库、文件服务器和Web应用，还有一些针对许多用户的分时应用。因此，浮点性能的重要性远低于整数和字符串。个人移动设备和嵌入式应用看中成本和能耗，所以代码规模非常重要，因为存储器更少就意味着成本和能耗更低。

在RISC-V存在的时代，x86的成功可能是由于PC软件保持二进制兼容在商业上很重要，再加上摩尔定律提供了大量的晶体管，Intel在CPU内部使用类似RISC的微指令。

2. 指令集体系结构的分类

处理器的内部存储类型是最基本的区别，所以本节主要关注这部分的各种选项：栈、累加器和寄存器组。操作数可以显示命名，也可以隐式命名：在栈体系结构中，操作数隐式位于栈的顶部，而在累加器体系结构中，操作数微隐式的累加器。同样寄存器体系结构只有显示操作数--要么寄存器，要么存储器地址。

实际上有两类寄存器计算机：

        1. 可以用任意指令来访问存储器，即寄存器--存储器体系结构；
        2. 只能用载入和存储指令来访问存储器，称为载入--存储体系结构；

尽管大多数早期计算机使用栈或累加器类型的体系结构，但1980年之后几乎所有新体系结构都是用载入--存储体系结构。通用寄存器计算机之所以会出现，主要原因有3：

        1. 寄存器快于存储器；
        2. 对编译器来说，使用寄存器的效率要高于使用其他内部存储形式；
        3. 寄存器可用来保存变量。当变量被分配到寄存器中，可以降低内存的访问量、加快程序速度、提高代码密度（寄存器的名称位数小于内存地址的位数）。

如果真正的通用的寄存器的数量过少，那么尝试将变量分配到寄存器中就没有什么好处。编译器通常保留所有未确认用途的寄存器，以便用于表达式求值。

多少个寄存器才算够呢？答案取决于编译器如何使用这些寄存器。大多数编译器会为表达式求值保留一些寄存器，为参数传递使用一些寄存器，其余寄存器可用于保存变量。

可用来区分通用寄存器体系结构的2个重要特性如下：
        1. ALU指令是2个还是3个操作数；
        2. ALU指令有多少操作数可以是内存地址；

优劣势不是绝对的：它们是定性的，它们的实际影响取决于编译器和实现策略。体系结构方面最普遍的影响之一是指令编码和执行一项任务所需的指令数。

3. 存储器寻址

体系结构必须定义如何解释存储器地址以及如何指定这些地址。

3.1 解释存储器地址

如何解释一个存储器地址呢？根据地址和长度会访问到什么对象呢？

第一个问题如何对一个较大对象中的字节进行排序？有两种方式：小端字节和大端字节。前者将低位的字节放在低位地址。

在采用不同排序方式的计算机之间交换数据时，字节顺序会成为一个问题。

第二个存储器问题是：在许多计算机中，对于大于1字节的对象的访问必须是对齐的。如果 地址% bpe=0，则在字节地址对大小bpe的对象的访问是对齐的。

为什么要设计一种带有对齐限制的计算机呢？由于存储器的对齐边界通常是单字或双字的整数倍，所以非对齐访问会增加硬件复杂度。

3.2 寻址方式

处理存储器的位置之外，寻址方式还指定常量和寄存器。在使用存储地址时，由寻址方式指定的实际存储器地址称为有效地址。

立即数和直接操作数寻址通常是被看作存储器寻址方式，PC相对寻址主要用于控制转移指令中指定代码地址。

寻址方式能够大幅度减少指令数目，也会增加构建计算机的复杂度，还可能增加每条指令的CPI。

位移量寻址和立即数寻址是使用最多的寻址方式。

3.3 位移量寻址方式

在使用位移量类型的寻址方式时，一个主要问题是所用位移量的范围，因为位移量字段的大小直接影响指令的长度。

3.4 立即数或直接操作数寻址方式

立即数可用于算术运算，比较（分支指令）和寄存器中需要常量的移动，包括代码常量和地址常量。对于立即数的使用，重点是知道需要对所有运算支持立即数，还是仅对一部分运算支持立即数。

另一个重要的指令集测量是立即数的取值范围。与位移量相似，立即数取值的大小也会影响指令长度。

3.5 存储器寻址

预测一个新的体系结构至少会支持以下寻址：位移量寻址（向量类型数据）、立即数寻址和寄存器间接寻址。预测位移量寻址方式中的地址至少为12~16位。预测立即数至少为8~16位。

4. 操作数的类型与大小

如何指定操作数的类型呢？通过在操作码中进行编码来制定操作数的类型，这是最常用的方法。

5. 指令集中的操作

关于所有体系结构的一条经验就是：执行最多的指令是指令集中简单操作。

6. 控制流指令

任何情况下都必须指定控制流指令中的目标地址。但过程返回是一个例外，这是因为在编译时无法知道要返回的目标地址。指定目标的最常见方法是提供一个将被加到PC的位移量。这类控制指令被称为PC相对指令。由于目标位置通常在当前指令附近，而且指令相对当前PC的位置需要的位数较少，所以PC相对分支或跳转指令具有一些优势。采用PC相对寻址还可以使代码的运行不受装载位置的影响。这一特性称为位置无关，可以在链接程序时减少一些工作，而且对于在执行期间进行动态链接的程序也比较有用。

6.1 控制流的寻址方式

如果在编译时不知道目标位置，为了实现返回和间接跳转，需要一种不同于PC相对寻址的方法。这时，必须有一种动态指定目标的方法，使目标在运行时发生变化。这种动态寻址可能非常简单，只需要给出包含目标地址的寄存器名称即可；跳转可能允许使用任意寻址方式来提供目标地址。这种寄存器间接跳转对于其他4种重要功能也是有用的：
        1. case或switch；
        2. 虚拟函数或者虚拟方法；
        3. 高阶函数或函数指针；
        4. 动态共享库；

在以上4种情况中，目标地址在编译时都是未知的，因此，通常是在寄存器间接跳转之前从存储器记载到寄存器中。

由于分支通常使用PC相对寻址来指定其目标，一个重要问题就是分支目标距离分支有多远？

6.2 条件分支选项

由于大多数控制流改变是分支，所以决定如何指定分支条件是很重要的。分支最明显特性之一是大量的比较是简单的测试，其中很多是和0比较。

6.3 过程调用选项

过程调用和返回包括控制转移，还可能涉及状态保存过程；至少必须将返回地址保存在某个地方，有时保存在特殊的链接寄存器，有时只是保存在通用寄存器中。较新的体系结构需要编译器为所有存储和恢复的每个寄存器生成存储和载入操作。

在保存寄存器中，有两种基本约定：要么由调用者保存，要么由被调用者保存。调用者保存是指发出调用过程的必须保存它希望在调用返回之后进行访问的寄存器。因此，被调过程不必操心寄存器。被调用者保存与之相反：被调用的过程必须保存它想使用的寄存器，而调用者不受限制。某些时候必须选择调用者保存方法，因为两种过程对全局可见变量的访问模式。

ABI指出了那些寄存器应当由调用者保存，那些应当由调用者保存。

6.4 小结：控制流指令

尽管条件分支有许多选项，但我们希望新体系结构中的分支寻址能够跳转到分支指令之前或之后数百条指令处。这一要求意味着PC相对分支位移量至少为8位。还希望看到跳转指令采用寄存器间接寻址和PC相对寻址，来支持过程返回和当前系统的许多其他功能。

7. 指令集编码

指令如何编码为二进制形式以供处理器执行。这不仅会影响编译后程序的大小，还会影响处理器的实现，处理器必须对这种表示形式进行译码，以快速找出操作和操作数。操作通常在一个称为操作码的字段中指定。如何通过编码将寻址方式与操作数结合在一起是一个非常重要的决定。

这一决定取决于寻址方式的范围以及操作码与寻址方式之间的独立程度。对于大量寻址方式而言，需要为每个操作数使用独立地址标识符：地址标识符说明使用哪种寻址方式来访问该操作数。另一种极端是仅有一个存储器操作数并且仅有一种或两种寻址方式的载入--存储计算机。

在进行指令编码时，由于寄存器字段和寻址方式字段可能在一条指令中出现多次，所以寄存器数目和寻址方式的数目都对指令大小有很大影响。在对指令集进行编码时，架构师必须平衡以下几种相互竞争的因素：
        1. 希望有尽可能多的寄存器和寻址方式；
        2. 寄存器字段和寻址方式的长度对平均指令大小有影响，从而对平均程序规模有影响；
        3. 希望编码后的指令长度易于流水线实现方式处理。至少，架构师希望指令的长度是字节的倍数，而不是任意长度。不过，这以牺牲平均代码规模为代价。

3种常见的指令集编码选择：
        1. 变长编码，因为它几乎允许对所有操作使用所有寻址方式。当存在许多寻址方式和操作时，这是最佳选择。
        2. 定长编码，因为它将操作和寻址方式合并到操作码中。当寻址方式和操作数较少时，其效果最好。
        3. 混合编码，降低变长体系结构中指令大小和指令功能的可变性，但提供多种指令长度来减少代码大小。
        在变长编码与定长编码之间做选择时，权衡的是程序的规模和处理器译码的难以程度。变长代码尽可能少的位数来表示程序，但是单个指令在大小和要执行的工作量方面可能有很大差异。

7.1 RISC精简代码

随着RISC计算机在嵌入式应用程序中使用，32位定长格式已经成为一种负担，因为成本和更小的代码非常重要。为应对这一情况，新版RISC指令集同时拥有16位和32位指令。这些精简的指令支持更少的运算种类、更小的地址范围与立即数字段、更少的寄存器和两地址格式，而不是RISC典型的3地址模式。

7.2 小结：指令集编码

更看重代码规模的架构师会选择变长编码，而更看重性能的架构师则会选择定长编码。

8. 交叉问题：编译器的角色

由于高级语言的畅行，意味着所指向的大多数指令都是编译器的输出，所以指令集体系结构就是编译器目标，则编译器会显著影响计算机的性能。

曾经流行一种做法：试图将编译器技术及其对硬件性能的影响与体系结构及其性能隔离开来，就像过去经常尝试将体系结构与其实现隔离开来。今日看来，这种隔离基本上是不可能的。

8.1 目前编译器的结构

编译器开发人员的首要目标就是正确新--所有有效程序都必须正确编译。第二个目标通常是编译后的代码速度。正常情况下，编译器的各次扫描将更抽象的高级表示转换为越来越低层级的表示，最后到达指令集级别。这种结构可以帮助控制转换的复杂度，使得编写出来没有错误的编译器变得更容易。

尽管采用多遍扫描的结构有助于降低编译器的复杂性，但这也意味着编译器必须对转换进行排序，某些转换必须在其他转换之前完成。在某些高级优化执行很久之后，编译器才能知道最终代码会是什么样子。一旦执行这种转换，编译器就不能承担返回并重新审视所有步骤，甚至撤销这些转换的代价。无论是从编译时间还是复杂度角度，都不允许进行这种迭代，即阶段排序问题。

根据转移类型，现代编译器执行的优化分类：
        1. 高级优化一般对源代码执行，并将输出结果传送给之后的优化扫描；
        2. 本地优化仅对直行代码段（基本块）内代码进行优化；
        3. 全局优化将本地优化扩展到分支范围之外，并引入了一组旨在优化循环的转换；
        4. 寄存器分配将寄存器与操作数关联在一起；
        5. 与处理器相关的优化尝试利用特定的体系结构知识。

8.2 寄存器分配

鉴于寄存器分配在加快代码速度和使其他优化发挥效用方面所扮演的角色，可以说它是最重要的优化之一。今天寄存器分配算法时一种名为图着色的技术为基础。基本思想就是构造一幅图，用来表示可能执行的寄存器分配方案，然后利用这个图来分配寄存器。大致来说，问题在于如何使用有限种颜色，使相关图中两个相邻节点的颜色都不相同。这种方法的重点是将活跃变量全部分配到寄存器中。

当至少有16个通用寄存器可用于整数变量进行全局分配时，而且有其他寄存器为浮点变量进行分配时，图着色方法的效果最好。遗憾的是，如果寄存器的数目很少，则图着色的启发式算法很可能失败。

8.3 优化对性能的影响

8.4 编译器技术对架构师决策的影响

编译器与高级语言之间的互动对程序利用指令集体系结构的方式有很大影响。这里有两个重要问题：
        1. 如何对变量进行分配和寻址；
        2. 需要多少寄存器才能对变量进行适当的分配？

为了回答这些问题，必须看当前高级语言用来分配数据的3个独立区域：

        1. 栈用来分配本地变量。栈会在过程调用与返回时相应增大或缩小。栈内的对象是相对于栈指针进行寻址的，这些对象主要是标量（单个变量），而不是数组。栈用于活动记录，而不是用于表达式求值。因此，几乎不会在栈中压入或弹出数值。
        2. 全局数据区用于静态分配所声明的对象，比如全局变量和常量。这些对象中有很大一部分是数组或者其他聚合数据结构。
        3. 堆用于分配那些不符合栈规则的动态对象。堆中对象用指针访问，并且通常不是标量。

寄存器分配对于分配到栈中的对象要比对全局变量有效得多，而对于分配到堆中的对象，寄存器分配基本上是不可能的，因为它们是通过指针访问的。全局变量和一些栈变量也不可能分配，因为它们具有别名，也就是可以用多种方法引用变量的地址，从而不能合法地将其放到寄存器中。

如果过程中的本地变量可能被某个指针所访问，某些编译器就不会分配任何本地变量到寄存器中。

8.5 架构师如何帮助编译器开发人员

若程序规模庞大而且其全局互动非常复杂，而且编译器的结构决定了在判定哪种代码序列最佳时，一次只能判断一步。

编译器开发人员更倾向于加快常见情况的速度，保证少见情况的正确性。

编译器希望的指令集特性：
        1. 提供正则性：只要有意义，指令集的三要素--操作、数据类型和寻址方式--就应当正交。正则性有助于简化代码生成过程，如果在决定生成何种代码时，需要再编译器的两遍扫描中做出决策。
        2. 提供原型而非解决方案：与一种语言构造或内核功能“相匹配”的特殊功能通常不可用。
        3. 简化候选项之间的权衡：对于编译器开发人员来说，最艰巨的任务之一就是对于所出现的任何一段代码，指出哪种指令序列最为适合。早期就是指令数或者代码规模可能是个好评价指标。有了缓存和流水线之后，权衡已经变得更加复杂。进行权衡最困难场景之一发生在寄存器-存储器体系结构中，就是判断一个变量的引用次数达到多少之后，将其载入寄存器的成本才更低一些。
        4. 提供一些指令，将编译器时已知量绑定为常量：编译器开发人员特别讨厌处理处理器在运行时费力解读一个在编译时就已知的取指。

8.6编译器对多媒体指令的支持

SIMD指令的设计者基本忽略：指令往往就是解决方案，而不是原型；它们缺少寄存器；数据类型与现有编程语言不匹配。

微处理器体系结构想向量寄存器大小设定在体系结构内部：对于MMX，元素大小的总和限制是64位，AltiVec限制为128位。当Intel决定扩展到128位向量时，它添加了一整台新指令，SSE。

向量计算机的一个主要优势是：一次载入许多元素，然后将执行和数据传输重叠起来，从而隐藏存储器访问的延迟。向量寻址方式的目标是收集散步在存储器中的数据，以紧凑方式放置它们，以便高效处理，然后将处理结果放回所属位置。

向量计算机包括步幅寻址和集中/分散寻址，以增加可向量化程序的数目。步幅寻址在每次访问之间跳过数量固定的字，所以顺序经常称为单位步幅访问。集中寻址与分散寻址在另一个向量寄存器中查找其地址：可以将其看做向量计算机的寄存器间接寻址。步幅寻址和集中/分散寻址方式是成功实现向量化的必备条件。

采用受体系结构限制的短向量，已经很少的寄存器和简单的存储器寻址方式，就更难利用向量化编译器技术。因此，这些SIMD指令更可能出现在手工编码库中，而不是编译后的代码中。

8.7 小结：编译器的角色

首先，希望一种新的指令集中至少拥有16个通用寄存器（浮点寄存器不算在内），以简化使用图着色的寄存器的分配。关于正交性的建议意味着所支持的全部寻址方式都适用于传送数据的指令。最后的三点建议（提供原型而非解决方案，简化候选项之间权衡，不要再运行时绑定常量）都意味着注重简单是最稳妥的。换句话说，要理解在指令集的设计中，少就是多。SIMD扩展是优秀技术落地的例子，而不是软硬件协调设计的成功。

10 谬论和易犯错误

易犯错误：设计专门支持高级语言结构的“高级”指令集功能

架构师试图在指令集中整合高级语言功能，从而提供功能强大、极具灵活性的指令。但是，这些指令所完成的工作通常会超出常见情景下的需求，或者不能与某些语言的需求完全匹配。

谬论：存在典型程序的一种东西

各个程序对指令集的使用方式有很大不同。

易犯错误：不考虑编译器，仅通过指令集体系结构的创新来缩小代码规模。

和性能优化相结合，架构是应当首先考虑编译器所能生成的最紧凑代码，然后在考虑通过硬件创新来节省空间。

谬论：有缺陷的体系结构不可能获得成功。

8086体系结构中不受欢迎的体系结构决策。例如，支持段式存储，而所有其他体系结构都选择页式存储；它为整型数据使用扩展累加器，而其他处理器则使用通用寄存器，它为浮点数使用栈么人其他所有人在很久之前就放弃了执行栈。

8086依旧取得成功的原因有三：
        1. 8086的二进制兼容性极为重要，因为最初的IBM PC选择它为微处理器。
        2. 摩尔定律提供了足够的资源，供8086在内部转换为类似RISC指令。
        3， PC微处理器的销量之高，使Intel可以轻松支付不断增加的硬件转换设计成本。以及高销量能够太高学习曲线，降低生成成本。

谬论：可以设计一种没有缺陷的体系结构

所有体系结构设计都需要一组软硬件技术之间进行权衡。1957年，VAX设计人员过度强调代码规模效率的重要性，低估了译码和流水化的重要性。RISC的例子就是延迟分支。对于浅流水线而言，控制流水线冒险很简单，但长流水中，在每个时钟周期发射多条指令，那就是一个挑战。此外，几乎所有体系结构最终都会因为缺少足够的地址空间而崩溃。

11. 结语

最早体系结构的指令集受到当时硬件技术的限制。只要硬件技术允许，计算机架构师就会探索支持高级语言的方式。在三个不同时期，关于如何高效支持程序，侧重点不一：
        1. 20世纪60年代，栈体系结构显得非常流行，跟高级语言很匹配。根据当时编译器技术，可能也的确如此。
        2. 20世纪70年达，架构师主要关注如何降低软件成本。其解决方案主要是用硬件代替软件，或者提供能够简化软件设计人员的高级体系结构。其结果就是高级语言计算机体系结构有着大量的寻址方式、多种数据类型和高度正交的体系结构。
        3. 20世纪80年代，更高级编译器技术和对处理器性能的再度重视，导致简单体系结构的回归，其主要就是载入-存储型计算机。

20世纪90年代，指令集体系结构发生了以下变化：
        1. 地址大小加倍：32位地址指令集被扩展到64位，寄存器宽度被扩展到64位。
        2. 通过条件分支优化条件分支：将条件分支替换为操作的条件执行。
        3. 通过预取优化缓存性能；
        4. 支持多媒体指令SIMD；
        5. 浮点运算速度更快；

20世纪50~60年代，计算机体系结构强调计算机算术运算；70年代~85年代，计算机体系结构主要任务是设计指令集。