【梳理】计算机组成与设计 第2章 指令（内附文档高清截图）
配套教材：
Computer Organization and Design: The Hardware / Software Interface (5th Edition)
这是专业必修课《计算机组成原理》的复习指引。建议将本复习指导与博客中的《简明操作系统原理》配合复习。
在本文的最后附有复习指导的高清截图。需要掌握的概念在文档截图中以蓝色标识，并用可读性更好的字体显示 Linux 命令和代码。代码部分语法高亮。
计算机组成原理不是语言课，本复习指导对用到的编程语言的语法的讲解也不会很细致。如果不知道代码中的一些关键字、指令或函数的具体用法，你应该自行查找相关资料。
第二章 指令
1、指令集（instruction set）包含了芯片支持的全部指令。
指令相当于计算机语言的词库。但是计算机语言不像不同国家的语言那样区别那么大，它们更像一个国家的不同地区的方言。如果你掌握了一门编程语言或者一种ISA的指令，那么掌握其它编程语言或其它ISA的指令的难度就要降低很多。
2、MIPS是最早商用的指令集，始于1980年代。ARMv7指令集和MIPS比较接近，是广泛应用的指令集之一。ARMv8诞生于2013年，是ARMv7的64位版本。但ARMv8似乎同样更接近MIPS而不是ARMv7。
获得了ARM公司的授权的合作伙伴在2019Q4总共出货了大约64亿颗ARM芯片，其中约42亿芯片是Cortex-M系列微控制器。微控制器广泛应用于嵌入式市场和消费级产品。ARM授权给其它公司的常见芯片设计主要分为Cortex-A、Cortex-R和Cortex-M三个系列（ARM自己不直接销售芯片，而是将设计的架构和指令集授权给其它公司使用或改进，并将芯片成品出售）。它们的指令集有些许不同，采用ARMv7指令集的分别称为ARMv7-A、ARMv7-R和ARMv7-M，采用ARMv8指令集的分别称为ARMv8-A、ARMv8-R、ARMv8-M。一些服务器CPU也开始使用ARMv8指令集。2020年5月，ARM还推出了Cortex-X系列，首个CPU设计为Cortex-X1。
高通的Krait、Kryo架构和三星的Mongoose，NVIDIA的Denver、Carmel，以及苹果的Swift、Cyclone、Typhoon、Twister、Hurricane、Monsoon / Mistral、Vortex / Tempest，Lightning / Thunder都是基于ARM指令集自主研发的CPU架构。
龙芯是中国科学院计算技术研究所研发的基于MIPS指令集的CPU。飞腾CPU则由国防科技大学计算机学院研制，原先基于SPARC，后续产品则基于ARMv8指令集，现服役于“天河”系列超级计算机。申威CPU由总参谋部第五十六研究所（江南计算技术研究所）研制，其“申威64”指令集来源于DEC Alpha 21164，现服役于“神威”系列超级计算机。
Intel / AMD的x86 CPU则具有x86指令集，它也是一系列指令集的集合。x86指令集及具备x86指令集的CPU主要应用于PC、工作站、服务器和超级计算机。
3、许多指令集具有不能忽略的相似性，因为所有的计算机基于的底层硬件技术和原理都很接近；最基本的操作，如算术运算、移位、逻辑运算、数据传输（如：读写）、控制（调用、跳转、……）等指令，也是所有计算机都必须支持的。例如，一个MIPS CPU支持的部分汇编指令和操作数如下：
计算机中，大多数指令都是无操作数（operand）（参与一个运算（操作，operation）的元素个数）、一个操作数、两个操作数或三个操作数的指令（一些指令集中的指令支持更多的操作数），而不是可变的。理由很简单：如果把指令设计成支持可变数量操作数的，那么硬件实现就很复杂。
基于这点事实，我们引出设计的第一个原则：规整的设计更简单。
4、Java、Python、Perl、SQL等语言使用解释器（interpreter）。Java解释器将Java语句解释为字节码（bytecode），字节码再被转换为机器指令。采用解释器的语言对跨平台（跨操作系统）的支持通常更好。
5、汇编指令是直接对应机器语言的低级指令。高级语言对操作数的数量没有限制，但汇编指令有。操作数保存在内存中或寄存器（register）中。寄存器是用于临时存储操作数（包括运算结果）的部件。寄存器的速度要快于高速缓存，但非常昂贵，因此数量很少。8086的寄存器是16位的，MIPS32 CPU的寄存器是32位的，MIPS64 CPU的寄存器是64位的。MMX指令集用到的寄存器有8个，长度为64位：mm0到mm7，都是浮点单元（Float point unit，FPU）的80位寄存器的低64位。SSE指令集中的指令专用的寄存器包括8个128位的xmm0到xmm7，x86-64还有额外的8个寄存器xmm8到xmm15。此外还有一个32位的控制 / 状态寄存器。AVX指令集使用的寄存器则是128位的xmm0到xmm15（x86-64模式下还有xmm16到xmm31）。AVX2指令集将操作数的宽度扩展到了256位，寄存器代号从ymm0到ymm15（x86-64模式下还有ymm16到ymm31），并可以输入后缀相同的xmm寄存器来取得低128位。AVX-512指令集将操作数的宽度进一步扩展到了512位，在x86-64下，寄存器代号从zmm0到zmm31，并可以输入后缀相同的xmm、ymm寄存器来分别取得低256位、低128位。
一个字（Word）通常是16位的。但在MIPS CPU中，一个字的长度是32位。
6、设计的第二个原则：更小的部件更快。如果把寄存器做得很多、缓存做得很大，那么它们的速度就会变慢。因为很多时候电信号要传递更远的距离。当然，这个并不是绝对的。例如MIPS CPU中，如果寄存器的总数是31个而不是32个，那么性能未必更好。
7、寄存器的数量实在太少，因此无法保存较多的数据或较复杂的数据结构。于是这些数据被保存在内存中。所有的CPU都包含数据传输指令（数据传送指令、数据搬移指令），用于在内存与寄存器之间搬运数据。如果需要访问内存中的内容，那么指令的其中一个操作数就需要是内存地址（address）。地址刻画了数据在内存中的位置。内存可以看成一个很大的一维数组，地址从0开始编号，并且每个字节的地址可以看成这个数组的下标。
8、把数据从内存读入寄存器的指令，称为读取（加载、装入，load）指令。Load指令的操作数自然是寄存器和内存地址。在MIPS架构的CPU中，任何变量的起始地址必须是4的倍数。这称为内存对齐（memory alignment）。如果尝试访问没有对齐的数据，会报错。x86架构则支持非对齐访问其实现机制是将非对齐访问指令拆分成多条指令执行，结合拼接（或者拆分）指令获取数据。缺点是牺牲性能。ARMv5不支持非对齐访问，ARMv6的部分指令支持，而ARMv7、ARMv8架构的对齐检查可以手动开启或关闭。如果使能（启用）对齐检查，那么任何指令的非对齐访问均会触发非对齐异常（exception）。注意：采用ARMv8指令集的CPU中，A64指令集的部分指令的非对齐访问在关闭对齐检查的情况下仍然会产生非对齐异常。也可以用软件等效实现非对齐访问，但会降低性能。
在编译时，可以通过调整编译选项来启用或关闭非对齐访问。
把数据从寄存器写入内存的指令，称为存储（store）指令。MIPS的Load / Store（L / S）指令一次只读一个数据、写一个数据，不进行运算。进行算术（arithmetic）时，一般都在寄存器中进行，使得运算更快。
9、内存中的数据有大端（big endian）和小端（little endian）两种读写模式。采用哪种模式是CPU架构决定的。MIPS是大端阵营的，一个变量的高位保存在低地址中，低位保存在高地址中；小端模式则相反。大端和小端分别也称“高尾端”和“低尾端”，其含义很清晰：大端即高尾端，意味着变量的末尾比变量的头部的地址更高；小端则相反。x86 CPU一般采用小端，IBM、Sun的CPU（SPARC）一般采用大端。有的CPU既能工作于小端也能工作于大端，如ARM、Alpha、Power PC。
10、编译器负责将最常用的变量保存到寄存器中。为了使寄存器尽可能提升性能，编译器需要正确利用寄存器，而且寄存器的数量不能太少也不能太多。许多ISA都包含16个或32个通用寄存器，以及其它一些专用的寄存器。
11、立即数（immediate operand，或immediate）是常量或表达式的结果。汇编器在将汇编语言转换为机器语言时，将立即数编码到指令中，这样就避免了执行包含立即数的指令时总是要从内存中读取常量。
12、现代计算机一律采用二进制。事实上，最早的商用计算机是进行十进制计算的，但是效率很低。因此，后来的计算机全部采用二进制进行运算，只在输入、输出时根据需要进行二进制与十进制的互相转换。
13、以前的计算机采用额外的位来记录符号位（sign bit），这导致运算的时候要额外花费一步来设置符号位，而且还会出现正0和负0，导致一些问题。后来，经过大量的研究，最终将内置类型中的最高位指定为符号位，0为正，1为负。于是一个int型的数据的取值范围是这样的：
这种表示法叫做二补数（two’s complement）表示法。一个n位的二进制无符号数x与其按位取反的数~x的和是2n。也就是说x的二补数是2n – x。类似地，有一补数（one’s complement）表示法：一个数x的一补数是x（代表按位取非，见第19点），即2n – x – 1。对一个32位的有符号数，如果用一补数表示法，那么0x80000000到0xFFFFFFFF表示-2147483647到-0。如果把数采用一补数表示法表示，那么需要多花费一步来减一个数。如果采用二补数表示法表示数，不但不需要多花费这一步，还可以把加减法统一按加法运算，提升性能。所以二补数表示法很快成为当今全部计算机采用的表示法。
硬件在判断一个数是否为负时，只需要读取最高位（符号位）。
以int型数据为例，一个数x = x31x30x29…x1x0可以表示成：
有符号数取相反数的公式是：–x = ~x + 1。
14、溢出（overflow）是指运算结果（无论是中间结果还是最后结果）的绝对值部分大于字长能表示的最大绝对值的现象。两个正数相加，结果大于机器的字长能表示的最大正数，称为正溢。两个负数相加，结果小于机器的字长能表示的最大负数，称为负溢。
15、将字节数更少的变量读入寄存器时，高位要填充。对无符号数，直接填零。对有符号数，则进行带符号扩展（sign extension）。在C / C++中，进行类型转换（cast）时也是如此。一个有符号数转为占用字节数更多的数，则高位填充原数的符号位。字节数较少的有符号数转换为字节数较多的有符号数时，值不变；但是不同字节数的有符号数和无符号数互相转换时，数值就可能发生改变了。不过，当变量或常量表示地址（即变量为指针）时，没有符号位。地址总是非负的。
16、指令是具有一定的规范的，称为指令格式（instruction format）。MIPS的每条指令都是32位长，而x86的指令是变长的，平均长度约3个字节。这些指令是从汇编指令转换来的，对应的语言称为机器语言（machine language）。一长串这样的机器指令，也叫机器码（machine code）。
17、设计原则3：好的设计要求好的折中。
MIPS的32位机器指令分成了6个区域：
op：操作码，指定了操作的种类（如：加法）。
rs：第一个操作数（寄存器）。
rt：第二个操作数（寄存器）。
rd：目标操作数（寄存器）。
shamt：移位数量（这个区域不常用）。
funct：函数（函数码），选择操作码对应的操作的变体。
到这里大家可以看出来，一个操作数只有5个bit，也就是说只能表示32种数。想表示更多的数的时候怎么办呢？MIPS的设计者们又设计了另外一种格式（I-type或I-format，I = immediate），区别于上述格式（R-type或R-format，R = register）：
这种格式的指令可以表示-32768到32767这65536（216）个常数（立即数），也可以表示该范围内的偏移地址。
虽然支持多种指令格式会使得硬件变得复杂，但是这两种格式的很多地方是相近的，比如前3个区域的功能和边界都一样，I型的最后一个区域的长度正好是R型的后三个区域的长度，所以实际上没有增加太多的复杂度。至于采用哪种格式，则由第一个区域的操作码决定。
18、逻辑运算是所有计算机必须支持的运算。部分C、Java的运算符与MIPS指令的对应关系如下表：
第一种逻辑运算是位移（shift）。位移分为左移（left shift，shift left）和右移（right shift，shift right）两种。左移把所有二进制位向左移动若干位，低位补零。如果数据类型是定长的，那么超出范围的高位自动丢失。右移把所有二进制位向右移动若干位，越过最低位的部分自动丢失。位移分为逻辑位移（logical shift）和算术位移（arithmetic shift）两种。逻辑左移和算术左移的规则是一样的；逻辑右移把空出的高位补0，算术位移把空出的高位补符号位。
MIPS的逻辑左移和逻辑右移指令分别是sll（shift left logical）和srl（shift right logical）。以左移指令为例：
sll s0,4 # reg $t2 = reg $s0 << 4 bits
将其转换为机器指令是这样的：
shamt存放了位移位数。rs区域无意义。
向左位移一位，相当于把原数乘以2；向右位移一位，相当于把原数除以2（整除）。类比一下：把十进制数左移一位相当于乘以10；把十进制数右移一位相当于除以10（整除）。
19、AND或&运算符称为按位与。如果这些运算符所在的段落采用拉丁字母（英文字母）书写，那么把这些运算符大写，以免与英文连词混淆。AND对两个位数相同的数做运算，只有两个数对应的位都为1时，结果的这一位才为1：
AND可以用两个数强制把指定的位设为0，因此有时候把其中一个操作数称为mask：mask“隐藏”了一些值为1的位。
注意：如果将两个位数不同的数做逻辑运算，那么位数较少的数的高位自动补0直到位数相同（无符号扩展，也称零扩展（zero extension）），而不作带符号扩展（sign extension）。
OR或|运算符称为按位或。类似地，两个位数相同的数，对应的位只要有一个为1，那么结果的对应位就为1。
NOT或~运算符是一元的，称为按位非（按位反、按位取反）。输入一个数，结果中对应的位与这个数中对应的位取值相反（0变1或1变0）。
XOR（exclusive or）或^运算符称为按位异或。输入两个位数相同的数，只有输入的两数的对应位不同时，结果的对应位才为1。
20、所有的计算机及计算机语言都支持if条件语句。MIPS中，if语句对应的汇编指令可能是：beq、bne，等等。两个指令分别表示branch if equal、branch if not equal。类似地，x86汇编中也有je jne jb ja jnb jna jbe jae jnbe jnae jg jng jge jnge jl jnl jle jnle等指令。其中b = below（无符号小于），a = above（无符号大于），n = not，e = equal，j = jump，g = greater（有符号大于），l = less（有符号小于）。这些语句称为条件分支（conditional branch），用于判断输入并根据输入情况执行指定语句。
条件分支的指令格式是I型的。后16个bit存储的是条件满足时跳转到的偏移地址（offset address）。基本上，所有的条件语句需要跳转的位置都离当前指令不太远，所以16个bit一般足够。MIPS的每个数据的内存地址都按4的整数倍对齐，所以这16个bit可以覆盖的跳转范围实际上达到218。
21、一个基本块（basic block）是一段没有分支（除了结束时）、没有标号（除了开始时）的汇编语句。编译的一个早期步骤就是要把程序分成若干个基本块。
22、slt s3,$s4 # $t0 = 1 if $s3 < zero来实现全部条件语句中的比较符号。MIPS并没有branch on less than指令，因为实现太复杂，而且势必增加时钟周期的长度（指令太慢），否则一条指令就需要额外的周期来执行（单条指令耗费的周期数必须是整数）。
比较指令必须支持有符号数的比较与无符号数的比较。slt、slti具有针对无符号数比较的变体sltu、sltiu。
23、很多计算机语言除了支持if-else语句以外还支持switch-case语句。实现switch-case语句的一个最简单的办法是把它们转换成if-else语句。但还有一个更高效的方法：构造跳转地址表（jump address table），也称跳转表（jump table）。跳转表是一个线性表，里面保存了一系列地址，地址与汇编语言中的标号（label）对应。程序把对应的地址读入寄存器，在跳转的时候，就跳至寄存器保存的地址。MIPS中的jr指令代表jump register，代表无条件跳转至寄存器指定的地址。
24、过程（procedure）是程序中的一段具有特定用途的子程序，根据参数来执行。有的编程语言把过程也视作函数（function）。过程的引入使得编程变得结构化，并允许程序员在一段时间内把精力集中在程序中的范围更小的部分或特定的层次，减小出错几率，增加方便程度和程序的可读性。
简单来讲，执行一个过程的步骤有6步：
（1）把参数放到过程可以访问的位置（压入栈中）。
（2）把控制权移交给过程。
（3）请求获得执行过程需要的资源。
（4）开始执行。
（5）把返回值放到调用该过程的程序可以访问的位置（压入栈或放入寄存器）。
（6）把控制权交回调用该过程的程序。
MIPS用四个寄存器a3传递参数，两个寄存器v1保存返回值，并用寄存器$ra保存返回地址（return address，指向调用过程的指令的下一条指令或该指令本身）。MIPS用指令jal调用一个过程。jal代表jump-and-link。link指的是把返回地址与过程关联起来。
25、程序计数器（program counter，PC），或者把这个历史遗留的名称换成指令地址寄存器（instruction address register），一般指向下一条要执行的指令在内存中的位置（机器指令是保存在内存中的）。
26、在执行完过程以后，我们当然希望从调用过程之前的进度开始继续执行。于是计算机引入了一个常用的数据结构——栈（stack）。栈是一种先进后出（last-in-first-out，LIFO）的数据结构，后被入栈（压栈，push）的数据比后被先入栈的数据先出栈（pop）。栈指针（stack pointer）总是指向栈顶，即指向最后入栈的元素。由于历史原因，栈总是从高地址向低地址生长（扩大）。也就是说当往栈中压入数据时，栈指针的地址减小（向0x0方向，0x为十六进制前缀）。在执行一个过程之前，需要把执行过程用到的寄存器原有的值压入栈中，执行完毕后再恢复，于是程序得以从已有进度继续。当参数较多以至于寄存器不能全部放下时，剩余的参数就会放到栈中。
27、有的过程在执行中还会调用其它过程，甚至调用它自己，称为递归（recursion）。为了使各个过程都能正确返回，在过程里调用过程时，同样要保存现场，也就是把被调用的过程需要用到的寄存器原有的值先压入栈中，等这个深层的过程返回了，再恢复这些寄存器的值，继续执行本层的过程。这些被保存的全体变量合成一个过程帧（procedure frame），也称栈帧（stack frame）、活动记录（activation record）。帧指针（frame pointer）指向一个过程保存在栈中的栈帧的第一个字。MIPS的帧指针保存在寄存器$fp中，而x86的帧指针是bp、ebp、rbp（16位 / 32位 / 64位下）。BP = base pointer。栈指针在过程的执行中可能会变化（新建局部变量（本地变量，local variable，也称自动变量（automatic variable））、调用另外的过程），而新的栈帧被压入栈时，这个栈帧保存了上一个栈帧的帧指针。从深层的过程返回后，这个帧指针要被恢复到寄存器中。帧指针和栈指针之间的范围（包括指针本身所指的数据）就是一个过程的栈帧，包含了这个过程的局部变量、参数、返回值和返回地址。出栈时，栈指针不能超过帧指针，就保证了不会错误弹出本层以外的过程保存的数据。当然，并不是所有时候都有帧指针。例如MIPS提供的C编译器不使用帧指针，GNU MIPS C编译器则相反。
28、将递归的代码改为循环，可以提升性能。尾调用（tail call）是指一个过程（函数）的最后一个语句是调用一个过程（函数）的情形。如果最后的调用是调用了自己，则称为尾递归（tail recursion）。编译器会针对尾调用，尤其是尾递归，进行深度优化，简化了函数调用栈的结构，提升性能（降低时空复杂度（complexity））。尾递归会被编译器优化成循环，也就是把调用的指令（例如call）和相应的返回指令直接改成跳转指令（例如jmp）。当然，如果过程含有参数或者局部变量，就要额外做相应的调整，必须确保被调用函数的函数帧在跳过去之前已设置好。意即：若是调用栈除了返回位置以外还有参数或本地变量，编译器需要输出调整调用栈的相关指令。
下面是尾调用优化的一个例子：
void f() {
return a();
}
翻译成x86汇编的结果大致是：
f:
call a
ret
消除尾部调用以后，就变成了：
f:
jmp a
在a函数完成的时候，它会直接返回到f的返回地址，省去了不必要的ret指令，也不用执行第24点中说的那几步，在时间和空间上都表现得更优秀。
29、MIPS支持对半字（halfword）进行操作。不过MIPS的栈要求对齐，因此一个单字节或半字的数据在栈内仍然占据4字节的空间。
30、MIPS的所有指令都是32位的。但是，如果需要参与运算的常数或地址也是32位的，指令就放不下。lui指令（load upper immediate）可以把常量的高16位放入寄存器中，跟随lui指令的指令中包含该常量的低16位。
31、MIPS还有一种指令格式叫做J型（J-type）。J型指令前6个bit是操作域，而后26个bit是地址域：
使用该种格式的指令主要是跳转指令j。条件语句需要跳转的位置通常都不很远，但是过程调用则不一定。可能需要跳转到较远的地方时，就用这种指令格式。MIPS的每个数据的内存地址都按4的整数倍对齐，所以这26个bit可以覆盖的跳转范围实际上达到228。如果需要跳至更远的范围，就应该使用jr指令（跳至寄存器中指定的地址）了。
当条件分支需要跳转到更远的地方时，跳转的目标地址就不能包含在一条指令里。这时候，MIPS编译器会把触发分支的条件变为相反条件，然后在分支指令之后添加一个无条件跳转语句来实现更远的跳转：
beq s1,L1
这个指令表示当寄存器s1相等时跳转到标号L1处。如果L1距离当前指令所在的内存地址太远，编译器会把这条指令转换成：
bne s1,L2
j L1
L2: # …
于是，当寄存器s1不相等时，就跳转到标号L2处，等效于转换之前s1不相等而不跳转到L1处；如果s1相等，就通过下一条j指令跳转到L1处，也与原来等效。
32、反汇编（disassembly），指的是将机器语言转换成汇编代码的过程。
33、在并发编程中，常用的机制是互斥锁（mutual exclusion，mutex）。互斥锁被用来构建临界区（critical section）。对应的锁上锁后，临界区只能被一个线程访问，以免不同的线程同时读写临界区造成出错。上锁与解锁操作是原子的（atomic），不能被调度器打断。也就是说在执行原子操作期间，调度器不能进行上下文切换选择其它线程继续运行。
34、实现正确的并发也有其它机制。例如指令对load-linked和store-conditional。MIPS提供这一对指令，并且sc必须在ll前使用。这对指令还能用于实现其它机制，比如compare-and-swap和fetch-and-increment。
这两个指令之间可以根据不同的要求插入不同的指令，但应该尽量少插入，防止失败次数增多导致重试次数增多。而且在中间插入指令时要防止死锁（deadlock）的产生。
35、一般而言，C / C++代码会先翻译为汇编语言，再翻译为目标模块，然后由链接器把目标模块混合，生成计算机可以执行的代码。有的编译器会直接生成目标模块而不先生成汇编，而有的系统使用链接加载器，在运行时进行链接并将程序载入内存。
36、伪指令（pseudoinstructions）是汇编语言中的一种指令。它们没有对应的机器指令，只能被汇编器识别。伪指令为编程带来了方便，并且也能简化汇编器的翻译过程。
MIPS会将伪指令move转换成add，将blt（branch on less than）转换成slt和bne。类似的例子还有bgt、bge和ble。x86汇编的常见伪指令有assume, segment, ends, end。
37、汇编器首先生成目标文件（object file）。目标文件包含一系列机器指令、数据和一些为了将程序正确放在内存而需要的信息。汇编器在汇编过程中需要把源程序中的标号（例如分支和跳转指令中出现的标号或代表一段数据的地址的标号）及其地址等内容收集并记录为符号表（symbol table）。
UNIX的目标文件一般包含六部分：
（1）目标文件头（object file header），表述目标文件其它部分的大小与位置。
（2）文本段（text segment），包含机器码。
（3）静态数据段（static data segment），包含伴随程序的整个生命过程的数据。
（4）重定位信息（relocation information），指示依赖绝对地址的指令和数据在内存中的位置。
（5）符号表（symbol table），包含未定义的剩余标号，例如对外部文件的内容的引用。
（6）调试信息（debugging information），包含的信息指示了这些模块是如何编译的，方便调试器将机器指令与C / C++的源文件关联起来。
以下是一个目标文件的示例。为了方便阅读，机器指令在这张表中被写成汇编指令。实际上对应位置存储的应该是机器指令的二进制码而不是助记符（汇编语句）。过程A需要确定lw指令需要用到的X的地址，还需要找到jal指令需要用到的过程B的地址。
38、有时候我们只是将程序中的少量语句简单修改了。如果将整个程序重新编译，是非常麻烦、非常浪费计算资源和时间的。一个可行的替代方案是：只重新编译改变的语句所在的过程。为了实现这个方案，需要用到链接器，全名是链接编辑器（link editor）。
链接器链接目标文件主要分三步：
（1）将代码和数据模块符号化并存入内存。
（2）确定数据和指令标号的地址。
（3）处理内部引用和外部引用。
解决外部引用后，链接器就要确定每个模块在内存中占据的位置。当把模块装入内存时，就要确定其绝对地址。
39、加载器（loader）负责将准备运行的程序放入内存。UNIX的加载器将程序载入内存时需要执行如下6步：
（1）读取可执行文件的文件头，确定文本段和数据段的大小。
（2）创建一个足够大的地址空间。
（3）将指令和数据复制到内存中。
（4）将入口函数的参数复制到栈中。
（5）初始化机器的寄存器，设定栈指针。
（6）跳至入口地址开始执行。当执行完毕后，通过系统调用exit来终止程序。
40、如果在生成可执行文件的过程中，将代码需要用到的库都链接好，虽然可以让对库的调用很快，但也有如下缺点：
（1）库成为了代码的一部分。如果调用的库更新了，最终编译好的应用程序使用的库仍然是旧版本。
（2）即使只用到一个库中的少量内容，也需要把整个库链接起来，导致最终生成的可执行文件很大。例如：将整个C标准库（standard C library）都链接到程序中，程序就要多出2.5 MB。如果把计算机里的这么多个可执行文件都链接C标准库，增加的大小可想而知。
为了解决这些问题，动态链接库（dynamically linked library，DLL）诞生了。DLL要配合动态链接器使用。当程序运行时，才使用可执行文件和库里的额外信息，将需要用到的库链接起来。最开始的DLL依然一次性将所有的可能需要用到的库与运行的程序链接。后来的DLL在程序运行时才进行链接。
当库函数被调用时，正在运行的程序先调用位于程序末端的“假入口”（用于进行间接跳转），跳至一段代码。这段代码将用于标识调用的库函数的值放入寄存器，然后跳至动态链接器。动态链接器找到需要调用的库函数，将其重映射（以此避免直接将整个库函数复制），然后将跳转位置指向库函数，再跳至库函数并开始执行。当库函数完成后，返回调用库函数的位置继续执行剩余的代码。如果在程序的本次运行期间再度调用这个库函数，就可以直接跳至已经找到的库函数的位置了。
Windows高度依赖DLL，UNIX系统亦然。
41、以C / C++为代表的传统计算机语言及计算机程序的运行模型注重高速，是高度针对特定的ISA甚至高度针对使用该ISA的计算机的。而Java等语言则不同。Java的一个主要的设计初衷是在不同的计算机上都能安全运行，即使是为此降低运行速度。
Java编写的程序在运行之前不编译为目标计算机的汇编语言，而是先编译成Java字节码（Java bytecode）指令集。这套指令集使得最后的编译过程变得简化。与C / C++编译器一样，Java编译器在编译时也会检查数据类型，并根据数据类型正确选择与数据类型匹配的操作。Java虚拟机（Java Virtual Machine，JVM）是软件解释器，用于执行字节码。解释器能模拟一套ISA。特定ISA的CPU的模拟器，例如MIPS模拟器，也是一种解释器。
用解释器执行代码的一个优势是可移植性（portability）。如今，手机和浏览器都要运行Java，运行Java的设备数需要以亿为单位来统计。但是使用解释器来执行会降低性能，因为代码并没有针对ISA进行编译，也就是说没有进行非常充分的优化。因此在高性能计算（High performance computing，HPC）等领域，C / C++等编译型语言依然占有绝对优势。
为了让Java的速率有所提高，Java代码中的一些常用的方法（函数）会被即时编译器（Just in time compiler，JIT）在运行时编译为机器指令。运行结束后，这些编译好的指令会被保存下来，以提升以后运行该程序的性能。
42、C / C++编译器提供了不同的优化等级。常用的优化级别为-O2。-O3虽然优化得更快，但是生成的可执行文件比较大，而且可能存在较多的Bug。-O2优化相比不优化，有时候可以令程序的总体性能提升超过100%。-Os则针对可执行文件的大小进行优化。
43、在访问数组的时候，有两种方法：一种是通过数组名称（代表首地址）和下标访问，一种是通过指针访问。例如下面这两个函数：
clear1(int array[], int size) {
int i;
for (i = 0; i < size; i += 1)
array[i] = 0;
}
clear2(int* array, int size) {
int* p;
for (p = &array[0]; p < &array[size]; p = p + 1)
*p = 0;
}
如果采用第一种方法，访问数组时需要根据下标来计算地址，理论上每次循环需要执行的指令数更多。所以程序员们曾被建议：“多用指针，即使代码变得让你看不懂。”当然，随着计算机的发展，较新的编译器已经能对下标访问数组进行充分优化，使得最终的性能不比使用指针访问数组差多少。而且，计算机性能的提高让这两种方法的性能差距在一般情况下可以忽略不计。但是，在一些极端情况下，比如数组的维数较多，或者循环次数非常大，那么访问数组中的元素时也许有必要使用指针访问来代替下标访问。在对性能要求极高的场合（比如高频交易和高性能计算），一些细微的优化步骤不可以省略。
44、ARM指令集架构和MIPS很像，主要的区别是MIPS拥有更多寄存器，而ARM拥有更多的寻址方式（addressing mode）。ARMv7的几乎所有指令的高4位都是条件码（condition code），用于决定每条指令在何种条件下执行。因此ARMv7没有专门的用于实现程序的分支结构的指令。（下表中，GPR代表通用寄存器（general purpose register））
当只用12-bit表示立即数时，ARM处理器能够接受的立即数的范围仍然是0到232 – 1。编译时会进行检查，如果输入的立即数不能用低8位循环右移（rotate right）高4位表示的数的两倍得到，就认为这个立即数非法，直接报错。循环右移会将右移过程中越过最低位的数重新放到最高位。ARMv7处理器没有循环左移（rotate left）指令。ARMv7这种表示方法正好能够让2的0到31次幂都是合法的立即数。
ARMv7还具有按块取（block load）和按块存（block store）指令，允许用一条指令同时读写多个寄存器。这两种指令非常有用，不但可以用于过程的开始和结束之前将一些寄存器一同入栈或出栈，还可以用于内存数据的成块复制。
45、下面梳理x86 ISA的发展历程上的几个重大事件：
·1978年，Intel推出了8086 CPU。它是16位的，用于接替8位CPU——8080，兼容汇编语言。但与MIPS不同，8086的许多寄存器都有专门的用途，因此8086的架构不被视为通用寄存器架构。
·1980年，Intel推出了8087浮点协处理器（coprocessor）。8087用于为8086扩展60条浮点指令。但8087不具备寄存器，而使用栈。
·1982年，8086的继任者80286上市了。其支持的地址空间（address space）范围提升到了24-bit，并通过一个精心设计的内存映射保护模型实现内存保护机制。80286也具备与这个模型相关的指令集。
·1985年，80386接替了80286。这是Intel的首个32位处理器，寄存器和地址空间都是32位的。80386提供了新的运算和寻址方式。新的指令让80386接近通用寄存器架构。除了段（segment）机制，80386还支持内存的分页（paging）机制。当然，80386提供专门的模式用于执行8086时期的程序，而无需程序员对代码做修改。80386只有8个通用寄存器，MIPS有32个，而ARMv7有16个。
·1989年到1995年，Intel又在1989年推出了80486，亦于1992、1995年分别推出了奔腾（Pentium）和奔腾Pro（Pentium Pro）系列处理器。在用户可见的指令范围内，新处理器新增了4条指令：3条用于辅助多道程序处理（multiprocessing），1条用于条件移动（move）指令。
·1997年，Pentium和Pentium Pro系列的新处理器添加了MMX（Multi Media Extension，多媒体扩展）指令集。MMX指令集拥有57条新指令，通过浮点栈来加速多媒体应用程序。MMX一般同时运算多个数据，支持这种运算的架构称为单指令多数据（SIMD）架构，将在第6章进一步学习。后来的Pentium II未新增任何指令。
·1999年，Intel添加了70条新指令，归为SSE（流式SIMD扩展，Streaming SIMD Extensions）指令集。这是Pentium III的一部分，最大改变是增加了8个新的128-bit专用寄存器（xmm0到xmm7，详见第5点），所以一次最多可以做4个32-bit的浮点数参与的运算（每个运算的每个操作数占用寄存器的1 / 4空间）。为了提升内存性能，SSE还包括缓存预读指令和流式存储指令，可以绕过缓存直接写入内存。
·2001年，Intel推出了新增144条指令的SSE2指令集。SSE2是针对双精度计算的，允许每周期同时执行2个64-bit浮点运算。几乎所有新增的指令都是已有的MMX和SSE指令集中进行双精度浮点运算的并行版本。SSE2不但为多媒体应用提升了更多性能，编译器在编译时还可选用8个SSE寄存器作为浮点寄存器，与CPU中的其它寄存器一起使用。SSE2指令集使得首次使用它的Pentium 4的浮点性能显著提升。
·2003年，AMD发布了一组新的架构扩展，将地址空间和寄存器宽度扩大到64位，该架构称为AMD64。64位架构具有翻倍数量（16个）的SSE寄存器。AMD64的主要改进是使所有x86指令都能使用64-bit的地址和数据。为了定位更多数量的寄存器，AMD64为指令增加了新前缀，以及4条新指令，并弃用27条旧指令。PC（程序计数器）相对的数据定址是另一项新引入的扩展。AMD64支持让64位操作系统中的程序运行在32位的环境。这种方式使得从32位到64位的过度比Intel的IA-64更平滑。
·2004年，Intel在IA-64架构的Itanium（安腾，不兼容原有的x86）上持续失利，最后选择引入AMD64架构，Intel将其称为EM64T（Extended memory 64 technology）。但AMD64和EM64T的一个主要不同是：EM64T增加了128-bit的compare-and-swap原子指令。这一年，Intel也发布了SSE3指令集。SSE3增加了13条指令，用于支持复数计算、在数组上进行的图形运算、视频编码、浮点转换和线程同步。AMD后来也支持了SSE3和compare-and-swap原子指令，这使得AMD和Intel的处理器在二进制层面上保持兼容。
·2006年，Intel发布了添加了54条新指令的SSE4指令集。新的指令主要加速计算绝对值差的和（sum of absolute difference，SAD）、点积、无 / 带符号扩展，以及虚拟机。
·2007年，AMD发布新增170条指令的SSE5指令集，其中46条指令支持三操作数。
·2008年，Intel推出了Larrabee架构的GPGPU（通用GPU，general-purpose GPU），支持新的AVX指令集（Advanced vector extensions，高级向量扩展），将专用寄存器宽度从SSE时代的128位提升至256位（仅增加对256位浮点的SIMD支持），重写了约250条指令，新增128条指令。后来AMD放弃支持SSE5，转而支持AVX。
·2011年，Intel发布AVX2指令集。AVX2增加了整数SIMD的256位支持。Intel同年发布了Sandy Bridge架构的CPU，支持AVX；2013年起，Intel陆续推出Haswell架构的的CPU，支持AVX2。
·2013年，Intel发布了AVX-512指令集。2017年的Skylake-SP服务器CPU支持AVX-512，而桌面级（消费级）CPU依然只支持到AVX2。
如今，虽然x86芯片的出货量远远不及ARM，但是x86 CPU仍然在服务器、云与高性能计算领域占有垄断性地位。当然，越来越多的巨头选择了自主研发ARM架构的服务器CPU。较新的ARM CPU也可以支持类似AVX的指令集（由获得相应架构的授权的厂商决定），它被称为SVE（Scalable Vector Extensions）。
46、如果你的学校的汇编语言课程使用x86的CPU作为教学平台，你应当发现：x86架构的指令中，双操作数的指令的其中一个寄存器既是源寄存器又是目标寄存器，而且其中一个操作数可以不是寄存器而来自内存。
这两幅图显示了80386的指令中操作数的类型限制。对二元运算，其中一个数可以是内存中的数或立即数，两个数也可以都不来自寄存器，但不允许两个数都来自内存。
80386的指令支持的寻址方式包括：
（1）寄存器间接寻址。地址保存在寄存器中，直接取用。
（2）基址+偏移。实际地址是基址+偏移地址。
（3）基址+放大的索引。根据数据类型（长度），数据的首地址为基址+下标×某个倍数。这是访问数组的寻址方式。
（4）基址+放大的索引+偏移。偏移和索引的意义分别与（2）（3）中的相同。
80386借鉴了8086的设计思路，通过为指令添加前缀来改变指令的具体行为。例如不同的指令前缀在80386中代表对不同的数据类型进行运算。
x86整数操作一般分为以下四类：
（1）数据传输指令，如赋值、进栈、出栈。
（2）算术与逻辑指令。例如整数和浮点运算、与或非、移位。
（3）控制指令，例如条件分支、无条件跳转、调用和返回。
（4）字符串指令，例如字符串的赋值与比较。
x86也像ARM那样具有条件码，又称标志（flag）。条件码主要用于刻画运算的副作用，例如结果的正、零或负，是否发生了进位或溢出等。条件语句通过读取标志寄存器中相应的位来判断条件是否成立。两个数比较的结果也会被存入标志寄存器，条件跳转指令可以通过读取标志寄存器来判断是否达到跳转条件。
x86的指令是变长的，不像ARMv7和MIPS那样固定为32位长（ARMv7的A32指令集是定长的，但T32指令集是变长的，有的指令是16位）：
变长指令使得x86指令的格式繁多，编码困难。虽然80386是1985年的产品，其设计的复杂度不可与当今的处理器相提并论，但它的指令长度仍然可以横跨1 Byte到15 Bytes。操作码刻画了指令的类型和其它必要信息，比如操作数是8-bit、16-bit还是32-bit，寻址方式，寄存器名称，等等。下图列举了几个常用指令的编码格式。
47、x86是最早将32-bit扩展到64-bit的，一个重要原因就是16-bit或32-bit的CPU支持的内存容量太小。这点改进远远早于它的竞争对手。1977年的Apple II计算机采用的是MOStek 6502，其地址线只有16位，也就是说采用这个CPU的计算机的内存最大不超过64 KB。虽然Apple II作为首台上市的个人计算机非常成功，但由于支持的内存容量太小，Apple II很快被扫进了历史的垃圾堆。
ARM从2007年开始设计64-bit版本的ARM CPU，最终于2013年正式发布，它们的指令集为ARMv8。与x86从32位迈向64位不同，ARMv7到ARMv8是一次大改。
首先，ARMv8指令放弃了如下的特性：
（1）指令中的高4位条件码。
（2）立即数是简单的12-bit（或由这12-bit左移而得），不再像ARMv7那样需要将这12-bit通过循环右移转换为一个合法的立即数。当然，有的指令留给立即数的位数更多。
（3）不具有读写多个寄存器的Load Multiple和Store Multiple指令。
（4）PC不再是寄存器。如果尝试写入到PC，会发生未定义的结果。
其次，ARMv8也添加了类似MIPS的新特性：
（1）ARMv8 CPU具有32个通用寄存器，并具有一个专门的寄存器代表0这个数值。
（2）寻址支持不同的数据类型。
（3）ARMv8增加了专门的除法指令。ARMv7是没有除法指令的，除法被做成一个函数。
（4）提供了MIPS中存在的branch if equal和branch if not equal指令。
ARMv8很接近MIPS，因此我们说ARMv7和ARMv8的相似点大概只有名字了。
48、功能越强的指令不一定性能越高。例如有两条向内存中写数据的指令（先把数据读入寄存器再复制到内存中的另一个位置）。现在用循环执行这一条指令若干次，速度就没有将循环展开更快。因为执行循环相关的指令（例如loop）本身也是要耗时的。不过，较新的CPU也许会使用比较宽的寄存器同时传送多个数据，这样就更快了。
49、使用汇编语言编写代码不一定能实现最高性能。以前，编译器生成的汇编代码与手写的汇编代码的性能确实存在较大差距；但是随着编译器的飞速发展，许多时候编译器生成的代码反而比手写的汇编要快。C / C++中的register修饰符令用户可以手动指定哪些变量要放入寄存器。以往的编译器不能很好地将合适的变量放入寄存器来发挥最佳性能，但是现在的编译器很多都能做到了。所以大量的编译器会直接忽略这个修饰。
必须承认，许多底层代码，例如驱动（driver）和操作系统的部分代码，依然有人用汇编语言书写，但是这样的人已经很少了。使用汇编语言实现同样的功能花费的时间远远长于使用高级语言。而且汇编语言是高度针对一个平台的，不像高级语言那样，只要使用的基本上是跨平台性好的代码，仅通过选择不同平台（x86 / ARM / MIPS等）的编译器就可以生成跨平台的应用程序。而且，程序发布以后，随着硬件的更迭，有必要对代码进行新的调整；发现新的Bug时，也需要修复。如果程序是汇编语言编写的，维护的工作就非常繁重。
50、为了在商业上保持对旧机器的兼容性，成功的指令集不一定不作任何修改。下表告诉我们，x86指令集在发布后的35年以来，平均每个月添加超过1条新指令。
直到今天，x86仍然在增加新的指令。例如改进多线程的TSX-NI，以及深度学习常用的BFloat16数据类型相关的指令集。非常古老的指令集也有被弃用的，例如3DNow!指令集在新的Intel CPU中已经不再支持。也许MMX也差不多完成了它的使命，不再于数年后的新CPU中提供。
51、注意：下一个字，或者下一个数据在内存中的首地址，不一定是当前数据的地址+1。很多程序员都踩过这个坑。
52、避免在局部变量的作用范围外定义指向局部变量的指针。因为过程返回后局部变量会被释放（清除），此时外部的指向原有局部变量的指针成为了野指针，对野指针访问会出错。