Last updated on 9 months ago

程序的机器级表示

程序的机器级表示

数据格式 & 访问信息

数据格式

下面我们给出 x86-64 指令集中关于数据大小的指令

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

这当中，字 word 表示 $2$ 个字节；双字 double word\long word 表示 $4$ 个字节；四字 quad word 表示 $8$ 个字节

需要说明的是，汇编代码用 l 表示双字与双精度，这并不会造成歧义，因为整数与浮点数使用的是不同的两套指令和寄存器

访问信息

一个 x86-64 的 CPU 包含一组 $16$ 个存储 $64$ 位的通用目的寄存器，以下为这 $16$ 个寄存器的名称及其作用

表中从左往右依次为：64 位、32 位、16 位、8 位

`Register`	`Function`	`Register`	`Function`
`%rax %eax %ax %al`	保存返回值	`%rbx %ebx %bx %bl`	被调用者保存
`%rcx %ecx %cx %cl`	第 4 个参数	`%rdx %edx %dx %dl`	第 3 个参数
`%rsi %esi %si %sil`	第 2 个参数	`%rdi %edi %di %dil`	第 1 个参数
`%rbp %ebp %bp %bpl`	被调用者保存	`%rsp %esp %sp %spl`	栈指针
`%r8 %r8d %r8w %r8b`	第 5 个参数	`%r9 %r9d %r9w %r9b`	第 6 个参数
`%r10 %r10d %r10w %r10b`	调用者保存	`%r11 %r11d %r11w %r11b`	调用者保存
`%r12 %r12d %r12w %r12b`	被调用者保存	`%r13 %r13d %r13w %r13b`	被调用者保存
`%r14 %r14d %r14w %r14b`	被调用者保存	`%r15 %r15d %r15w %r15b`	被调用者保存

不同的指令可以对单个寄存器中不同大小的数据进行操作：

字节级操作可以访问最低的字节
$16$ 位操作可以访问最低的 $2$ 个字节
$32$ 位操作可以访问最低的 $4$ 个字节
$64$ 位操作可以访问整个寄存器

如果某条指令以这些寄存器为目标，对于生成小于 $8$ 字节结果的指令，寄存器中剩余字节由以下两条规则指定：

生成 $1$ 字节或 $2$ 字节结果的指令会保持剩下的字节不变
生成 $4$ 字节结果的指令，会使高位 $4$ 字节全部清零

操作数指示符

大多数指令有一个或多个操作数 operand ，用以表示该操作中要使用的源数据值和放置目标结果的位置

源数据值可以是常数给出或者从寄存器或内存当中读出，其结果可以存放在寄存器或内存

因此，操作数可以被分为三种类型：

立即数 immediate ，用以表示常数值，通常用 $ 后面跟一个 C 标准的整数
寄存器 register ，用以表示寄存器的内容，我们用 $r_a$ 来表示任意寄存器 $a$ ，而引用 $R[r_a]$ 则可以表示该寄存器的值
内存引用 memory ，它会根据计算出来的地址来访问某个内存位置，我们用 $M_b[Addr]$ 表示从地址 $Addr$ 开始的连续 $b$ 个字节的引用（通常我们省去下标 $b$）

关于在内存当中的寻址模式，在这里我们给出一种最通用的：

\[ Imm(r_b,r_i,s)=M[Imm+R[r_b]+s\cdot R[r_i]] \]

在这里，$Imm$ 为立即数偏移，$r_b$ 为基址寄存器，$r_i$ 为变址寄存器，$s$ 为比例因子，必须是 $1,2,4,8$

需要注意的是，当采用基址与变址寄存器来进行内存寻址时，二者都必须要是 $64$ 位寄存器

指令 & 算术和逻辑操作 & 控制

数据传送指令

$MOV$ 类指令可以将数据从源位置复制目的位置，此过程中不做任何改变。$MOV$ 类由四条基本指令构成，它们的区别仅仅在于操作数据的大小不同，分别是 $1,2,4,8$ 字节

`Command`	`Effect`	`Description`
$MOV \quad S,D$	$S\rightarrow D$	传送
`movb\movw\movl\movq`		分别传送字、字节、二字、四字（从补码角度看待）
`movabsq`		传送四字（从无符号的角度看待）

下面用 movx 来表示 movb\movw\movl\movq

源操作数要么是立即数、寄存器或者内存引用，目的操作数要么是寄存器或者内存引用,这里有一条限制是：两个操作数不能都是内存引用

这些指令的操作数可以是 $16$ 个寄存器当中有标号部分的任意一个，但需要注意的是，寄存器的大小必须与指令所指示的大小相一致

无论操作数当中有几个寄存器（一个或两个），它们的大小都需要与指令所指示的相一致

例如：movl %eax %rdx 这是错误的，因为源寄存器为 $32$ 位，目的寄存器为 $64$ 位，二者并不相同

需要额外说明的是，不能以两个内存引用作为操作数的原因在于，内存引用是无法确定大小的，但寄存器或立即数却可以确定大小。因此对于内存到内存的复制，需要先从内存到寄存器，再从寄存器到内存

$MOV$ 指令只会更新目的操作数指定的寄存器字节或内存，其他位置不会发生改变，唯一的例外是使用 movl 且目的地为寄存器时，这会使得高位的 $4$ 字节全部清零

常规的 movx 指令只能以 $32$ 位补码立即数作为源操作数，然后将该数字符号拓展得到 $64$ 位的值（也就是前面写的从补码的角度考虑），而 movabsq 则可以以任意 $64$ 位立即数作为源操作数，并且只能以寄存器作为目的地

上面的指令如果是以 $1,2$ 为字节单位的指令，则不会对高位进行填充，例如：

movabsq $0x0011223344556677, %rax   # %rax = 0011223344556677
movb    $-1, %al                    # %rax = 00112233445566FF
movw    $-1, %ax                    # %rax = 001122334455FFFF
movl    $-1, %eax                   # %rax = 00000000FFFFFFFF
movq    $-1, %rax                   # %rax = FFFFFFFFFFFFFFFF

可以看到，以 b 和 w 为大小指定的指令不会对高位进行修改，下面两个 $MOV$ 的拓展类可以实现对剩余字节的填充

$MOVZ$ 通过零拓展进行填充，将剩余字节填充为 $0$
$MOVS$ 通过符号拓展进行填充，将剩余字节填充为源操作数的最高位

`Command`	`Effect`	`Description`
$MOVZ \quad S,R$	$零拓展(S)\rightarrow R$	以零拓展进行传送
`movzbw\movzbl\movzwl\movzbq\movzwq`

指令	效果	描述
$MOVS \quad S,R$	$符号拓展(S)\rightarrow R$	以符号拓展进行传送
`movsbw\movsbl\movswl\movsbq\movswq\movslq`
`cltq`	$符号拓展(\%eax)\rightarrow \%rax$	将 `%eax` 符号拓展后的结果放到 `%rax` 中

$MOVZ$ 与 $MOVS$ 均以寄存器或内存作为源，以寄存器作为目的地

正如上面指令所指示的那样，最后两个字符用以表示大小，第一个指示源操作数的大小，第二个指示目的操作数的大小

需要说明的是，这里面没有 movzlq ，这是因为对于以 $4$ 字节为操作数的 $MOV$ 指令，会将高位全部置零，因此这条指令没有必要出现

ctlq 指令没有操作数，它以 %eax 作为源，将其符号拓展后的结果放到 %rax 中，本质上与 movslq %eax, %rax 完全一致

数据传送之于指针

C 语言代码：

long wxchange(long* xp, long y)
{
    long x = *xp;
    *xp = y;
    return x;
}

对应汇编代码为：

# xp in %rdi, y in %rsi
movq    (%rdi), %rax
movq    %rsi, (%rdi)
ret

注意到两点：

局部变量均保存在寄存器中，而不是在内存当中。这是显而易见的，因为访问寄存器比访问内存要快
由于 xp 传入的是指针，因此寄存器当中保存的是一个内存引用，而不是直接将该指针所指对象的值直接放到寄存器中（xp 是从内存当中读取出来的）

数据传送之于转型

有如下代码

//声明
src_t *sp;
dest_t *dp;
//sp in %rdi, dp in %rsi

//转型
*dp = (dest_t)*sp;

其中 src_t 和 dest_t 均为 typedef 声明的不同数据类型，我们考虑的是不同数据大小之间的转型是如何进行的

把握两个原则：

从小到大需要拓展
- 有符号数需要做符号拓展，使用 $MOVS$ 类指令
- 无符号数需要做零拓展，使用 $MOVZ$ 类指令
从大到小直接截断

具体如下表：

`src_t`	`dest_t`	`Command`
`long`	`long`	`movq (%rai), %rax; movq %rax, (%rsi)`
`char`	`int`	`movsbl; movl`
`char`	`unsigned`	`movzbl; movl`
`unsigned char`	`int`	`movzbl; movl`
`int`	`char`	`movl; movb`
`unsigned`	`unsigned char`	`movl; movb`

