深入理解计算机系统

程序的机器级表示

从源代码转为机器代码的过程:

  1. 预处理器会扩展源代码,插入所有用#include指令的文件,扩展所有用#define声明指定的宏。
  2. 编译器基于编程语言的规则、目标机器的指令集和操作系统的惯例,会将源代码转换为汇编代码作为输出,给出程序的每一条指令。
  3. 汇编器将汇编代码转化为二进制目标代码文件,它是机器代码的一种形式,包含了所有指令的二进制表示,但是还没有填入全局值的地址。
  4. 链接器将目标代码文件和实现库函数的代码合并,产生最终可执行代码文件。

image-20221216143416879

生成 mstore.c 所对应得汇编文件 mstore.s:

  • -Og:是生成机器代码的优化等级,这个表示编译器会生成符合原始C代码整体结构的机器代码,这是用于调试的级别,便于我们学习观察。其他的-O1-O2会得到更好的程序性能,但是机器代码和源代码的关系就比较难以理解。
  • -S:只生成到汇编代码。
1
gcc -Og -S mstore.c

打开如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
    .file    "mstore.c"
.text
.globl mulstore
.type mulstore, @function
mulstore:
.LFB0:
.cfi_startproc
endbr64
pushq %rbx
.cfi_def_cfa_offset 16
.cfi_offset 3, -16
movq %rdx, %rbx
call mult2@PLT
movq %rax, (%rbx)
popq %rbx
.cfi_def_cfa_offset 8
ret
.cfi_endproc
.LFE0:
.size mulstore, .-mulstore
.ident "GCC: (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0"
.section .note.GNU-stack,"",@progbits
.section .note.gnu.property,"a"
.align 8
.long 1f - 0f
.long 4f - 1f
.long 5
0:
.string "GNU"
1:
.align 8
.long 0xc0000002
.long 3f - 2f
2:
.long 0x3
3:
.align 8
4:

所有以.开头的行都是指导汇编器和链接器工作的伪指令,我们通常可以忽略这些行。对其化简并加上解释,可以得到汇编代码:

1
2
3
4
5
6
7
multstore:
pushq %rbx
movq %rdx, %rbx
call mult2@PLT
movq %rax, (%rbx)
popq %rbx
ret

pushq这条指令的意思是将寄存器 rbx 的值压入程序栈进行保护。

movq 将寄存器 rdx 的内容复制到寄存器 rbx 中。后缀 q 表示数据大小。

image-20221216155558520

call 表示函数调用,函数的返回值存到 mult2 中。

popq 恢复寄存器 rbx 的内容。

ret 函数返回。

最初接触,感觉好难,后面我应该会再次接触这些,这里只是随便写写。

执行以下命令,产生相对应得机器代码文件 mastore.o:

1
gcc -Og -c mstore.c

该文件是二进制表示,所以需要使用 objdump 这个反汇编器将机器代码反编译成汇编代码:

1
objdump -d mstore.o

结果:

1
2
3
4
5
6
7
8
0000000000000000 <mulstore>:
0: f3 0f 1e fa endbr64
4: 53 push %rbx
5: 48 89 d3 mov %rdx,%rbx
8: e8 00 00 00 00 callq d <mulstore+0xd>
d: 48 89 03 mov %rax,(%rbx)
10: 5b pop %rbx
11: c3 retq

寄存器与数据传送指令

寄存器:

以下都是以 %r 开头:

image-20221216152140619

一个x86-64的CPU中包含16个存储64位值的通用目的寄存器,可以用来存储整数数据和指针。有些寄存器有特殊用途:

  • 栈指针%rsp用来指明运行时栈的结束位置
  • 比如%rdi%rsi%rdx%rcx%r8%r9用来保存函数的参数
  • %rip用来保存当前执行指令的地址
  • %rax用来存放函数的返回值

在大部分情况下这些寄存器都可用来保存程序数据。并且有一组标准编程规范控制着如何使用寄存器来管理栈、传递函数参数、从函数返回值,以及存储局部和临时数据。

image-20221216155917917

我们可以对这些寄存器的低位字节中存放的不同大小的数据进行操作,%r表示64位、%e表示32位。

对于生成小于8字节结果的指令,有两条规则:

  1. 生成1字节或2字节数据的指令会保持剩下的字节内容不变;
  2. 生成4字节数据的指令会把高位 4个字节置零。

