¿Por qué GCC genera un ensamblaje tan radicalmente diferente para casi el mismo código C?

184

Mientras escribía una ftolfunción optimizada , encontré un comportamiento muy extraño en GCC 4.6.1. Déjame mostrarte el código primero (para mayor claridad, marqué las diferencias):

fast_trunc_one, C:

int fast_trunc_one(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = mantissa << -exponent;                       /* diff */
    } else {
        r = mantissa >> exponent;                        /* diff */
    }

    return (r ^ -sign) + sign;                           /* diff */
}

fast_trunc_two, C:

int fast_trunc_two(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = (mantissa << -exponent) ^ -sign;             /* diff */
    } else {
        r = (mantissa >> exponent) ^ -sign;              /* diff */
    }

    return r + sign;                                     /* diff */
}

Parece lo mismo, ¿verdad? Bueno, el CCG no está de acuerdo. Después de compilar con gcc -O3 -S -Wall -o test.s test.cesto es la salida del ensamblaje:

fast_trunc_one, generado:

_fast_trunc_one:
LFB0:
    .cfi_startproc
    movl    4(%esp), %eax
    movl    $150, %ecx
    movl    %eax, %edx
    andl    $8388607, %edx
    sarl    $23, %eax
    orl $8388608, %edx
    andl    $255, %eax
    subl    %eax, %ecx
    movl    %edx, %eax
    sarl    %cl, %eax
    testl   %ecx, %ecx
    js  L5
    rep
    ret
    .p2align 4,,7
L5:
    negl    %ecx
    movl    %edx, %eax
    sall    %cl, %eax
    ret
    .cfi_endproc

fast_trunc_two, generado:

_fast_trunc_two:
LFB1:
    .cfi_startproc
    pushl   %ebx
    .cfi_def_cfa_offset 8
    .cfi_offset 3, -8
    movl    8(%esp), %eax
    movl    $150, %ecx
    movl    %eax, %ebx
    movl    %eax, %edx
    sarl    $23, %ebx
    andl    $8388607, %edx
    andl    $255, %ebx
    orl $8388608, %edx
    andl    $-2147483648, %eax
    subl    %ebx, %ecx
    js  L9
    sarl    %cl, %edx
    movl    %eax, %ecx
    negl    %ecx
    xorl    %ecx, %edx
    addl    %edx, %eax
    popl    %ebx
    .cfi_remember_state
    .cfi_def_cfa_offset 4
    .cfi_restore 3
    ret
    .p2align 4,,7
L9:
    .cfi_restore_state
    negl    %ecx
    sall    %cl, %edx
    movl    %eax, %ecx
    negl    %ecx
    xorl    %ecx, %edx
    addl    %edx, %eax
    popl    %ebx
    .cfi_restore 3
    .cfi_def_cfa_offset 4
    ret
    .cfi_endproc

Esa es una diferencia extrema . Esto también aparece en el perfil, fast_trunc_onees alrededor de un 30% más rápido que fast_trunc_two. Ahora mi pregunta: ¿qué está causando esto?

orlp
fuente
1
Con fines de prueba, creé una esencia aquí donde puede copiar / pegar fácilmente la fuente y ver si puede reproducir el error en otros sistemas / versiones de GCC.
orlp
12
Ponga los casos de prueba en un directorio propio. Compilarlos con -S -O3 -da -fdump-tree-all. Esto creará muchas instantáneas de la representación intermedia. Camine a través de ellos (están numerados) uno al lado del otro y debería poder encontrar la optimización que falta en el primer caso.
zwol
1
Sugerencia dos: cambie todo inta unsigned inty vea si la diferencia desaparece.
zwol
55
Las dos funciones parecen estar haciendo matemáticas ligeramente diferentes. Si bien los resultados pueden ser los mismos, la expresión (r + shifted) ^ signno es la misma que r + (shifted ^ sign). ¿Supongo que eso confunde al optimizador? FWIW, MSVC 2010 (16.00.40219.01) produce listados que son casi idénticos entre sí: gist.github.com/2430454
DCoder
1
@DCoder: ¡Maldita sea! No vi eso. Sin embargo, no es la explicación de la diferencia. Permítanme actualizar la pregunta con una nueva versión donde se descarta esto.
orlp

Respuestas:

256

Actualizado para sincronizar con la edición del OP

Al jugar con el código, he logrado ver cómo GCC optimiza el primer caso.

Antes de que podamos entender por qué son tan diferentes, primero debemos entender cómo se optimiza GCC fast_trunc_one().

Lo creas o no, fast_trunc_one()se está optimizando para esto:

int fast_trunc_one(int i) {
    int mantissa, exponent;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);

    if (exponent < 0) {
        return (mantissa << -exponent);             /* diff */
    } else {
        return (mantissa >> exponent);              /* diff */
    }
}

Esto produce exactamente el mismo ensamblaje que el original fast_trunc_one(): registrar nombres y todo.

Observe que no hay xors en el ensamblado para fast_trunc_one(). Eso es lo que me lo regaló.


¿Cómo es eso?


Paso 1: sign = -sign

Primero, echemos un vistazo a la signvariable. Desde entonces sign = i & 0x80000000;, solo hay dos valores posibles que signpueden tomar:

  • sign = 0
  • sign = 0x80000000

Ahora reconocer que en ambos casos sign == -sign. Por lo tanto, cuando cambio el código original a esto:

int fast_trunc_one(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = mantissa << -exponent;
    } else {
        r = mantissa >> exponent;
    }

    return (r ^ sign) + sign;
}

Produce exactamente el mismo ensamblaje que el original fast_trunc_one(). Le ahorraré el ensamblaje, pero es idéntico: registre nombres y todo.


Paso 2: reducción matemática:x + (y ^ x) = y

signsolo puede tomar uno de dos valores, 0o 0x80000000.

  • Cuando x = 0, entonces x + (y ^ x) = yluego trivial se mantiene.
  • Agregar y xoring por 0x80000000es lo mismo. Voltea el bit de signo. Por x + (y ^ x) = ylo tanto, también se cumple cuando x = 0x80000000.

Por lo tanto, se x + (y ^ x)reduce a y. Y el código se simplifica a esto:

int fast_trunc_one(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = (mantissa << -exponent);
    } else {
        r = (mantissa >> exponent);
    }

    return r;
}

Nuevamente, esto se compila exactamente en el mismo ensamblado: registrar nombres y todo.


Esta versión anterior finalmente se reduce a esto:

int fast_trunc_one(int i) {
    int mantissa, exponent;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);

    if (exponent < 0) {
        return (mantissa << -exponent);             /* diff */
    } else {
        return (mantissa >> exponent);              /* diff */
    }
}

que es casi exactamente lo que genera GCC en el ensamblaje.


Entonces, ¿por qué el compilador no se optimiza fast_trunc_two()a la misma cosa?

La parte clave fast_trunc_one()es la x + (y ^ x) = yoptimización. En fast_trunc_two()la x + (y ^ x)expresión se está dividiendo en la rama.

Sospecho que podría ser suficiente para confundir a GCC para no hacer esta optimización. (Tendría que levantar la ^ -signrama y fusionarla r + signal final).

Por ejemplo, esto produce el mismo ensamblaje que fast_trunc_one():

int fast_trunc_two(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = ((mantissa << -exponent) ^ -sign) + sign;             /* diff */
    } else {
        r = ((mantissa >> exponent) ^ -sign) + sign;              /* diff */
    }

    return r;                                     /* diff */
}
Místico
fuente
44
Editar, parece que he respondido la revisión dos. La revisión actual volcó los dos ejemplos y cambió un poco el código ... esto es confuso.
Mysticial
2
@ nightcracker No te preocupes. He actualizado mi respuesta para sincronizar con la versión actual.
Mysticial
1
@Mysticial: su declaración final ya no es así con la nueva versión, haciendo que su nula respuesta (que no responde a la pregunta más importante, "¿Por qué GCC generar dicho conjunto radicalmente diferente" .)
orlp
11
Respuesta actualizada nuevamente. No estoy seguro si es lo suficientemente satisfactorio. Pero no creo que pueda hacerlo mucho mejor sin saber exactamente cómo funcionan los pases de optimización de GCC relevantes.
Mysticial
44
@Mysticial: Estrictamente hablando, siempre y cuando el tipo firmado se use incorrectamente en este código, casi todas las transformaciones que el compilador está haciendo aquí son casos en los que el comportamiento no está definido ...
R .. GitHub DEJA DE AYUDAR A ICE
63

Esta es la naturaleza de los compiladores. Asumir que tomarán el camino más rápido o mejor, es bastante falso. Cualquiera que implique que no necesita hacer nada a su código para optimizarlo porque los "compiladores modernos" llenan el espacio en blanco, hacen el mejor trabajo, hacen el código más rápido, etc. En realidad, vi que gcc empeora de 3.x a 4.x en el brazo al menos. 4.x podría haber alcanzado hasta 3.x en este punto, pero al principio produjo un código más lento. Con la práctica, puede aprender a escribir su código para que el compilador no tenga que trabajar tan duro y, como resultado, produzca resultados más consistentes y esperados.