压栈与出栈

在 x86-64 中，栈是向下增长的，因此栈顶元素的地址是栈中所有元素当中最低的

压栈与出栈主要涉及两条指令：

`Command`	`Effect`	`Description`
$pushq\quad S$	$(R[\%rsp]-8)\rightarrow R[\%rsp]\\S\rightarrow M[R[\%rsp]]$	将 `quad word` 压入栈
$popq\quad D$	$M[R[\%rsp]]\rightarrow D\\(R[\%rsp]+8)\rightarrow R[\%rsp]$	将 `quad word` 弹出栈

pushq %rbp 等价于：
1
2
subq $8, %rsp
movq %rbp, (%rsp)
popq %rax 等价于：
1
2
movq (%rsp), %rax
addq $8, %rsp

注意到：

push 指令是先将栈指针减小，然后再将寄存器的值压入栈中，且减少的数值是固定的
pop 指令会先将内存当中的值传递到寄存器中，然后再增加栈指针

算术和逻辑操作

基本操作

下面我们直接给出 x86-64 的一些整数与逻辑操作。这里面当中，除了 leaq 以外，其余的都代表一个指令类，用以对不同大小的数据进行操作。例如，$ADD$ 类由 addb; addw; addl; addq 四种组成

`Command`	`Effect`	`Description`
$leaq\quad S,\ D$	$D\ \gets\ \&S$	加载有效地址
$INC\quad D$	$D\ \gets\ D+1$	加 1
$DEC\quad D$	$D\ \gets\ D-1$	减 1
$NEG\quad D$	$D\ \gets\ -D$	取负
$NOR\quad D$	$D\ \gets\ \sim D$	取补
$ADD\quad S,\ D$	$D\ \gets\ D+S$	加
$SUB\quad S,\ D$	$D\ \gets\ D-S$	减
$IMUL\quad S,\ D$	$D\ \gets\ D\times S$	乘
$XOR\quad S,\ D$	$D\ \gets\ D \oplus S$	异或
$OR\quad S,\ D$	$D\ \gets\ D\ \\|\ S$	或
$AND\quad S,\ D$	$D\ \gets\ D\ \&\ S$	与
$SAL\quad k,\ D$	$D\ \gets\ D<<k$	左移
$SHL\quad k,\ D$	$D\ \gets\ D<<k$	左移，等同于 $SAL$
$SAR\quad k,\ D$	$D\ \gets\ D>>_{A}k$	算术右移
$SHR\quad k,\ D$	$D\ \gets\ D>>_{L}k$	逻辑右移

加载有效地址 load effective address 指令 leaq ，可以将数据从内存读到寄存器中，需要注意的是，这里的读取内存并不是将那个值读取出来，而是将地址写入到寄存器中，因此用 & 来描述更为合适

其次 leaq 可以简洁地描述一些算术操作。例如，如果 %rdx 的值为 $x$ ，那么 leaq 7(%rdx, %rdx, 4), %rax 会将 %rax 的值设置成 $5x+7$（这里需要说明的是，$x$ 的值并没有指定，既可以是地址，也可以是数值）

leaq 的目的操作数必须是寄存器

移位操作中，需要先给出移位量，再给出需要移位的数。移位量可以是立即数，也可以是字节寄存器 %cl 当中的数值

需要说明的是，在 x86-64 中，对 $\omega$ 位的数据进行移位操作时，移位量为 %cl 的低 $m$ 个字节，这里 $2^{m}=\omega$

举例来说就是，如果 %cl 的值被置为 0xFF ，那么有：

若 $\omega = 8$（对应 salb ），则 %cl 中由低 $3$ 位来决定位移量，这里为 $7$
若 $\omega = 16$（对应 salw ），则 %cl 中由低 $4$ 位来决定位移量，这里位 $15$
若 $\omega = 32$（对应 sall ），则 %cl 中由低 $5$ 位来决定位移量，这里位 $31$
若 $\omega = 64$（对应 salq ），则 %cl 中由低 $6$ 位来决定位移量，这里位 $63$

特殊操作

正如前面所提到的那样，两个 $64$ 位的无符号数或有符号数的结构需要 $128$ 位来进行存储

x86-64 指令集对 $128$ 位（$16$ 字节）同样提供支持，延续之前的命名方式，$16$ 字节被称为八字，以下描述的是支持两个 $64$ 位数字的全 $128$ 位乘法或除法的指令：

`Command`	`Effect`	`Description`
$imulq\quad S\\mulq\quad S$	$S\times R[\%rax]\rightarrow R[\%rdx]:R[\%rax]\\S\times R[\%rax]\rightarrow R[\%rdx]:R[\%rax]$	$有符号全乘法\\无符号全乘法$
$cqto$	$符号拓展(R[\%rax])\rightarrow R[\%rdx]:R[\%rax]$	$转换为八字$
$idivq\quad S\\divq\quad S$	$R[\%rdx]:R[\%rax]\div S\rightarrow R[\%rax]\\R[\%rdx]:R[\%rax]\bmod S\rightarrow R[\%rdx]$	$有符号除法\\无符号除法$

前面给出过一种双操作数的 $IMUL$ 类指令，用于实现两个 $64$ 位数的乘积，其结果还是 $64$ 位数，本质上是实现 $*_{64}^{u}$ 与 $*_{64}^{t}$

对于乘法，x86-64 提供一种单操作数的指令用于计算无符号数和有符号数的全 $128$ 位乘积。两条指令均要求一个数由寄存器 %rax 给出，另一个由操作数的形式给出。而最终的结果，低 $64$ 位存储于 $rax 中，高 $64$ 位存储于 %rdx 中

对于 $128$ 位的全除法则略有不同，两条指令以寄存器 %rdx （低 $64$ 位）和 %rax （高 $64$ 位）中的 $128$ 位数作为被除数，以操作数的形式给出除数。最终将商存储在 %rax ，余数存储在 %rdx （商存在低 $64$ 位，余数存储在高 $64$ 位）

除法的 $divq$ 指令支持 $128$ 位的被除数，但很多时候被除数一般为 $64$ 位，存放于 %rax 中，此时 %rdx 应当被设为全零（无符号除法）或者 %rax 的符号位（有符号除法）。而该操作可以用 $cqto$ 完成

该指令不需要操作数，它可以隐式读出 %rax 的符号位并将其复制到 %rdx 中

控制

当遇到条件语句、循环语句和分支语句时，就需要有条件地执行指令了，也就是改变控制流或者数据流，而实现控制流改变的方式有两种：「条件控制」和「条件传送」，下面我们逐一介绍

条件控制

CPU 除了维护整数寄存器以外，还会维护一组单个位的条件码 condition code ，这些条件码用于描述最近的算术或逻辑操作的属性。我们通过检测这些条件码的方式来实现控制流的改变这个过程，称为条件控制

常用的条件码有：

CF：进位标志——最近的操作使最高位产生了进位，用于检查无符号操作的溢出
ZF：零标志——最近的操作得出的结果为零
SF：符号标志——最近的操作得到的结果为负数
OF：溢出标志——最近的操作导致补码的溢出，正溢出或负溢出

上面列出的指令中，除了 $lea$ 不会设置标志位外，其余的都会设置标志位并且会改变寄存器的值，下面介绍两种只设置标志位而不改变寄存器数值的指令

`Command`	`Base On`	`Description`
$CMP\quad S_1,\ S_2$	$S_2-S_1$	$比较$
`cmpb\cmpw\cmpl\cmpq`		`比较字节\字\双字\四字`
$TEST\quad S_1,\ S_2$	$S_2\And S_1$	$测试$
`testb\testw\testl\testq`		`测试字节\字\双字\四字`

$TEST$ 指令的两个操作数是一样的，用于判断是小于零，等于零，还是大于零

关于条件码设置的具体细节（设置了哪些条件码），我们可以不用关注，因为这不重要，重要的是基于条件码所产生的条件控制才是我们应当关注的重点

访问条件码

条件码不会直接读取，常用的使用方式有三种：

将条件码的组合设置某个字节为 $0$ 或者 $1$
根据条件码跳转到程序的某个其他部分
根据条件码来传送数据

下面我们分别介绍这三者的使用

字节设置

我们可以用一整组 $\rm SET$ 指令来对某个字节设置成 $0$ 或者 $1$ ，指令当中的后缀指的是不同的条件，而不是像之前那样表示数据的大小

$\rm SET$ 指令的目的操作数是低位单字节寄存器或者一个字节的内存地址，而对于寄存器而言，为了得到一个 $32$ 位或 $64$ 位的结果，我们必须对高位进行清零

具体指令如下：

