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

实现条件操作的传统方法是通过使用控制的条件转移。当条件满足时，程序沿着一条执行路径执行，而当条件不满足时，就走另一条路径。这种机制简单而通用，但是在现代处理器上，它可能会非常低效。

一种替代的策略是使用数据的条件转移。这种方法计算一个条件操作的两种结果，然后再根据条件是否满足从中选取一个。只有在一些受限制的情况中，这种策略才可行，但是如果可行，就可以用一条简单的条件传送指令来实现它，条件传送指令更符合现代处理器的性能特性。我们将介绍这一策略，以及它在 x86-64 上的实现。

图 3-17a 给出了一个可以用条件传送编译的示例代码。这个函数计算参数 x 和 y 差的绝对值，和前面的例子一样（图 3-16）。不过前面的例子中，分支里有副作用，会修改 lt_cnt 或 ge_cnt 的值，而这个版本只是简单地计算函数要返回的值。

GCC 为该函数产生的汇编代码如图 3-17c 所示，它与图 3-17b 中所示的 C 函数 cmovdiff 有相似的形式。研究这个 C 版本，我们可以看到它既计算了 y - x，也计算了 x - y，分别命名为 rval 和 eval。然后它再测试 x 是否大于等于 y，如果是，就在函数返回 rval 前，将 eval 复制到 rval 中。图 3-17c 中的汇编代码有相同的逻辑。关键就在于汇编代码的那条 cmovge 指令（第 7 行）实现了 cmovdiff 的条件赋值（第 8 行）。只有当第 6 行的 cmpq 指令表明一个值大于等于另一个值（正如后缀 ge 表明的那样）时，才会把数据源寄存器传送到目的。

long absdiff(long x, long y)
{
    long result;
    if (x < y)
        result = y - x;
    else
        result = x - y;
    return result;
}

a）原始的 C 语言代码

1  long cmovdiff(long x, long y)
2  {
3      long rval = y - x;
4      long eval = x - y;
5      long ntest = x >= y;
6      /* Line below requires
7         single instruction: */
8      if (ntest) rval = eval;
9      return rval;
10 }

b）使用条件赋值的实现

long absdiff(long x, long y)
x in %rdi, y in %rsi

1  absdiff:
2      movq   %rsi, %rax
3      subq   %rdi, %rax       rval = y-x
4      movq   %rdi, %rdx
5      subq   %rsi, %rdx       eval = x-y
6      cmpq   %rsi, %rdi       Compare x:y
7      cmovge %rdx, %rax       If >=, rval = eval
8      ret                     Return rval

c）产生的汇编代码

图 3-17　使用条件赋值的条件语句的编译。a）C 函数 absdiff 包含一个条件表达式；b）C 函数 cmovdiff 模拟汇编代码操作；c）给出产生的汇编代码

为了理解为什么基于条件数据传送的代码会比基于条件控制转移的代码（如图 3-16 中那样）性能要好，我们必须了解一些关于现代处理器如何运行的知识。正如我们将在第 4 章和第 5 章中看到的，处理器通过使用流水线（pipelining）来获得高性能，在流水线中，一条指令的处理要经过一系列的阶段，每个阶段执行所需操作的一小部分（例如，从内存取指令、确定指令类型、从内存读数据、执行算术运算、向内存写数据，以及更新程序计数器）。这种方法通过重叠连续指令的步骤来获得高性能，例如，在取一条指令的同时，执行它前面一条指令的算术运算。要做到这一点，要求能够事先确定要执行的指令序列，这样才能保持流水线中充满了待执行的指令。当机器遇到条件跳转（也称为“分支”）时，只有当分支条件求值完成之后，才能决定分支往哪边走。处理器采用非常精密的分支预测逻辑来猜测每条跳转指令是否会执行。只要它的猜测还比较可靠（现代微处理器设计试图达到 90% 以上的成功率），指令流水线中就会充满着指令。另一方面，错误预测一个跳转，要求处理器丢掉它为该跳转指令后所有指令已做的工作，然后再开始用从正确位置处起始的指令去填充流水线。正如我们会看到的，这样一个错误预测会招致很严重的惩罚，浪费大约 15～30 个时钟周期，导致程序性能严重下降。