El error aquí es sus expectativas de lo que se producirá, no de lo que realmente se produjo. Si desea que el compilador genere la misma salida, aliméntelo con la misma entrada. No es matemáticamente lo mismo, no es lo mismo, pero en realidad es lo mismo, no hay caminos diferentes, no se comparten ni distribuyen operaciones de una versión a otra. Este es un buen ejercicio para comprender cómo escribir su código y ver qué hacen los compiladores con él. No cometa el error de suponer que un día, una versión de gcc para un objetivo de procesador produjo un cierto resultado que es una regla para todos los compiladores y todo el código. Tienes que usar muchos compiladores y muchos objetivos para tener una idea de lo que está sucediendo.

gcc es bastante desagradable, te invito a mirar detrás de la cortina, mirar las tripas de gcc, intentar agregar un objetivo o modificar algo tú mismo. Apenas se mantiene unido por cinta adhesiva y cable de seguridad. Se agrega o elimina una línea adicional de código en lugares críticos y se desmorona. El hecho de que haya producido código utilizable es algo de lo que estar satisfecho, en lugar de preocuparse por qué no cumplió con otras expectativas.

¿Viste qué diferentes versiones de gcc producen? 3.xy 4.x en particular 4.5 vs 4.6 vs 4.7, etc. y para diferentes procesadores de destino, x86, arm, mips, etc. o diferentes sabores de x86 si ese es el compilador nativo que usa, 32 bits frente a 64 bits, etc. ¿Y luego llvm (clang) para diferentes objetivos?

Mystical ha hecho un excelente trabajo en el proceso de pensamiento requerido para resolver el problema de analizar / optimizar el código, esperando que un compilador presente algo de lo que, bueno, no se espera de ningún "compilador moderno".

Sin entrar en las propiedades matemáticas, código de este formulario

if (exponent < 0) {
  r = mantissa << -exponent;                       /* diff */
} else {
  r = mantissa >> exponent;                        /* diff */
}
return (r ^ -sign) + sign;                           /* diff */

llevará al compilador a A: impleméntelo de esa forma, realice el if-then-else y luego converja en un código común para terminar y regresar. o B: guarde una rama ya que este es el final de la función. Tampoco se moleste en usar o guardar r.

if (exponent < 0) {
  return((mantissa << -exponent)^-sign)+sign;
} else {
  return((mantissa << -exponent)^-sign)+sign;
}

Luego puede entrar como Mystical señaló que la variable de signo desaparece por completo para el código tal como está escrito. No esperaría que el compilador vea que la variable de signo desaparece, por lo que debería haberlo hecho usted mismo y no forzar al compilador a intentar resolverlo.

Esta es una oportunidad perfecta para profundizar en el código fuente de gcc. Parece que ha encontrado un caso en el que el optimizador vio una cosa en un caso y luego otra en otro. Luego, dé el siguiente paso y vea si no puede obtener gcc para ver ese caso. Cada optimización está ahí porque algún individuo o grupo reconoció la optimización y la puso intencionalmente allí. Para que esta optimización esté ahí y funcione cada vez que alguien tenga que ponerla allí (y luego probarla y luego mantenerla en el futuro).

Definitivamente no asuma que menos código es más rápido y más código es más lento, es muy fácil crear y encontrar ejemplos de que eso no sea cierto. En la mayoría de los casos, es posible que menos código sea más rápido que más código. Como lo demostré desde el principio, puedes crear más código para guardar ramificaciones en ese caso o bucles, etc. y hacer que el resultado neto sea un código más rápido.

La conclusión es que alimentó una fuente diferente del compilador y esperaba los mismos resultados. El problema no es la salida del compilador sino las expectativas del usuario. Es bastante fácil demostrar para un compilador y procesador en particular, la adición de una línea de código que hace que toda una función sea mucho más lenta. Por ejemplo, ¿por qué cambiar a = b + 2; a a = b + c + 2; ¿porque _fill_in_the_blank_compiler_name_ genera código radicalmente diferente y más lento? La respuesta, por supuesto, es que el compilador recibió un código diferente en la entrada, por lo que es perfectamente válido para el compilador generar diferentes resultados. (aún mejor es cuando intercambia dos líneas de código no relacionadas y hace que la salida cambie drásticamente) No existe una relación esperada entre la complejidad y el tamaño de la entrada con la complejidad y el tamaño de la salida.

for(ra=0;ra<20;ra++) dummy(ra);