`Command`	`Synonyms`	`Effect`	`Condition`
$sete\ D$	$setz$	$D\gets ZF$	`相等、零`
$setne\ D$	$setnz$	$D\gets\ ZF$	`不等、非零`
$sets\ D$		$D\gets SF$	`负数`
$setns\ D$		$D\gets\ SF$	`非负数`
$setg\ D$	$setnle$	$D\gets\sim(SF \oplus OF)\And ZF$	`大于（有符号 > ）`
$setge\ D$	$setnl$	$D\gets\sim(SF \oplus OF)$	`大于等于（有符号 >= ）`
$setl\ D$	$setnge$	$D\gets SF \oplus OF$	`小于（有符号 < ）`
$setle\ D$	$setng$	$D\gets (SF \oplus OF)\vee ZF$	`小于等于（有符号 <= ）`
$seta\ D$	$setnbe$	$D\gets \sim CF\And ZF$	`超过（无符号 > ）`
$setae\ D$	$setnb$	$D\gets \sim CF$	`超过或相等（无符号 >=）`
$setb\ D$	$setnae$	$D\gets CF$	`低于（无符号 < ）`
$setbe\ D$	$setna$	$D\gets CF\vee ZF$	`低于或相等（无符号 <= ）`

在实际的汇编代码中，我们并不需要关注这些是如何推导的，我们只需要知道根据什么条件设置了哪个位置的值即可

举个例子：

int comp(data_t a, data_t b)
# a in %rdi, b in %rsi

comp:
  cmpq    %rsi, %rdi    # compare a : b
  setl    %al           # set low-order byte of %eax
  movzbl  %al, %eax     # clear rest of %eax
  ret

注意到，汇编代码中只是用 setl 指令根据 $a$ 与 $b$ 的值设置了 %al 的值，我们并不需要关注标志位的情况

条件跳转

跳转指令会导致程序的执行切换到一个全新的位置，跳转的目的地通常用一个标号 label 指明，比如：

  jmp .L1
  movq
.L1
  pushq

在产生目标代码文件时，编译器会确定所有带标号的指令的地址，也就是将跳转目标作为跳转指令编码的一部分进行考虑

下面给出不同的跳转指令，总共分为无条件跳转和条件跳转

`Command`	`Synonyms`	`Condition`	`Description`
$jmp\ Lable$		`无`	`直接跳转（直接跳转到以寄存器的值为地址的地方）`
$jmp\ *Operand$		`无`	`间接跳转（以寄存器的值作为地址再次跳转）`
$je\ Lable$	$jz$	$ZF$	`相等、零`
$jne\ Lable$	$jnz$	$\sim ZF$	`不相等、非零`
$js\ Lable$		$SF$	`负数`
$jns\ Lable$		$\sim SF$	`非负数`
$jg\ Lable$	$jnle$	$\sim(SF \oplus OF)\And ZF$	`有符号大于`
$jge\ Lable$	$jnl$	$\sim(SF \oplus OF)$	`有符号大于等于`
$jl\ Lable$	$jnge$	$SF \oplus OF$	`有符号小于`
$jle\ Lable$	$jne$	$(SF \oplus OF)\vee ZF$	`有符号小于等于`
$ja\ Lable$	$jnbe$	$\sim CF\And ZF$	`无符号超过`
$jae\ Lable$	$jnb$	$\sim CF$	`无符号超过或等于`
$jb\ Lable$	$jnae$	$CF$	`无符号低于`
$jbe\ Lable$	$jna$	$CF\vee ZF$	`无符号低于或等于`

$jmp$ 为无条件跳转，分为直接跳转和间接跳转两种

直接跳转是以标号作为跳转目标，就如上面所演示的那样

间接跳转以寄存器或内存当中的某个值作为跳转目标，通常写法带有 *

例如：

jmp *%rax 以寄存器 %rax 的值作为跳转目标；jmp *(%rax) 以寄存器 %rax 的值作为地址，以该地址所对应的值为跳转目标

需要说明的是，只有无条件跳转才可以间接跳转，有条件跳转不能间接跳转

关于跳转指令的编码，规则为：以目标指令地址与跳转指令后面那条指令的地址之间的差值作为编码

基于条件跳转实现条件分支

对于 C 语言当中的 if-else 语句，其通用形式如下：

if(test-expr)
    then-statement
else
    else-statement

这里的 test-expr 是一个整数表达式，其值只有零（解释为假）或非零（解释为真），下面的两条分支语句 then-statement 和 else-statement 只会执行一个

对于这种形式，汇编通常会产生如下代码，我们用 C 语言来描述其程序控制流

t = test-expr
if(!t)
    goto false;
	then-statement
    goto done;
false:
	else-statement
done:

也就是说，汇编器会为 then-statement 和 else-statement 生成各自的代码块，但只会执行一个

举个例子，考虑如下代码：

int test(int x, int y)
{
	int result = 0;
	if (x > y)
		result = x - y;
	else
		result = y - x;
	return result;
}

我们将其汇编代码翻译为等效的 C 语言代码，如下：

int test_goto(int x, int y)
{
	int result = 0;
	bool t = x > y;
	if (!t)
		goto x_g_y;
	result = y - x;
    return result;
x_g_y:
	result = x - y;
	return result;
}

条件传送

我们前面介绍过 $MOV$ 类指令，那是无条件传送指令，我们在此给出条件传送的版本

`Command`	`Synonyms`	`Condition`	`Description`
$cmove\quad S,R$	$cmovz$	$ZF$	`相等、零`
$cmovne\quad S,R$	$cmovnz$	$\sim ZF$	`不相等、非零`
$cmovs\quad S,R$		$\sim SF$	`负数`
$cmovns\quad S,R$		$\sim SF$	`非负数`
$cmovg\quad S,R$	$cmovnle$	$\sim(SF \oplus OF)\And ZF$	`有符号大于`
$cmovge\quad S,R$	$cmovnl$	$\sim(SF \oplus OF)$	`有符号大于等于`
$cmovl\quad S,R$	$cmovnge$	$SF \oplus OF$	`有符号小于`
$cmovle$	$cmovng$	$(SF \oplus OF)\vee ZF$	`有符号小于等于`
$cmova$	$cmovnbe$	$\sim CF\And ZF$	`无符号超过`
$cmovae$	$cmovnb$	$\sim CF$	`无符号超过或等于`
$cmovb$	$cmovnae$	$CF$	`无符号低于`
$cmovbe$	$cmovna$	$CF\vee ZF$	`无符号低于或等于`

条件传送的源操作数为寄存器或内存地址，目的操作数为寄存器。条件传送的源和目的地可以是 $16$ 位，$32$ 位，$64$ 位，但不支持单字节传送（而无条件传送指令则会显式指定大小）

基于条件传送实现条件分支

需要事先说明的是，基于条件传送的实现应用场景十分有限

处理器通过使用流水线 pipelining 设计来获取高性能，这要求能够事先确定要执行的指令序列，这样能够保证流水线中充满了指令

在遇到分支时，处理器会猜测一条路线，将该路线的指令全部加载到流水线中。显然如果猜测失败则会相应的时间惩罚，这便是条件控制实现的问题

如何确定分支预测错误的惩罚

设预测错误的概率为 $p$ ，如果没有预测错误所需时间为 $T_{ok}$ ，预测错误的处罚为 $T_{mp}$

因此，代码的平均执行时间为：$T_{avg}(p)=(1-p)T_{ok}+p(T_{ok}+T_{mp})=T_{ok}+pT_{mp}$

如果已知 $T_{ok}$ （预测可靠）和 $T_{ran}$ （预测随机，$p=0.5$），我们要确定 $T_{mp}$

将其带入得：$T_{ran}=T_{ok}+0.5T_{mp}$ ，所以有 $T_{mp}=2(T_{ran}-T_{ok})$

基于条件传送是指，处理器会对两条支路均进行计算，最后通过判断来确定该返回哪个值（此汇编代码由编译器生成）

还是上面的例子，基于条件传送生成的汇编代码对应的 C 代码如下：

int test_goto(int x, int y)
{
	int rval = x - y;
	int eval = y - x;
	int test = x > y;
	if (!test)//当条件不满足是返回eval
		rval = eval;
	return rval;
}

更一般地，我们考虑下面条件和赋值表达式的通用形式

1	`v = test-expr ? then-statement : else-statement`

基于条件控制的汇编器会得到如下代码：

t = test-expr;
if(!t)
    goto false;
    v = then-statement;
	goto done;
false:
	v = else-statement;
done:

而基于条件传送的汇编器会得到如下代码：

v = then-statement;
ve = else-statement;
t = test-expr;
if(!t)
    v = ve;

在开头已经说明的是，条件传送的应用场景十分有限，如果 then-expr 和 else-expr 需要做大量的计算，那么当条件不满足时，所作出的工作也就白费了，因此哪怕冒着预测错误招致的处罚，编译器也会更倾向于生成基于条件跳转的条件分支指令

循环

do-while 循环

do-while 语句的通用形式如下：

1
2
3

do
  body-statement
  while(test-expr);

代码首先会执行一遍 body-statement ，然后对 test-expr 求值，如果结构非零，则继续循环

