深入理解计算机系统（一）

大多数计算机 使用 8 位的块，或者字节（byte），作为最小的可寻址的内存单位， 而不是访问内存中单独的位。机器级程序将内存视为一个非常大的字节数组，称为虚拟内存（virtual memory）。内存的每个字节都由一个唯一的数字来标识，称为它的地址（address），所有可能地址的集合就称为虚拟地址空间（virtual address space）。

字数据大小

每台计算机都有一个字长（word size），指明指针数据的标称大小（nominal size）。因为虚拟地址是以这样的一个字来编码的，所以字长决定的最重要的系统参数就是虚拟地址空间的最大大小。也就是说，对于一个字长 x 位的机器而言，虚拟地址的范围为$0 \sim 2^{x}$

现在市面上大部分的机器都是 64 位字长，以及现在的智能手机也是 64 位的处理器。32 位字长限制了虚拟地址空间位 4294967296 字节，也就是 4 GB，而扩展到 64 位字长使得虚拟地址空间为 16EB，大约是 $ 1.84\times 10^{19} $ 字节。

下面列举出了 Java 中的九种基本类型大小：

基本类型	装箱类型	大小	取值范围
byte	Byte	1 字节	$-2^{7}\sim 2^{7}-1$
short	Short	2 字节	$-2^{15}\sim 2^{15}-1$
char	Character	2 字节	$-2^{15}\sim 2^{15}-1$
int	Integer	4 字节	$-2^{31}\sim 2^{31}-1$
float	Float	4 字节	$-2^{31}\sim 2^{31}-1$
boolean	Boolean	4 字节或 1 字节	$-2^{31}\sim 2^{31}-1$ $-2^{7}\sim 2^{7}-1$
long	Long	8 字节	$-2^{63}\sim 2^{63}-1$
double	Double	8 字节	$-2^{63}\sim 2^{63}-1$
returnAddress	-	-	-

returnAddress 类型的值是指向字节码的指针，不管是物理机还是虚拟机，运行时内存中的数据总归可分为两类：代码，数据。对于冯诺依曼结构的计算机，指令数据和数值数据都存储在内存中，而哈弗结构的计算机，将程序指令与数据分开存储。

对于 JVM 来说，程序就是存储在方法区的字节码指令，而 returnAddress 类型的值就是指向特定指令内存地址的指针。

JVM 支持多线程，每个线程有自己的程序计数器（pc register），而 pc 中的值就是当前指令所在的内存地址，即 returnAddress 类型的数据，当线程执行 native 方法时，pc 中的值为 undefined。

returnAddress 类型会被 JVM 中的无条件转移指令 jsr、ret 和 jsr_w 指令所使用，returnAddress 类型的值指向一条虚拟机指令的操作码。但是 jsr、ret 和 jsr_w 指令主要用来实现 finally 语句块，后来改为冗余 finally 块代码的方式实现，到了 JDK7 时，JVM 中已不允许 Class 文件内出现这几条指令，returnAddress 类型也就名存实亡。

寻址和字节顺序

对于跨越多字节的程序对象，我们必须建立两个规则：这个对象地址是什么？如何在内存中排列这些字节？
在几乎所有的机器上，多字节对象都被存储为连续的字节序列，对象的地址为所使用字节中最小地址。

在排序方式上有两种方式：

1. 大端法：将低位放在高地址。
2. 小端法：将高位放在高地址。

在计算机内存中，通常都是以字节，即 8 位一存储。

如果存储一个 int x，那么假设地址为：0x20001207。

由于是 8 位一存储，所以地址分割后位 20 00 12 07 四块。

使用大端法就是将低位放在高地址，地址则是 0x07120020；
使用小端法就是将高位放在低地址，地址则是 0x20001207。

移位运算

