2019-03-09

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

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

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

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

1.1 if 分支

if 语句可以表述为：

if (expr) {
    then-expr;
} else {
    else-expr;
}

在汇编中，指令流的逻辑顺序为：

begin:
    if (! expr): goto false;
    v = then-expr;
    goto done;
false:
    v = else-expr;
done:
    ...

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

// 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-expr 和 else-expr 都求值，然后根据 test-expr 来决定最后选择哪个值。可以看到，虽然多了一次求值，但是避免了跳转，并且 100% 确定了指令流水线。
还是以上面的函数为例子，条件传送的实现可能就成为了:

// 汇编
// 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，就有可能造成错误：

// 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 的指令流的开始地址。
我们还是看例子吧：

// 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...while、 while 和 for...。其实这三种可以彼此转换，尤其是前两种，所以实现的逻辑差别也不大。
在了解怎么基于跳转实现分支后，了解基于跳转实现的循环也不是什么难事，无非是一个往后跳，一个往前跳。

2.1 do…while 循环的实现

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

loop:
    body-statements
    t = test-expr
    if (t):
        goto loop
done

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

2.2 while 循环的实现

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

    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。

ImHuWQ

穷则独善其身,达则兼济天下