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

Question

从我的大学课程中,我听说,按照惯例,最好放置更多可能的条件if而不是in 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块更可能被执行,因此处理器可以利用已经放在指令获取缓冲区中的指令.

最终,有一篇由英特尔,分支和循环重组编写的文章,以防止错误预测,其中总结了两个规则:

当微处理器遇到分支时没有收集数据时使用静态分支预测,这通常是第一次遇到分支.规则很简单:

• 正向分支默认不采用
• 向后分支默认采用

为了有效地编写代码以利用这些规则,在编写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

我发现强制所需行为的唯一方法是if使用__builtin_expect以下方法重写条件:

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

... up to & through 号称foo一切都是“最优的”，在传统意义上，无论退出策略如何。

当然，最优性最终由处理器决定。