Java 提供了一组移位运算，向左或向右移位。对于一个位表示为[\; x_{w-1}, \; x_{w-2}, \; x_{w-3}, \; ..., \; x_{0} \;] $ 的操作数 x，x << k 会生成一个新的值，位表示为 $ [\; x_{w-1-k}, \; x_{w-2-k}, \; x_{w-3-k}, \; ..., \; x_{0}, \; 0, \; ..., \; 0 \; ]。也就说，x 左移 k 位，丢弃最高的 k 位，并在右端补 k 个 0。而 x >> k 操作也会生成一个新的值，但是右移有两种：逻辑右移和算术右移。逻辑右移在左侧补 k 个 0，结果是 $ [; 0, ; …, ; 0, ; x_{w-1}, ; x_{w-2}, ; x_{w-3}, ; …, ; x_{k} ; ]$。算术右移是在左端补 k 个最高有效位的值，得到的结果是 $[; x_{w-1}, ; x_{w-2}, ; x_{w-3}, ; …, ; x_{k} ; ] $ 。这种做法看上去可能很奇特，但是它对有符号整数数据的运算非常有用。

操作	值
参数 x	$[01100011] \quad [10010101]$
x << 4	$[0011\mathbf{0000}] \quad [0101\mathbf{0000}]$
x >> 4 (逻辑右移)	$[\mathbf{0000}0110] \quad [\mathbf{0000}1001]$
x >> 4 (算数右移)	$[\mathbf{0000}0110] \quad [\mathbf{1111}1001]$

粗体的数字表示的是最右端（左移）或最左端（右移）填充的值。

整数编码

无符号整数编码

假设有一个整数又$w$位。其位向量为：$\vec{x} = [\; x_{w-1}, \; x_{w-2}, \; x_{w-3}, \; ..., \; x_{0} \;]$：

$$B2U_w(\vec x)\doteq \sum_{i=0}^{w-1}x_i2^i$$

样例：

$B2U_4([0001])=0\times2^3+0\times2^2+0\times2^1+1\times2^0=0+0+0+1=1$

$B2U_4([0101])=0\times2^3+1\times2^2+0\times2^1+1\times2^0=0+4+0+1=5$

$B2U_4([1011])=1\times2^3+0\times2^2+1\times2^1+1\times2^0=8+0+2+1=11$

$B2U_4([1111])=1\times2^3+1\times2^2+1\times2^1+1\times2^0=8+4+2+1=15$

而$w$能表示的值的范围，最小值用位向量$[000.......000]$表示，也就是整数$0$，

补码编码

对于许多应用，我们还希望表示负数值。最常见的有符号数的计算机表示方式就是补码形式。

对向量$\vec{x} = [\; x_{w-1}, \; x_{w-2}, \; x_{w-3}, \; ..., \; x_{0} \;]$：

$$B2T_w(\vec x)\doteq -x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2^i$$

最高有效位$x_{w-1}$也称为符号位，它的“权重”为$-2_{w-1}$，是无符号表示中权重的负数。符号位为 1 时，表示为负数，而当符号位为 0 时，值为正数。

样例：

$B2T_4([0001])=-0\times2^3+0\times2^2+0\times2^1+1\times2^0=0+0+0+1=1$

$B2T_4([0101])=-0\times2^3+1\times2^2+0\times2^1+1\times2^0=0+4+0+1=5$

$B2T_4([1011])=-1\times2^3+0\times2^2+1\times2^1+1\times2^0=-8+0+2+1=-5$

$B2T_4([1111])=-1\times2^3+1\times2^2+1\times2^1+1\times2^0=-8+4+2+1=-1$

通用目的寄存器

一个 x86-64 的中央处理单元（CPU）包含一组 16 个存储 64 位值的通用目的寄存器。这些寄存器用来存储整数数据和指针。

