GCC是否会为静态分支预测生成次优代码？

Question

根据我在大学课程中所听到的，按照惯例，在 if 中放置更可能的条件而不是在 else 中放置更可能的条件可以帮助静态分支预测器。例如：

if (check_collision(player, enemy)) { // very unlikely to be true
    doA();
} else {
    doB();
}

可能被重写为：

if (!check_collision(player, enemy)) {
    doB();
} else {
    doA();
}

我发现了一篇博客文章《分支模式，使用GCC》，其中更详细地解释了这种现象：

if语句会生成向前分支。使它们不太可能被执行的理由是：处理器可以利用分支指令后面的指令已经被放置在指令单元内的指令缓冲区中这个事实。

它旁边还写着 (强调是我的):

编写if-else语句时，始终使“then”块比else块更容易执行，这样处理器就可以利用已经放置在指令获取缓冲区中的指令。

最终，Intel撰写了一篇文章《预防错误预测的分支和循环重组》，总结出两条规则：

当微处理器遇到分支时，在没有收集到数据的情况下使用静态分支预测，通常是第一次遇到分支时。规则很简单：

• 向前分支默认为未执行
• 向后分支默认为已执行

为了有效地编写代码以利用这些规则，在编写if-else或switch语句时，应首先检查最常见的情况，并逐步向下处理最不常见的情况。

据我所知，这个想法是流水线CPU可以按照指令缓存中的指令来执行代码段，而不会通过跳到代码段中的另一个地址来打破它。然而，我知道现代CPU微体系结构可能要复杂得多。

然而，看起来GCC没有遵循这些规则。考虑以下代码：

extern void foo();
extern void bar();

int some_func(int n)
{
    if (n) {
        foo();
    }
    else {
        bar();
    }
    return 0;
}

它生成的是（版本6.3.0，使用-O3 -mtune=intel）：

some_func:
        lea     rsp, [rsp-8]
        xor     eax, eax
        test    edi, edi
        jne     .L6            ; here, forward branch if (n) is (conditionally) taken
        call    bar
        xor     eax, eax
        lea     rsp, [rsp+8]
        ret
.L6:
        call    foo
        xor     eax, eax
        lea     rsp, [rsp+8]
        ret

我发现强制执行期望行为的唯一方法是通过使用__builtin_expect来重写 if 条件:

if (__builtin_expect(!!(condition), 1)) { // expected behavior } else { // unexpected behavior }

if (__builtin_expect(n, 1)) { // force n condition to be treated as true

因此，汇编代码将变为：

some_func:
        lea     rsp, [rsp-8]
        xor     eax, eax
        test    edi, edi
        je      .L2             ; here, backward branch is (conditionally) taken
        call    foo
        xor     eax, eax
        lea     rsp, [rsp+8]
        ret
.L2:
        call    bar
        xor     eax, eax
        lea     rsp, [rsp+8]
        ret

- Grzegorz Szpetkowski

---

Linux内核使用宏（称为__builtin_expect）来利用对条件分支的先验知识。 - wildplasser

现代英特尔CPU不使用静态分支预测。我也不认为GCC承诺在if/else语句的“true”子句中考虑最有可能的备选方案。你应该使用像wildplasser提到的__builtin_expect来告诉它哪个更有可能。或者更好的是，使用基于性能分析的优化。 - Ross Ridge

请查看Anger Fog的微架构手册。第3.16节“PM和Core 2中的静态预测”：“这些处理器不使用静态预测。预测器只是在第一次看到分支时根据分配给新分支的BTB条目中的内容随机做出一个预测。”。http://www.agner.org/optimize/ - Ross Ridge

即使在全面的程序中，这也不太可能有影响。除非您正在使用仅具有静态预测的处理器，否则大多数跳转将被动态预测。 - Ross Ridge

由于某种原因，gcc的"profile_estimate"优化过程猜测变量n有54%的可能性为0...（请参见-fdump-tree-all-all）。通常情况下，它有一个启发式规则，即“==”更可能是false，但似乎在这里没有使用。您可以在gcc的bugzilla上提出问题来询问相关情况。请注意，如果您使用-fprofile-generate编译程序，然后运行程序，再使用-fprofile-use重新编译，则gcc将获得实际统计数据并做出更好的决策。 - Marc Glisse

Answer 1

简短回答：不是。

GCC执行大量的非平凡优化，其中之一是通过控制流图来猜测分支概率。

根据GCC手册：

fno-guess-branch-probability 不使用启发式算法来猜测分支概率。

如果没有提供分析反馈（-fprofile-arcs），则GCC使用启发式算法来猜测分支概率。这些启发式算法基于控制流图。如果某些分支概率由__builtin_expect指定，则启发式算法用于猜测其余控制流图的分支概率，并考虑__builtin_expect信息。启发式算法和__builtin_expect之间的交互可能很复杂，在某些情况下，禁用启发式算法可能很有用，以便更容易理解__builtin_expect的影响。

-freorder-blocks也可能交换分支。

此外，正如OP提到的那样，可以使用__builtin_expect来覆盖该行为。

证明

请看下面的清单。

void doA() { printf("A\n"); }
void doB() { printf("B\n"); }
int check_collision(void* a, void* b)
{ return a == b; }

void some_func (void* player, void* enemy) {
    if (check_collision(player, enemy)) {
        doA();
    } else {
        doB();
    }
}

int main() {
    // warming up gcc statistic
    some_func((void*)0x1, NULL);
    some_func((void*)0x2, NULL);
    some_func((void*)0x3, NULL);
    some_func((void*)0x4, NULL);
    some_func((void*)0x5, NULL);
    some_func(NULL, NULL);
    return 0;
}

很明显，check_collision 大多数情况下会返回 0。因此，doB() 分支是可能的，GCC 可以猜测到这一点：

gcc -O main.c -o opt.a
objdump -d opt.a

some_func的汇编代码如下：

sub    $0x8,%rsp
cmp    %rsi,%rdi
je     6c6 <some_func+0x18>
mov    $0x0,%eax
callq  68f <doB>
add    $0x8,%rsp
retq   
mov    $0x0,%eax
callq  67a <doA>
jmp    6c1 <some_func+0x13>

但毫无疑问，我们可以防止GCC变得过于智能：

gcc -fno-guess-branch-probability main.c -o non-opt.a
objdump -d non-opt.a

我们将得到：

push   %rbp
mov    %rsp,%rbp
sub    $0x10,%rsp
mov    %rdi,-0x8(%rbp)
mov    %rsi,-0x10(%rbp)
mov    -0x10(%rbp),%rdx
mov    -0x8(%rbp),%rax
mov    %rdx,%rsi
mov    %rax,%rdi
callq  6a0 <check_collision>
test   %eax,%eax
je     6ef <some_func+0x33>
mov    $0x0,%eax
callq  67a <doA>
jmp    6f9 <some_func+0x3d>
mov    $0x0,%eax
callq  68d <doB>
nop
leaveq 
retq  

所以GCC将按照源代码的顺序留下分支。

我在这些测试中使用了gcc 7.1.1。

- ivaigult

---

公平起见，您应该使用相同的“-O”标志编译两个版本，然后在第二个版本中包含“-fno-guess-branch-probability”。没有优化的代码与使用“-O”的第一个代码完全不同，您无法得出结论，仅仅是“-fno-guess-branch-probability”标志改变了块的顺序，因为有数十个其他标志和优化应用于前者而不是后者。 - BeeOnRope

Answer 2

我认为你发现了一个“漏洞”

有趣的是，优化空间和不进行优化是唯一生成“最佳”指令代码的情况：gcc -S [-O0 | -Os] source.c

some_func:
FB0:
       pushl   %ebp
       movl    %esp, %ebp
       subl    $8, %esp
       cmpl    $0, 8(%ebp)
       je      L2
       call    _foo
       jmp     L3
2:
       call    _bar
3:
       movl    $0, %eax
       # Or, for -Os:
       # xorl    %eax, %eax
       leave
       ret

---

我的观点是...

---

some_func:
FB0:
       pushl   %ebp
       movl    %esp, %ebp
       subl    $8, %esp
       cmpl    $0, 8(%ebp)
       je      L2
       call    _foo

---

......直到并通过调用foo，一切都是“最优”的，从传统意义上讲，无论退出策略如何。

当然，最终决定优化的是处理器。

- veganaiZe

---

真的吗？又一个没有解释的踩票？这对任何人有什么帮助吗？这是确切的汇编输出（减去指令），它确实是传统CPU的最优选择——它跳转到else，而不是true条件。相应的gcc选项是违反直觉的。在这种情况下，对于现代x86 CPU来说，不存在最优代码。 - veganaiZe

我们具体讨论的是分支预测。这意味着在某个时候会有一个jmp指令。关键是没有jmp来调用foo... jmp是为了调用bar。在这种情况下，-O0和-Os之间唯一的区别是如何将零返回给调用环境。--该代码对于（旧）使用传统分支预测的x86 CPU是最优的（即在采取“then”情况时不使用jmp）。 - veganaiZe

我说的是 jmp，而不是 je。当然你需要一个 je（除非你在两个函数指针之间选择无分支），但是在 je 之后的代码可以是 call _foo / xor %eax,%eax / leave / ret，以避免使用 jmp。尾部复制会增加代码大小，但会减少动态指令计数，并减少所需的跳转次数。对于 call _foo 的情况，没有使用 jmp 或 jcc 指令。 - Peter Cordes

“分支预测”在这种情况下，与“调用”之前的“跳转”有关。据我所知，“jmp L3”只是必要的副作用，以到达退出代码。 - veganaiZe

感谢您抽出时间与我讨论，彼得。我尊重您的意见。那么，将对话重新引向我试图表达的观点（以及原帖），为什么-O3会跳转到foo而-Os/-O0不会呢？在这种情况下，传统的x86不会尝试预取else(bar)而不是then(foo)吗？目前的情况似乎与预期的行为相矛盾。 - veganaiZe