编译器级别的分支预测

Question

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

Answer 1

当然.如果编译器知道,它可以获得预测信息:

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

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

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

有时编译器会生成间接使用硬件分支预测功能的分支代码.编译的OO语言(静态或JITted)必须编译方法调用,并且跳转间接是昂贵的.一个廉价的技巧是在每个调用站点保留最近调用的方法的小动态缓存,并检查被调度的对象类型.如果在调用站点频繁使用相同类型的对象进行调度,则高速缓存中的第一个(并且稍微少于第二个)条目的比较/分支序列是非常可能的,并且执行的代码因此避免了错误预测.这比跳跃间接要好得多.

最后一个标准技巧:如果你可以避免做分支,你就不必正确预测它!许多代码序列看起来像这样:

  if (exp1 relop exp2)
      X = Y
  endif

现代CPU具有"谓词"指令,其实际上是"MOV_if_relop A到B",用于所有相关条件相等,不等于,等等.因此,编译器生成:而不是为上述构造生成分支.

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