寄存器跟内存的区别

两者都可以用来存储数据,寄存器和内存是计算机的两种不同的存储方式。

寄存器是计算机的内部存储器,它位于 CPU 的内部,用于保存 CPU 运算过程中使用的临时数据。寄存器的容量通常很小,大约只有几千字节,但是它的速度非常快,几乎是内存的几十倍。因为寄存器的容量有限,所以只能用来保存 CPU 当前正在使用的数据。

内存是计算机的外部存储器,它位于 CPU 外部,用于保存程序运行所需的数据和指令。内存的容量要比寄存器大得多,一般在几百兆字节到几十兆字节之间。内存的速度比寄存器慢得多,但是它可以保存更多的数据。

总的来说,寄存器用于保存 CPU 当前正在使用的临时数据,而内存则用于保存程序运行所需的数据和指令。

数据格式

C 语言数据类型在 x86 和 x64 下的字节大小。在 64 位机器中,指针长 8 字节。

C 声明 汇编代码后缀 32 位机器(x86) 64 位机器(x64)
char b(字节) 1 1
short w(字) 2 2
int l(双字) 4 4
long l(双字) / q(四字) 4 8
char * l / q 4 8
float s(单精度) 4 4
double l(双精度) 8 8

操作码和操作数

像上面得 movqaddqsubq 等这部分被定义为操作码(Operation code),它决定 CPU 得操作类型,而在操作数后面的是操作数(Operand),大部分操作码都有多个操作数,但是 ret 这种返回指令是没有操作数的。

操作数可分为以下三类:

  1. 立即数(Immediate):在 AT&T 格式的汇编中,立即数以 $ 符号开头后面跟一个整数,这个整数满足 C 语言格式。它表示一个固定的数值,它可以用来表示常数、数组下标、循环计数器等。

  2. 寄存器(Register):指令要操作的数据存放在CPU中的寄存器里,指令中给出寄存器名即可。

  3. 内存引用:小括号中带一个寄存器。操作数 (%rax) 表示的是内存地址 %rax 上存储的值。在汇编语言中,括号用来表示内存寻址

    它会根据计算出来的地址访问某个内存位置。有不同的寻址模式,最常用的是$Imm(r_b,r_i,s)$,其中,要求寄存器大小都是64位的,才能完整索引整个虚拟内存空间,并且不能使用%rsp

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

    假设寄存器 %rax 存放的值为 0x100,地址 0x100存放的值是 0xFF,则操作数 (%rax) 的值是0xFF,4(%rax) 的值是内存地址 0x100+4 上的值即 0x104 上的值。

内存引用(重点掌握如何计算):

一个立即数(Imm)

一个基址寄存器(Base Register -> $r_b$)

变址寄存器(Index Register -> $r_i$)

比例因子(Scale Factor -> $s$)取值 [1, 2, 4, 8]

定义 char 类型的数组,比例因子就是 1,int 类型,比例因子就是 4,double 类型,比例因子就是 8。

如有以下内存引用:

(%rdx, %rdx, 4)。那么它的地址值是:%rdx + %rdx * 4。4就是比例因子。

image-20221216154638223

大多数指令由一个或多个操作数(Operand),指示出一个操作中要使用的元数据值,以及放置结果的目的位置。x86-64支持的操作数格式如下:

image-20221216160000263

数据传送指令

最频繁使用的指令是将数据从一个位置复制到另一个位置的指令。

数据传送指令一共可分为五种,分别是 mov、movs、movz、push以及pop。

MOV

MOV 格式:MOV Source operand Destination operand。MOV 指令的作用是将源操作数 S 中的数据复制到目的操作数 D 中。

image-20221216160334751

源操作数(Source operand)指定的值是一个立即数,存储在寄存器中或者内存中。目的操作数(Destination operand)指定一个位置,要么是寄存器或者,要么是一个内存地址。x86-64 加了一条限制,传送指令的两个操作数不能都指向内存位置。

movl 指令以寄存器作为目的时,它会把该寄存器的高位 4 字节设置为 0 。这是因为 x86-64 采用的惯例:任何为寄存器生成 32 位值的指令都会把该寄存器的高位部分置成 0 。

%rax 是 64 位(四个 word),%eax 是 32 位,%ax 是 16位,%al 是 8 位。其他 寄存器也同样的格式:%rdx 是 64 位,%edx 是 32 位,%dx 是 16 位,%dl 是 8 位。

