阎晶晶

跑男嘉宾【计算机组成与设计】第二章：指令：计算机的语言-一个理科生的自我修养

【计算机组成与设计】第二章：指令：计算机的语言-一个理科生的自我修养

第二章：指令：计算机的语言2.1 引言
指令集（instruction set）：一个给定的计算机体系结构所包含的指令集合。
存储程序概念（stored-program concept）：多种类型的指令和数据均以数字形式存储于存储器中的概念，存储程序型计算机即来源于此。
我们采用 MIPS 技术的指令集。使用自顶向下，循序渐进的方法并结合各部件及其说明。
尽管可以简单使用序号 0 ~ 31来表示相应的寄存器，但 MIPS 约定书写指令时候使用一个 "$"符后面跟两个字符来表示一个寄存器。现在，我们使用$s0,$s1....表示 C 和 Java 程序中的变量所对应的寄存器；用 $t0,$t2...来表示将程序编译为 MIPS 指令所需的临时寄存器。
如下表，为指令集的总体情况。
2.2 计算机硬件的操作
硬件设计的三条基本原则：
简单源于规整
越小越快
优秀的设计需要适宜的折中方案2.3 计算机硬件的操作数
与高级语言程序不同，MIPS 算术运算指令的操作数是很严格的，它们必须来自于寄存器。寄存器由硬件直接构建并且数量有限，是计算机硬件设计的基本元素。当计算机完成设计之后，寄存器对程序员是可见的。MIPS体系结构中寄存器大小是 32位，考虑到 32位为一组的情况出现，因此出现了 字 的概念。
字（word）：计算机中的基本访问单位，通常是 32 位为一位，在MIPS体系结构中与寄存器大小相同。
MIPS 一类的典型的现代计算机中有 32 个寄存器。在这里三个操作数限定必须从 32 个 32 位寄存器中选取。
2.3.1 存储器操作数
在复杂的数据结构中的数据元素可能远多于计算机中寄存器的个数，那么计算机如何表示和访问这样大得结构呢？在计算机的 5 个组成部分中。计算机只能将少量数据保存在寄存器中，但存储器中有数十亿的数据元素。因此，数据结构（比如数组和结构）是存放在存储器中的。因此，MIPS的算术运算指令只对寄存器进行操作，故MIPS 必须包含在存储器和寄存器之间传送数据的指令。这便是数据传送指令。另外，为了访问存储器中的一个字，指令必须给出存储器地址。
数据传送指令（data transfer instruction）：在存储器和寄存器之间移动数据的指令。
地址（address）：用于在存储器空间中指明某特定数据元素位置的值。
在下图中，存储器地址和该地址对应的是数据。如果这些元素是字，那么这些地址就是错误的，因为MIPS实际上是按照字节编址的。而一个字是 4 个字节，下图为顺序字编址的内存地址。
取数（load word，lw）：将数据从存储器复制到寄存器的数据传送指令。
除了将变量和寄存器对应起来，编译器还在存储器中为诸如数组和结构这类的数据机构分配了相应的位置。编译器可以将它们在存储器中的起始位置放到数据传送指令中。很多程序都用到 8 比特的字节类型，并且大多数体系结构按字节编址。因此，一个字的地址必须和它所包括的 4 字节中某一个地址相匹配，并且连续的字的地址相差 4.可见下图：
对齐限制（alignment restriction）：数据地址与存储器的自然边界对齐的要求。因为 MIPS 是按照字节编址的，所以字的起始位置必须是 4 的倍数。这叫做对齐限制 ，许多体系结构都有这样的限制。
两种类型的字节寻址计算机：大端寻址（big end）：使用最左边的字节地址作为字地址。小段寻址（little end）：使用最右边的字节地址作为字地址。MIPS 使用的大端编址。由于使用相同的地址取访问一个字和 4 个字节时“端”才起作用，因此大多数情况下勿需关注。
字节寻址也影响数组下标。例如，A是含有一百个字的数组，如果需要访问 A8, 它的偏移量为 4 * 8 = 32.
与取数指令相对应的指令叫做存数（store）指令，它将数据从寄存器复制到存储器。存数指令的格式与取数指令相似：首先是操作码，接着是包含存数数据的寄存器，然后是数组元素的偏移量，最后是基址寄存器。MIPS中存储指令为 sw，为 store word 的缩写。
许多程序的变量个数要远多于计算机的寄存器个数。因此，编译器会尽量将最常用的变量保持在寄存器中，而将其他的变量放在存储器中。方法是使用取数/存数指令在寄存器和存储器之间传送变量。将不常用的变量（或者稍后才使用的变量）存回到存储器中的过程叫做寄存器一处（spilling）.
存储器一定比寄存器慢，因为存储器器数量更少。
寄存器中的数据更容易得到利用，一条 MIPS 算术运算指令能够完成读两个寄存器、对它们进行运算以及回写运算结果的操作。而一条 MIPS 数据传送指令只能完成读一个操作数或者写一个操作数的操作，并且不能对他们进行运算。
寄存器与存储器相比，访问时间短，吞吐率高，七寸其中的数据访问速度快并且易于利用，访问寄存器相对于访问存储器功耗更小。因此，为了获得高性能和节约功耗，指令集的体系结构必须拥有足够的寄存器，并且编译器必须高效地利用这些寄存器。
2.3.2 常数或立即操作数
仅仅从已经介绍过的指令来看，如果要使用常数必须先将它从存储器中取出。例如，如果要使寄存器$\$$3 加 4,则代码为： $$ lw~~ $t0,AddrConstant4($s1) $$ $$ add~~ $s3,$s3,t0 $$避免使用取数指令的另一个方法是，提供其中一个操作数是常数的算术运算指令。有一种常数操作数的快速加法指令叫做加立即数（add immediate），可以写作 addi.则上述代码可以简化为 $$ addi ~~$s3,$s3,4$$相对于从存储器中取常数，这样的算术运算指令的执行速度快，耗能低。
常数 0 的作用，除了当作里技术之外，还可以有效使用它来简化指令集。例如，数据传送指令刚好可以被是做一个操作数为 0 的加法。因此，MIPS 将 $zero 恒置为 0.（此寄存器的编号也为 0 ）。注：根据使用频率来确定要定义的常数是加速大概率事件的另一个好办法。
在本笔记中，虽然讲到的 MIPS 寄存器都是 32位，但是也有 64位版本的MIPS指令集，它具有32 个 64位的寄存器。为了加以区分，我们分别称之为 MIPS-32 和 MIPS-64.
MIPS 中偏移量加基址的寻址方式非常适合数组和结构，因为基址寄存器可以指向结构的首地址，偏移量可以用来选择所需要的数据元素。
在最初设计数据传送指令时，基址寄存器用于保存数组下标，而偏移量用来表示数组的起始地址。因而基址寄存器也叫做下标寄存器*（index register）。而现在，存储器容量大大增加，数据分配的软件模型也变得更复杂，所以数组的基地址通常放在寄存器中。
由于 MIPS 支持常负数，因此MIPS中不需要设置减立即数的指令。
2.4 有符号数和无符号数
首先回顾一下，计算机是如何存储数字的。在生活中，我们大多使用十进制，但是数的进制是任意的。在计算机硬件中，数是以一串或高或低的电信号来体现的，因此可以被认为基为 2 的数。
二进制数位（binary digit）：又称为二进制位，非 0 即 1，是信息的基本组成单位。
无符号数
进制转换，对于任意进制而言，第 i 位数字 d 的值是 $ d * Base^i$ ，在这里，i是从 0 开始并且从右向左递增的。显而易见，计算一个数各位数值的方法是使用幂。例如 $ 10112 = （1*2^0 + 1*2^1 + 0*2^2 + 1*2^3）{10} = 11{10} $.在 32位的字中（一个字为 4 个字节，一个字节为 8 位）我们从右向左标记各位0，1，2.....，下面的表格表示了 MIPS 字中的每一位编号和数字 $ 10112 $的存放位置：
由于字是在水平或者竖直方向上书写的，用最左边或者最右边表示大小带有不确定性。最低有效位（least significant bit） 表示最右边一位（比如上图中第 0 位，对应数据 1），最高有效位（ most significant bit）表示最左边一位（上图中的第 31 位，对应数据 0 ）。
MIPS 的字有 32 位，可以表示 $ 2^{32} $ 个不同的 32 位模式，很自然就可以使这些组合表示从 $0 $到 $2^{32} - 1 $之间的数：$$ 0000 ~0000~0000~0000~0000~0000~0000~0000 2 = 0{10} $$$$ 0000 ~0000~0000~0000~0000~0000~0000~0001 2 = 1{10} $$ $$....$$$$ 1111 ~1111~1111~1111~1111~1111~1111~1111 2 = 4 ~294 ~967~295{10} $$如下式， 32 位的二进制数字也可以表示成为每位的值乘以该数字位上对应的 2 的幂次的形式$$x{31}* 2^{31}+ x{30}* 2^{30}+...+ x{1}* 2^{1} + x{0}* 2^{0} $$
历史上，第一台商用计算机使用的是十进制算术。而问题出现在开关信号上，在十进制表示的计算机中，一个十进制数字由几个二进制数字表示。事实证明十进制的效率非常低，所以后来所有计算机都转换为 2 进制，只有在相对很少发生的 I/O 事件中才将数据转换为十进制。
有符号数。
符号和幅值（sign and magnitude）：计算机程序需要对正数和负数进行计算。所以需要增加一个独立的符号位来区分正负数。但由于符号位放置在哪里不够明确，左边还是右边？早期计算机对于这两种方法都尝试过。另外，不可能在计算时提前得知结果的符号，对于符号和幅值表示的数字进行计算需要额外的一步来设置符号。还有，一个单独的符号为意味着存在正零和负零，因子很对这种表示方法便被舍弃了。
二进制补码（two's complement）：前导位 0 表示正数，1 表示负数。这种表示方法易于硬件实现。例如： $$ 0000 ~0000~0000~0000~0000~0000~0000~00002 = 0{10} $$$$ 0000 ~0000~0000~0000~0000~0000~0000~00012 = 1{10} $$ $$....$$$$ 0111 ~1111~1111~1111~1111~1111~1111~11112 = 2~147~483~647{10} $$$$ 1000 ~0000~0000~0000~0000~0000~0000~00002 = - 2~147~483~648{10} $$$$...$$$$ 1111 ~1111~1111~1111~1111~1111~1111~11112 = -1{10} $$ 其中需要注意的是，$ 1000 ~0000~0000~0000~0000~0000~0000~0000 $ 对应的 -2 147 483 648 没有相应的正数与之对应。 所有负数的最高位都是 1，这个位通常叫做符号位。 现代计算机都采用二进制补码的方法表示有符号数。 $ $
溢出（overflow）：
对于无符号数：二进制数加减乘除等操作的结果不能被最右端的硬件位表示。
对于有符号数：对二进制补码数的操作也有可能发生溢出。溢出发生在有限二进制数最左边的符号位与采用无穷多位表示该数时左边的值不同的情况下（即符号位不确定）：该数是负号时符号位为 0 ，或者该数是正号的时候符号位为 1. $ $
和算术运算一样，对于取数指令而言，有符号数和无符号数是有区别的。取回有符号数之后需要使用符号位填充寄存器的所有剩余位，称为符号扩展。但其目的是在寄存器中放入数字正确的表达方式。取回无符号数知识简单用 0 来填充数左侧的剩余位置，因为这种表示形式的数是没有符号的。当把 32 位的字加载到 32 位的寄存器中时，以上的讨论是没有意义的，因为无符号数和有符号数的加载是完全相同的。MIPS 提供了两种字节加载的方法：一种是用于字节加载的 lb（load byte） , lb 将字节看作有符号数临沂正直驾校，使用符号扩展来填充寄存器的左侧 24 位。另一种是无符号整数加载的 lbu（load byte unsigned）.由于 C 语言程序几乎都是使用字节来表示字符，很少用来表示有符号短整数，所以实际中几乎所有字节加载都是用 lbu .
与上述讨论的数不同，存储器地址很自然地从 0 开始，一直连续增加到最大的地址。换而言之，负地址是没有意义的。但是，有时候程序需要处理一些可以是正的可以是负的数，有时需要处理一些仅仅可能是正的数字。一些编程语言反映了这些区别，例如，在 C 语言中，前者为 int 类型，后者为 unsigned int.
处理二进制补码数的简单方法：
考虑以下事实，对于任何一个二进制数 $ x $ 对它的每一位取反得到 $ \bar{x} $, 且$ x + \bar{x} = 111...1112 = -1{10}$，因此有$ \bar{x} + 1 = x$. 基于以上原理的方法，对二进制补码数取反的快速方法：简单地对每一位取反，0 变成 1 ， 1 变成 0，然后对结果 加1.
符号扩展（sign extension）：将一个用 n 位表示的二进制数转换成一个多于 n 位表示的数。
反码（one's complement）：一个数的相反数就是将这个数的每一位按位取反，0 变成 1, 1 变成 0. 与补码相比，反码除了有两个零，$00...002 ,100...002 $ 之外，其余都是一样的。绝对值最大的负数（最小的负数）为 $10...00_2$，并且负数的个数和正数的个数是一样的。当采用反码时，加法器需要一个额外的步骤减去一个数来修正结果。
-偏移表示法（biased notation）：又称为移码，通过将数加一个偏移使其具有非负的表示形式，最小的负数为 $ 00..0002$，最大的正数为 $ 11...1112 $表示， 0一般使用$ 10...000_2 $ 表示，此时选择的偏移值为 $ 2^n - 1$.2.5 计算机中指令的表示
指令在计算机内部是以若干个或高或低的电信号的序列表示的，并且形式上和数的表示相同。实际上，指令的各个部分都可以看成一个独立的数，将这些数字拼接在一起就形成了指令。
几乎所有的指令都需要使用寄存器，所以必须有一套规定，以将寄存器名字映射成数字。在MIPS语言中，寄存器的映射可见下图：
字段（field）：机器指令可以分为若干字段。如下例程熙媛，，其中第一个字段和最后一个字段（ 0 和 32）组合起来告诉 MIPS 计算机该指令为加法运算，第二个字段表示加法的第一个源操作数寄存器号，第三个字段表示加法的另一个源操作数寄存器号。第四个字段表示存放运算结果的目的七寸其好。第五个字段在这条指令中没有用到，因此置 0..当然，这条指令也可以写成二进制形式。
指令格式（instruction format）：二进制数字段组成的指令表示的形式。从位的数目上来看， MIPS 指令占 32 位，与数据字的位数相等。为了遵循简单源于规整的原则，所有的MIPS指令都是 32位长。
机器语言（machine code）：在计算机系统中用于交流的二进制表示形式。其指令序列叫做机器码（machine code）。
十六进制（hexadecimal）：基数为 16 的数，为了避免读写冗长乏味的二进制字串，一般采用十六进制（它比二进制基数更大，并且易于转为为二进制）。可以简单地通过 每 4 位二进制数替换为 1 位十六进制数 来完成转换，反之亦然。顺便说明，在 C 和 Java 中，使用符号 0xnnnn 来表示 十六进制数字。
MIPS字段
为了使讨论变得简单，给 MIPS 字段命名如下：oprsrtrdshamtfunct6位5位5位5位5位6位
MIPS 中各字段的名称以及含义如下：op：指令的基本操作，通常被称作操作码（opcode），操作码：指令中用来表示操作和格式的字段。rs：第一个源操作数的寄存器。rt：第二个源操作数的寄存器。rd：用于存放操作结果的目的寄存器。shamt：位移量。funct：功能。一般被称作功能码（function code），用于指明 op 字段中操作的特定变式。
3.问题：当某条指令需要比上述字段更长的字段时，问题就会发生。例如，取字指令必须指定两个寄存器和一个常数，在上述各始终，如果地址使用其中的一个 5 位字段，那么取字指令的常数就被限制在 32 之内。而这个常数通常用来从数组或者数据结构中选择元素，所以它常常比 32 大的多。因此， 5 位字段因太小而用途不大。故此，所有指令长度相同 和 统一的指令格式 二者之间产生了矛盾。我们回头看硬件设计原则：优秀的设计需要适宜的折中方案。而 MIPS的设计者们选择了如下这种方案：保持所有的指令长度相同，但是不同类型的指令采用不同的指令格式。在上述表格的格式中，被称为 R型（用于寄存器）。而另外一种用于立即数的指令格式被称为 I型（立即数和数据传送指令用的就是这种格式），I型 的字段如下所示：oprsrtconstant or address6位5位5位16位
16 位的地址字段意味着取字指令可以取相对于基址寄存器地址 $\pm 2^{15} $或者 32768 个字节（$\pm 2^{13} $ 或 8192 个字）范围内的任意数据字。类似地，加立即数指令中常数也被限制不超过 $\pm 2^{15} $.可以看到，在这种格式下，很难设置 32 个以上的寄存器，因为 rs 和 rt 字段必须增加额外的位，这导致 32 位字长的指令很难满足要求。
上图展示了最近使用过的 MIPS 指令的每个字段的值，其中，“reg”代表寄存器的编号，“address”表示 16 位地址，“n.a.”（not applicable）表示这个字段在该指令格式中不出现。
定长指令的需求与设置尽可能多的寄存器的需求矛盾。寄存器数量任何增加都需要在指令格式中的各个寄存器字段中至少增加 1 位。总格考虑这些限制和越小越快的原则强臣环伺 ，当今大多数指令系统中有 16个或者 32 个通用寄存器。
当今计算机基于以下两个重要的准则构建：1. 指令用数的形式表示。2. 和数据一样，程序存储在存储器中，并且可以读写。这两个原则引出了存储程序（stored-program）的概念，这一发明释放了计算机的巨大潜力。指令可以表示成数的好处就是程序可以被当作二进制数字的文件发型。商业上的意义就是计算机可以沿用那些指令集兼容的现成软件。
2.6 逻辑操作
对字中由若干位组成的字段甚至对单个位进行操作是很有用的。因此，在编程语言和指令集体系结构中便增加了一些指令，用于简化对字中若干位进行打包或者拆包的操作。这些指令便是逻辑操作。
如下图，展示了C,Java金堂教育网 ,MIPS 中的逻辑操作。
移位（shift）：这个操作将一个字里面的所有位向左或向右移动，并在空出来的位置上添加零。例如：$ 0000~0000~0000~0000~0000~0000~0000~10012 =9{10} $，如果对它左移 4 位，那么得到的数值是$ 0000~0000~0000~0000~0000~0000~1001~00002 = 144{10}$与左移对应的是右移。这两条指令在 MIPS 中对应的是逻辑左移 sll 和逻辑右移 srl。我们重新看 R 指令格式，之前没有解释 shamt字段，它在移位指令中表示移位量（shift amount）。注：逻辑左移在数值上的意义是，每左移一位，其十进制数只边乘 2.
按位与（AND）：当两个操作数都为 1 时，经过AND 运算后才为 1.例如，$ 0000~0000~0000~0000~0000~1101~1100~0000 $ 和 $ 0000~0000~0000~0000~0011~1100~0000~0000~$ 得到的值是： $ 0000~0000~0000~0000~0000~1100~0000~0000 $AND 操作提供了一种将源操作数置零的能力。
按位或（OR）：当两个操作数其中有一个为 1 时，经过 OR 运算变成 1.
按位取反（NOT）：对于这个操作，它将位上的 0 变成 1，1 变成 0.
或非（NOR）：按位先或后非操作，仅当两个操作位均为 0 时结果才为 1.
MIPS也提供了 立即数与（andi）、立即数或（ori），但是没有提供NOR立即数版本。
异或（XOR）：当两个操作数对应位置不同时为1，相同时为 0.
2.7 决策指令
条件分支（copnditional branch）：该指令先比较两个值，然后根据比较的结果决定是否从程序中的一个新地址开始执行指令序列。 MIPS 中两条类似与 if 和 go to 语句功能的指令。
beq register1,register2,L1，该指令表示，如果register1 和 register2 中的数值相等，那么转到标签为 L1 的语句中执行。beq代表的是如果相等则分支（branch if equeal）.
bne register1,register2,L1，该指令表示，如果register1 和 register2 中的数值不相等，那么转到标签为 L1 的语句中执行。bnq代表的是如果不相等则分支（branch if not equeal）.2.7.1 循环
基本块（basic block）：没有分支（可能出现在末尾者除外）并且没有分支目标/分支标签（可能出现在开始者除外）的指令序列。
小于则置位（set on less than）：slt，比较两个寄存器的内容后，如果第一个寄存器小于第二个寄存器，那么将第三个寄存器置为 1.
MIPS编译器使用slt、slti、beq、bne和固定值 0 （总是可以通过读取寄存器$zero来获得）来创建所有的比较条件：相等，不等，小于，小于或等于，大于，大于或等于。由于遵循冯诺依曼关于设备简单性的原则，MIPS体系结构中并没有提供“小于则分支”的指令，因为这种指令过于复杂，它会延长时钟周期时间，或者增加平均执行每条指令的周期数（CPI）。
比较指令应该具有分清符号数和无符号数的能力。有时候二进制最高位为1 的数代表了一个负位，它当让应该小于所有最高有效位为0的整数。另一方面，如果是无符号数成奎安葬礼，那么最高位为1 的数将会大于所有最高有效位为0的数。因此，MIPS为这两种情况提供了两个版本的小于则置位的指令，slt 和 slti（set on less than immediate）指令用来处理有符号整数，而sltu（set on less than unsigned） 和sltiu（set on less than immediate unsigned）用来处理无符号整数。将有符号数作为无符号数来处理，是一种检验 $ 0 \le x < y $ 的低开销方法，常常用来检查数组的下标是否越界。问题的关键是 负数在二进制补码表示法中看起来项式无符号表示法中一个很大的数，温翠苹因为在无符号数中最高有效位是符号位，而在有符号数中最高有效位是具有最大权重的位。因此使用无符号比较 x < y，在检查 x 是否小于 y 的同时，也检查了 x 是否是一个负数。
2.7.2 case/switch语句
转移指令表（jump address table）：又称作转移表（jump table），将多个指令序列分支的地址编码为一张表。它是由一个代码中标签所对应地址构成的数组。
使用转移指令表的程序只需要索引该表即可以跳转到恰当的指令序列。程序跳转的时候首先将转移地址表中适当的项加载到寄存器中，然后使用寄存器中的地址值进行跳转。为了支持这种情况，像MIPS这样的计算机提供了寄存器跳转指令jr（jump register），用来无条件地跳转到寄存器的指定位置。
虽然在 C 或者 Java 这样的编程语言中有许多决策和循环语句，但是在指令集这一个层次上实现其功能的基本语句是条件分支。
2.8 计算机硬件对过程的支持
过程（procedure）：根据提供的参数执行一定任务的存储的子程序。它或者函数是程序员进行结构化编程的工具，二者均有助于提高程序的理解性和代码的可重用性。过程允许程序员每次只需将精力集中在任务的一部分，由于参数能传递数值并返回结果，因此参数承担过程与其他程序、数据之间接口的角色。过程是软件中实现抽象的一种方法。
在过程运行中，程序必须遵守以下 6 个步骤：
将参数放在过程可以访问的位置。
将控制转交给过程。
获得过程所需的存储资源。
执行需要的任务。
将结果的值放在调用程序可以访问的位置。
将控制返回初始点，因为一个过程可能由一个程序中的多个点调用。
由于寄存器是计算机中保存数据最快的位置，所以我们希望尽可能多的使用寄存器。MIPS 软件在为过程调用分配 32 个寄存器时遵循以下约定：
\$a0 ~ \$a3：用来传递参数的 4 个参数寄存器。
\$v0 ~ \$v1：用来返回值的两个值的寄存器。
\$ra：用来返回起始点的返回地址寄存器。 除了分配这些寄存器之外， MIPS汇编语言还包括一条过程调用指令：跳转到某一个地址的同时将下一个指令的地址保存在寄存器$ra中。这便是跳转和链接指令。
跳转和链接指令（jump-and-link instru）：跳转到某个地址的同时将下一个指令的地址保存在寄存器 \$ra中的指令。格式： jalProcedureAddress
返回地址（return address）：指向调用点的链接，是过程可以返回到合适的地址郑毅洁，在MIPS中它存储在寄存器\$ra中。返回地址是必须的，因为在同意过程中可能在程序的不同部分调用。
为了支持上述情况，类似 MIPS 的计算机使用寄存器跳转（jump rgister）指令jr，用于case语句，表示无条件跳转到寄存器指定的地址： jr $ra.
调用者（caller）：调用一个工成并未工成提供必要的参数值的程序。寄存器跳转指令跳转到存储在 \$ra 寄存器中的地址，调用者将参数值放到 \$a0 ~ \$a3,然后使用 jal X 跳转到过程 X（有时候称为被调用者）。
被调用者（callee）：根据调用者提供的参数执行一系列存储的指令，然后将控制权返回调用者的过程。被调用者执行计算桃运狂医 ，然后将结果放到 \$v0 和 \$v1 中，然后使用 jr \$ra 指令将控制返回给调用者。
程序计数器（program counter，PC）：PC 中包含在程序中正在被执行指令地址的寄存器。在程序存储概念中，使用一个寄存器来保存当前运行的指令地址是绝对有必要的。这个寄存器比较合理的名字应该是 指令地址寄存器，但是处于历史的原因，这个寄存器被称作 程序计数器，在MIPS体系结构中简写为 PC. jal 指令是将上将 PC + 4 保存在寄存器\$ra中，从而将链接指向下一条指令，为过程返回做好准备。
2.8.1 使用更多的寄存器
对于一个过程，假设编译器需要使用多余 4 个参数今存其和两个返回值寄存器。由于在任务完成之后必须消除痕迹，因此调用者使用的任何寄存器都必须恢复到过程调用前存储的值。这种情况下可以看成是需要将寄存器换出到存储器的一个例子。此时，我们引入栈的概念，因为它是换出寄存器的最理想的数据结构。
栈（stack）：被组织成后进先出队列形式并用于寄存器换出的数据结构。栈需要一个指针，以指向栈中最新分配的地址，以只是下一个过程放置换出寄存器的位置，或者是寄存器旧值的存放位置。
栈指针（stack pointer）：指示栈中最近分配得地址的值，它只是寄存器被换出的位置，或寄存器旧值得存放位置。在MIPS中，栈指针是寄存器 \$sp（29号寄存器）.栈指针是以字为单位进行调整。
两个最基本的操作：
压栈（push）：向栈中增加元素。
出栈（pop）：从栈中移出元素。
按照管理，栈“增长”是按照地址由高到低的顺序进行的。这意味着宋宇彬，数据压栈时，栈指针减小；数据出栈时，栈长度缩短，栈指针增大。2.8.2 嵌套过程
叶过程（leaf procedure)：不调用其他过程的过程。如果所有过程都是叶过程，那么情况就很简单美女宝典，但是实际并么如此谦君一发 。例如，假设主程序将参数 3 存入寄存器 \$a0，然后使用 jal A调用过程A，在使用过程A通过jal B调用过程 B，参数为 7，同样存入\$a0.由于A还没有结束任务，所以在寄存器 \$a0的使用上发生冲突。同样，在寄存器 \$ra 中保存的返回地址上也存在冲突，因为它现在保存着 B 的返回地址。我们需要采取措施阻止这类问题发生。一个解决方法时将其他所有必须保留的寄存器压栈，就像将保存寄存器压栈一样。调用者将所有调用后还需要的参数寄存器（\$a0 ~ \$a3）或临时寄存器（\$t0~\$t9）压栈。被调用者将返回地址寄存器\$ra 和被调用者使用的保存寄存器(\$s0 ~ \$s7）都压栈，栈指针\$sp随着栈中寄存器的个数而调整。到返回时，寄存器会从存储器中回复，栈指针也重新调整。
全局指针（global pointer）：指向静态数据区的保留寄存器。C语言中的一个变量通常对应存储中的一个位置，其解释取决于其类型（type）和存储方式（storage class）。例如整型和字符型。C语言包括两种存储方式：动态的（automatic）和静态的（static）。动态变量位于过程中，退出过程时失效。静态变量在进入和退出过程时始终存在。在所有过程之外声明的 C 变量，以及声明时候使用的关键字 static 的变量都被视作静态的，其余的变量都被视作动态的。为了简化静态数据的访问，MIPS 软件保留了一个寄存器，这便是全局指针亲亲八宝粥。即 \$gp.
保留|不保留|---|---|---|保存寄存器：\$s0 ~ \$s7|临时寄存器：\$t0 ~ \$t9|栈指针寄存器：\$sp|参数寄存器：\$a0 ~ \$a3|返回地址寄存器：\$ra|返回值寄存器：\$v0 ~ \$v1|栈指针以上的栈|栈指针以下的栈|2.8.3 在栈中为新数据分配空间
栈的最后一点复杂性在于栈还需要存储过程的局部变量，但是这些变量不适合于寄存器，例如局部的数组或者结构体。
过程帧（procedure frame）：也称作活动记录，栈中包含过程所保存的寄存器以及局部变量的片段。上图显示了过程调用之前，之中和之后栈的状态。帧指针\$fp指向该帧的第一个字（一般是保存的参数寄存器），而栈指针\$sp指向栈顶。栈可调整为由足够的空间来容纳所有的保存寄存器和驻留内存的局部变量，因为在程序运行期间栈指针可能发生改变，所以对于程序员而言，虽然使用栈指针和少量的地址运算就可能完成对变量的引用，但是使用固定的帧指针引用变量会更加简单。如果在一个过程中栈内没有局部变量，编译器将可以不设置和不hui恢复帧指针以节省时间。当使用帧指针时，在调用中使用 \$sp的地址进行初始化，而\$sp可以使用\$fp来恢复。
帧指针（frame pointer，\$fp）：指向给定过程中保存的寄存器和局部变量的值。某些MIPS软件使用帧指针指向过程帧的第一个字。在过程中，栈指针可能发生改变，因此存储器中对于局部变量的引用在过程中的不同位置可能具有不同的偏移量，跑男嘉宾这时的过程更加难以理解。可另外一种方法是，帧指针在一个过程中为局部存储器引用提供一个固定的基址寄存器。注意，无论是否使用显示的帧指针，活动记录都出现咋栈中。我们通过避免在过程中修改\$sp来避免使用\$fp.
2.8.4 在堆中为新数据分配空间
除了动态变量对于过程是局部有效之外，C程序员还需要再内存中为静态变量和动态数据结构提供空间，如下图，给出了MIPS分配内存的约定：栈由内存高端开始向下增长。内存低端的第一部分是保留的。之后是MIPS机器代码的第一部分，通常称为代码段（text segment）。代码段之上的代码为静态数据段（static data segment），是存储常量和其他静态变量的空间。尽管数组通常具有固定长度因而能和静态数据段很好的匹配，但是类似链表这样的数据结构通常会再生命期内增加或者缩短。这类数据结构对应的段习惯上称为堆（heap），一般再存储器中放在静态数据段之后，注意，这种分配允许栈和堆相互增长我的女鬼老婆，从而再两个段此消彼长的过程中达到内存的高效使用。
C语言通过显式的函数调用再堆上分配ta和释放空间。malloc() 再堆上分配空间并指向它的指针，free() 释放指针指向的堆空间。内存分配由 C 程序控制，这是很多错误产生的根源。忘记释放空间会导致“内存泄漏”，它会逐渐耗尽大量内存以至于操作系统可能崩溃。过早释放空间会导致“悬摆指针”(dangling pointer)，这会造成指针指向程序不想访问的位置。在Java中使用自动的内存分配和无用单元回收机制来放置类似的错误发生。
MIPS汇编语言的寄存器约定。这种约定是加速大概率事件的另外一个例子。使用 4 个参数、2个寄存器用于返回结果、保存 8 个寄存器、10个暂存器对于大多数过程调用来说是足够的。在上图中 \$at 寄存器 1 被汇编器保留。\$k0~\$k1寄存器 26~27 被操作系统保留。
如果参数多于 4 个怎么办？MIPS约定将额外的参数放到栈中帧指针的上方。这样，过程从寄存器\$a0 到 \$a3中获得前 4 个参数，通过帧指针在内存中寻址获得其余参数。
帧指针的方便性在于对于过程中所有栈内的变量引用都具有相同的偏移。然而，帧指针并不是不许的。GNU MIPS C 编译器使用帧指针，而来自 MIPS 的C 编译器就没有使用，它将寄存器 30 用作于另一个保存的寄存器。
一些递归过程可以使用迭代的方式来实现。通过消除过程调用的相关开销，迭代可以显著提升性能。例如，考虑以下求和过程
考虑过程调用sum(3,0)。这会递归调用sum(2,3)，sum(1,5)，sum(0,6),然后将结果 6 进行 4 次返回操作。这种求和的递归调用称作尾调用（tail call），然而这个例子可以使用尾迭代（tail recursion）来高效地实现。
\\假设$a0 = n.$a1=acc;
sum:
slti $t0,$a0,1
bne $t0,$zero,sum_exit
add $a1,$a1,$a0
addi $a0,$a0,-1
j sum
sum_exit:
add $v0,$a1,$zero
jr $ra
int sum( int n,int acc){
if(n>0)
reuturn sum( n-1, acc + n);
else
return acc;
}2.9 人机交互
ASCII，使用 8 位的字节来表示字符。
可以使用一系列指令从一个字中提取出一个字节，所以字的读取和存储同样可以完成对字节的传输。在有些程序中，对文本的操作十分普遍，所以MIPS还提供了字节传输指令， 字节读取 lb (load byte)指令从内存中读出一个字节，并将其放在一个寄存器最右边的 8 位。 字节存储 sb (store byte)指令把一个寄存器最右边的 8 位取出来然后写道内存中。
三种表示字符串的方法。 字符通常被组合为字符数目可变的字符串，方法有三种：
保留字符串的第一个位置用于给出字符串的长度。
附加一个带有字符串长度变量。例如在结构体中。
字符串最后的位置用一个字符来标志其结尾。C语言选择在尾部添加 结束符\0.
MIPS指令集包含显式的读取和存储 16位 半字（halfword）的指令。 读取半字指令lh（load half）从存储器中读出一个半字，然后将其放在存储器的最右边 16位。lg也将半字看作有符号数并进行符号扩展，以填充寄存器左侧的16位。 无符号读取半字指令lhu（load halfword unsigned）将半字视作无符号数，与lh相比，这条指令更加常用。 存储半字指令sh（store half）将寄存器最右边的 16 位写入存储器。
MIPS 软件试图保持栈和字地址的对齐，这就允许程序总是使用lw和sw（要求必须是对齐的）来访问栈。这一约定意味着一个char类型变量在栈中被分配 4个字节，尽管它并需要这枚都。然而，一个C字符串变量或者一个字节数组会把每 4 个字节压缩成一个字，而一个Java字符串变量或者short类型数组会把每 2 个半字压缩成一个字。
为了反应web的全球性特征，当今的大部分web页面采用Unicode，而不是ASCII.2.10 MIPS中 32 位立即数和寻址2.10.1 32位立即数
尽管常数往往比较短而且适用于 16 位字段，但有时它们会非常大，MIPS指令集中的 读取立即数高位指令lui （load upper immediate）专门用于设置寄存器中常数的高 16 位，允许后续指令设置常数的低 16位。
编译器或汇编程序必须把大的常数分解为若干个小的常数，然后再合并到一个寄存器中。立即数字段大小的限制，无论是再取/存数指令中对存储器的地址还是在立即数指令中对长度都可能带来问题。若果这项工作由汇编程序来做，例如MIPS软件，那么汇编程序必须有一个可用的临时寄存器来创建长整数值佶天鸿 。这便是汇编程序保留 \$at 寄存器的一个原因。
2.10.2 分支和跳转中的寻址
MIPS跳转指令寻址采用最简单的寻址方式。它们使用最后一种 MIPS 指令格式，称为 J 型。J型除了 6 位操作码之外，其余位都是地址字段。所以 j10000可以汇编位下面格式其中跳转操作码的值位 2，跳转地址为10000.和跳转指令不同，条件分支指令除了规定分支地址之外还必须规定两个操作数，因此 bne $s0,$s1,Exit 被汇编为下面的指令，只保留了 16 位用于指定分支地址。如果让程序地址适应该 16 位字段，则意味着任何程序都不可以大于 $ 2^{16}$,在今天看来，这太小了，因此这是一种很不现实的选择。另一种可选择的办法是制定一个总是添加到分支地址上的寄存器，这样指令分支的地址可按照如下方式计算。程序计数器 = 寄存器 + 分支地址这个求和的结果允许程序的大小达到 $ 2^{32}$，并且依然可以使用条件分支，从而解决了分支地址大小的问题。但是随之而来的问题便是，应该使用哪个寄存器呢？答案取决于条件分支是如何使用的。条件分支在循环和if语句中都可以找到黄乃扬 ，它们倾向于转到附近的指令。例如，在SPEC基准测试中，大概一半条件分支的跳转距离小于 16条指令。因为程序计数器中包含当前指令的地址乐圣是谁，如果我们使用PC作为增加地址的寄存器，我们可以转移到举例当前指令距离为$ \pm2^{15} $ 个字的地方。几乎所有的循环和if语句都远远小于 $2^{16}$个字，因此PC是一个比较理想的选择。这种分支寻址形式称为PC相对寻址。
PC相对寻址(PC-relative addressing)：一种寻址方式，它将 PC和指令中的常数相加作为寻址结果。
MIPS 对所有条件分支使用PC相对寻址，因为这些指令的跳转目标一般都比较接近其分支地址。另外一方面，跳转连接指令并非总是靠近调用者的过程，所以它们通常使用其他调用方式。因此，MIPS体系结果通过使用跳转和跳转链接指令的J型格式来为过程调用提供长地址。因为所有MIPS指令都是 4 字节长，所以 PC相对寻址时所加的地址被设计为字地址而不是字节地址，相对于 16 位的字节地址，16位的字地址跳转范围扩大了 4 倍。同样，跳转指令的 26 位字段也是字地址，它可以表示 28 位的字节地址。
因为PC 是 32 位的，所以有 4 位必须来自于跳转指令之外的其他地方。MIPS跳转指令仅仅是代替PC的低 28 位，而高 4位保持不变。
大多数条件分支都会转移到一个附近的位置，但有时也会转移很远，距离超过条件分支指令的16位可以表示的范围。汇编器的解决方法：插入一个跳转到目标分支的无条件跳转，并将条件取反以便由分支决定是否跳过该无条件跳转指令。
2.10.3 MIPS寻址模式总结
寻址模式（addressing mode）：根据对操作数和/或地址的使用不同加以区分的多种寻址方式中的一种。
立即数寻址（immediate addressing）：操作数是位于指令自身中的常数。
寄存器寻址（register addressing）：操作数是寄存器。
基址寻址（base addressing)：又称为偏移寻址（displacement addressing），操作数在内存中，其地址是指令中基址寄存器和常数的和。
PC相对寻址（PC-relative addressing）：地址是PC和指令中常数的和。
伪直接寻址（pseudodirect addressing)：跳转指令由指令中 26 位字段和PC高位相连而成。
虽然MIPS系统结构按照 32位地址描述，但是几乎所有的微处理器（包括MIPS）都可以进行 64位扩展。这些扩展主要针对大型程序的需要。2.10.4 机器语言解码
2.11 并行与指令：同步
数据竞争（data race）：假如来自不同线程的两个方寸请求访问同一个地址，它们连续出现，并且至少一个是写操作，那么这两个存储访问性成数据竞争。当任务之间相互独立的时候，任务的并行执行是比较容易实现的。但是往往人物之间互相协作，这种协作通常意味着某些任务的结果是其他任务需要读取的值。这时候执行读任务的一方就需要直到写任务的一方什么时候完成了写操作，此时可以安全地读数据，否则便发生数据竞争，导致读数据出错而引起运行结果的改变。
在计算机中，同步机制要依赖硬件提供的同步指令，这些指令可以由用户调用。我们讨论加锁（lock）和解锁（unlock）同步操作的实现。采用枷锁和解锁可以直接创建一个仅允许单个处理器操作的区域，叫做互斥（mutual exclusion）区。更复杂的同步机制实现方式也是类似。
在多处理器实现同步需要一组硬件原语，提供对存储的单元进行原子读和原子写的操作，使得在进行存储器原子读和原子写操作时候任何其他操作不得插入。硬件原语十分重要，如果没有它，同步机制花费的代价特别高。
建立基本的原语有若干可选的方案，并且这些方案都可以实现原子读和原子写的操作，并可以用某种方法表示这些操作是否为原子操作。通常，体系结构设计人员并不希望基本硬件原语被用户使用，而是希望原语被系统程序员来建立同步库。
如何建立基本的同步机制？我们使用原子交换原语（atomic exchange或atomic swap），这个原语是将寄存器中的一个值和存储器中的一个值互相交换。假定使用存储器中某个单元来表示一个锁变量：数值0表示解锁，数值1表示加锁。一个处理器尝试对锁单元进行枷锁，方法是用一个寄存器中的1与该锁单元的值进行交换。交换后锁单元的值为1，返回值（锁单元的原值）如果是1，表明这个锁已经被其他的处理器占用，返回值0表明锁是自由的，尝试枷锁成功。此时锁单元的值为1，可以防止其他的处理器来占用。假如考虑有两个处理器同时尝试进行交换操作，它们的竞争关系就会遭到破坏，因为其中只有一个处理器先执行交换操作，并返回值0，那么第二个处理器执行完交换操作时返回值便变为1.用交换原语实现同步的关键在于操作的原子性：交换操作是不可分割的，并且由硬件对两个同时执行的交换操作进行排序。有可能两个处理器同时尝试置位同步变量，但是这两个处理器认为它们同时成功设置同步变量是不可能的。
实现单个额原子存储器操作给处理器的设计者带了很大挑战性，因为这要求存储器的读写操作都是单条不可被中断打断的指令完成的。一种可行的方法是采用指令对，其中第二条指令返回一个表明这对原子执行的标志值。假如处理器的操作都是在这对指令之后或者之前执行，这对指令就是原子的。因此，当一个指令对是原子的，没有哪个处理器能改变两个指令执行之间的数据值。
在MIPS处理器中之一对包括一条叫做链接取数（load linked）的特殊取数指令和一条叫做条件存数（store conditional）的特殊存数指令。顺序使用这两条指令：如果链接取数指令所指的锁单元的内容在相同地址的条件存数指令执行之前就已被改变，那么从条件存数指令就执行失败。我们定义条件存数指令完成以下功能：保存寄存器的值园山风景区，并且如果执行成功则将寄存器的值修改为1，失败则修改为0.因为链接取数指令返回锁单元的初始值，条件存数指令执行成功时候才返回1。链接取数-条件存数机制的优点是：可以通过它们来构造其他的诸如原子比较和交换或者原子取后加等同不愿意。
单处理器中原子操作也很有用。
2.12 翻译并执行程序
2.12.1 编译器
汇编语言（assembly language）：一种符号语言，可以被翻译为二进制语言。 编译器可以将C语言程序转换为汇编语言程序。2.12.2 汇编器
伪指令（pseudoinstruction）：汇编语言指令的一种变种，通常被看作一条汇编指令。因为汇编语言对于高层次软件是一个接口，所以汇编器也可以处理一些机器语言指令的常见变种。硬件不需要实现这些指令，然而他们在汇编语言中的存在简化了程序转换和编程。
MIPS汇编器使用16进制。这个特性十分方便。
汇编器将汇编语言转换成为目标文件（object file），它包括机器语言指令、数据和指令正确放入内存中所需要的信息。
符号表（symbol table）：一个用来匹配标记名和指令所在内存字的地址得列表。为了产生汇编语言程序中每条指令对应的二进制表示，汇编器必须处理所有标号对应的地址。
2.12.3 链接器
到目前为止，我们描述的内容表明，对于源程序任意一行代码的修改都需要重新编译和汇编整个程序。这无疑是非常浪费的，一种方法是单独编译和汇编每个过程，使得某一行代码的改变只需要编译和汇编一个过程。
链接器（linker）：又称作链接编辑器。它是一个系统程序，用来把各个独立汇编的机器语言组合起来并解决所有未定义的标记，最后生成可执行文件。链接器的工作分为三个步骤：1. 将代码和数据模块象征性地放入内存。2. 决定数据和指令标签的地址。3. 修补内部和外部的引用。
链接器使用每个目标模块中的重定位信息和符号表，来解析所有未定义的标签。这种引用发生在分支指令、跳转指令和数据寻址处，所以这个程序的工作就非常像一个编辑器：它寻找所有旧地址并用新的地址取代它们。
可执行文件（executable file）：它可以在一台计算机上运行。通常，这个文件与目标文件具有相同的格式，但是它不包含未解决的引用。
2.12.4 加载器
加载器（loader）：把目标程序装在到内存中以准备运行的系统程序。2.12.5 动态链接库
动态链接库（dynamicaly linked library，DLL）：在程序执行过程中才被链接的库例程。