编译器级别的分支预测

Question

我一直在阅读有关分支预测的内容，但我发现的唯一实现主要是在计算机的硬件方面。处理器似乎负责大部分预测。我的问题是，编译器可以进行分支预测吗？ 我唯一发现的是两种方法，函数内联和循环展开。这些被认为是正确的吗？还在用吗？

Answer 1

当然。 如果编译器知道的话，它就可以获得预测信息：

• 通过仪器运行收集的统计分支概率
• 仪器运行收集的变量值的统计分布；然后它可以预测条件的平均结果，从而预测分支
• 程序员关于条件的频率或偏差的断言
• 基于范围的循环边界估计（如果未知，则默认为“10”:)
• 知道分支向后返回到循环顶部（预测“已采取”

使用这些信息，它可以预测条件的可能结果，然后生成倾向于由硬件正确“预测”的分支指令。

一些编译器完成的一组特别有趣的优化是“跟踪调度”，它根据顺序遇到的分支的概率来确定代码的路径集。通过确定最高概率路径，编译器可以在整个路径上进行优化，而不仅仅是在基本块内进行优化。

有时编译器会生成间接使用硬件分支预测功能的分支代码。 编译型 OO 语言（静态或 JITted）必须编译方法调用，并且间接跳转的成本很高。 一个简单的技巧是在每个调用站点保留最近调用的方法的小型动态缓存，并检查正在分派的对象类型。 如果在调用站点频繁使用相同类型的对象进行分派，则高速缓存中的第一个（第二个条目稍少）的比较/分支序列很有可能，并且执行的代码因此避免了错误预测。 这比间接跳转要好得多。

最后一个标准技巧：如果您可以避免执行分支，则不必正确预测它！ 许多代码序列看起来像这样：

  if (exp1 relop exp2)
      X = Y
  endif

现代CPU具有“谓词”指令，实际上是“MOV_if_relop A to B”， 对于所有关系条件等于、不等于、小于等。 因此，编译器不会为上述构造生成分支，而是生成：

  <compute exp1 and exp2>
  CMP  exp1,exp2 ; sets condition code
  MOVif_relop  X,Y