将其汇编语言翻译为等价的 C 语言形式如下：

loop:
  body-statement
  t = test-expr;
  if(t)
    goto loop;

while 循环

while 循环语句的通用形式如下：

1 2	`while(test-expr) body-statement`

与 do-while 不同的是，while 循环会先执行一次条件判断，此时就有可能直接结束循环，在此给出两种其翻译方法

第一种被称为 jump-to-middle 策略，它首先执行一次无条件跳转，到达循环的底部进行判断，此后再依据判断结果决定是否循环

  goto test;
loop:
  body-statement;
test:
  t = test-expr;
  while(t)
    goto loop;

第二种翻译方法被称为 guarded-do 策略。这种策略首先使用条件分支进行一次判断，如果成立的话则转为 do-while 循环，不成立的话直接跳过

  t = test-expr;
  if(!t)
    goto done;
loop:
  body-statement;
  t = test-expr;
  if(t)
    goto loop;
done:

实际上，GCC 编译器会更偏向于使用 guarded-do 策略，jump-to-middle 策略虽然更容易阅读，但是由于会多执行一次跳转指令，因此相应的开销更大

for 循环

for 循环的通用形式如下：

1 2	`for(init-expr; test-expr; update-expr) body-statement`

本质上，这个代码与以下的 while 循环等价

init-expr;
while(test-expr)
{
  body-statement;
  update-expr;
}

采取 jump-to-middle 策略如下：

``cpp init-expr; goto test; loop: body-statement; update-expr; test: t = test-expr; while(t) goto loop;

采取 *guarded-do* 策略则是：
```cpp
  init-expr;
  t = test-expr;
  if(!t)
    goto done;
loop:
  body-statement;
  update-expr;
  t = test-expr;
  if(t)
    goto loop;
done:

switch 语句

switch 可以通过一个整数索引进行多重分支，通常通过跳转表 jump table 来实现

相比于用很长的 if-else ，用跳转表的优点在于只需要根据输入值进行一次跳转而不需要进行多次判断，效率更高

考虑如下函数：

int f(int x)
{
    int val = 0;
    switch(x)
    {
        case 1:
            val = 2;
            break;
        case 5: 
            val = 10;
            break;
        default:
            val = -1;
    }
    return val;
}

x 的有效值为 $1$ 和 $5$，但由于跳转表的实现是一个数值，因此跳转表需要包含的下标为 $1$ 到 $5$ ，还需要加上 default ，因此跳转表一共需要 $6$ 个表项

下面是用 C 语言描述汇编代码的结果：

int f(int x)
{
    int val = 0;

    // 使用跳转表实现 switch-case 语句
    static void *jump_table[] = {
        &&default_case, &&L1, &&default_case,
        &&default_case, &&defaule_case, &&L2
    };

    // 根据 x 的值跳转到不同的位置
    if (x <= 5)
        goto *jump_table[x];
    else // 默认分支
        goto default_case;

L1:
    // case 1 处理逻辑
    val = 2;
    goto return_val;

L2:
    // case 5 处理逻辑
    val = 10;
    goto return_val;

default_case:
    // 默认处理逻辑
    val = -1;
    goto return_val;

return_val:
    return val;
}

在 C 语言中，&& 用来表示一个标签，这个标签实际上是一个内存地址，类型为 void*

可以看到，在跳转表中，下标为 1 和 5 的位置会跳到 L1 和 L2 ，其余的全部跳到 default_case

对应汇编代码如下：

# x in %rdi
f:
    # 跳转表实现 switch-case 语句
    cmpq    $5, %rdi                # 比较 x 是否小于等于 5
    ja      .L3                     # 如果大于 5，跳转到标记点 L3
    jmp     *.jump_table(,%rdi,8)   # 通过计算跳转表中的偏移量和跳转到对应标记点

.L2:
    movl    $10, -8(%rbp)   # 如果 x 等于 5，执行相应的逻辑
    jmp     .L4             # 跳转到返回值处理部分

.L1:
    movl    $2, -8(%rbp)    # 如果 x 等于 1，执行相应的逻辑
    jmp     .L4             # 跳转到返回值处理部分

.L3:
    movl    $-1, -8(%rbp)   # 默认情况，执行相应的逻辑
.L4:
    movl    -8(%rbp), %eax  # 将返回值从栈中取出并存储到寄存器 eax 中
    leave                   # 恢复堆栈
    ret                     # 返回函数调用位置

.section        .rodata
    .align 8             # 向 8 对齐        
.jump_table:
    .quad   .L3          # 标记点 default_case 的地址
    .quad   .L1          # 标记点 L1 的地址
    .quad   .L3          # 标记点 default_case 的地址
    .quad   .L3          # 标记点 default_case 的地址
    .quad   .L2          # 标记点 L2 的地址

跳转表的引用采用的是间接引用 jmp *.jump_table(,%rdi,8) ，%rdi 为索引 x，.jump_table 为跳转表表头

跳转表声明在 .rodata （只读数据 read only data）的目标代码中。这当中有 $5$ 个标号，每个标号都代表一个地址，大小与四字相同

过程

过程提供了一种用于封装代码方式，用一组指定的参数和一个可选的返回值实现某种功能，然后我们可以在函数的任何部分调用该过程

在不同的语言中，过程的表现形式各有不同：函数 function 、方法 methor 、子例程 subroutine 、处理函数 handler 等，这些均可以统称过程

假设过程 $P$ 调用过程 $Q$ ，$Q$ 执行完之后返回 $P$ ，为了实现过程的机器级支持，需要提供以下机制：

传递控制。当进入过程 $Q$ 时，程序计数器需要设置为过程 $Q$ 的起始地址；在返回时，程序计数器需要设置为过程 $P$ 中调用过程 $Q$ 后面那条语句的地址
传递数据。$P$ 需要向 $Q$ 传递一个或多个数据，$Q$ 需要向 $P$ 返回至多一个数据
分配和释放内存。在开始时，可能需要为 $Q$ 的局部变量分配空间；在返回时，又需要释放这些空间

下面，我们按照传递控制、传递数据、内存管理的顺序分别介绍

控制转移

运行时栈

在过程 $P$ 调用过程 $Q$ 的例子中，我们发现当 $Q$ 执行时，$P$ 以及所有向上追溯到 $P$ 的过程均处于被挂起的状态。另一方面，当执行 $Q$ 时，我们需要为其分配空间用于存储局部变量，或者调用下一个过程。当 $Q$ 返回时，我们需要将 $Q$ 所占用的空间全部释放掉，此时回到调用 $Q$ 的上一级过程

上述这整个调用过程，恰好可以用栈来描述。当过程 $P$ 执行时，控制流处于 $P$ 所在的区域，当调用 $Q$ 时，相当于将 $Q$ 压入 $P$ 的上方，此时控制流处于 $Q$ 所在的区域。因此我们将这个栈称为运行时栈

x86-64 的栈向低地址增长，因此栈顶在低地址，栈底在高地址。栈指针 %rsp 指向栈顶，我们可以用 pushq 或 popq 向栈顶压入或弹出元素

当执行一个过程所需的空间超出寄存器所能存放的大小时，就需要在栈上分配空间，此空间被称为该过程的栈帧（如果一个过程不需要栈帧，那么就不会分配），需要注意的是，栈帧一般都是定长的，在过程开始时通过以下指令分配好：

1	`subq $16, %rsp # 分配 16 字节的栈帧`

而过程结束时则通过以下指令回收：

1	`addq $16, %rsp # 回收栈帧`

当前正在执行的过程的栈帧总是位于栈顶，栈帧主要是用于保存该过程的相关信息。当过程 $P$ 调用过程 $Q$ 时，会先将返回地址压入 $P$ 的栈帧中，表明当 $Q$ 返回时需要从哪里开始继续执行代码（通常是调用语句的下一条语句的地址）。这个返回地址是过程 $P$ 栈帧的一部分，因为它指明了过程 $P$ 的相关属性

而对于过程 $Q$ 而言，则会拓展当前栈的边界（向下拓展），用于分配其栈帧所需要的空间。在这个空间中，过程可以保存寄存器的值、分配局部变量、为其他调用过程分配参数。对于一个栈帧的通用结构，如下图所示：

也就是说，处于栈顶的栈帧总是当前正在执行的过程

转移控制

将控制从过程 $P$ 转移到过程 $Q$ 只需要简单地将程序计数器的值设为 $Q$ 起始位置的地址即可。在 $Q$ 返回的时候，处理器必须知道在 $P$ 中继续执行指令的地址

在 x86-64 中，这个过程是通过一组指令 $call\quad Q$ 和 $ret$ 执行的

$call\quad Q$ 会将地址 $A$ 压入栈中，并将程序计数器的值设为 $Q$ 的起始地址。这里的 $A$ 被称为返回地址，也就是 $call$ 指令后面的那条指令的地址

$ret$ 会将返回地址 $A$ 从栈中弹出，并将程序计数器设置为 $A$