• 黄色区域的是 8 位寄存器，其可以访问 1 个字节。
• 紫色区域的是 16 位寄存器，其可以访问 2 个字节，可以访问 8 位寄存器中的内容。
• 绿色区域的是 32 位寄存器，其可以访问 4 个字节，可以访问 8 位和 16 位寄存器中的内容。
• 蓝色区域的是 64 位寄存器，其可以访问 8 个字节，可以访问 8 位、16 位和 32 位寄存器中的内容。

对此有两条规则：

1. 生成 1 字节和 2 字节数字的指令会保持剩下的字节不变。
2. 生成 4 字节数字的指令会把高位 4 个字节置为 0。

规则 2 是作为从 IA32 到 x86-64 的扩展的一部分而采用的。

数据格式

由于是从 16 位体系结构扩展成 32 位的，Intel 用术语 “字（word）” 表示 16 位数据类型。因此，称 32 位数为“双字（double words）”，称 64 位数为“四字（quad words）”。标准 int 值存储为双字（32 位）。指针（在此用 char*表示）存储为 8 字节的四字，64 位机器本来就预期如此。x86-64 中，数据类型 long 实现为 64 位，允许表示的值范围较大。x86-64 指令集同样包括完整的针对字节、字和双字的指令。

数据类型	Intel 数据类型	汇编后缀	大小
char	字节	b	1
short	字	w	2
int	双字	l	4
long	四字	q	8
char*	四字	q	8
float	单精度	s	4
double	双精度	l	8

操作数指令符

大多数指令有一个或多个操作数（operand），指示出执行一个操作中要使用的源数据值，以及放置结果的目的位置。源数据值可以以常数形式给出，或是从寄存器或内存中读出。结果可以存放在寄存器或内存中。

因此，各种不同的操作数的可能性被分为三种类型：

1. 立即数（immediate），用来表示常数值。在ATT格式的汇编代码中，立即数的书写方式是 “$” 后面跟一个用标准 C 表示法表示的整数，比如，$-577 或 $0x1F。不同的指令允许的立即数值范围不同，汇编器会自动选择最紧凑的方式进行数值编码。
2. 寄存器（register），它表示某个寄存器的内容，16 个寄存器的低位 1 字节、2 字节、4 字节或 8 字节中的一个作为操作数，这些字节数分别对应于 8 位、16 位、32 位或 64 位。用符号$r_a$，来表示任意寄存器 a，用引用$R[r_a]$来表示它的值，这是将寄存器集合看成一个数组 R，用寄存器标识符作为索引。
3. 内存引用，它会根据计算出来的地址（通常称为有效地址）访问某个内存位置。因为将内存看成一个很大的字节数组，我们用符号$M_b[Addr]$表示对存储在内存中从地址 Addr 开始的 b 个字节值的引用。为了简便，我们通常省去下标b。

其实有多种不同的寻址模式，允许不同形式的内存引用。表中底部用语法$Imm（r_b，r_i，s）$表示的是最常用的形式。这样的引用有四个组成部分：

1. 立即数偏移$Imm$
2. 基址寄存器$r_b$
3. 变址寄存器$r_i$
4. 比例因子 s

这里 s 必须是1、2、4 或者 8。基址和变址寄存器都必须是 64 位寄存器。有效地址被计算为$Imm+R[r_b]+R[r_i]\cdot s$。引用数组元素时，会用到这种通用形式。其他形式都是这种通用形式的特殊情况，只是省略了某些部分。

类型	格式	操作数值	名称
立即数	$Imm$	$Imm$	立即数寻址
寄存器	$r_a$	$R[r_a]$	寄存器寻址
存储器	$Imm$	$M[Imm]$	绝对寻址
存储器	$(r_a)$	$M[R[r_a]]$	间接寻址
存储器	$Imm(r_b)$	$M[Imm+R[r_b]]$	（基址 + 偏移量）寻址
存储器	$(r_b,\;r_i)$	$M[R[r_b]+R[r_i]]$	变址寻址
存储器	$Imm(r_b,\;r_i)$	$M[Imm+R[r_b]+R[r_i]]$	变址寻址
存储器	$(,\;r_i,\;s)$	$M[R[r_i]\cdot s]$	比例变址寻址
存储器	$Imm(,\;r_i,\;s)$	$M[Imm+R[r_i]\cdot s]$	比例变址寻址
存储器	$(r_b,\;r_i,\;s)$	$M[R[r_b]+R[r_i]\cdot s]$	比例变址寻址
存储器	$Imm(r_b,\;r_i,\;s)$	$M[Imm+R[r_b]+R[r_i]\cdot s]$	比例变址寻址