image-20221217122754972

需要观察源数据是多少位寄存器而适用不同的后缀

image-20221216155558520

MOVS

MOVS 指令的作用是将源操作数 S 中的数据做符号扩展后,再复制到目的操作数 D 中,MOVS 指令有两个数据格式和两个操作数,因此一般的形式为 [movsxy S D]。其中 x、y 为数据格式,S 为源操作数,D 为目的操作数。其中 x、y 的组合一共有三种,分别是 bw、bl、wl,这三个组合代表的意思分别是单字节到双字节单字节到双字以及双字节到双字

关于后缀的解释:

后缀wl表示源操作数(即左操作数)长度为w(即word,一个字),目标操作数(即右操作数)长度为l(即long,双字),s表示从 w 扩展到 l 高位全部用符号位补充

举例:

movswl %dx %eax

movswl

如上图所见,我们先将 %dx 进行一个符号位拓展到 32 位然后复制到 %eax 中。

MOVZ

MOVS 指令的作用是将源操作数 S 做零扩展后(unsign 使用零拓展),再复制到目的操作数中。它与 MOVS 指令十分相似,也有两个数据格式和两个操作数,因此一般的形式为 [movzxy S D]。其中 x、y 为数据格式,S 为源操作数,D 为目的操作数。其中 x、y 的组合一共有三种,分别是 bw、bl、wl,这三个组合代表的意思分别是单字节到双字节单字节到双字以及双字节到双字

举例:

movzwl %dx %eax

movzwl

这里只是进行零拓展之后再进行复制。它于 MOVS 是十分相似的。

CSAPP 书上的例子:

对于下面汇编代码的每一行,根据操作数,确定适当的指令后缀。(例如,mov 可以被重写成 movb、movw、movl 或者 movq 。)

1 word = 2 byte = 16 bit

题目 解释
mov__ %eax, (%rsp) 源数据是 32 位寄存器,所以应该是 movl
mov__ (%rax), %dx 目标是一个字,应该使用 movw
mov__ $0xFF, %bl 是一个字节传送,应该使用 movb
mov__ (%rsp, %rdx, 4), %dl 目标是一个字节,应该使用 movb
mov__ (%rdx), %rax 目标是 64 位寄存器,应该使用 movq
mov__ %dx, (%rax) 从一个字传送到 64 位寄存器,使用 movw

记住一个重要特性,x86-64 中的内存引用总是用四字长寄存器给出,例如 %rax,哪怕操作数只是一个字节、一个字或是一个双字

当我们调用汇编器的时候,下面代码的每一行都会产生一个错误消息。解释每一行都是哪里出了错。

题目 解释
movb $0xF, (%ebx) 取地址一定是从寄存器中取,所以报错。(%ebx) 是内存引用
movl %rax, (%rsp) %rax 是四个字而 l 代表两个字,改成 movl %eax, (%esp) 或者 movq %rax, (%rsp)
movw (%rax), 4(%rsp) 两个操作数不能都是内存引用
movb %al, %sl 没有寄存器的名字叫做 %sl
movq %rax, $0x123 目的操作数应指定一个位置,要么是一个寄存器要么是一个内存地址。
movl %eax, %rdx 两个寄存器长度不一致
movb %si, 8(%rbp) %si 的长度是 w,与指令的长度不符。改成 movb %sil, 8(%rbp) 或 movw %si, 8(%rbp)

压入和弹出栈数据

栈遵循 “后进先出” 的原则。通过 push 操作把数据压入栈中,通过 pop 操作删除数据。弹出的值永远是最近被压入而且仍然在栈中的值。根据惯例,栈是倒过来画的,栈顶在图的底部。栈指针 %rsp 保存着栈顶元素的地址

image-20221217130944819

将一个四字值压入栈中,首先要将栈指针减去 8,然后将值写入到新的栈顶地址。所以一个 pushq %rbp 就等价于以下两条指令:

1
2
subq $8 %rsp    将栈顶的指针减去8
movq %rbp, (%rsp) 存储值

同理弹出也是差不多的。

算术和逻辑操作

以下是一些整数算术操作:

image-20221217131552791

以下规则也将适用(即后面的 b w l q):

image-20221216155558520

加载有效地址

