从汇编的角度理解程序(二)—— 分支和循环控制

在上一节 从汇编的角度理解程序(一)—— 操作数据的指令流 中提到,程序其实就是按顺序执行的操作寄存器数据的指令流。
不过,按顺序执行的指令流是如何实现程序中常见的分支和循环功能的呢?
简单地说,就是有条件的跳转 —— 依据条件寄存器和跳转指令实现,非常类似 C 语言里面的 goto

一、如何基于跳转实现分支

分支有两种方式,一种是 if...else... 还一种是 switch...case
if 的实现大致就是对表达式求值并设置条件寄存器,然后根据条件寄存器决定是不是要跳转。switch 的实现方式大致是根据所有 case 值的取值范围建立一个 array 作为跳转表,array 中每个元素是一种 case 的指令流的开始地址。以 switch 表达式的值作为下标在跳转表中获取要跳转到的位置。

1.1 if 分支

if 语句可以表述为:

1
2
3
4
5
if (expr) {
then-expr;
} else {
else-expr;
}

在汇编中,指令流的逻辑顺序为:

1
2
3
4
5
6
7
8
begin:
if (! expr): goto false;
v = then-expr;
goto done;
false:
v = else-expr;
done:
...

也就是说,先对 test-expr 求值,根据情况决定是否跳到 else-expr 逻辑。
以一段程序来说明如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// c 函数
long abs_diff(long x, long y) {
long result;
if (x < y) result = y - x;
else result = x - y;
return result;
}

//汇编
// x in %rdi, y in %rsi
abs_diff:
compq %rsi, %rdi
jge .L2
movq %rsi, %rax
subq %rdi, %rax
ret
.L2
movq %rdi, %rax
subq %rsi, %rax
ret

这种实现方式我们称之为条件控制—— 根据条件来跳转控制。从人的感官上非常容易理解它,但是它对 CPU 性能不那么友好。具体原因在于 CPU 使用指令流水线(PipeLine) 来加速执行速度。
CPU 执行的每条指令有多个阶段,包括从内存读取指令、从内存读取数据、执行计算、往内存写入数据等,其中有些阶段等待比较长(往内存读写),因此可以在执行一条指令时,开始往内存读取下一条指令。而这就需要 CPU 知道接下来的指令顺序。而在这种分支的实现方法上,在 test-expr 结果计算出来之前,CPU 是无法知道接下来究竟要去执行什么命令的(此时 CPU 最优选择是预测某个分支)。
为了改善这种情况,还有一种实现方式,称之为条件传送—— 根据条件来传送数据,而不是跳转控制。它和条件控制的区别在于,它先把 then-exprelse-expr 都求值,然后根据 test-expr 来决定最后选择哪个值。可以看到,虽然多了一次求值,但是避免了跳转,并且 100% 确定了指令流水线。
还是以上面的函数为例子,条件传送的实现可能就成为了:

1
2
3
4
5
6
7
8
9
10
// 汇编
// x in %rdi, y in %rsi
abs_diff:
movq %rdi, %rax
subq %rsi, %rax
movq %rsi, %rdx
subq %rdi, %rdx
cmpq %rsi, %rsi
cmovl %rdx, %rax
ret

但是,事情也没有那么美好,条件传送也不是在所有情况下都适用的。最明显的情况就是else-expr 耗时超过了分支预测失败的惩罚,此时还不如使用条件控制实现。
还有一种情况分支传送也不适用,比如当 test-expr 包含了对 else-expr 的保护逻辑时,如果不顾 test-expr 直接就开始执行 else-expr,就有可能造成错误:

1
2
3
4
5
6
7
8
9
10
11
12
13
// c 函数
long read(long * p) {
return p ? *p : 0;
}

// 汇编
// p in %rdi
read:
movq (%rdi), %rax // 读 p 指针的值,此时可能会空指针报错
movl 0, %edx
testq %rdi, %rdi
cmove %rdx, %rax
ret

本来先判断 p 是否为空指针然后再决定是否返回其值的,但是在条件传送的实现中,绕过了对 p 的判断,直接就开始取值了,这很可能会出错。
所以说,到底是用条件控制+分支预测好,还是用条件传送好,这里面也有很多学问。

1.2 switch 分支

分支的另外一种实现方式是使用 switch。当分支数量比较多但是层级不深的情况下(flat),使用 switch 不管对 readability 还是 performance 都是好事。
switch 的实现,依赖于跳转表。跳转表是一个 array,下标(index)对应 switch 里面的 case 值,下标 x 对应的元素值是 case x 的指令流的开始地址。
我们还是看例子吧:

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// c 函数
void switch_example(long x, long n, long* dest) {
long val = x;
switch (n) {
case 100:
val *= 13;
break;
case 102:
val += 10;
case 103:
val += 11;
break;
case 104:
case 106:
val *= val;
break;
default:
val = 0;
}
*dest = val;
}

