无分支代码 属于

关于 无分支代码

条件分支概念介绍了jcc，这是一族根据条件进行分支的指令。 jcc只有在满足其条件时，才会把执行转移到程序中的另一个位置。

然而，现代 CPU 速度很快，能够并行执行许多指令。 如果让所有工作都停下来，等待 CPU 对某个条件做运行时检查，代价就太高了。

正因为如此，CPU 在内部并不会等待。 它会用分支预测器猜测某个条件的结果，并开始推测性地执行预测的那条路径。

如果预测正确，执行就照常继续，就像没有分支一样。 但如果预测错误，CPU 就必须丢弃在预测路径上已完成的工作，并在正确的路径上重新开始。

这叫做分支预测错误，代价很高，会带来延迟。

当某个分支难以预测时，这些预测错误就会不断累积。 在这种情况下，有时更好的做法是完全避开这个分支，让同一批指令无论条件如何都照常执行。 像这样不用jcc就在若干值之间做选择的代码，叫做无分支代码。

有几种办法可以组织代码，让它分支得更少，或者让它确实存在的那些分支更容易预测。 尤其是 x86-64，它提供了两个常用于编写无分支代码的指令族。

条件移动

cmovcc这一族指令只有在满足某个特定条件时，才会把源操作数复制到目标操作数。 否则，目标操作数保持不变。

cc后缀的命名与jcc相同，含义也一样：

这些规则与jcc类似：

1. l和g用于有符号比较；b和a用于无符号比较。
2. 在后缀上加上e，表示把相等的情况也算进去。
3. 加上n表示对条件取反。
4. 还有一些变体针对的是某个标志位是否被设置。 例如cmovz和cmovc。

来看一个求有符号整数绝对值的例子：这个整数存放在rdi中，结果通过rax返回。 用jcc来写的话，这个函数会在两条路径之间选一条：

abs_branch:
    mov rax, rdi
    cmp rax, 0
    jge .done
    neg rax
.done:
    ret

用cmovcc来写的话，两个候选值都会被无条件地计算出来，再由条件移动从中选一个：

abs_branchless:
    mov rax, rdi
    neg rax            ; rax = -rdi
    cmp rdi, 0
    cmovge rax, rdi    ; if rdi >= 0, rax = rdi
                       ; otherwise rax stays = -rdi
    ; now rax = abs(rdi)
    ret

无分支版本始终执行同一批指令。 没有jcc可供预测器猜测。

cmovcc的目标操作数必须是一个寄存器。 源操作数可以是寄存器或内存位置，但不能是立即数。

abs_branchless:
    mov rax, rdi
    neg rax            ; rax = -rdi. `neg` sets SF = 1 if the result is negative
    cmovs rax, rdi     ; if SF = 1 (i.e., rax < 0), replace rax with rdi
                       ; otherwise rax stays = -rdi, which is non-negative
    ; now rax = abs(rdi)
    ret

条件设置

setcc这一族指令会在满足某个特定条件时把目标操作数设为1，否则设为0。 目标操作数始终是一个8 位操作数。

cc后缀的命名与jcc和cmovcc相同。 例如，如果ZF == 1，setz会把目标设为1，否则设为0。

由于目标操作数是 8 位的，当需要更宽的值时，通常会紧跟在setcc后面接一条movzx：

cmp rdi, rsi
setg al             ; al = 1 if rdi > rsi (signed), 0 otherwise
movzx eax, al       ; eax (and rax) = 1 or 0, with the upper bits cleared

这是把比较结果转换成整数0或1的常见写法。

何时使用无分支代码

无分支代码并不总是比有分支的代码更快。 当一个分支高度可预测时，预测器几乎每次都能猜对，jcc基本上不花什么代价。 用来替换这种分支的无分支代码反而更慢，因为它总是把两个候选计算都执行一遍。

循环计数器就是最典型的例子。 来看一个函数，它把从rdi开始的rsi个 64 位整数相加：

sum_array:
    xor rax, rax
.loop:
    add rax, [rdi]
    add rdi, 8
    dec rsi
    jnz .loop          ; taken on every iteration except the last
    ret

这正是分支预测器最擅长处理的那类模式，所以无论sum_array处理多少个元素，这个分支基本上都是免费的。

当分支难以预测，或者无论输入如何都要求时序一致时，无分支代码才有回报。