下面给出两条指令的一般形式：

`Command`	`Description`
$call\quad Label$	`过程调用（直接）`
$call\quad *Operand$	`过程调用（间接）`
$ret$	`从调用过程中返回`

$call$ 指令的目标，为被调用过程的起始地址。同跳转一样，可以是直接的（用已确定地址的标号），也可以是间接的（从寄存器或内存中读取）

需要说明的是：在返回时，返回值保存在寄存器 %rax 中

数据传送

当调用一个过程时，除了要将控制传递外，还需要传递相应的参数，而该过程也可能会返回相应的参数。在 x86-64 中，数据的传送大多是通过寄存器实现的

在访问信息那里我们看到，$16$ 个寄存器中有专门用于传递参数的，分别为：

`Parameter Order`	`Register`
`1`	`%rdi`
`2`	`%rsi`
`3`	`%rdx`
`4`	`%rcx`
`5`	`%r8`
`6`	`%r9`

说明：这些寄存器分别可用 $64$、$32$、$16$、$8$ 位的，这里并没有列出

如果一个过程有超过 $6$ 个参数，那么超过的部分就需要通过栈来传递。假设过程 $P$ 调用过程 $Q$ ，这当中需要传递 $n\ (n\gt 6)$ 个参数，那么 $P$ 的栈帧必须要存储第 $7$ 到第 $n$ 号参数

如上图所示，$P$ 需要将参数 $1\sim 6$ 放入寄存器中，把参数 $7\sim n$ 放到自己的栈帧中，而参数 $7$ 位于栈顶。通过栈传递参数时，所有的数据大小都需要按 $8$ 的倍数对齐。参数复制完毕后就可以将控制转移到 $Q$ 了

相应地，如果 $Q$ 也调用了另一个超过 $6$ 个参数的过程，那么它也需要在自己的栈帧中为超出 $6$ 个参数的部分分配空间，这对应图中的「参数构造区」

内存管理

我们知道在过程的开始时，会通过 add 指令分配栈帧，在过程结束时会通过 sub 指令回收栈帧，但我们还需要细化这个过程

栈上的局部存储

数据除了放置在寄存器中，还会有放置内存（函数对应的栈帧中）当中的可能，情况如下：

寄存器空间无法存储所有的本地变量
对一个局部变量使用取地址 & ，得到的指针必须存储与内存中
当局部变量是数组或结构时，需要通过指针或引用才能访问，因此必须存储与内存中

举个例子

void foo(int x) {
    int* px = &x;
    return;
}

该函数对应汇编代码为“

foo:
    pushq   %rbp          # 将当前帧的底部指针压入栈中
    movq    %rsp, %rbp    # 设置新的帧的底部指针为当前栈顶指针

    leaq    -4(%rbp), %rax   # 将x的地址存储在rax寄存器中
    movq    %rax, -8(%rbp)   # 将x的地址存储到px变量中

    nop     # 空操作，用于占位符
    popq    %rbp          # 恢复上一帧的底部指针
    ret                  # 返回

可以看到，%rax 的地址存储在内存当中，也就是说 px 是存储在内存而不是寄存器中

存储局部变量的区域在栈帧中被标记为「局部变量」

寄存器中的局部存储

我们知道，寄存器是唯一被所有过程共享的资源。虽然在过程的相互调用中，只会有一个过程访问寄存器，但我们需要保证当一个过程调用另一个过程时，被调用者不会覆盖调用者稍后会使用的资源

为此，x86-64 规定了部分寄存器分为调用者保存和被调用者保存

寄存器 %rbx、%rbp 和 %r12 ~ %人5 被划分为被调用者保存寄存器

当过程 $P$ 调用过程 $Q$ 时，$Q$ 需要保证这些寄存器的值从 $Q$ 回到 $P$ 与调用 $Q$ 之前的值一样。而过程 $Q$ 保证一个寄存器的值不变，要么不去改变它，要么在自己的栈帧中保存该寄存器的值，然后在返回时弹出该值（这样的话 $Q$ 就可以随意修改该寄存器了）。若寄存器的值被压入栈帧中，则会被标记为「被保存的寄存器」

其余所有寄存器，除了栈指针 %rsp 外，都被划分为调用者保存寄存器，这意味者任何调用过程均可以修改这些寄存器的值，因此它们会被调用者保存。可以这样理解「调用者保存」：当过程 $P$ 调用过程 $Q$ 时，为了实现 $Q$ 可以任意修改该寄存器的值，将该寄存器的值保存就是 $P$ 的责任

数组 & 结构 & 联合 & 对齐 & 变长栈帧 & 缓冲区溢出

数组

当声明数组：T D[R][C]

其元素 D[i][j] 在内存当中的地址为：

\[ \&D[i][j]=x_0+L(C\times i+j) \]

其中 $x_0$ 为数组起始地址，$L$ 为类型 D 的大小

假设我们定义了一个 $5\times 3$ 的数组，$x_0,\ i,\ j$ 分别存储在寄存器 %rdi, %rsi, %rdx ，当需要访问元素 D[i][j] 时，有：

1
2
3

leaq  (%rsi, %rsi, 2),  %rax  # 计算 3i
leaq  (%rdi, %rax, 4),  %rax  # 计算 4 * 3i + x
movl  (%rax, %rdx, 4),  %eax  # 读取内存 M[x + 4(3 * i + j)]

结构

在不考虑内存对齐的情况下，结构当中的数据按照其定义顺序依次排列，例如：

struct rec
{
    int a;
    long b;
    char* c;
};

变量 rec val 当中各成员的偏移如下：

`menber`	`offset`
`val`	`0`
`val.a`	`0`
`val.b`	`4`
`val.c`	`4 + 8 = 12`

也就是说，变量 val 的地址与第一个成员变量的地址一样，往后的每个成员按前面成员的字节大小进行内存偏移

变量 val 的总大小为（64 位机器，不考虑内存对齐）：$4+8+8=20$

联合

联合允许用多种数据类型来引用同一个内存块，用联合声明的变量大小为最大字段的大小。考虑下面的声明：

struct st
{
    char c;
    int[2] i;
    double v;
};
struct un
{
    char c;
    int[2] i;
    double v;
};

字段偏移分别（考虑内存对齐）为：

`type`	`c`	`i`	`v`	`size`
`st`	`0`	`4`	`16`	`24`
`un`	`0`	`0`	`0`	`8`

后面内存对齐部分会解释为什么 v 是以 16 开始

不同于结构的是，该联合的大小仅为 $8$ 字节，并且允许三种不同类型访问同一块内存。通常，这种行为是不安全的，一种联合的应用场景是，我们事先已知两个不同字段的使用是互斥的，那么将其声明为联合而不是结构则可以有效节约内存

举个例子，如果我们想实现一个二叉树，满足：每个叶子节点都有两个 double 数据；每个内部节点都有指向两个孩子的指针而没有数据

在此种定义下，每个节点的数据和指针的使用就是互斥的，我们考虑将其声明为：

union node
{
    struct {
        union node* left;
        union node* right;
    }internal;
    double data[2];
};

此种定义下的大小为 $16$ ，如果单纯将其声明为结构，那么大小为 $32$ ，节约了一般的字节

这么声明有一个问题是，我们没办法确定一个节点到达是叶子还是内部节点，因此在其基础上添加一个枚举类型来表示：

typedef enum { LEAF, INTERNAL } nodetype;
struct node
{
    nodetype type;
    union {
        struct {
            union node* left;
            union node* right;
        }internal;
        double data[2];
    }info;
};

这样，一个节点的大小变为 $24$ ，在这个例子中单个节点内存节省了 $25\%$

联合还可以用来访问不同数据类型的位模式，比如：

union  
{
    unsigned long a;
    double b;
}val;

这样对于变量 val 而言，其位模式我们可以既可以从 unsigoned long 的角度视之，也可以从 double 的角度视之

一个应用场景是是用于判断当前机器是大端存储还是小端存储，如：

void fun()
{
    union { int a; char b; } val;
    val.a = 0x11223344;
    //高位在前为大端，低位在前为小端，11为高位
    if(val.b == 0x11) printf("big endian");
    else printf("little endian");
}

对齐

数据在内存当中的对齐原则为：任何 $K$ 字节的基本对象的地址必须是 $K$ 的倍数，基于此，基本类型的对齐数分别为：

`type`	`align`
`char`	`1`
`short`	`2`
`int, float`	`4`
`char*, long, double`	`8`

对于结构而言，其大小必须对齐为最大基本成员大小的整数倍

举个例子：

struct S1
{
    int a;
    char b;
    int c;
};

偏移量为：a -- 0、b -- 4、c -- 8

我们发现 b 的后面填补了三个字节，这是因为需要保证 c 的偏移量为其大小的整数倍，也就是需要对齐 $8$

再来一个：

struct S2
{
    long long a;
    S1 b;
};