// 汇编
// x in %rdi, n in %rsi, dest in %rdx
switch_example:
subq $100, %rsi // case 最小值为 100,最大为 106,0-100 没用,所以把基数减 100,跳转表长度也减少
cmpq $6, %rsi // 跳转表有 7 种情况
ja .L8 // case 值大于 6 时不使用跳转表,直接跳到 default 逻辑
jmp *.L4(,%rsi,8) // 跳转到 M[L4+8*%rsi],也就是以 %rsi 为下标去跳转表找地址
.L3:
leaq (%rdi, %rdi, 2), %rax // 3x
leaq (%rdi, %rax, 4), %rdi // 13x
jmp .L2 // break?
.L5:
addq $10, %rdi // x+=10,没有 break
.L6:
addq $11, %rdi // x += 11
jmp .L2 // 此时可以肯定 .L2 肯定是 break 后的逻辑
.L7:
imulq %rdi, %rdi // x *= x
jmp .L2
.L8:
movl $0, %edi // default 逻辑,x = 0
.L2:
movq %rdi, (%rdx) // val = x
ret

.section .rodata
.align 8
.L4:
.quad .L3 // case 100
.quad .L8 // case 101, default
.quad .L5 // case 102
.quad .L6 // case 103
.quad .L7 // case 104
.quad .L8 // case 105, default
.quad .L7 // case 106

可以看到,在生成跳转表时,会首先缩小 case 的取值,从 100-106 缩小到了 0-6,0-100 范围没有 case 出现,所以直接减去了100。这极大地缩小了跳转表的大小。
此外,跳转表会为没有出现的 case 使用 default 指令的位置。
跳转表放在 read-only 数据区,以 8 字节对其,然后以 L4(,%rsi,8) 的方式寻址,即 L4+8*%rsi。
switch 的实现也对 CPU PipeLine 不算太友好,所以我猜测提高分支预测的正确率是优化的方向。

二、如何基于跳转实现循环

循环有三种语法 do...whilewhilefor...。其实这三种可以彼此转换,尤其是前两种,所以实现的逻辑差别也不大。
在了解怎么基于跳转实现分支后,了解基于跳转实现的循环也不是什么难事,无非是一个往后跳,一个往前跳。

2.1 do…while 循环的实现

do...while 循环的逻辑是三种循环逻辑实现的基础,其它两种都是它的变种。
do...while 的基本逻辑为:

1
2
3
4
5
6
loop:
body-statements
t = test-expr
if (t):
goto loop
done

此系列博客的目的不在于怎么写汇编,所以此处就不再写汇编的例子了。和分支的实现差不多,只不过分支是往后跳,循环是往前跳。

2.2 while 循环的实现

while 循环和 do...while 循环的区别在于,前者要进行一次判断后才决定要不要执行 body-expr。我们可以把 do...while 的逻辑稍加修改就能达到目的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
    goto test
loop:
body-statements
test:
t = test-expr
if (t):
goto loop
done
```
可以看到,它只是在 `do...while` 的逻辑的最前面加了一个 `goto` 语句以直接开始 `test-expr`。这种**跳到 do...while 逻辑中间**的实现叫 `jump-to-middle` 实现。
既然专门给它取了名字,就说明还有其它的实现。想想这个 `jump-to-middle` 的实现,首先是忽略了重头戏的 `body-statements`, 然后在 `test-expr` 之后紧接着就是一个往前的跳转,导致 CPU 不能很好地做 PipeLine 优化。因此,还有一种 `guarded-do` 的实现,理解为 `gurded do-while` 实现:
```c
t = test-expr
if (!t):
goto done
loop:
body-statements
t = test-expr
if (t):
goto loop
done

这种实现其实和 do...while 也很像,只是在最前面添加了一个 test-expr 作为 guard。它的好处在于,在执行最开始的 test-expr 时,编译期可以假设结果总是为真,并开始处理接下来的 body-statements PipeLine。
看起来这比 jump-to-middle 似乎只是第一次更快,但是我猜可以在这里做指令缓存,这样的话之后的循环也可以从第一次循环的加速中获益。

2.3 for 循环

for 循环基于 jump-to-middle 或者 guarded-do 逻辑实现,只需要在 test-expr 之前加上 init-expr 以及在 body-statements 之后加上 update-expr 就 ok 了,在此不再赘述。

三、总结

按顺序执行的指令流,搭配搭配上条件寄存器和跳转指令,就能实现分支和循环。分支和循环的差别不大,不过一个是往后跳转,一个是往前跳转。
如何尽量减少判断语句对指令流 PipeLine 的影响是个大学问。在实现分支时,可以尝试使用跳转传送,或者继续使用跳转控制以及更优良的分支预测算法;在实现循环时,可以尝试用 guarded-do