数据传送指令

数据传送指令用来把数据、地址或者立即数传送到寄存器或存储单元中。

而数据传送指令又可分为4类：

1. 通用数据传送指令
2. 输入输出指令
3. 地址传送指令
4. 标志传送指令

除标志传送指令外，其他指令的执行对标志位均不产生影响。

标志位相关知识：[标志位详解][]

通用数据传送指令

通用数据传输指令又可分为 5 类：

1. 一般数据传输指令
2. 堆栈操作指令
3. 交换指令
4. 查表转换指令
5. 字位扩展指令

这 5 类指令的执行，均不影响标志位。

一般数据传输指令 MOV

格式：MOV DEST，SRC

操作：src$\longrightarrow$dest

例如：MOV AL，BL

上述例子就是将 BL 中的数据传输至 AL 中，但是MOV指令有一下几点需要注意：

• 两操作数字长必须相同
• 两操作数不允许同时为存储器操作数
• 两操作数不允许同时为段寄存器
• 在源操作数是立即数时，目标操作数不能是段寄存器
• IP和CS不作为目标操作数，FLAGS一般也不作为操作数在指令中出现

CS：指令段地址

IP：当前指令地址

CS + IP：当前指令的绝对地址

MOV指令有分以下几种：

MOV指令	作用	MOV种类
MOVB	完成 1 个字节的复制	普通的MOV指令
MOVW	完成 2 个字节的复制	普通的MOV指令
MOVL	完成 4 个字节的复制	普通的MOV指令
MOVQ	完成 8 个字节的复制	普通的MOV指令
MOVSBW	做符号扩展的 1 字节复制到 2 字节	做符号扩展的MOVS指令
MOVSBL	做符号扩展的 1 字节复制到 4 字节	做符号扩展的MOVS指令
MOVSBQ	做符号扩展的 1 字节复制到 8 字节	做符号扩展的MOVS指令
MOVSWL	做符号扩展的 2 字节复制到 4 字节	做符号扩展的MOVS指令
MOVSWQ	做符号扩展的 2 字节复制到 8 字节	做符号扩展的MOVS指令
MOVSLQ	做符号扩展的 4 字节复制到 8 字节	做符号扩展的MOVS指令
MOVZBW	做零扩展的 1 字节复制到 2 字节	做零扩展的MOVZ指令
MOVZBL	做零扩展的 1 字节复制到 4 字节	做零扩展的MOVZ指令
MOVZBQ	做零扩展的 1 字节复制到 8 字节	做零扩展的MOVZ指令
MOVZWL	做零扩展的 2 字节复制到 4 字节	做零扩展的MOVZ指令
MOVZWQ	做零扩展的 2 字节复制到 8 字节	做零扩展的MOVZ指令
MOVZLQ	做零扩展的 4 字节复制到 8 字节	做零扩展的MOVZ指令

堆栈操作指令 PUSH POP

原则：先进后出，以字（两字节）为单位。

操作数可以是寄存器或者存储器两单元，不能是立即数，如果是存储器操作数必须声明字长，不能从栈顶弹出一个字给CS。

PUSH 指令

压栈：PUSH OPRD

PUSH指令有以下几种：