该对象大小为 $24$，a 的偏移量为 $0$ ，b 按照其最大成员的大小的倍数进行对齐（也就是 $4$），此时大小计算得到 $20$

然后，S2 对象整体的大小需要与最大成员的大小的倍数进行对齐，其成员有：a -- align: 8、b -- align: 4 ，因此需要与 $8$ 对齐，整体大小为 $24$

到此为止我们便引出了一个问题：该如何排列结构体内部的成员使得整体所占空间最小？

对于成员均为 $2$ 的幂次大小的结构体，一个有效的策略是，我们按照其大小降序的顺序排列成员，可以使得整体所占内存最小

变长栈帧

我们目前见过的代码，在编译期就可以预先确定栈帧的大小，但有些函数的局部存储需要在运行期才能确定，比如使用 malloc 申请的内存

这个时候固定长度的栈帧就不足以满足需求了，因此 x86-64 允许使用变长栈帧

在 x86-64 中，用寄存器 %rbp 作为帧指针 frame pointer（也被称为基指针 base pointer）

当使用帧指针时，必须把 %rbp 原先的指保存在栈帧中，因为这是被调用者保存寄存器。然后在整个执行过程中，保证 %rbp 都指向固定位置，用局部变量相对于 %rbp 的偏移量来引用内存

push rbp      # 保存调用者的rbp寄存器值
mov rbp, rsp  # 设置当前函数的rbp寄存器为当前堆栈指针
sub rsp, 4    # 分配4个字节的局部变量空间

...

mov rsp, rbp # 恢复堆栈指针
pop rbp      # 恢复调用者的rbp寄存器值
ret          # 返回函数调用

在上面的代码中，首先将 %rbp 当前值压入栈中予以保存，然后将当中栈指针的值赋给 %rbp，之后是对可以确定大小的局部变量分配栈帧

在省略的代码中，可以用局部变量相对于 %rbp 的偏移量来访问内存，例如：movq -8(%rbp), %rax

在函数的结尾，我们首先需要将栈指针 %rsp 恢复到最初的值，也就是将 %rbp 赋值给 %rsp（%rbp 的值始终不发生改变），然后，我们需要从栈中弹出最开始保存的 %rbp 的值还给 %rbp ，最后再返回

缓冲区溢出

在过程 $P$ 调用过程 $Q$ 时，$P$ 会将返回地址 $add$（调用指令的下一条指令的地址）压入到自己的栈帧中，然后控制转移到 $Q$

$Q$ 的栈帧处于低地址，返回地址 $add$ 处于高地址，如果 $Q$ 调用了某个不安全的函数，导致覆盖了 $P$ 的返回地址 $add$，此时程序便无法正常运行，这被称为缓冲区溢出 buffer overflow

这种不安全的函数在 C 语言中有很多，例如：get、strcpy、strcat、scanf、sprintf 这些，它们都没有范围限制，很容易就会导致溢出风险

缓冲区溢出更致命的错误是会让程序执行一个它原本不愿意执行的程序，这也是一种最常见的网络攻击的手段。攻击者可以给程序输入一个字符串，这个字符串包含一些可执行程序的字节编码，这被称为攻击代码 exploit code，另外的一些字节会用一个指向攻击代码的指针替换原本的返回地址，那么执行 ret 指令就会跳转到攻击代码，这对于系统而言风险极高

往后，我们介绍一些在 Linux 中，GCC 所提供的来对抗这种情况的机制

栈随机化

为了在系统中插入指向攻击代码的指针，那么必须要知道攻击代码的地址。在过去程序的栈地址非常容易预测

栈随机化的思想是使得栈在每次程序运行时都有所不同。也就是机器运行同样的代码，但每次的地址都不一样。具体实现为当程序的开始时在栈上随机分配 $0\sim n$ 个字节的空间而不使用它，这样程序每次执行时后续的栈空间也就发生了变化

这里有一个矛盾的问题是，$n$ 必须足够大以至于保证获得足够的空间变化，$n$ 又必须足够小以保证不至于浪费过多的空间

这种机制只能在一定程度上阻止缓冲区溢出，因为攻击者可以通过暴力穷举的方式来猜出程序真实的执行地址（具体做法为在攻击代码前插入很粗糙的 nop 指令，该指令只会让程序计数器加一而不产生其他任何影响）

栈破坏检测

我们可以在栈中随机插入特殊的金丝雀 canary 值。在程序执行完后检测金丝雀值，如果发生改变则程序终止

金丝雀的插入与检测代码如下：

# 插入
movq %fs:40, %rax
movq %rax, 8(%rsp)

...

# 检查
movq 8(%rsp), %rax
xorq %fs:40, %rax

首先从内存当中读取一个值，将其放入到 8(%rsp) 的位置。金丝雀值的采用 %fs:40 的寻址，这是段寻址 segmented addressing，在现代操作系统中已经很少见了

在检查时，通过 xor 指令，如果两个数相同，那种该指令得到的结果为 $0$ ，此时可以正常返回

限制代码可执行区域

在内存中，将保存编译器产生的代码的那段内存设定为可执行，其余部分限制为只允许读和写，这样便可以限制程序的执行区域，避免程序执行意外的代码

浮点

AVX2 指令集

在 x86 架构的处理器中，指令集 $\rm AVX2$ 可以执行高速浮点运算，$\rm AVX2$ 是 $\rm AVX$ Advanced Vector Extension 的第二个版本

x86 和 x86-64 的区别：这两者都是指 Intel 公司的 CPU 架构，区别在于地址总线的位数和支持的内存容量

最开始的 x86 是 $32$ 位地址总线的，因此其内存只能访问 $4GB$

而 x86-64 是 x86 的 $64$ 位版本，有 $64$ 位地址总线，可寻址范围达 $2^{64}=16EB$ exabytes

现代计算机通常采用 x86-64 架构，也就是应用程序为 64 位，但 32 位的程序依然可以在 x86-64 上运行

指令集 $\rm AVX2$ 提供了 $16$ 个 $256$ 位的寄存器，分别命名为 %ymm0 ~ %ymm15。当对标量数据进行操作时，这些寄存器只保存浮点数。

ymm 用于保存 $32$ 位自己，xmm 可以访问低 $16$ 个字节

`Register`	`Register`	`Effect`
$ymm0$	$xmm0$	`1st FP arg.返回值`
$ymm1$	$xmm1$	`2nd FP 参数`
$ymm2$	$xmm2$	`3rd FP 参数`
$ymm3$	$xmm3$	`4th FP 参数`
$ymm4$	$xmm4$	`5th FP 参数`
$ymm5$	$xmm5$	`6th FP 参数`
$ymm6$	$xmm6$	`7th FP 参数`
$ymm7$	$xmm7$	`8th FP 参数`
$ymm8$	$xmm8$	`调用者保存`
$ymm9$	$xmm9$	`调用者保存`
$ymm10$	$xmm10$	`调用者保存`
$ymm11$	$xmm11$	`调用者保存`
$ymm12$	$xmm12$	`调用者保存`
$ymm13$	$xmm13$	`调用者保存`
$ymm14$	$xmm14$	`调用者保存`
$ymm15$	$xmm15$	`调用者保存`

需要说明的是，xmm 寄存器主要用于 $\rm SSE$ Streaming SIMD Extension 指令集，ymm 则是 $AVX2$ 指令集引入的，往后我们说明的对象统一为 $\rm AVX2$ 指令集

$AVX2$ 指令集支持向量指令和标量指令

标量指令是对单个数据值进行操作的指令，对象通常是正数和浮点数，操作包括加减乘除等基本运算以及比较、转换、存储的基本操作
向量指令是同时对多个数据值进行操作的指令，也被称为 $\rm SIMD$ Single Instruction, Multiple Data，向量指令是将多个标量合并为一个指令，以提升运行效率

浮点操作

当对标量数据进行操作时，由于只会使用到 $128$ 位字节，因此不论是整数还是浮点数，均用 xmm 寄存器来进行存取

传送

下面给出从 xmm 寄存器到内存或从内存到 xmm 寄存器的传送浮点数的相关指令。由于引用内存的指令一定是标量指令，因此它们的操作对象只能是标量而不是向量。数据要么保存在 xmm 寄存器中（表中用 $\rm X$ 表示），要么保存在内存当中（表中用 $M_{32}$ 或 $M_{64} 表示$）

需要说明的是，无论是否对齐，这些指令都能正确的执行，但 $32$ 为数据最好对齐 $4$，$64$ 位数据最好对齐 $8$

`Command`	`src`	`dest`	`Description`
`vmovss`	$M_{32}/X$	$X/M_{32}$	`传送单精度数值`
`vmovsd`	$M_{64}/X$	$X/M_{64}$	`传送双精度数值`
`vmovaps`	$X$	$X$	`传送对齐的封装好的单精度数值`
`vmovapd`	$X$	$X$	`传送对齐的封装好的双精度数值`

