compiler - c to asm

GCC optó por la oportunidad perdida

Question

Estoy compilando este código C:

int mode; // use aa if true, else bb
int aa[2];
int bb[2];

inline int auto0() { return mode ? aa[0] : bb[0]; }
inline int auto1() { return mode ? aa[1] : bb[1]; }

int slow() { return auto1() - auto0(); }
int fast() { return mode ? aa[1] - aa[0] : bb[1] - bb[0]; }

Las funciones slow() y fast() tienen la intención de hacer lo mismo, aunque fast() hace con una instrucción de rama en lugar de dos. Quería comprobar si GCC colapsaría las dos ramas en una sola. Lo he intentado con GCC 4.4 y 4.7, con varios niveles de optimización, como -O2, -O3, -Os y -Ofast. Siempre da los mismos resultados extraños:

lento():

        movl    mode(%rip), %ecx
        testl   %ecx, %ecx
        je      .L10

        movl    aa+4(%rip), %eax
        movl    aa(%rip), %edx
        subl    %edx, %eax
        ret
.L10:
        movl    bb+4(%rip), %eax
        movl    bb(%rip), %edx
        subl    %edx, %eax
        ret

rápido():

        movl    mode(%rip), %esi
        testl   %esi, %esi
        jne     .L18

        movl    bb+4(%rip), %eax
        subl    bb(%rip), %eax
        ret
.L18:
        movl    aa+4(%rip), %eax
        subl    aa(%rip), %eax
        ret

De hecho, solo se genera una rama en cada función. Sin embargo, slow() parece ser inferior de una manera sorprendente: utiliza una carga extra en cada rama, para aa[0] y bb[0] . El código fast() usa directamente desde la memoria en los subl sin cargarlos primero en un registro. Entonces slow() usa un registro extra y una instrucción adicional por llamada.

Un simple micro-benchmark muestra que llamar fast() mil millones de veces lleva 0,7 segundos, frente a 1,1 segundos para slow() . Estoy usando un Xeon E5-2690 a 2.9 GHz.

¿Por qué debería ser esto? ¿Puedes modificar mi código fuente de alguna manera para que GCC haga un mejor trabajo?

Editar: aquí están los resultados con clang 4.2 en Mac OS:

lento():

        movq    _aa@GOTPCREL(%rip), %rax   ; rax = aa (both ints at once)
        movq    _bb@GOTPCREL(%rip), %rcx   ; rcx = bb
        movq    _mode@GOTPCREL(%rip), %rdx ; rdx = mode
        cmpl    $0, (%rdx)                 ; mode == 0 ?
        leaq    4(%rcx), %rdx              ; rdx = bb[1]
        cmovneq %rax, %rcx                 ; if (mode != 0) rcx = aa
        leaq    4(%rax), %rax              ; rax = aa[1]
        cmoveq  %rdx, %rax                 ; if (mode == 0) rax = bb
        movl    (%rax), %eax               ; eax = xx[1]
        subl    (%rcx), %eax               ; eax -= xx[0]

rápido():

        movq    _mode@GOTPCREL(%rip), %rax ; rax = mode
        cmpl    $0, (%rax)                 ; mode == 0 ?
        je      LBB1_2                     ; if (mode != 0) {
        movq    _aa@GOTPCREL(%rip), %rcx   ;   rcx = aa
        jmp     LBB1_3                     ; } else {
LBB1_2:                                    ; // (mode == 0)
        movq    _bb@GOTPCREL(%rip), %rcx   ;   rcx = bb
LBB1_3:                                    ; }
        movl    4(%rcx), %eax              ; eax = xx[1]
        subl    (%rcx), %eax               ; eax -= xx[0]

Interesante: clang genera condicionales sin ramas para slow() pero una rama para fast() ! Por otro lado, slow() hace tres cargas (dos de las cuales son especulativas, una será innecesaria) frente a dos para fast() . La implementación fast() es más "obvia" y, como con GCC, es más corta y usa un registro menos.