加载有效地址load effective address)指令 leaq 实际上是 movq 指令的变形。它的指令形式是从内存读数据到寄存器,但实际上它根本没有引用内存。它的第一个操作数看上去是一个内存引用,但该指令并不是从指定的位置读入数据,而是将有效地址写入到目的操作数。

通过练习来了解如何使用:

练习一:假设寄存器 %rax 的值为 x,%rcx 的值为 y。填写下表,指明下面每条汇编代码指令存储在寄存器 %rdx 中的值:

表达式 结果
leaq 6 (%rax), %rdx x + 6
leaq (%rax, %rcx), %rdx x + y
leaq (%rax, %rcx, 4), %rdx x + 4y
leaq 7 (%rax, %rax, 8), %rdx 9x + 7
leaq 0xA (, %rcx, 4), %rdx 4y + 10
leaq 9 (%rax, %rcx, 2), %rdx x + 2y + 9

练习二:考虑下面的代码,我们省略了被计算的表达式:

1
2
3
4
long scale2(long x, long y, long z) {
long t = ____________________;
return t;
}

用 GCC 编译实际的函数得到如下的汇编代码:

1
2
3
4
5
6
7
# long scale2(long x, long y, long z)
# x in %rdi, y in %rsi, z in %rdx
scale2:
leaq (%rdi, %rdi, 4), %rax
leaq (%rax, %rsi, 2), %rax
leaq (%rax, %rdx, 8), %rax
ret

填写出 C 代码中缺失的表达式。

1
long t = 5x + 2y + 8z;

一元和二元操作

operation

在这张图中,第一组操作是 leaq

第二组操作是一元操作,只有一个操作数,既是源也是目的。

第三组是二元操作,第二个操作数既是源也是目的。类似 C 语言中的赋值运算符(x -= y),源操作数是第一个,目的操作数是第二个。比如 sub 指令,后面减去前面,并且将值保存在后面的寄存器。

subq %rax, %rdx 就是从 %rdx 中减去 %rax。第一个操作数可以使立即数(立即数以 $ 符号开头后面跟一个整数,这个整数满足 C 语言格式。)、寄存器或是内存位置。第二个操作数可以是寄存器或是内存位置

**注意:**当第二个操作数是内存地址时,处理器必须从内存地址中读出值,执行操作,再把结果写回内存。

通过一些练习了解使用:

假设下面的值存放指定的内存地址和寄存器中:

地址
0x100 0xFF
0x108 0xAB
0x110 0x13
0x118 0x11
寄存器
%rax 0x100
%rcx 0x1
%rdx 0x3

填写下表,给出下面指令的效果,说明将被更新的寄存器或内存位置,以及得到的值:

指令 目的
addq %rcx, (%rax) 0x100 0xFF + 0x1 = 0x100
subq %rdx, 8 (%rax) 0x108 0xAB - 0x3 = 0xA8
imulq $16, (%rax, %rdx, 8) 0x100 + 0x3 * 8 = 0x118 0x11 * 16 = 0x110
incq 16 (%rax) 0x110 0x14
decq %rcx %rcx 0x0
subq %rdx, %rax %rax 0xFD

移位操作

左移指令有两个 SHL、SAL,两者一样,都是在右边填上 0。右移指令不同,SAR 执行算术右移(填上符号位),而 SHR 执行逻辑移位(填上 0)。移位操作的目的操作数可以是一个寄存器或是一个内存位置。

移位量 k,它可以是一个立即数,或者放在单字节寄存器 %cl 中的数,对于移位量,只允许以这个特定的寄存器作为操作数,其他的寄存器不行。寄存器 %cl 的长度为单字节 8 位,所以移位量的编码范围理论上可达 255 ($2^8-1$)。但是,对于 $w$ 位的操作数进行移位操作,移位量取决于寄存器 %cl 的低 m 位决定:$2^m=w$。举个例子:

对于一个移位操作指令假设我们这里是 salb,这里后缀是 b 说明目的操作数是 8 位,即 $w$ 为 8,所以 m 为 3,也就是说移位量由寄存器 %cl 的低 3 位决定。同理,对于指令 salw,目的操作数是 16 位,所以移位量由寄存器 %cl 的低 4 位决定。

移位操作的格式:

1
2
salq  $4, %rax     # x <<= 4
sarq %cl, %rax # x >>= n

举例:

1
2
// z 存在 %rdx 寄存器中
long t2 = z * 48;
1
2
leaq (%rdx, %rdx, 2), %rax
salq $4, %rax

