economia - ¿GCC genera código subóptimo para la predicción de bifurcación estática?

subóptimo definicion

Question

De mi curso universitario, me enteré de que, por convención, es mejor colocar una condición más probable en if que en else , lo que puede ayudar al pronosticador de la rama estática . Por ejemplo:

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

puede ser reescrito como:

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

Encontré una publicación de blog Branch Patterns, Using GCC , que explica este fenómeno con más detalle:

Las ramas hacia adelante se generan para las sentencias if. El motivo por el que no es probable que se tomen es que el procesador puede aprovechar el hecho de que las instrucciones que siguen a la instrucción de bifurcación ya pueden colocarse en el búfer de instrucciones dentro de la Unidad de Instrucción.

al lado, dice (énfasis mío):

Al escribir una instrucción if-else, siempre haga que el bloque "then" sea más probable que se ejecute que el bloque else , de modo que el procesador puede aprovechar las instrucciones ya colocadas en el buffer de recuperación de instrucciones.

En última instancia, hay un artículo, escrito por Intel, Branch and Loop Reorganization to Prevent Mispredicts , que resume esto con dos reglas:

La predicción de derivación estática se usa cuando el microprocesador no recopila datos cuando encuentra una derivación, que suele ser la primera vez que se encuentra una derivación. Las reglas son simples:

• Una rama de reenvío predeterminada no se toma
• Una rama hacia atrás adopta por defecto

Para escribir de manera efectiva su código para aprovechar estas reglas, al escribir if-else o cambiar las declaraciones, marque primero los casos más comunes y trabaje progresivamente hasta llegar a los menos comunes.

Según tengo entendido, la idea es que la CPU canalizada puede seguir las instrucciones de la memoria caché de instrucciones sin romperla saltando a otra dirección dentro del segmento de código. Sin embargo, soy consciente de que esto puede ser demasiado simplificado en caso de microarquitecturas de CPU modernas.

Sin embargo, parece que GCC no respeta estas reglas. Dado el código:

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

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

genera (versión 6.3.0 con -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 única forma que encontré para forzar el comportamiento deseado es reescribiendo la condición if usando __builtin_expect siguiente manera:

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

por lo que el código de ensamblado se convertiría en:

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

Creo que has encontrado un "error"

Lo curioso es que la optimización del espacio y la no optimización son los únicos casos en los que se genera el código de instrucción "óptimo": gcc -S [-O0 | -Os] source.c 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

Mi punto es que ...

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

... hasta y a través de la llamada a foo todo es "óptimo", en el sentido tradicional, independientemente de la estrategia de salida.

La optimalidad la determina el procesador, por supuesto.

Answer 2

La respuesta corta: no, no lo es.

GCC hace métricas de optimización no trivial y una de ellas adivina las probabilidades de ramificación a juzgar por el gráfico de flujo de control.

De acuerdo con el manual de GCC :

fno-guess-branch-probability

No adivine las probabilidades de ramificación usando heurística.

GCC usa la heurística para adivinar las probabilidades de las ramas si no son provistas por los comentarios de perfil ( -fprofile-arcs ). Estas heurísticas se basan en el gráfico de flujo de control. Si __builtin_expect especifica algunas probabilidades de __builtin_expect , entonces las heurísticas se usan para adivinar las probabilidades de bifurcación para el resto del gráfico de flujo de control, teniendo en cuenta la información de __builtin_expec t. Las interacciones entre la heurística y __builtin_expect pueden ser complejas, y en algunos casos, puede ser útil desactivar la heurística para que los efectos de __builtin_expect sean más fáciles de comprender.

-freorder-blocks pueden intercambiar ramas.

Además, como OP mencionó, el comportamiento podría ser anulado con __builtin_expect .

Prueba

Mira la siguiente lista.

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

Es obvio que check_collision devolverá 0 mayoría de las veces. Entonces, la rama doB() es probable y GCC puede adivinar esto:

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

El asm de some_func es:

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>

Pero seguro, podemos hacer que GCC no sea demasiado inteligente:

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

Y obtendremos:

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  

Entonces, GCC abandonará las sucursales en orden de origen.

Utilicé gcc 7.1.1 para esas pruebas.