作为一个示例，我们在 Intel Haswell 处理器上运行 absdiff 函数，用两种方法来实现条件操作。在一个典型的应用中，x < y 的结果非常地不可预测，因此即使是最精密的分支预测硬件也只能有大约 50% 的概率猜对。此外，两个代码序列中的计算执行都只需要一个时钟周期。因此，分支预测错误处罚主导着这个函数的性能。对于包含条件跳转的 x86-64 代码，我们发现当分支行为模式很容易预测时，每次调用函数需要大约 8 个时钟周期；而分支行为模式是随机的时候，每次调用需要大约 17.50 个时钟周期。由此我们可以推断出分支预测错误的处罚是大约 19 个时钟周期。这就意味着函数需要的时间范围大约在 8 到 27 个周期之间，这依赖于分支预测是否正确。

旁注　如何确定分支预测错误的处罚

假设预测错误的概率是 p，如果没有预测错误，执行代码的时间是 T_OK，而预测错误的处罚是 T_MP。那么，作为 p 的一个函数，执行代码的平均时间是：
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_avg(0.5) = T_OK + 0.5T_MP
T_MP = 2(T_ran - T_OK)
因此，对于 T_OK = 8 和 T_ran = 17.5，我们有 T_MP = 19。

另一方面，无论测试的数据是什么，编译出来使用条件传送的代码所需的时间都是大约 8 个时钟周期。控制流不依赖于数据，这使得处理器更容易保持流水线是满的。

练习题 3.19 在一个比较旧的处理器模型上运行，当分支行为模式非常可预测时，我们的代码需要大约 16 个时钟周期，而当模式是随机的时候，需要大约 31 个时钟周期。

A. 预测错误处罚大约是多少？

B. 当分支预测错误时，这个函数需要多少个时钟周期？

图 3-18 列举了 x86-64 上一些可用的条件传送指令。每条指令都有两个操作数：源寄存器或者内存地址 S，和目的寄存器 R。与不同的 SET（3.6.2 节）和跳转指令（3.6.3 节）一样，这些指令的结果取决于条件码的值。源值可以从内存或者源寄存器中读取，但是只有在指定的条件满足时，才会被复制到目的寄存器中。

源和目的的值可以是 16 位、32 位或 64 位长。不支持单字节的条件传送。无条件指令的操作数的长度显式地编码在指令名中（例如 movw 和 movl），汇编器可以从目标寄存器的名字推断出条件传送指令的操作数长度，所以对所有的操作数长度，都可以使用同一个的指令名字。

指令	同义名	传送条件	描述
`cmove` S, R	`cmovz`	ZF	相等／零
`cmovne` S, R	`cmovnz`	~ZF	不相等／非零
`cmovs` S, R		SF	负数
`cmovns` S, R		~SF	非负数
`cmovg` S, R	`cmovnle`	~(SF ^ OF) & ~ZF	大于（有符号 >）
`cmovge` S, R	`cmovnl`	~(SF ^ OF)	大于或等于（有符号 >=）
`cmovl` S, R	`cmovnge`	SF ^ OF	小于（有符号 <）
`cmovle` S, R	`cmovng`	(SF ^ OF) \| ZF	小于或等于（有符号 <=）
`cmova` S, R	`cmovnbe`	~CF & ~ZF	超过（无符号 >）
`cmovae` S, R	`cmovnb`	~CF	超过或相等（无符号 >=）
`cmovb` S, R	`cmovnae`	CF	低于（无符号 <）
`cmovbe` S, R	`cmovna`	CF \| ZF	低于或相等（无符号 <=）

图 3-18　条件传送指令。当传送条件满足时，指令把源值 S 复制到目的 R。有些指令是“同义名”，即同一条机器指令的不同名字

同条件跳转不同，处理器无需预测测试的结果就可以执行条件传送。处理器只是读源值（可能是从内存中），检查条件码，然后要么更新目的寄存器，要么保持不变。我们会在第 4 章中探讨条件传送的实现。

为了理解如何通过条件数据传输来实现条件操作，考虑下面的条件表达式和赋值的通用形式：