以上汇编实现了上面的 C 语言中的乘法操作。

1
2
R[%rdx] + R[%rdx]*2 = 3 * z -> %rax
2^4 * R[%rax] = 16 * (3 * z) = 48 * z 右移四位相当于乘 16.

控制指令

除了之前介绍的保存整数和指针的16个64的寄存器以外,CPU还维护了一组单个位的条件码(Condition Code)寄存器,我们不会直接对条件码进行设置,而是根据最近的算数、逻辑或者测试的结果,自动设置这些条件码寄存器的值。

条件码包括:

  • **ZF(Zero Flag):**零标志,最近的操作得到的结果是否为 0。
  • 无符号数:
    • **CF(Carry Flag):**进位标志,最近的操作使得最高位产生进位。可用来检查无符号数是否存在溢出。
  • 补码:
    • **SF(Sign Flag):**符号标志,最近的操作得到的结果为负数。
    • **OF(Overflow Flag):**溢出标志,最近的操作导致补码溢出(可以通过符号位进一步判断是正溢出还是负溢出)。

以上条件码若符合则会被置 1。

以下的指令都会影响条件码

operation

注意:

x86-64提供了另外两类指令,只会设置条件码而不会改变目的寄存器

  • CMP S1, S2:用来比较 S1S2根据 S2-S1 的结果来设置条件码。主要用来比较两个数的大小。
  • TEST S1, S2:用来测试 S1S2根据 S1 & S2 的结果来设置条件码。可以将一个操作数作为掩码,用来指示哪些位用来测试。比如 testq %rax, %rax 就可以检查 %rax 是正数、负数还是0。

**注意:**使用CMP进行比较时,要注意顺序是相反的。比如CMP S1, S2得到大于的结果,则表示S2大于S1

image-20221221125139356

SET指令,能够自动根据条件码的组合来得到结果,如下图所示:

image-20221221125751113

我么可以从 set 指令的后缀看出有符号数还是无符号数。

set 指令的用法:

1
2
3
int comp(char a, char b) {
return (a < b);
}
1
2
3
4
comb %sil, %dil
setl %al
movzbl %al, %eax
ret

如果 a < b 则将寄存器 al 设置为 1。

跳转指令

跳转(Jump)指令能够改变指令执行的顺序,跳转到新的指令后继续顺序执行。挑战的目的地通常用一个标号(lable)来指明。如下标号(lable)就是 .L1

1
2
3
4
5
  movq $0, %rax
jmp .L1
movq (%rax), %rdx
.L1:
popq %rdx

而跳转指令我们可以分成不同的类型:

  • 根据提供跳转目标的方式:

    • **直接跳转:跳转目标作为指令的一部分进行编码。汇编语言中,跳转目标通常用一个标号(Label)**指明,比如下面汇编代码里的.L1就是标号。在产生目标代码时,汇编器以及链接器会确定跳转目标的适当编码,并将其编码为跳转指令的一部分。
    • 间接跳转:跳转目标从寄存器或内存位置中读取出来。需要在前面添加一个*,比如jmp *%rax就是跳转到寄存器%rax中保存的地址;jmp *(%rax)就是跳转到内存地址(%rax)中保存的地址。也就是说,简接跳转会从内存中读出跳转目标。
  • 根据跳转的条件:

    • 无条件跳转:没有任何条件,看到jmp就直接跳转。
    • 有条件跳转:根据条件码组合来判断是否进行跳转。

指令 jmp .L1 会导致程序跳过 movq 指令,而从 popq 指令开始继续执行。

以下是常见的所有跳转指令:

image-20221221135441232

跳转指令的编码

  • PC 相对的(PC-relative):跳转目标地址减去跳转指令下一条指令地址的差作为编码(偏移量),这些地址偏移量可以编码为 1、2 或 4 字节。
  • 绝对地址:用4字节直接给定目标地址。

举例:

jump_encode

  • 如上图,通过反汇编软件得到机器指令与汇编语言,其中左边为机器指令编码,右边为对应汇编语言含义,最左边为每条机器指令地址。
  • jmp 指令的对应机器指令有两个字节:eb 表示这是 jmp 指令,03 描述跳转信息。值得注意的是,跳转指令进行编码时,采用相对位置编码,如 03 描述的就是偏移量
  • 结合实例进行理解:在未执行 jmp 指令时,rip 寄存器存储的地址为 4004d5(rip 寄存器存放即将加载的指令地址);执行 jmp 指令后,rip 寄存器的值改为新的目标位置地址,目标位置 = 原先位置 + 偏移量,在此例子中为 4004d5 + 03 = 4004d8。目标位置减去跳转指令下一条指令地址就是 03jg 指令同理。
  • 存放相对位置意义:可获得更高灵活度,若存放绝对地址,分配地址可能改变;而相对位置一定不変。

