《计算机系统：系统架构与操作系统的高度集成》——2.4　表达式和赋值语句

本节书摘来自华章计算机《计算机系统：系统架构与操作系统的高度集成》一书中的第2章，第2.4节,作者：（美）拉姆阿堪德兰（Ramachandran, U.）（美）莱希（Leahy, W. D.）著， 更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.4　表达式和赋值语句

我们知道任何高级语言（例如Java、C和Perl）都有算术/逻辑表达式和赋值语句：

上面的每条语句都以两个操作数为输入，执行一次操作，然后将结果存到第三个操作数中。
考虑在一个处理器指令集中的下面3条指令：

高级语言结构（1）、（2）、（3）分别直接映射为指令（4）、（5）、（6）。
这样的指令称为双操作数（binary）指令，因为它们都利用两个操作数进行工作来产生一个结果。它们也被称为三操作数（three-operand）指令，因为有三个操作数（两个源操作数和一个目的操作数）。是不是每个双操作数指令都需要三个操作数呢？简单地说，不是。在接下来的小节中我们将详细阐述这个问题的答案。
2.4.1　操作数放在哪里
让我们讨论一下上面提到的等式中的变量（a,b,c,d,e,f,x,y,z）的位置。图2-1是一个简单的处理器模型。

处理器内部是一个算术/逻辑单元，或者叫做ALU，它执行ADD、SUB、AND和OR等运算。我们现在讨论这些指令的操作数放在什么地方。首先以一个比喻来开始。
假设你有一个工具箱，里面有很多工具。很多工具箱都有一个工具盘（tool-tray）。如果你在做某件事情（比如修理厨房的水龙头），将螺丝刀和水管扳手从工具箱移到工具盘中，然后将工具盘拿到厨房水槽处。接着你会进行修理，完成后将工具盘中的工具放回工具箱中。显然，你不会每次拿工具都跑到工具箱去拿，而是希望这个工具已经在工具盘里面了。换句话说，你通过将需要的最少工具放入工具盘，优化了跑到工具箱边的次数。
我们在设计指令的时候也想这样。我们已经知道术语寄存器用来描述处理器中可用的资源。它们就像内存一样，但是在处理器内部的，所以在物理上（因此也在电子上）更加靠近ALU，被制造得比内存更快，如图2-2所示。

因此，如果指令的操作数都在寄存器中，那么取得操作数就会比操作数在内存中的情况要快得多。但这还不是故事的全部。
使用寄存器还有另一个引人注目的原因，尤其对于现代拥有大内存的处理器更是如此。我们将这个问题称为操作数的可寻址性。回到工具箱和工具盘的比喻。假设你经营着一家汽车修理店，现在你的工具箱相当大。你的工作需要工具箱中几乎所有的工具，但会在不同时候用到。因此，在你工作的不同阶段，你会将工具盘中的工具送回工具箱，将下一阶段需要的工具放入工具盘中。显然，每个工具在工具箱中都有唯一的位置，但在工具盘中却没有。实际上你重复使用工具盘上的空间来放工具箱中的不同工具。
一个对操作数进行唯一寻址的体系结构将面临同样的困境。现代处理器有着非常大的存储系统。随着内存容量的增加，内存地址的大小（即用来表示内存中唯一地址的位数）也相应增加。因此，如果一条指令需要三个内存操作数，那么每条指令的大小都会增加。操作数的可寻址性是个大问题，每条指令都需要占据好几个内存单元以满足对所有内存操作数的唯一命名。
另一方面，有了少数寄存器配合当前程序所需（就像工具盘），我们就可以解决内存可寻址性问题，因为用来表示唯一寄存器地址所需的位数很少。作为内存可寻址性问题的推论，寄存器数量必须较小以限制用来寻址寄存器所需的位数（即便是芯片集成技术允许体系结构中包含更多的寄存器）。
所以，我们的指令看起来是这样的：

另外，程序常需要使用常量。例如，将寄存器初始化为某个值是某个例程的要求。满足这个要求的最简单方法就是指令自身的某一部分作为常量。这样的常量值称为立即值。
例如，我们有一条这样的指令：

