编译器可以如何处理分支信息？

Question

编译器可以如何处理分支信息？

optimizationassemblycompiler-constructionbranch-predictionx86

12

在现代Pentium上，似乎不再可能向处理器提供分支提示。假设像gcc这样的分析编译器使用基于配置文件的优化来获取有关可能分支行为的信息，它能做些什么来生成更快执行的代码呢？

我所知道的唯一选择是将不太可能的分支移到函数的末尾。还有其他选择吗？

更新。 http://download.intel.com/products/processor/manual/325462.pdf 第2卷a，第2.1.1节说：

“分支提示前缀（2EH、3EH）允许程序向处理器提供有关分支的最可能代码路径的提示。只能将这些前缀与条件分支指令（Jcc）一起使用。在Intel 64或IA-32指令中，对分支提示前缀和/或其他未定义操作码的其他使用保留；这种使用可能会导致不可预测的行为。”

然而，我不知道这些是否实际上有任何影响。

另一方面，http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf 的3.4.1节说：

“编译器生成的代码可以提高Intel处理器中分支预测的效率。 Intel C ++编译器通过以下方式实现：

将代码和数据保留在不同的页面上
使用条件移动指令来消除分支
生成与静态分支预测算法一致的代码
适当时进行内联
如果迭代次数可预测，则展开循环

通过基于配置文件的优化，编译器可以布置基本块以消除函数最常执行路径上的分支或至少提高其可预测性。分支预测在源级别不需要考虑。有关更多信息，请参见Intel C ++编译器文档。”

http://cache-www.intel.com/cd/00/00/40/60/406096_406096.pdf在“使用PGO进行性能改进”中提到：

PGO最适用于具有许多难以在编译时预测的频繁执行分支的代码。例如，具有密集错误检查的代码，在其中大多数情况下错误条件都是错误的。可以将不经常执行（冷）的错误处理代码重新定位，使分支很少被错误地预测。将最小化插入频繁执行（热）代码的冷代码可改善指令缓存行为。

- marshall

4个回答

3

如果明显地可以看出一个循环很少被执行，或者通常只迭代很少的次数，那么编译器可能会避免展开循环，因为这样做会增加许多有害的复杂性来处理边缘情况（如奇数次迭代等）。在这种情况下应该避免使用向量化。

编译器可能会重新排列嵌套测试，以便最常导致短路的测试用于避免对50%通过率的某个东西进行测试。

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

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

- sh1

你知道哪些编译器实际上会执行这些操作吗？例如，gcc会吗？ - marshall

2

我能想到的，你有两个选择。

选项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 */

希望这可以帮助您。

- Sparky

谢谢。我的问题是，选项1在现代Pentium上如何转换为汇编？ - marshall

1

它可以使得未被执行的分支成为最常用路径，这有两个重要影响：

每个时钟周期只能执行一个分支，或者在某些处理器上甚至需要2个时钟周期，因此如果还有其他分支（通常是这样，大部分有意义的代码都在循环中），那么执行分支会带来不好的消息，而不执行分支则相对较好。
当分支预测错误时，代码必须执行的部分更可能在代码缓存（或µop缓存，在适用的情况下）中。如果不是这样，那将是重新启动流水线和等待缓存未命中的双重打击。在大多数循环中，这不太是问题，因为分支的两侧很可能都在缓存中，但在大型循环和其他代码中，这就成为了问题。

它还可以基于比启发式猜测更好的数据来决定是否进行if-conversion。If-conversions可能看起来像“总是一个好主意”，但实际上并非如此，它们只是“通常是一个好主意”。如果分支在分支实现中被预测得非常好，则进行if-conversion的代码可能会变慢。

- harold

“使得贯穿成为最常用的路径”当然是指移动代码。例如：“if(x<0) x=-x; label:statement;”，并且预计x几乎永远不会为负数。我们将代码“x=-x；goto label;”移到远离的地方，然后将原始代码更改为“if(x<0) goto farawaycode; label:statement;”。现在代码已经改变，以至于条件分支几乎不会被执行。 - gnasher729

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- migle · Accepted Answer

你想获取信息的来源有两个：

Intel 64和IA-32架构软件开发人员手册（三卷）。这是一个有着几十年发展历史的庞大作品。在许多主题方面，包括浮点运算，它是我所知道的最好的参考资料。在这种情况下，您需要查看第2卷，指令集参考。
Intel 64和IA-32架构优化参考手册。这将以比较简要的术语告诉你每个微体系结构可以期待什么。

现在，我不知道你所说的“现代Pentium”处理器是什么，现在是2013年，对吧？已经没有Pentium了...

该指令集支持通过条件分支指令的前缀（如JC、JZ等）告诉处理器分支是否被采取。请参见(1)第2A卷第2.1.1节（我所拥有的版本）。有2E和3E前缀用于未采取和已采取。

至于这些前缀是否实际起作用，如果我们可以获得这些信息，那将出现在优化参考手册中，即您想要的微体系结构的章节（我确信这不会是Pentium）。

除了使用这些内容，参考手册还有一个完整的章节讨论了该主题，即第3.4.1节（我所拥有的版本）。

将以下步骤简述一下：

使用条件指令（CMOV、SETcc）消除跳转指令
考虑静态预测算法（3.4.1.3）
内联
循环展开

此外，一些编译器（例如GCC），即使当无法使用CMOV时，通常也执行按位运算来选择计算出的两个不同值之一，从而避免分支。特别是在矢量化循环时，它会使用SSE指令进行操作。

基本上，静态条件如下：

无条件分支预测将被采取（...有点可预见...）
间接分支被预测不被采取（因为存在数据依赖关系）
向后条件被预测将被采取（对于循环非常有用）
向前条件被预测不被采取

你可能想阅读整个第3.4.1节。