GCC 4.7 en Mac OS generalmente sufre el mismo problema que en Linux. Sin embargo, utiliza el mismo patrón "carga 8 bytes luego dos veces extrae 4 bytes" como Clang en Mac OS. Eso es algo interesante, pero no muy relevante, ya que el problema original de emitir subl con dos registros en lugar de una memoria y un registro es el mismo en cualquiera de las plataformas para GCC.

Answer 1

¿Ha intentado modificar los parámetros de los compiladores internos (--param name = value en la página man)? Esos no se cambian con ningún nivel de optimizaciones (con tres excepciones menores).

Algunos de ellos controlan la reducción / deduplicación del código.

Para algunas optimizaciones en esta sección, puede leer cosas como «valores más grandes pueden aumentar exponencialmente el tiempo de compilación».

Answer 2

La razón es que en el código intermedio inicial, emitido para slow() , la carga de memoria y la resta están en diferentes bloques básicos:

slow ()
{
  int D.1405;
  int mode.3;
  int D.1402;
  int D.1379;

  # BLOCK 2 freq:10000
  mode.3_5 = mode;
  if (mode.3_5 != 0)
    goto <bb 3>;
  else
    goto <bb 4>;

  # BLOCK 3 freq:5000
  D.1402_6 = aa[1];
  D.1405_10 = aa[0];
  goto <bb 5>;

  # BLOCK 4 freq:5000
  D.1402_7 = bb[1];
  D.1405_11 = bb[0];

  # BLOCK 5 freq:10000
  D.1379_3 = D.1402_17 - D.1405_12;
  return D.1379_3;
}

mientras que en fast() están en el mismo bloque básico:

fast ()
{
  int D.1377;
  int D.1376;
  int D.1374;
  int D.1373;
  int mode.1;
  int D.1368;

  # BLOCK 2 freq:10000
  mode.1_2 = mode;
  if (mode.1_2 != 0)
    goto <bb 3>;
  else
    goto <bb 4>;

  # BLOCK 3 freq:3900
  D.1373_3 = aa[1];
  D.1374_4 = aa[0];
  D.1368_5 = D.1373_3 - D.1374_4;
  goto <bb 5>;

  # BLOCK 4 freq:6100
  D.1376_6 = bb[1];
  D.1377_7 = bb[0];
  D.1368_8 = D.1376_6 - D.1377_7;

  # BLOCK 5 freq:10000
  return D.1368_1;
}

GCC se basa en la combinación de instrucciones para manejar casos como este (es decir, aparentemente no en el pase de optimización de mirilla) y la combinación de trabajos en el alcance de un bloque básico. Es por eso que la resta y la carga se combinan en una sola entrada en fast() y ni siquiera se consideran para combinar en slow() .

Más tarde, en el paso de reordenamiento del bloque básico, la resta en slow() se duplica y se mueve a los bloques básicos, que contienen las cargas. Ahora hay una oportunidad para que el combinador combine la carga y la resta, pero desafortunadamente, el pase combinador no se ejecuta nuevamente (y tal vez no se puede ejecutar tan tarde en el proceso de compilación con los registros duros ya asignados y esas cosas).

Answer 3

No tengo una respuesta en cuanto a por qué GCC no puede optimizar el código de la forma en que lo desea, pero tengo una forma de reorganizar su código para lograr un rendimiento similar. En lugar de organizar su código de la manera en que lo hizo en slow() o fast() , le recomendaría que defina una función en línea que devuelva aa o bb función del mode sin necesidad de una bifurcación:

inline int * xx () { static int *xx[] = { bb, aa }; return xx[!!mode]; }
inline int kwiky(int *xx) { return xx[1] - xx[0]; }
int kwik() { return kwiky(xx()); }

Cuando compilado por GCC 4.7 con -O3 :

    movl    mode, %edx
    xorl    %eax, %eax
    testl   %edx, %edx
    setne   %al
    movl    xx.1369(,%eax,4), %edx
    movl    4(%edx), %eax
    subl    (%edx), %eax
    ret

Con la definición de xx() , puede redefinir auto0() y auto1() manera:

inline int auto0() { return xx()[0]; }
inline int auto1() { return xx()[1]; }

Y, a partir de esto, debería ver que slow() ahora compila en código similar o idéntico a kwik() .