在这条指令中，作为指令一部分的立即值成了第三个操作数。在编译高级语言时立即值非常方便。
例2-1　给出下面的指令：

ADD Rx, Ry, Rz    ;    Rx ← Ry + Rz
ADDI Rx, Ry, Imm    ;    Rx ←Ry + 立即值
NAND Rx, Ry, Rz    ;    Rx ← NOT(Ry AND Rz)

如何达到下面这条指令的效果？

SUB Rx, Ry, Rz    ;     Rx ← Ry - Rz

答：

NAND Rz, Rz, Rz    ;     将Rz变为Rz的反码
ADDI Rz, Rz, 1    ;     将Rz变为Rz的补码


    ;     现在Rz其实包含了-Rz
ADD Rx, Ry, Rz    ;     Rx ← Ry + (-Rz)
    ;     后面两条指令恢复了Rz的原始值
NAND Rz, Rz, Rz    ;     将Rz变为Rz的反码
ADDI Rz, Rz, 1    ;    将Rz变为Rz的补码

对于这些算术/逻辑运算来说，所有的操作数都在寄存器中。我们引入寻址模式的概念，寻址模式指的是在一条指令中如何指定某个操作数。这里使用的寻址模式，所有的操作数都在寄存器中，因此被称为寄存器寻址。
关于高级结构（1）、（2）、（3），现在探索程序变量a，b，c，d，e，f，x，y，z和这些处理器寄存器的关系。首先，假设这些变量都在内存中，由编译器放在众所周知的地方。因为变量在内存中但算术/逻辑运算指令只能使用寄存器，因此必须将变量从内存搬到寄存器中。所以，我们需要另外一些指令来将数据在内存和寄存器之间来回搬运。这些指令称为加载（从内存加载到寄存器）和存储（从寄存器存储回内存）指令。
例如，

有了加载/存储指令和算术/逻辑指令，现在可以将这样的一个结构

“编译”为

也许有人感到奇怪，为什么不单纯使用内存操作数来避免寄存器的使用呢？毕竟，这一条单独的指令

与（7）～（10）所示的4条指令序列相比是如此优雅而有效。
借助于工具箱比喻可以很好地理解其中的原因。你知道自己在工作中要多次使用螺丝刀，因此，并不是每次都到工具箱中取螺丝刀，而是花费一些代价将其移至工具盘中，然后多次重用它，直到将它放回工具箱为止。
内存就像工具箱，而寄存器就像是工具盘。你预计程序中的变量将会在多个表达式中使用。考虑如下的高级语言语句：

可以看到，一旦a，b，c从内存被带到寄存器中，仅仅在这一个表达式求值中就重用了若干次。试着将这个表达式“编译”为指令序列（假设乘法指令有着和加法指令相似的形式）。变量在寄存器中的重用给我们带来了什么呢？答案是速度。正如本节中已经说明的那样，因为寄存器在处理器内部，因此我们访问程序变量的时间与每次都到内存中访问相比缩短了很多。
在一条加载指令中，其中一个操作数是一个内存地址，另一个操作数是这条加载指令的目的寄存器（见图2-3）。同样，在一条存储指令中，目标是一个内存地址。

例2-2　一种体系结构有一个称为累加器（ACC）的寄存器，以及操作内存的指令，ACC如下：

LD ACC, a    ;    ACC ← 内存地址a的内容
ST a, ACC    ;    内存地址a的内容 ← ACC
ADD ACC, a    ;    ACC ← ACC + 内存地址a的内容