vmovss/vmovsd 指令只能在寄存器与内存当中进行传送，不能在寄存器与寄存器或内存与内存当中传送。当在寄存器与寄存器之间传送数据时，编译器使用 vmovaps/vmovapd 指令。指令中的 a 表示 aligned，也就是数据要求对齐

转换

当把浮点数向整数转换时，会执行截断 truncation 操作，将值向零舍入

数据转换的指令分为双操作数和三操作数，双操作数用于浮点转整数，三操作数用于整数转浮点

双操作数

`Command`	`src`	`dest`	`Description`
`vcvttss2si`	$X/M_{32}$	$R_{32}$	`将单精度截断为整数`
`vcvttsd2si`	$X/M_{64}$	$R_{32}$	`将双精度截断为整数`
`vcvttss2siq`	$X/M_{32}$	$R_{64}$	`将单精度截断为四字整数`
`vcvttsd2siq`	$X/M_{64}$	$R_{64}$	`将双精度截断为四字整数`

表中 $R_{32}$ 表示 $32$ 为通用寄存器，如 $eax，$R_{64}$ 表示 $64$ 通用寄存器，如 %rax

三操作数

`Command`	`src1`	`src2`	`dest`	`Description`
`vcvtsi2si`	$M_{32}/R_{32}$	$X$	$X$	`整数转为单精度数`
`vcvtsi2sd`	$M_{32}/R_{32}$	$X$	$X$	`将整数转为双精度数`
`vcvtsi2ssq`	$M_{64}/R_{64}$	$X$	$X$	`将四字整数转为单精度数`
`vcvtsi2sdq`	$M_{64}/R_{64}$	$X$	$X$	`将四字整数转为双精度数`

三操作数指令中，有两个源和一个目的。第一个源读自内存或通用寄存器，第二个源只影响高位字节，在这里我们直接将其忽略（设为 $X$），因此在实际的使用场景中，后两个操作数通常是一样的，例如：vcvtsi2sdq %rax, %xmm1, %xmm1

过程

xmm0 ~ xmm7 寄存器最多可以传递 $8$ 个参数，按照参数列表出现的顺序来使用这些寄存器，如果参数多余 $8$ 个则用栈来传递
xmm0 用于保存函数的返回值
所有 xmm 寄存器均为调用者保存，因此被调用者可以直接覆盖这些寄存器当中的任意一个

例如：函数声明 double f1(int x, double y, long z)

其中 x 放在 xmm0 中，y 放在 %rdi 中，z 放在 %rsi 中

使用浮点常数

与整数运输不同，$AVX2$ 浮点操作不能使用立即数作为操作数，因此编译器必须为所有的常量分配空间，然后从内存当中读入

具体看下面这个函数：

double f(double x)
{
    return 1.8 * x + 32.0;
}

汇编代码为：

f:
    movsd %xmm0, %xmm1     # 将参数x从xmm0寄存器移动到xmm1寄存器
    mulsd .LC0(%rip), %xmm1   # xmm1 = 1.8 * xmm1
    addsd .LC1(%rip), %xmm1   # xmm1 = xmm1 + 32.0
    ret                      # 返回结果
.LC0:
    .double 1.8             # 存储常数1.8
.LC1:
    .double 32.0            # 存储常数32.0

可以看到汇编代码中有两个标签 .LC0 和 .LC1 用来指示两个字面值在内存当中的地址（这两个字面值在内存当中以 double 的形式存储）

也就是说，这两个字面值是需要占用内存的

运算

下面的标量 $\rm AVX2$ 指令中，每条指令都有一个或两个源操作数，一个目的操作数。第一个源操作数可以是 xmm 寄存器或内存位置，第二个源操作数和目的操作数必须是 xmm 寄存器。每条指令分为单精度和双精度两种

`Single Precision`	`Double Precision`	`Effect`	`Description`
`vaddss`	`vaddsd`	$S_2+S_1\rightarrow D$	`浮点数加法`
`vsubss`	`vsubsd`	$S_2-S_1\rightarrow D$	`浮点数减法`
`vmelss`	`vmelsd`	$S_2\times S_1\rightarrow D$	`浮点数乘法`
`vdivss`	`vdivsd`	$S_2/S_1\rightarrow D$	`浮点数除法`
`vmaxss`	`vmaxsd`	$\max(S_2,S_1)\rightarrow D$	`浮点数最大值`
`vminss`	`vminsd`	$\min(S_2,S_1)\rightarrow D$	`浮点数最小值`
`sqrtss`	`sqrtsd`	$\sqrt{S_1}\rightarrow D$	`浮点数平方根`

$\rm AVX2$ 指令集还提供位级运算和比较运算

位级运算会更新整个 xmm 寄存器，对两个源寄存器的所有位均执行同样的操作

`Single Precision`	`Double Precision`	`Effect`	`Description`
`vxorps`	`vxorpd`	$S_2\oplus S_1\rightarrow D$	`位级异或`
`vandps`	`vandpd`	$S_2\And S_1\rightarrow D$	`位级与`

比较操作如下：

`Command`	`Based on`	`Description`
$vucomiss\ S1,S2$	$S2-S1$	`比较单精度数值`
$vucomisd\ S1,S2$	$S2-S1$	`比较双精度数值`

其中 $S_1$ 可以在 xmm 寄存器或内存中，$S_2$ 必须在 xmm 寄存器中

CSAPP

#CSAPP

CSAPP 第三章程序的机器级表示

https://nishikichisato.github.io/2023/04/15/CSAPP/程序的机器级表示/

Author

Nishiki Chisato

Posted on

April 15, 2023

Updated on

June 2, 2023

Licensed under

CSAPP 第二章信息的表示和处理 Previous

快速排序算法分析及其改进 Next

`Command`	`Effect`	`Description`
\(leaq\quad S,\ D\)	\(D\ \gets\ \&S\)	加载有效地址
\(INC\quad D\)	\(D\ \gets\ D+1\)	加 1
\(DEC\quad D\)	\(D\ \gets\ D-1\)	减 1
\(NEG\quad D\)	\(D\ \gets\ -D\)	取负
\(NOR\quad D\)	\(D\ \gets\ \sim D\)	取补
\(ADD\quad S,\ D\)	\(D\ \gets\ D+S\)	加
\(SUB\quad S,\ D\)	\(D\ \gets\ D-S\)	减
\(IMUL\quad S,\ D\)	\(D\ \gets\ D\times S\)	乘
\(XOR\quad S,\ D\)	\(D\ \gets\ D \oplus S\)	异或
\(OR\quad S,\ D\)	\(D\ \gets\ D\ \\|\ S\)	或
\(AND\quad S,\ D\)	\(D\ \gets\ D\ \&\ S\)	与
\(SAL\quad k,\ D\)	\(D\ \gets\ D<<k\)	左移
\(SHL\quad k,\ D\)	\(D\ \gets\ D<<k\)	左移，等同于 \(SAL\)
\(SAR\quad k,\ D\)	\(D\ \gets\ D>>_{A}k\)	算术右移
\(SHR\quad k,\ D\)	\(D\ \gets\ D>>_{L}k\)	逻辑右移

`Command`	`Effect`	`Description`
\(imulq\quad S\\mulq\quad S\)	\(S\times R[\%rax]\rightarrow R[\%rdx]:R[\%rax]\\S\times R[\%rax]\rightarrow R[\%rdx]:R[\%rax]\)	\(有符号全乘法\\无符号全乘法\)
\(cqto\)	\(符号拓展(R[\%rax])\rightarrow R[\%rdx]:R[\%rax]\)	\(转换为八字\)
\(idivq\quad S\\divq\quad S\)	\(R[\%rdx]:R[\%rax]\div S\rightarrow R[\%rax]\\R[\%rdx]:R[\%rax]\bmod S\rightarrow R[\%rdx]\)	\(有符号除法\\无符号除法\)

`Command`	`Synonyms`	`Effect`	`Condition`
\(sete\ D\)	\(setz\)	\(D\gets ZF\)	`相等、零`
\(setne\ D\)	\(setnz\)	\(D\gets\ ZF\)	`不等、非零`
\(sets\ D\)		\(D\gets SF\)	`负数`
\(setns\ D\)		\(D\gets\ SF\)	`非负数`
\(setg\ D\)	\(setnle\)	\(D\gets\sim(SF \oplus OF)\And ZF\)	`大于（有符号 > ）`
\(setge\ D\)	\(setnl\)	\(D\gets\sim(SF \oplus OF)\)	`大于等于（有符号 >= ）`
\(setl\ D\)	\(setnge\)	\(D\gets SF \oplus OF\)	`小于（有符号 < ）`
\(setle\ D\)	\(setng\)	\(D\gets (SF \oplus OF)\vee ZF\)	`小于等于（有符号 <= ）`
\(seta\ D\)	\(setnbe\)	\(D\gets \sim CF\And ZF\)	`超过（无符号 > ）`
\(setae\ D\)	\(setnb\)	\(D\gets \sim CF\)	`超过或相等（无符号 >=）`
\(setb\ D\)	\(setnae\)	\(D\gets CF\)	`低于（无符号 < ）`
\(setbe\ D\)	\(setna\)	\(D\gets CF\vee ZF\)	`低于或相等（无符号 <= ）`