MOV指令	作用
PUSHW	将 2 个字节压入堆栈
PUSHL	将 4 个字节压入堆栈
PUSHQ	将 8 个字节压入堆栈
PUSHA	将所有的 16 位通用寄存器压入堆栈，AX，CX，DX，BX，BP，SI，DI
PUSHAD	将所有的 32 位通用寄存器压入堆栈，EAX，ECX，EDX，EBX，EBP，ESI，EDI
PUSHF	将所有的 16 位标志寄存器EFLAGS压入堆栈
PUSHFD	将所有的 32 位通用寄存器EFLAGS压入堆栈

POP 指令

弹栈：POP OPRD

POP指令有以下几种：

MOV指令	作用
POPW	将 2 个字节弹出堆栈
POPL	将 4 个字节弹出堆栈
POPQ	将 8 个字节弹出堆栈
POPA	将所有的 16 位通用寄存器弹出堆栈，DI，SI，BP，BX，DX，CX，AX
POPAD	将所有的 32 位通用寄存器弹出堆栈，EDI，ESI，EBP，EBX，EDX，ECX，EAX
POPF	将所有的 16 位标志寄存器EFLAGS弹出堆栈
POPFD	将所有的 32 位通用寄存器EFLAGS弹出堆栈

算术和逻辑操作

下图 x86-64 的一些整数和逻辑操作。大多数操作都分成了指令类，这些指令类有各种带不同大小操作数的变种（只有LEAQ没有其他大小的变种）。
例如，指令类ADD由四条加法指令组成: ADDB、ADDW、ADDL 和 ADDQ，分别是字节加法、字加法、双字加法和四字加法。
事实上，给出的每个指令类都有对这四种不同大小数据的指令。这些操作被分为四组：加载有效地址、一元操作、二元操作和移位。二元操作有两个操作数，而一元操作有一个操作数。

指令	效果	描述
LEAQ	$D \longleftarrow \&S$	加载有效地址
INC	$D \longleftarrow D+1$	加 1
DEC	$D \longleftarrow D-1$	减 1
NEG	$D \longleftarrow -D$	取负
NOT	$D \longleftarrow \sim D$	取补
ADD	$D \longleftarrow D+S$	加
SUB	$D \longleftarrow D-S$	减
IMUL	$D \longleftarrow D\ast S$	乘
XOR	$D \longleftarrow D\;\wedge\;S$	异或
OR	$D \longleftarrow D\;|\;S$	或
AND	$D \longleftarrow D\;\&\;S$	与
SAL	$D \longleftarrow D\ll k$	左移
SHL	$D \longleftarrow D\ll k$	左移（等同于 SAL）
SAR	$D \longleftarrow D\gg _{A}k$	算术右移
SHR	$D \longleftarrow D\gg _{L}k$	逻辑右移

整数算术操作。加载有效地址（LEAQ）指令通常用来执行简单的算术操作。其余的指令是更加标准的一元或二元操作。我们用$\gg _{A}$和$\gg _{L}$，来分别表示算术右移和逻辑右移。注意，这里的操作顺序与 ATT 格式的汇编代码中的相反。

加载有效地址

加载有效地址（Load Effective Address）指令 LEAQ 实际上是 MOVQ 指令的变形。它的指令形式是从内存读数据到寄存器，但实际上它根本就没有引用内存。它的第一个操作数看上去是一个内存引用，但该指令并不是从指定的位置读入数据，而是将有效地址写入到目的操作数。编译器经常发现 LEAQ 的一些灵活用法，根本就与有效地址计算无关。目的操作数必须是一个寄存器。

LEAQ 指令能执行加法和有限形式的乘法，在编译像$1+7*3+12*5-7$这样的算术表达式时，是很有用处的。

一元和二元操作

INC、DEC、NEG、NOT 是一元操作，只有一个操作数，既是源操作数又是目的操作数。这个操作数可以是一个寄存器，也可以是一个内存位置。比如说，指令 INCQ (%rsp) 会使栈顶的 8 字节元素加 1。这种语法让人想起 C 语言中的加 1 运算符（++）和减 1 运算符（–）。