使用跳转指令实现条件执行和循环结构

用条件控制实现条件分支

实现条件操作的传统方法是通过使用控制的条件转移,当条件满足时,程序沿着一条执行路径执行,而当条件不满足时,就走另一条路径。对于条件分支:

1
2
3
4
5
if(x < y){
proc1;
}else{
proc2;
}

其中x保存在%rdi,y保存在%rsi,可以定义对应的汇编语言

1
2
3
4
5
6
7
  cmpq %rsi, %rdi
jge .L1
PROC2
ret
.L1:
PROC1
ret

使用以上方法的性能并不优越。

处理器在执行一条指令时,会经历一系列过程,而每个过程执行所需操作的一小部分,通过重叠连续指令可以提高性能,比如当前指令执行计算时,下一条指令可以执行取指阶段,这个方法称为流水线(Pipelining)。但是当遇到条件需要跳转时,只有知道跳转结果才能确定指令顺序,才能使用流水线,现在处理器采用分支预测的方法来预测跳转的结果,即处理器会预测当前跳转的结果,然后将预测的指令进行流水线,如果预测正确则会提高性能,如果预测错误,就需要把之前流水线清空,然后在正确的分支重新开始流水线,会损失很多性能。

我们可以使用条件传送实现条件分支:

用条件传送来实现条件分支

而用条件传送来实现条件分支,不会先判断跳转,而是先将两个分支的结果进行计算,将结果分别保存在两个寄存器中,然后再通过**条件传送指令CMOV**将正确结果传送到输出的寄存器中。

比如以下的计算 x 和 y 的差的绝对值的函数:

1
2
3
4
5
6
long absdiff(long x, long y){
if(x < y)
return y-x;
else:
return x-y;
}

使用条件控制的方法实现的汇编代码为:

1
2
3
4
5
6
7
8
9
10
absdiff:
cmpq %rsi, %rdi //y-x
jl .L1
movq %rdi, %rax //y>=x
subq %rsi, %rax
ret
.L1:
movq %rsi, %rax
subq %rdi, %rax
ret

这里在第二行中会直接执行一个cmp,所以就存在不确定的分支,处理器为了能够流水线执行指令,就会先预测结果,如果预测错误,就会很损伤性能。

使用条件传送方法实现的汇编代码为:

1
2
3
4
5
6
7
8
absdiff:
movq %rsi, %rax
subq %rdi, %rax //y-x
movq %rdi, %rdx
subq %rsi, %rdx //x-y
cmpq %rsi, %rdi
cmovge %rdx, %rax
ret

这里会直接将两个分支的计算结果x - yy - x分别保存在寄存器%rdx%rax中,然后最后通过cmovge判断如果x > y就将x - y的结果保存在%rax。这里就不需要进行分支预测,性能就十分稳定。

但是条件传送也实现的条件分支也存在局限性

  1. 如果条件判断是里面执行语句的可行性判断时,使用条件传送实现条件分支就会出现错误。比如对于指针xp,有个条件分支为xp ? *xp : 0,如果使用条件传送来实现,就会先运行*xp,如果该指针不存在,就会报错。
  2. 如果执行语句需要大量计算时,由于条件传送会先全部计算后再进行选择,则会浪费一些时间。

所以只有当两个执行语句很简单时,才会使用条件传送来实现条件分支。

