Получает ли GCC субоптимальный код для предсказания статической ветки?

Из моего университетского курса я слышал, что по соглашению лучше разместить более вероятное условие в 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, Реорганизация ветвей и циклов для предотвращения Mispredicts, которая суммирует это с двумя правилами:

Статическое предсказание ветвления используется, когда нет данных, собранных микропроцессор, когда он встречает ветвь, которая обычно является первый раз встречается ветка. Правила просты:

  • Перемещение по умолчанию по умолчанию не принято
  • Отключенная ветка по умолчанию принята

Чтобы эффективно писать свой код, чтобы воспользоваться этими правила при написании операторов if-else или switch, проверьте наиболее общие случаи сначала и работать постепенно вниз до наименее общего.

Как я понимаю, идея состоит в том, что конвейерный 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

Ответы

Ответ 1

Короткий ответ: нет, это не так.

GCC делает метрики тонны нетривиальной оптимизации, а одна из них - гадать вероятности ветвления, судя по графу потока управления.

В соответствии с Руководство GCC:

FNo предугадывать Гиса-вероятность

Не угадывайте вероятности ветвей, используя эвристики.

GCC использует эвристику, чтобы угадать вероятности ветвей, если они не обеспечиваемое профилирующей обратной связью (-fprofile-arcs). Эти эвристики основанный на графике потока управления. Если некоторые вероятности ветвления указанный __builtin_expect, тогда эвристика используется для угадывания вероятности ветвления для остальной части графика потока управления, принимая во вкладке __builtin_expec t. Взаимодействие между эвристика и __builtin_expect могут быть сложными, а в некоторых случаях может быть полезно отключить эвристику, чтобы эффекты __builtin_expect легче понять.

-freorder-blocks может также обмениваться ветками.

Кроме того, как упоминалось в OP, поведение может быть переопределено с помощью __builtin_expect.

Proof

Посмотрите следующий список.

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

Asm 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 для этих тестов.

Ответ 2

Думаю, что вы нашли ошибку "

Самое смешное, что оптимизация для space и нет оптимизации - это случаи только, в которых генерируется "оптимальный" код команды: 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 все является "оптимальным", в традиционном смысле, независимо от стратегии выхода.

Оптимальность в конечном итоге определяется процессором, конечно.