使用上面的指令，该如何实现下面指令的语义？
ADD a,b,c; 内存地址a的内容 ← 内存地址b的内容 + 内存地址c的内容
答：
LD ACC, b
ADD ACC, c
ST a, ACC
2.4.2　在指令中如何指定内存地址
我们考虑如何使用指令的一部分来指定内存地址。当然，可以将地址直接嵌入指令中。但是这个途径有一个问题。在2.4.1节中提到，用来表示一个内存地址的位数已经很多了，并且随着内存容量的增大，情况只会变得更糟。例如，如果我们有一个PB级（大约250字节）的内存，则在指令中需要50位来表示一个内存操作数。进一步，正如将在2.5节中所见的那样，编译高级语言（尤其是面向对象的语言）写的程序时，编译器只知道复杂数据结构（如数组或对象）的每个成员的偏移量（相对于这个结构的地址）。所以，我们引入一种寻址模式来缓解每条指令都需要将整个内存地址操作数放入其中的情况。
这样的寻址模式称为基址加偏移量（base+offset）模式。在这种寻址模式中，指令中的内存地址为一个寄存器（基址寄存器）的内容与一个偏移量（以立即值形式包含于指令中）的和。通常表示为

如果rb包含变量b的内存地址，而偏移量为0，则上面的指令等价于将程序变量b加载到寄存器r2中。
注意，rb可以是处理器中的任意一个寄存器。
如前所述，基址加偏移量寻址模式的威力在于它可以用来加载和存储简单的变量，很快我们将会看到，它还可以用于复合变量（比如数组和结构）的元素。
例2-3　给出下列指令：
LW Rx, Ry, OFFSET ; Rx ← MEM[Ry + OFFSET]
ADD Rx, Ry, Rz ; Rx ← Ry + Rz
ADDI Rx, Ry, Imm ; Rx ← Ry + 立即值
现在要完成一种新的寻址模式，称为自动递增寻址，用于具有下列语义的加载指令：
LW Rx, (Ry)+ ; Rx ← MEM[Ry];

;     Ry ← Ry + 1;

请给出一个解答，用给出的指令来实现上述LW指令。
答：
LW Rx, Ry, 0 ; Rx ← MEM[Ry + 0]
ADDI Ry, Ry, 1 ; Ry ← Ry + 1

2.4.3　每个操作数应该有多宽
操作数的宽度与其粒度或者说精度有关。为了回答这个问题，我们需要回顾高级语言及其支持的数据类型。我们用C语言作为一种典型的高级语言代表。C语言中的基本数据类型有short、int、long、char。这些数据类型的宽度与实现相关，一般来说，short是16位，int是32位，char是8位。我们知道char数据类型在C中用来表示字母数字字符。char类型宽8位的背后有着历史原因。为了在计算机和通信设备之间交换信息，人们使用ASCII码作为字母数字字符（打字机上能找到的那些符号）数字编码的标准。ASCII码使用7位来表示一个字符。也许有人觉得char数据类型应该是7位宽。然而，在C语言诞生的年代，流行的指令集都使用8位宽的操作数，所以对于C语言来说，使用8位的char类型非常方便。类似地，int数据类型为32位宽的原因是32位的处理器体系结构十分常见。
下一个问题是选择每个操作数的粒度。这依赖于数据类型所需的精度。我们先给出数据精度的非正式定义。假设你在程序中需要一个变量x来存储取值范围在0～255的无符号整数，那么仅需要8位来表示这样一个变量。因此，x所需的精度是8位。类似地，如果在你的程序中有一个有符号整数y取值范围在–231～231–1，那么需要32位精度来表示这样一个变量（假设使用补码表示）。高级语言中的数据类型（如C中的int、short、char）给程序员提供了为不同需求的变量定制不同数据精度的灵活性。你可能惊讶于为什么会提供这样的定制而不是简单地采取体系结构所支持的最高精度，答案是，这是一个在时间和空间上进行优化的机会。程序变量的精度越低，在内存中占用的空间就越小。此外，对于精度需求较低的算术/逻辑运算来说，在处理器和内存之间来回运送操作数也会有一定的时间优势，对于浮点算术运算来说尤为如此。所以，为了空间和时间上的优化，最好是指令中操作数的精度恰好满足数据类型的需求。这也解释了为什么处理器在指令集上支持多种精度，即字、半字和字节。字精度通常指的是体系结构在硬件上对算术/逻辑运算支持的最高精度。其他的精度类别允许在时间和空间上进行优化。
为了方便讨论，我们约定一个字是32位，半字是16位，字节是8位。这些精度类别正好对应于大部分C语言实现中的int、short和char类型。这样的选择是基于2009年前后大部分的硬件字长都是32位。在2.4.1节中，我们已经介绍了操作数可寻址性的问题。当体系结构支持多种精度后，就出现一个内存操作数的可寻址性问题。这里的可寻址性指的是能够在内存中单独指定的最低精度的操作数。比如，如果一台机器是字节可寻址的，那么能够单独寻址的最低精度就是字节。如果是字可寻址的，那么能够单独寻址的最低精度就是字。我们约定讨论中是字节可寻址的。
因此，一个字在内存中看起来是这样的：