循环
  • do-while

    1
    2
    3
    4
    5
    6
    7
    8
    long fact_do(long n){
    long result = 1;
    do{
    result *= n;
    n = n - 1;
    }while(n > 1);
    return result;
    }

    对应的汇编代码为:

    1
    2
    3
    4
    5
    6
    7
    8
    fact_do:
    movl $1, %eax
    .L1:
    imulq %rdi, %rax
    subq $1, %rdi
    cmpq $1, %rdi
    jg .L1
    rep; ret

    可以发现,在跳转标号.L1之前是循环的初始化,跳转标号之后就是循环体,然后最后要判断是否继续循环体。

  • while

    有两种实现 while 循环的方法,在实现初始测试的方法不同。

    对于以下代码

    1
    2
    3
    4
    5
    6
    7
    8
    long fact_while(long n){
    long result = 1;
    while(n > 1){
    result *= n;
    n = n - 1;
    }
    return resul;
    }

    Jump-to-middle

    类似于 do-while 的汇编代码,只是需要在开始就跳转到后面的判断语句

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    fact_while:
    movl $1, %eax
    jmp .JUDGE
    .L1:
    imulq %rdi, %rax
    subq $1, %rdi
    .JUDGE:
    cmpq $1, %rdi
    jg .L1
    rep; ret

    特点:一开始就有一个无条件跳转指令。

    guarded-do

    当使用较高优化等级时,比如-O1时,GCC会使用这种策略

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    fact_while:
    cmpq $1, %rdi
    jle .L1
    movl $1, %eax
    .L2:
    imulq %rdi, %rax
    subq $1, %rdi
    cmpq $1, %rdi
    jne .L2
    rep; ret
    .L1:
    movl $1, %eax
    ret

    这里是直接进行判断。这个之所以更加高效,是因为一开始进入循环时,通常不会不满足循环条件,即一开始不会跳转到后面,所以会直接顺序一直执行循环体。

  • for

    for 循环可以转化为 while 循环,然后根据优化等级,GCC 会为其产生的代码是 while 循环的两种方法之一。

    1
    2
    3
    4
    5
    6
    7
    8
    long fact_for(long n){
    long i;
    long result = 1;
    for(i = 2; i <= n; i++){
    result *= i;
    }
    return result;
    }

    可以将其转化为 while 语句

    1
    2
    3
    4
    5
    6
    7
    8
    9
    long fact_for_while(long n){
    long i = 2;
    long result = 1;
    while(i <= n){
    result *= i;
    i += 1;
    }
    return result;
    }

    之后就可以按照 while 之前的汇编语言。

  • switch

    switch 语句可以根据一个整数索引数值进行多重分支。通常使用跳转表(Jump Table)数据结构使得实现更加高效,它是一个数组,每个元素是对应的代码块起始地址,根据整数索引得到对应的代码地址后,就可以直接跳转到对应的代码块。相比很长的if-else语句的优势在于:执行switch语句的时间与分支数目无关。比如有很长的分支语句,如果用if-else实现,则可能需要经过若干个if-else才能跳转到目的代码块,而使用switch能根据跳转表直接获得代码块地址。

    下面是源代码:

    image-20230118225414691

    这是源代码的实现:

    image-20230118225436749

    里面有一个跳转表数组jt,GCC 提供了一个新的运算&&,能够创建一个指向代码位置的指针。首先在第 9 行中,计算输入值xswitch的最小值的差,并将其保存到无符号数中。然后将其作为跳转表的索引,直接在第16行中跳转到索引的代码位置。

    **注意:**这里使用无符号数的原因在于,即使你输入比switch中最小值还小的值,则相减会得到负数,由于无符号数会将负数溢出到很大的正数(溢出),所以还是会跳转到default。所以汇编代码会使用ja对其使用无符号数的判断,判断是小于 0 还是大于最大值。

    **注意:**跳转表中会创建从最小值到最大值的代码位置,对于重复的情况,比如104106,就会跳转到相同的代码位置;对于缺失的情况,比如101105,就会直接跳转到default

    我们看看汇编代码:

    image-20230118230007797

    首先将计算结果保存在%rsi中,然后在第4行中jmp *.L4(, %rsi, 8)利用了跳转表,跳转表的内容由编译器自动生成填写,其声明如下所示:

    image-20230118230312336

    .rodata表示这是只读数据(Read-Only Data),.align 8表示将元素地址与8对其,.L4就定义了一个跳转表,其枚举了从最小值到最大值的跳转目标。对于*.L4(, %rsi, 8),首先根据.L4可以获得该跳转表的初始位置,然后因为该跳转表每个元素占 8 个字节,所以计算(, %rsi, 8),即8*%rsi,就能得到对应的跳转目标。

参考文章:

深入理解计算机系统(3.3)—数据传送(或者说复制)指令详解 - 左潇龙 - 博客园 (cnblogs.com)

《深入理解计算机系统(原书第 3 版)》第三章练习题(上) | 拾遗记 (imkasen.com)1000000111001$