分支预测器是否会启动？

Question

大多数(如果不是全部)现代处理器都使用一种称为"分支预测"的技术,用它来猜测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;
}

分支预测器将在第二个示例中"预测"分支,但第一个示例又如何呢？会猜到吗？什么将被加载到管道？是否有任何速度可以通过任何一个例子忽略块中实际代码的影响？

我的猜测,它取决于编译器:如果使用跳转实现语句(在汇编中),只有在寄存器中的compare标志置位时才进行跳转.现在汇编指令究竟是什么样的取决于编译器.除非每个编译器都有一种常用的处理方式,我怀疑它是否存在,否则这是编译器依赖的.在这种情况下,最新的Visual Studio C++和GC++编译器会发生什么？

作为hexafraction指出,以及如何返回值之间的关系someCondition确定...分支预测器可能不踢.我们只考虑true和false作为返回值.对于条件,让我们假设它是一个已经预定的字段,在函数内部或外部,局部变量和一些算术语句.

老实说,我并不怀疑条件是局部变量的情况与该字段已在同一函数中预定的情况之间存在很大差异.

Answer 1

最有可能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 对其输入和标志都有数据依赖性。条件分支是一种控制依赖性。使用 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/ , recent Intel CPUs remember patterns of up to 64 iterations for loops. So loops that run the same number of iterations every time don't have a branch mispredict on the last iteration, if the number of iterations is 64 or less.

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

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

在 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

lsIntel Sandybridge (i5 2500k) 在低功耗时钟速度下，使用默认的 cpufreq 调速器，在完成之前不会提高时钟速度。