每个字里面有4个字节。（MSB指最高有效字节（most significant byte）；LSB指最低有效字节（least significant byte））。例如，我们在程序中有一个整数变量为
0=x11223344
那么它在内存中看起来是这样的：

每一个字节都能够单独被寻址，想必体系结构上会有在这个级别的精度上进行操作的指令。
那么，指令集中应该包含操作不同精度操作数的指令，如下所示：

支持多种精度的操作数的体系结构决策和处理器的硬件实现之间是有关系的。硬件实现包括确定数据通路的宽度以及数据通路中各种硬件资源（如寄存器）的宽度。我们将在第3章和第5章讨论处理器实现的更多细节。因为在讨论中我们认为一个字（32位）是硬件支持的最大精度，为了方便，假设数据通路是32位宽。也就是说，所有的算术/逻辑运算的操作数都是32位的。相应地，假设寄存器的宽度是32位以恰好满足数据通路的宽度。需要注意的是，寄存器和数据通路的宽度正好与体系结构选择的数据宽度相同并不是必需的，但确实是方便且有效的。与此同时，体系结构和硬件实现也需要为操作较低精度操作数的指令提供一些便利。例如，像addb这样的指令是8位精度的，它使用源寄存器中的低8位进行加运算，然后将结果置于目标寄存器的低8位中。
值得注意的是，现代的体系结构已经升级为64位整数运算。甚至连C语言都引入了64位精度的数据类型，但这些数据类型的名字在不同的编译器中可能有些不一致。然而，本章中我们对指令集设计进行的概念上的讨论，与实际硬件支持的精度是完全正交的。
2.4.4　字节序
字节可寻址的机器中存在着一个有趣的问题，就是一个字中各个字节排列的顺序。在字节可寻址的机器中，一个4字节的字，如果从地址100开始，那么这个字其实占据了内存中100、101、102、103这4个连续字节。

这4个字节组合起来就成了地址100处的一个字。

假设100处的这个字的值为0x11223344，那么这4个字节在字中有两种可能的组织方式：
组织方式1：

在这种组织方式中，该字的MSB（包含11hex）位于字的地址即100上。这种组织方式称为大端模式。
组织方式2：

在这种组织方式中，该字的LSB（包含44hex）位于字的地址即100上，这种组织方式称为小端模式。
由此可见，字节序是根据哪个字节处于字的地址上来区分的。如果是MSB，就是大端；如果是LSB，就是小端。
原则上，对于使用高级语言编程来说，字节序其实是无所谓的，前提是严格按照所声明的数据类型要求的那样去使用程序中的变量。
然而，在C这样的语言中，数据类型的使用可能与其声明的不同。
考虑如下的代码片段：

我们来研究一下打印出来的c的值会是什么。这依赖于机器的字节序。在一个大端的机器上，结果将是11hex；而在小端的机器上，结果则是44hex。这个故事告诉我们，如果你声明了某种精度的数据类型却用别的精度去访问它，因为字节序的问题，这可能会成为灾难的根源。一些体系结构如IBM PowerPC和Sun SPARC是大端的，而Intel x86、MIPS和DEC Alpha则是小端的例子。一般说来，字节序对于程序的性能是没有影响的，但总能找到一些病态的例子使得某一种字节序比另一种具有更好的性能，这些例子通常为字符串操作。
比如说，考虑字符串“RAMACHANDRAN”和“WAMACHANDRAN”在大端机器中的内存布局（如图2-4所示）。假设前一个字符串的起始地址为100。