`Command`	`Synonyms`	`Condition`	`Description`
\(jmp\ Lable\)		`无`	`直接跳转（直接跳转到以寄存器的值为地址的地方）`
\(jmp\ *Operand\)		`无`	`间接跳转（以寄存器的值作为地址再次跳转）`
\(je\ Lable\)	\(jz\)	\(ZF\)	`相等、零`
\(jne\ Lable\)	\(jnz\)	\(\sim ZF\)	`不相等、非零`
\(js\ Lable\)		\(SF\)	`负数`
\(jns\ Lable\)		\(\sim SF\)	`非负数`
\(jg\ Lable\)	\(jnle\)	\(\sim(SF \oplus OF)\And ZF\)	`有符号大于`
\(jge\ Lable\)	\(jnl\)	\(\sim(SF \oplus OF)\)	`有符号大于等于`
\(jl\ Lable\)	\(jnge\)	\(SF \oplus OF\)	`有符号小于`
\(jle\ Lable\)	\(jne\)	\((SF \oplus OF)\vee ZF\)	`有符号小于等于`
\(ja\ Lable\)	\(jnbe\)	\(\sim CF\And ZF\)	`无符号超过`
\(jae\ Lable\)	\(jnb\)	\(\sim CF\)	`无符号超过或等于`
\(jb\ Lable\)	\(jnae\)	\(CF\)	`无符号低于`
\(jbe\ Lable\)	\(jna\)	\(CF\vee ZF\)	`无符号低于或等于`

`Command`	`Synonyms`	`Condition`	`Description`
\(cmove\quad S,R\)	\(cmovz\)	\(ZF\)	`相等、零`
\(cmovne\quad S,R\)	\(cmovnz\)	\(\sim ZF\)	`不相等、非零`
\(cmovs\quad S,R\)		\(\sim SF\)	`负数`
\(cmovns\quad S,R\)		\(\sim SF\)	`非负数`
\(cmovg\quad S,R\)	\(cmovnle\)	\(\sim(SF \oplus OF)\And ZF\)	`有符号大于`
\(cmovge\quad S,R\)	\(cmovnl\)	\(\sim(SF \oplus OF)\)	`有符号大于等于`
\(cmovl\quad S,R\)	\(cmovnge\)	\(SF \oplus OF\)	`有符号小于`
\(cmovle\)	\(cmovng\)	\((SF \oplus OF)\vee ZF\)	`有符号小于等于`
\(cmova\)	\(cmovnbe\)	\(\sim CF\And ZF\)	`无符号超过`
\(cmovae\)	\(cmovnb\)	\(\sim CF\)	`无符号超过或等于`
\(cmovb\)	\(cmovnae\)	\(CF\)	`无符号低于`
\(cmovbe\)	\(cmovna\)	\(CF\vee ZF\)	`无符号低于或等于`

`Command`	`Effect`	`Description`
\(MOV \quad S,D\)	\(S\rightarrow D\)	传送
`movb\movw\movl\movq`		分别传送字、字节、二字、四字（从补码角度看待）
`movabsq`		传送四字（从无符号的角度看待）

`Command`	`Effect`	`Description`
\(MOVZ \quad S,R\)	\(零拓展(S)\rightarrow R\)	以零拓展进行传送
`movzbw\movzbl\movzwl\movzbq\movzwq`

指令	效果	描述
\(MOVS \quad S,R\)	\(符号拓展(S)\rightarrow R\)	以符号拓展进行传送
`movsbw\movsbl\movswl\movsbq\movswq\movslq`
`cltq`	\(符号拓展(\%eax)\rightarrow \%rax\)	将 `%eax` 符号拓展后的结果放到 `%rax` 中

`Command`	`Effect`	`Description`
\(pushq\quad S\)	\((R[\%rsp]-8)\rightarrow R[\%rsp]\\S\rightarrow M[R[\%rsp]]\)	将 `quad word` 压入栈
\(popq\quad D\)	\(M[R[\%rsp]]\rightarrow D\\(R[\%rsp]+8)\rightarrow R[\%rsp]\)	将 `quad word` 弹出栈

`Command`	`Base On`	`Description`
\(CMP\quad S_1,\ S_2\)	\(S_2-S_1\)	\(比较\)
`cmpb\cmpw\cmpl\cmpq`		`比较字节\字\双字\四字`
\(TEST\quad S_1,\ S_2\)	\(S_2\And S_1\)	\(测试\)
`testb\testw\testl\testq`		`测试字节\字\双字\四字`

`Command`	`Description`
\(call\quad Label\)	`过程调用（直接）`
\(call\quad *Operand\)	`过程调用（间接）`
\(ret\)	`从调用过程中返回`

`Register`	`Register`	`Effect`
\(ymm0\)	\(xmm0\)	`1st FP arg.返回值`
\(ymm1\)	\(xmm1\)	`2nd FP 参数`
\(ymm2\)	\(xmm2\)	`3rd FP 参数`
\(ymm3\)	\(xmm3\)	`4th FP 参数`
\(ymm4\)	\(xmm4\)	`5th FP 参数`
\(ymm5\)	\(xmm5\)	`6th FP 参数`
\(ymm6\)	\(xmm6\)	`7th FP 参数`
\(ymm7\)	\(xmm7\)	`8th FP 参数`
\(ymm8\)	\(xmm8\)	`调用者保存`
\(ymm9\)	\(xmm9\)	`调用者保存`
\(ymm10\)	\(xmm10\)	`调用者保存`
\(ymm11\)	\(xmm11\)	`调用者保存`
\(ymm12\)	\(xmm12\)	`调用者保存`
\(ymm13\)	\(xmm13\)	`调用者保存`
\(ymm14\)	\(xmm14\)	`调用者保存`
\(ymm15\)	\(xmm15\)	`调用者保存`

`Command`	`src`	`dest`	`Description`
`vmovss`	\(M_{32}/X\)	\(X/M_{32}\)	`传送单精度数值`
`vmovsd`	\(M_{64}/X\)	\(X/M_{64}\)	`传送双精度数值`
`vmovaps`	\(X\)	\(X\)	`传送对齐的封装好的单精度数值`
`vmovapd`	\(X\)	\(X\)	`传送对齐的封装好的双精度数值`

`Command`	`src`	`dest`	`Description`
`vcvttss2si`	\(X/M_{32}\)	\(R_{32}\)	`将单精度截断为整数`
`vcvttsd2si`	\(X/M_{64}\)	\(R_{32}\)	`将双精度截断为整数`
`vcvttss2siq`	\(X/M_{32}\)	\(R_{64}\)	`将单精度截断为四字整数`
`vcvttsd2siq`	\(X/M_{64}\)	\(R_{64}\)	`将双精度截断为四字整数`

`Command`	`src1`	`src2`	`dest`	`Description`
`vcvtsi2si`	\(M_{32}/R_{32}\)	\(X\)	\(X\)	`整数转为单精度数`
`vcvtsi2sd`	\(M_{32}/R_{32}\)	\(X\)	\(X\)	`将整数转为双精度数`
`vcvtsi2ssq`	\(M_{64}/R_{64}\)	\(X\)	\(X\)	`将四字整数转为单精度数`
`vcvtsi2sdq`	\(M_{64}/R_{64}\)	\(X\)	\(X\)	`将四字整数转为双精度数`

`Single Precision`	`Double Precision`	`Effect`	`Description`
`vaddss`	`vaddsd`	\(S_2+S_1\rightarrow D\)	`浮点数加法`
`vsubss`	`vsubsd`	\(S_2-S_1\rightarrow D\)	`浮点数减法`
`vmelss`	`vmelsd`	\(S_2\times S_1\rightarrow D\)	`浮点数乘法`
`vdivss`	`vdivsd`	\(S_2/S_1\rightarrow D\)	`浮点数除法`
`vmaxss`	`vmaxsd`	\(\max(S_2,S_1)\rightarrow D\)	`浮点数最大值`
`vminss`	`vminsd`	\(\min(S_2,S_1)\rightarrow D\)	`浮点数最小值`
`sqrtss`	`sqrtsd`	\(\sqrt{S_1}\rightarrow D\)	`浮点数平方根`

`Single Precision`	`Double Precision`	`Effect`	`Description`
`vxorps`	`vxorpd`	\(S_2\oplus S_1\rightarrow D\)	`位级异或`
`vandps`	`vandpd`	\(S_2\And S_1\rightarrow D\)	`位级与`

`Command`	`Based on`	`Description`
\(vucomiss\ S1,S2\)	\(S2-S1\)	`比较单精度数值`
\(vucomisd\ S1,S2\)	\(S2-S1\)	`比较双精度数值`

CSAPP 第三章 程序的机器级表示