¿Por qué GCC genera un ensamblaje radicalmente diferente para casi el mismo código C?
gcc flags (3)
Mientras escribía una función ftol 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 el mismo derecho? Bueno, GCC no está de acuerdo. Después de compilar con gcc -O3 -S -Wall -o test.s test.c este es el resultado del ensamblado:
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_one es aproximadamente un 30% más rápido que fast_trunc_two . Ahora mi pregunta: ¿qué está causando esto?
Esta es la naturaleza de los compiladores. Suponiendo que tomarán el camino más rápido o mejor, es bastante falso. Cualquiera que implique que no necesita hacer nada con su código para optimizarlo porque los "compiladores modernos" completan el espacio en blanco, hacen el mejor trabajo, crean el código más rápido, etc. De hecho, vi que gcc empeoraba de 3.xa 4. x en el brazo al menos. 4.x podría haber llegado a 3.x en este punto, pero al principio produjo un código más lento. Con la práctica puede aprender cómo 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 su expectativa de lo que se producirá, no de lo que realmente se produjo. Si desea que el compilador genere el mismo resultado, 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 entender cómo escribir su código y ver qué hacen los compiladores con él. No cometa el error de suponer que debido a que una versión de gcc para un procesador objetivo un día produjo un determinado resultado que esa 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 entrañas de gcc, intentar agregar un objetivo o modificar algo tú mismo. Apenas se sostiene junto con cinta adhesiva y alambre de achique. Una línea adicional de código agregado o eliminado en lugares críticos y se derrumba. El hecho de que haya producido un código utilizable es algo de lo que hay que alegrarse, en lugar de preocuparse por por qué no cumplió con otras expectativas.
¿miraste qué versiones diferentes de gcc producen? 3.x y 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 bit vs 64 bit, etc. Y luego llvm (clang) para diferentes objetivos?
Mystical ha realizado un excelente trabajo en el proceso de pensamiento necesario para resolver el problema del análisis / optimización del código, esperando que un compilador presente algo de eso, bueno, no se espera de ningún "compilador moderno".
Sin entrar en las propiedades matemáticas, código de esta forma
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 el código común para finalizar y regresar. o B: guarda una rama ya que este es el final de la función. Además, no se moleste en usar o guardar r.
if (exponent < 0) {
return((mantissa << -exponent)^-sign)+sign;
} else {
return((mantissa << -exponent)^-sign)+sign;
}
Entonces puedes entrar como Mystical señaló que la variable del signo desaparece para el código tal como está escrito. No esperaría que el compilador vea desaparecer la variable del signo, 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 donde el optimizador vio una cosa en un caso y luego otra cosa en otro caso. Luego tome el siguiente paso y vea si no puede obtener gcc para ver ese caso. Toda optimización está ahí porque algún individuo o grupo reconoció la optimización e intencionalmente la puso allí. Para que esta optimización esté ahí y funcione cada vez que alguien tenga que colocarla 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 es cierto. Es más probable que el caso de que menos código sea más rápido que más código. Como demostré desde el principio, puedes crear más código para guardar la bifurcación en ese caso o bucles, etc. y tener el resultado neto de un código más rápido.
La conclusión es que le proporcionó a un compilador una fuente diferente y esperaba los mismos resultados. El problema no es la salida del compilador sino las expectativas del usuario. Es bastante fácil de 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 dramáticamente más lenta. Por ejemplo, ¿por qué cambiar a = b + 2; a a = b + c + 2; porque _fill_in_the_blank_compiler_name_ genera un 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 para generar resultados diferentes. (aún mejor es cuando intercambia dos líneas de código no relacionadas y hace que la salida cambie drásticamente) No se espera una relación entre la complejidad y el tamaño de la entrada a la complejidad y el tamaño de la salida. Alimenta algo como esto en clang:
for(ra=0;ra<20;ra++) dummy(ra);
Produjo entre 60 y 100 líneas de ensamblador. Desenrolló el bucle. No conté las líneas, si lo piensas, tiene que agregar, copiar el resultado a la entrada de la llamada a la función, realizar la llamada a la función, tres operaciones como mínimo. así que dependiendo del objetivo, probablemente sean 60 instrucciones como mínimo, 80 si cuatro por ciclo, 100 si cinco por ciclo, etc.
Mysticial ya dio una gran explicación, pero pensé que agregaría, FWIW, que realmente no hay nada fundamental sobre por qué un compilador haría la optimización para uno y no para el otro.
El compilador de clang de LLVM, por ejemplo, proporciona el mismo código para ambas funciones (excepto el nombre de la función), que proporciona:
_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 largo como el segundo.
El código de otro compilador (que no nombraré), que compila 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
que es fascinante porque computa ambos lados del if y luego usa un movimiento condicional al final para elegir el correcto.
El compilador de 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 alguna manera en particular.
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 GCC optimiza fast_trunc_one() .
Créalo 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 el mismo ensamblaje exacto que el original fast_trunc_one() - registra nombres y todo.
Observe que no hay xor en el ensamblaje de fast_trunc_one() . Eso es lo que me regaló.
¿Cómo es eso?
Paso 1: sign = -sign
Primero, echemos un vistazo a la variable de sign . Dado que sign = i & 0x80000000; , solo hay dos valores posibles que el sign puede tomar:
-
sign = 0 -
sign = 0x80000000
Ahora reconoce que en ambos casos, sign == -sign . Por lo tanto, cuando cambio el código original a este:
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 el mismo ensamblaje exacto que el original fast_trunc_one() . Te ahorraré la asamblea, pero es idéntica: nombres de registro y todo.
Paso 2: reducción matemática: x + (y ^ x) = y
sign solo puede tomar uno de dos valores, 0 o 0x80000000 .
- Cuando
x = 0, entoncesx + (y ^ x) = yentonces se cumple trivial. - Agregar y anotar por
0x80000000es lo mismo. Da vuelta el bit de signo. Por lo tanto,x + (y ^ x) = ytambién se cumple cuandox = 0x80000000.
Por lo tanto, 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;
}
De nuevo, esto se compila en el mismo ensamblaje exacto - nombres de registro 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 más o menos exactamente lo que genera GCC en el ensamblaje.
Entonces, ¿por qué el compilador no optimiza fast_trunc_two() para lo mismo?
La parte clave en fast_trunc_one() es la optimización x + (y ^ x) = y . En fast_trunc_two() la expresión x + (y ^ x) se divide en la rama.
Sospecho que eso podría ser suficiente para confundir a GCC de no hacer esta optimización. (Tendría que izar el ^ -sign de la rama y ^ -sign en el r + sign al 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 */
}