分支预测器是否参与其中？

Question

大多数（如果不是全部）现代处理器都使用一种称为 "branch prediction" 的技术，它会猜测在 if-then-else 分支中的路径。

我对这个方案有疑问。假设我们有这段代码，没有使用特定语言：

if(someCondition)
{
    // some action
    return someValue;
}
// some other action
return someOtherValue;

从逻辑上讲，该代码等效于此代码：

if(someCondition)
{
    // some action
    return someValue;
}
else
{
    // some other action
    return someOtherValue;
}

分支预测器会 'predict' 第二个例子中的分支，但是第一个例子呢？它会猜吗？什么将被加载到管道中？忽略块中实际代码的影响，这两个示例中的任何一个都可以提高速度吗？

我的猜测，这取决于编译器：If 语句是使用跳转（在汇编中）实现的，只有在设置了寄存器中的比较标志时才会进行跳转。现在汇编指令究竟是什么样子取决于编译器。除非每个编译器都有一种通用的处理方式（我怀疑是否存在），否则这取决于编译器。在那种情况下，最新的 Visual Studio C++ 和 GC++ 编译器会发生什么情况？

正如 hexafraction 指出的那样，return 值之间的关系以及 someCondition 的确定方式......分支预测器可能不会启动。让我们只考虑 true 和 false return 值。对于条件，我们假设它是函数内部或外部已经预先确定的字段、局部变量和一些算术语句。

老实说，我不怀疑条件是局部变量的情况和字段在同一个函数中已经预先确定的情况有什么区别。

Answer 1

这两个代码示例之间没有区别。 else 无关紧要，因为不需要在 true 子句的末尾进行分支。即使那不是真的，真子句末尾的分支也不是有条件的。

换句话说，代码必须编译成类似于：

  Compute test expression
  Branch if false to false_label
  True action
  Return some value
False_label;
  False action
  Return some other value

Answer 2

很可能 gcc -O3 会使用条件移动指令将其优化为无分支序列。例如在 x86 上

# generate someValue in %rax, the x86-64 ABI's return value register
# generate someOtherValue in %rdi, to pick one at random
    test someCondition   # probably actually test or cmp a register
    cmovz  %rdi, %rax    # copy %rdi to %rax, if the zero flag is set.
    ret

cmov 对其输入和标志都有数据依赖性。条件分支是 control 依赖项。使用 cmov 通常很好，除非它是一个长依赖链的一部分并且分支是相当可预测的。

如果 if 块内有更多工作，gcc 将生成条件跳转指令。

# generate someValue in %rax
    test someCondition
    jz  .zero
    ret
.zero:
    # compute someOtherValue.  This work doesn't need to happen at all
    # if we don't end up needing it, unlike in the cmov case
    mov  someOtherValue, %rax
    ret

分支预测对条件跳转指令进行操作，而不是对高级结构进行操作。如果循环条件为真，则使用相同的指令跳回循环顶部。根据 http://agner.org/optimize/ 的说法，最近的英特尔 CPU 记住了多达 64 次循环迭代的模式。因此，如果迭代次数为 64 或更少，则每次运行相同迭代次数的循环在最后一次迭代中不会出现分支错误预测。

因此，分支预测器不是根据指令序列来猜测是否会执行跳转。每个单独的分支指令在被执行时都会在分支历史缓冲区中获得一个条目。是的，每个编译器别无选择，只能使用 jcc（条件代码跳转）指令来实现 branches/loops.

默认为预测未采纳。如果该预测是正确的，CPU 不会从缓存中逐出可能仍然有用的信息来腾出空间。有关更多底层详细信息，请参阅 Agner Fog 的微架构文档。

在 Linux 上，要查看正在运行的分支预测器，您可以使用 perf stat:

perf stat /bin/ls  # in some big directory
    ... normal ls output

 Performance counter stats for '/bin/ls':

     10.403069      task-clock (msec)         #    0.094 CPUs utilized
         2,255      context-switches          #    0.217 M/sec
             0      cpu-migrations            #    0.000 K/sec
           190      page-faults               #    0.018 M/sec
    16,612,260      cycles                    #    1.597 GHz
     7,843,399      stalled-cycles-frontend   #   47.21% frontend cycles idle
     5,205,565      stalled-cycles-backend    #   31.34% backend  cycles idle
    20,227,093      instructions              #    1.22  insns per cycle
                                              #    0.39  stalled cycles per insn
     3,975,777      branches                  #  382.173 M/sec
########### These two lines ######
        55,785      branch-misses             #    1.40% of all branches

   0.110765717 seconds time elapsed

英特尔 Sandybridge (i5 2500k)，在低功耗时钟速度下，使用默认的 cpufreq 调控器，在 ls 完成之前时钟速度不会上升。

分支预测器是否参与其中？

Does the branch predictor kick in with this?

optimization

performance

compiler-optimization

branch-prediction