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

Question

从我的大学课程中，我听说，按照惯例，最好将更可能的条件放在if中，而不是放在其他条件中，这可能有助于静态分支预测器。例如：

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块更容易执行，以便处理器可以利用已经放在取指令缓冲区中的指令。

最后，英特尔撰写了一篇文章《防止预测失误的分支和循环重组》，其中总结了两条规则:

静态分支预测用于微处理器在遇到分支时未收集任何数据的情况，这通常是第一次遇到分支。规则很简单：

• 一个前向分支默认为未采取
• 一个向后分支默认为已获取

为了有效地编写代码以利用这些规则，在编写 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=英特尔）：

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(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

Answer 1

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

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

高达

当然，最优性最终取决于处理器。

Answer 2

简短的回答是:不，不是。

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

根据GCC手册：

f无-猜测-分支-概率

不要使用试探法猜测分支概率。

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

< code>-freorder-blocks也可以交换分支。

此外，正如OP提到的，该行为可能会被< code>__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的asm是：

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 进行这些测试。