ADD、SUB、IMUL、XOR、OR、AND 是二元操作，其中，第二个操作数既是源操作数又是目的操作数。这种语法让人想起 C 语言中的赋值运算符，例如 x-=y、x+=y。不过，要注意，源操作数是第一个，目的操作数是第二个，对于不可交换操作来说，这看上去很奇特。例如，指令 subq %rax,%rdx 使寄存器 %rdx 的值减去 %rax 中的值。第一个操作数可以是立即数、寄存器或是内存位置。第二个操作数可以是寄存器或是内存位置。注意，当第二个操作数为内存地址时，处理器必须从内存读出值，执行操作，再把结果写回内存。

移位操作

SAL、SHL、SAR、SHR 是移位操作，先给出移位量，然后第二项给出的是要移位的数。可以进行算术和逻辑右移。移位量可以是一个立即数，或者放在单字节寄存器 %cl 中（这些指令很特别，因为只允许以这个特定的寄存器作为操作数）。原则上来说，1 个字节的移位量使得移位量的编码范围可以达到$2^{8}-1=255$。x86-64 中，移位操作对 w 位长的数据值进行操作，移位量是由 %cl 寄存器的低 m 位决定的，这里$2^{m}=w$。高位会被忽略。所以，例如当寄存器 %cl 的十六进制值为 0xFF 时，指令 SALB 会移 7 位， SALW 会移 15 位，SALL 会移 31 位，而 SALQ 会移 63 位。

特殊的算术操作

两个 64 位有符号或无符号整数相乘得到的乘积需要 128 位来表示。x86-64 指令集对 128 位（16 字节）数的操作提供有限的支持。延续字（2 字节）、双字（4 字节）和四字（8 字节）的命名惯例，Intel 把 16 字节的数称为八字（oct word）。下图描述的是支持产生两个 64 位数字的全 128 位乘积以及整数除法的指令。

指令	效果	描述
IMULQ	$R[\%rdx]:R[\%rax] \longleftarrow S \times R[\%rax]$	有符号全乘法
MULQ	$R[\%rdx]:R[\%rax] \longleftarrow S \times R[\%rax]$	无符号全乘法
CLTO	$R[\%rdx]:R[\%rax] \longleftarrow (R[\%rax])$	转换为八字
IDIVQ	$R[\%rdx]:R[\%rdx] \longleftarrow R[\%rax]\;mod\;S$ $R[\%rdx]:R[\%rdx] \longleftarrow R[\%rax]\;\div\;S$	有符号除法
DIVQ	$R[\%rdx]:R[\%rdx] \longleftarrow R[\%rax]\;mod\;S$ $R[\%rdx]:R[\%rdx] \longleftarrow R[\%rax]\;\div\;S$	无符号除法

特殊的算术操作。这些操作提供了有符号和无符号数的全 128 位乘法和除法。一对寄存器 %rdx 和 %rax 组成一个 128 位的八字。

控制

到目前为止，我们只考虑了直线代码的行为，也就是指令一条接着一条顺序地执行。C 语言中的某些结构，比如条件语句、循环语句和分支语句，要求有条件的执行，根据数据测试的结果来决定操作执行的顺序。机器代码提供两种基本的低级机制来实现有条件的行为 : 测试数据值，然后根据测试的结果来改变控制流或者数据流。
与数据相关的控制流是实现有条件行为的更一般和更常见的方法，所以我们先来介绍它。通常，C 语言中的语句和机器代码中的指令都是按照它们在程序中出现的次序，顺序执行的。用 jump 指令可以改变一组机器代码指令的执行顺序，jump 指令指定控制应该被传递到程序的某个其他部分，可能是依赖于某个测试的结果。编译器必须产生构建在这种低级机制基础之上的指令序列 , 来实现 C 语言的控制结构。
本文会先涉及实现条件操作的两种方式，然后描述表达循环和 switch 语句的方法。