编译器如何处理分支信息?

Question

在现代Pentium上，似乎不再可能向处理器提供分支提示。假设具有概要文件引导优化的分析编译器(如gcc)获得了关于可能的分支行为的信息，它能做些什么来生成执行速度更快的代码呢?

我知道的唯一选择是将不可能的分支移动到函数的末尾。还有别的吗?

更新。

http://download.intel.com/products/processor/manual/325462.pdf volume 2a，第2.1.1节说

"分支提示前缀(2EH, 3EH)允许程序给处理器一个关于最可能的代码路径的提示的一个分支。这些前缀仅用于条件分支指令(Jcc)。分支提示前缀的其他用法和/或其他带有Intel 64或IA-32指令的未定义操作码保留;这样的使用可能会造成不可预知的后果的行为。"

我不知道这些是否真的有任何效果。

另一方面，第3.4.1节。

"编译器生成的代码提高了英特尔处理器分支预测的效率。英特尔c++编译器通过:

• 将代码和数据保存在单独的页面
• 使用条件移动指令消除分支
• 生成与静态分支预测算法一致的代码
• 内联
• 展开，如果迭代次数是可预测的

通过配置文件引导的优化，编译器可以布局基本块以最大限度地消除分支经常执行的函数路径，或者至少提高它们的可预测性。分支预测需求不要在源级上引起关注。有关更多信息，请参阅英特尔c++编译器文档。"

http://cache-www.intel.com/cd/00/00/40/60/406096_406096.pdf在"PGO的性能改进"中说

"PGO最适合具有许多频繁执行的分支的代码在编译时进行预测。具有密集错误检查的代码就是一个例子大多数情况下，错误条件为假。不经常执行的(冷)错误处理代码可以重新定位，因此分支很少被预测错误。最小化将冷代码穿插到频繁执行的(热)代码中可以提高指令缓存的行为。

Answer 1

您想要的信息有两个可能的来源:

1. 有Intel 64和IA-32架构软件开发人员手册(3卷)。这是一项历经数十年发展的巨大工作。它是我所知道的关于许多主题的最好的参考，包括浮点数。在本例中，您想要检查卷2，指令集引用。
2. 有Intel 64和IA-32架构优化参考手册。这将简要地告诉您每个微架构的期望。

现在，我不知道你说的"现代奔腾"处理器是什么意思，这是2013年，对吗?没有奔腾了…

指令集支持告诉处理器该分支是否被条件分支指令(如JC、JZ等)的前缀所接受。参见(1)的2A卷，第2.1.1节(我拥有的版本)指令前缀。未取和取分别有2E和3E前缀

至于这些前缀是否真的有任何影响，如果我们能得到这些信息，它将在优化参考手册，你想要的微架构部分(我敢肯定它不会是奔腾)。

除了使用这些，在优化参考手册中有一个完整的章节是关于这个主题的，那是第3.4.1节(我拥有的版本)。

在这里复制没有意义，因为您可以免费下载手册。简要:

• 使用条件指令(CMOV, SETcc)消除分支，
• 考虑静态预测算法(3.4.1.3)，
• 内联
• 循环展开

同样，一些编译器，例如GCC，即使在不可能使用CMOV的情况下，也经常执行位算术来从两个不同的计算项中选择一个，从而避免分支。在向量化循环时，SSE指令尤其如此。

基本上，静态条件是:

• 预计将采取无条件分支(…)…)
• 预测不采取间接分支(因为数据依赖)
• 预测将采用向后条件(适用于循环)
• 预测不采用正向条件

你可能想阅读完整的3.4.1节

Answer 2

如果很明显很少进入循环，或者它通常迭代很少，那么编译器可能会避免展开循环，因为这样做会增加很多有害的复杂性来处理边缘条件(奇数迭代等)。在这种情况下，尤其应该避免矢量化。

编译器可能会重新排列嵌套测试，以便最经常导致快捷方式的测试可以用来避免对通过率为50%的东西执行测试。

可以优化寄存器分配，以避免在通常情况下很少使用的块强制寄存器溢出。

这些只是一些例子。我肯定还有其他我没想到的。

Answer 3

在我的脑海里，你有两个选择。

选项#1:通知编译器提示，并让编译器适当地组织代码。例如，GCC支持以下命令…

__builtin_expect((long)!!(x), 1L)  /* GNU C to indicate that <x> will likely be TRUE */
__builtin_expect((long)!!(x), 0L)  /* GNU C to indicate that <x> will likely be FALSE */

如果您将它们放在宏形式中，例如…

#if <some condition to indicate support>
    #define LIKELY(x)    __builtin_expect((long)!!(x), 1L)
    #define UNLIKELY(x)  __builtin_expect((long)!!(x), 0L)
#else
    #define LIKELY(x)   (x)
    #define UNLIKELY(x) (x)
#endif

…

if (LIKELY (x != 0)) {
    /* DO SOMETHING */
} else {
    /* DO SOMETHING ELSE */
}

这使得编译器可以根据静态分支预测算法自由地组织分支，并且/或者如果处理器和编译器支持它，可以使用指示哪个分支更有可能被采用的指令。

选项#2:使用数学来避免分支。

if (a < b)
    y = C;
else
    y = D;

可以重写为…

x = -(a < b);   /* x = -1 if a < b, x = 0 if a >= b */
x &= (C - D);   /* x = C - D if a < b, x = 0 if a >= b */
x += D;         /* x = C if a < b, x = D if a >= b */

希望这对你有帮助。

Answer 4

它可以使穿越(即没有采取分支的情况)成为最常用的路径。这有两大影响:

1. 每个时钟只能占用一个分支，或者在某些处理器上甚至每2个时钟占用一个分支，所以如果有任何其他分支(通常有，大多数重要的代码都在循环中)，一个被占用的分支是坏消息，一个未被占用的分支则不那么坏。
2. 当分支预测器错误时，它必须执行的代码更有可能在代码缓存中(或µop缓存，如果适用)。如果不是，那将是重新启动管道和等待缓存丢失的双重打击。这在大多数循环中不是一个问题，因为分支的两边都可能在缓存中，但它在大循环和其他代码中发挥作用。

它还可以根据更好的数据而不是启发式猜测来决定是否进行if转换。如果转换似乎"总是一个好主意"，但它们不是，它们只是"经常是一个好主意"。如果分支实现中的分支被很好地预测，那么If转换的代码很可能会变慢。