v = test-expr ? then-expr : else-expr;

用条件控制转移的标准方法来编译这个表达式会得到如下形式：

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

这段代码包含两个代码序列：一个对 then-expr 求值，另一个对 else-expr 求值。条件跳转和无条件跳转结合起来使用是为了保证只有一个序列执行。

基于条件传送的代码，会对 then-expr 和 else-expr 都求值，最终值的选择基于对 test-expr 的求值。可以用下面的抽象代码描述：

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

这个序列中的最后一条语句是用条件传送实现的——只有当测试条件 t 不满足时，ve 的值才会被复制到 v 中。

不是所有的条件表达式都可以用条件传送来编译。最重要的是，无论测试结果如何，我们给出的抽象代码会对 then-expr 和 else-expr 都求值。如果这两个表达式中的任意一个可能产生错误条件或者副作用，就会导致非法的行为。前面的一个例子（图 3-16）就是这种情况。实际上，我们在该例中引入副作用就是为了强制 GCC 用条件转移来实现这个函数。

作为说明，考虑下面这个 C 函数：

long cread(long *xp) {
    return (xp ? *xp : 0);
}

乍一看，这段代码似乎很适合被编译成使用条件传送，当指针为空时将结果设置为 0，如下面的汇编代码所示：

long cread(long *xp)
Invalid implementation of function cread
xp in register %rdi

1  cread:
2      movq  (%rdi), %rax      v = *xp
3      testq %rdi, %rdi        Test xp
4      movl  $0, %edx          Set ve = 0
5      cmove %rdx, %rax        If x==0, v = ve
6      ret                     Return v

不过，这个实现是非法的，因为即使当测试为假时，movq 指令（第 2 行）对 xp 的间接引用还是发生了，导致一个间接引用空指针的错误。所以，必须用分支代码来编译这段代码。

使用条件传送也不总是会提高代码的效率。例如，如果 then-expr 或者 else-expr 的求值需要大量的计算，那么当相对应的条件不满足时，这些工作就白费了。编译器必须考虑浪费的计算和由于分支预测错误所造成的性能处罚之间的相对性能。说实话，编译器并不具有足够的信息来做出可靠的决定；例如，它们不知道分支会多好地遵循可预测的模式。我们对 GCC 的实验表明，只有当两个表达式都很容易计算时，例如表达式分别都只是一条加法指令，它才会使用条件传送。根据我们的经验，即使许多分支预测错误的开销会超过更复杂的计算，GCC 还是会使用条件控制转移。

所以，总的来说，条件数据传送提供了一种用条件控制转移来实现条件操作的替代策略。它们只能用于非常受限制的情况，但是这些情况还是相当常见的，而且与现代处理器的运行方式更契合。

练习题 3.20 在下面的 C 函数中，我们对 OP 操作的定义是不完整的：

#define OP              /* Unknown operator */

long arith(long x) {
    return x OP 8;
}

当编译时，GCC 会产生如下汇编代码：

long arith(long x)
x in %rdi

arith:
    leaq   7(%rdi), %rax
    testq  %rdi, %rdi
    cmovns %rdi, %rax
    sarq   $3, %rax
    ret

A. OP 进行的是什么操作？

B. 给代码添加注释，解释它是如何工作的。

练习题 3.21 C 代码开始的形式如下：

long test(long x, long y) {
    long val = ____________________;
    if (____________________) {
        if (____________________)
            val = ____________________;
        else
            val = ____________________;
    } else if (____________________)
        val = ____________________;
    return val;
}

GCC 会产生如下汇编代码：

long test(long x, long y)
x in %rdi, y in %rsi

test:
    leaq   0(,%rdi,8), %rax
    testq  %rsi, %rsi
    jle    .L2
    movq   %rsi, %rax
    subq   %rdi, %rax
    movq   %rdi, %rdx
    andq   %rsi, %rdx
    cmpq   %rsi, %rdi
    cmovge %rdx, %rax
    ret
.L2:
    addq   %rsi, %rdi
    cmpq   $-2, %rsi
    cmovle %rdi, %rax
    ret

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

← 3.6.5 用条件控制来实现条件分支 3.6.7 循环 →