Produjo en algún lugar entre 60-100 líneas de ensamblador. Desenrolló el bucle. No conté las líneas, si lo piensas bien, tiene que agregar, copiar el resultado a la entrada de la llamada a la función, hacer la llamada a la función, tres operaciones como mínimo. entonces, dependiendo del objetivo, es probable que haya al menos 60 instrucciones, 80 si cuatro por ciclo, 100 si cinco por ciclo, etc.

viejo contador de tiempo
fuente
¿Por qué destrozaste tu respuesta? Oded también parecía estar en desacuerdo con la edición ;-).
Peter - Restablece a Monica el
@ PeterA.Schneider todas sus respuestas parecen haber sido destrozadas en la misma fecha. Creo que alguien con sus datos de cuenta (¿robado?) Lo hizo.
trinity420
23

Mysticial ya ha dado una gran explicación, pero pensé agregar, FWIW, que realmente no hay nada fundamental acerca de por qué un compilador haría la optimización para uno y no para el otro.

El clangcompilador de LLVM , por ejemplo, proporciona el mismo código para ambas funciones (excepto el nombre de la función), dando:

_fast_trunc_two:                        ## @fast_trunc_one
        movl    %edi, %edx
        andl    $-2147483648, %edx      ## imm = 0xFFFFFFFF80000000
        movl    %edi, %esi
        andl    $8388607, %esi          ## imm = 0x7FFFFF
        orl     $8388608, %esi          ## imm = 0x800000
        shrl    $23, %edi
        movzbl  %dil, %eax
        movl    $150, %ecx
        subl    %eax, %ecx
        js      LBB0_1
        shrl    %cl, %esi
        jmp     LBB0_3
LBB0_1:                                 ## %if.then
        negl    %ecx
        shll    %cl, %esi
LBB0_3:                                 ## %if.end
        movl    %edx, %eax
        negl    %eax
        xorl    %esi, %eax
        addl    %edx, %eax
        ret

Este código no es tan corto como la primera versión de gcc del OP, pero no tan larga como la segunda.

El código de otro compilador (que no nombraré), compilando para x86_64, produce esto para ambas funciones:

fast_trunc_one:
        movl      %edi, %ecx        
        shrl      $23, %ecx         
        movl      %edi, %eax        
        movzbl    %cl, %edx         
        andl      $8388607, %eax    
        negl      %edx              
        orl       $8388608, %eax    
        addl      $150, %edx        
        movl      %eax, %esi        
        movl      %edx, %ecx        
        andl      $-2147483648, %edi
        negl      %ecx              
        movl      %edi, %r8d        
        shll      %cl, %esi         
        negl      %r8d              
        movl      %edx, %ecx        
        shrl      %cl, %eax         
        testl     %edx, %edx        
        cmovl     %esi, %eax        
        xorl      %r8d, %eax        
        addl      %edi, %eax        
        ret                         

lo cual es fascinante porque calcula ambos lados del ify luego usa un movimiento condicional al final para elegir el correcto.

El compilador Open64 produce lo siguiente:

fast_trunc_one: 
    movl %edi,%r9d                  
    sarl $23,%r9d                   
    movzbl %r9b,%r9d                
    addl $-150,%r9d                 
    movl %edi,%eax                  
    movl %r9d,%r8d                  
    andl $8388607,%eax              
    negl %r8d                       
    orl $8388608,%eax               
    testl %r8d,%r8d                 
    jl .LBB2_fast_trunc_one         
    movl %r8d,%ecx                  
    movl %eax,%edx                  
    sarl %cl,%edx                   
.Lt_0_1538:
    andl $-2147483648,%edi          
    movl %edi,%eax                  
    negl %eax                       
    xorl %edx,%eax                  
    addl %edi,%eax                  
    ret                             
    .p2align 5,,31
.LBB2_fast_trunc_one:
    movl %r9d,%ecx                  
    movl %eax,%edx                  
    shll %cl,%edx                   
    jmp .Lt_0_1538                  

y código similar, pero no idéntico para fast_trunc_two.

De todos modos, cuando se trata de optimización, es una lotería: es lo que es ... No siempre es fácil saber por qué el código se compila de una manera particular.

Charphacy
fuente
10
¿Es el compilador que no nombrarás algún supercompilador de alto secreto?
orlp
44
El compilador de Top Secret es probablemente Intel icc. Solo tengo la variante de 32 bits, pero produce un código muy similar a este.
Janus Troelsen
55
También creo que es ICC. El compilador sabe que el procesador es capaz de un paralelismo de nivel de instrucción y, por lo tanto, ambas ramas se pueden calcular simultáneamente. La sobrecarga del movimiento condicional es mucho menor que la sobrecarga de la predicción de rama falsa.
Filip Navara