现在来考虑一下相同的字符串在小端机器中的内存布局，如图2-5所示。仔细观察图2-4和图2-5可以发现，在大端机器中，字符串从左往右排布；而在小端机器中则从右往左排布。为了比较这两个字符串，在两种体系结构中，程序员都可以利用字符串在内存中的布局来获得一些性能上的提高。
　
　
正如前面提到的，如果按照声明的那样去操作数据类型，那么字节序对于你的程序是毫无影响的。然而，总有这样的情况，即使一个程序并没有违反上面的规则，字节序依然会影响程序行为。最常见的情况是网络有关的代码，因为它需要在多种不同的机器上工作。如果发送端是小端机器而接收端是大端机器，甚至连网络代码的正确性都会受到影响。正是由于这个原因，网络代码中使用格式转换例程在网络格式和本机格式之间进行来回转换，以避免这样的陷阱。
读者可能会感到奇怪，为什么计算机的制造者不都选择同一种字节序呢？问题在于，对不同的计算机制造者来说，字节序都是神圣的，而且目前也没有有关的标准，因此程序员只能适应多种不同字节序处理器共存的现实。
为了方便讨论，在本章接下来的部分我们都采用小端体系结构。
2.4.5　操作数打包以及字操作数的对齐
现代的计算机系统有大量的内存。因为有大量的内存可以使用，所以对内存的使用没有必要吝啬。然而，这并不完全正确。随着内存容量的增加，软件对内存的胃口也更大了。程序在内存中占据的空间通常被称为内存印迹。如果编译器在编译时非常简单粗暴，可能会尝试将程序在内存中的操作数打包以节约空间。具体来说，如果数据结构中包含了多种不同粒度的变量（即int、char等）且体系结构支持多种精度的操作数，那么这是很有意义的。顾名思义，打包的意思是将操作数排布在内存中时保证没有空间被浪费。然而，在本章中我们将解释为何打包并非总是正确的途径。
首先，我们讨论编译器如何排布内存中的操作数以达到节约空间的目的。考虑下面的数据结构。

这个数据结构在内存中的一种可能布局以100为起始地址，如下图所示

让我们来确定这个数据结构最终需要占据的内存大小。因为每个char是1字节，所以数据结构的实际大小是4字节，但上面的布局却浪费了50%用于存储的空间。阴影部分就是浪费的空间。这就是未打包的布局。
有效的编译器将释放掉浪费的空间而将上面的数据结构打包，以100为起始地址，如下图所示：

编译器进行的打包与数据类型要求的精度和体系结构支持的可寻址性都是对应的。除了节省空间以外，这样的布局还能减少在处理器寄存器和内存之间来回搬运该数据结构（包含变量a和b）所需的访存次数。因此，打包操作数在空间和时间上都是高效的。
正如我们上面提到的，对于编译器来说，打包并非总是应当采取的策略。
考虑下面的数据结构：

我们来再次确定这个数据结构需要在内存中占据多少空间。一个char是1字节，一个int是1个字（即4字节）。因此，总共需要5字节来存储这个结构。我们来看看其中一种可能的布局，以100为起始地址。

这种布局的问题在于，b是一个int，它始于地址101，结束于104。为了加载b，需要从内存中读取两个字（分别从100和104两个地址读取）。无论由硬件还是软件来实现，这都是非常低效的。体系结构通常要求字操作数从字地址开始，这就是所谓的操作数与操作地址的对齐限制。
如果address不在字边界（100、104等）上的话，那么下面的指令

就是一条非法指令。尽管编译器可以生成代码来加载两个字（在地址100、104处）并将它们在处理器中重新组成所需的int数据类型，但这在时间上是非常低效的。因此，典型的编译器在布局数据结构时会使得需要字精度的操作数位于字边界地址。
所以，编译器很可能将上面的数据结构按下图的方式来布局，起始地址为100：

尽管这个布局浪费了37.5%的空间，但从访问操作数的时间这个角度来看，变得更加高效了。
你将会看到，计算机科学领域在第1章列出的所有抽象层次（从应用程序到体系结构）上都会表现出这种经典的时间–空间的权衡。