GCC génère-t-il du code sous-optimal pour la prédiction statique des branchements ?

Question

De mon cours universitaire, j'ai entendu dire que, par convention, il est préférable de placer les conditions les plus probables dans if plutôt que dans else ce qui peut aider le statique prédicteur de branche. Par exemple :

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

peut être réécrit comme suit :

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

J'ai trouvé un article de blog Patrons de branche, utilisation de GCC qui explique ce phénomène plus en détail :

Les branches avant sont générées pour les instructions if. La raison pour laquelle de les rendre peu susceptibles d'être prises est que le processeur peut tirer du fait que les instructions suivant l'instruction de branchement peuvent déjà être placées dans le tampon d'instruction à l'intérieur de l'unité d'instruction. unité d'instruction.

A côté, il est dit (c'est moi qui souligne) :

Lorsque vous écrivez une instruction if-else, toujours faire le bloc "alors" plus d'être exécuté que le bloc else , d'instructions déjà placées dans le tampon d'extraction d'instructions. d'instructions.

En fin de compte, il y a un article, écrit par Intel, Réorganisation des branches et des boucles pour éviter les mauvaises prédictions qui résume cela en deux règles :

La prédiction statique des branches est utilisée lorsque microprocesseur lorsqu'il rencontre un branchement, ce qui est typiquement la première fois qu'un branchement est rencontré. Les règles sont simples :

• Une branche avant a pour valeur par défaut pas pris
• Une branche arrière a pour valeur par défaut prise

Afin d'écrire efficacement votre code pour profiter de ces règles, lorsque vous écrivez si-else o commutateur s les plus courants et descendez progressivement vers les moins courants.

D'après ce que j'ai compris, l'idée est que le CPU en pipeline peut suivre les instructions du cache d'instructions sans les interrompre en sautant à une autre adresse dans le segment de code. Je suis conscient, cependant, que cela peut être largement simplifié dans le cas des microarchitectures modernes de CPU.

Cependant, il semble que GCC ne respecte pas ces règles. Étant donné le code :

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

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

qu'il génère (version 6.3.0 avec -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

La seule façon que j'ai trouvée pour forcer le comportement désiré est de réécrire l'interface de l'utilisateur. if en utilisant __builtin_expect comme suit :

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

donc le code d'assemblage deviendrait :

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

La réponse courte : non, ce n'est pas le cas.

GCC fait des tonnes de métriques d'optimisation non triviale et l'une d'entre elles consiste à deviner les probabilités de branchement en se basant sur le graphique de flux de contrôle.

Selon Manuel GCC :

fno-guess-branch-probabilité

Ne devinez pas les probabilités de branche en utilisant heuristique.

GCC utilise des heuristiques pour deviner les branches fournies par le retour de profilage ( -fprofile-arcs ). Ces heuristiques sont basée sur le graphe de flux de contrôle. Si certaines probabilités de branche sont spécifiées par __builtin_expect puis l'heuristique est utilisée pour deviner probabilités de branche pour le reste du graphe de flux de contrôle, en prenant le site __builtin_expec de l'info en compte. Les interactions entre les heuristiques et __builtin_expect peut être complexe, et dans certains cas peut être utile de désactiver le t __builtin_expect sont plus faciles à comprendre.

-freorder-blocks peuvent également échanger des branches.

De plus, comme l'a mentionné l'OP, le comportement peut être modifié avec la fonction __builtin_expect .

Preuve

Regardez la liste suivante.

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;
}

Il est évident que check_collision retournera 0 la plupart du temps. Ainsi, le doB() est probable et GCC peut le deviner :

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

L'asm de some_func est :

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>

Mais il est certain que nous pouvons empêcher GCC d'être trop intelligent :

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

Et nous aurons :

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  

Donc GCC laissera les branches dans l'ordre des sources.

J'ai utilisé gcc 7.1.1 pour ces tests.

Answer 2

Je pense que vous avez trouvé un "bug".

Le plus drôle, c'est que l'optimisation pour espace y pas de l'optimisation sont les seulement les cas dans lesquels le code d'instruction "optimal" est généré : 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

---

Ce que je veux dire, c'est que...

---

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

---

... jusqu'à & par l'appel à foo tout est "optimal", au sens traditionnel du terme, quelle que soit la stratégie de sortie.

L'optimalité est en fin de compte déterminée par le processeur, bien sûr.