c++ - flag - gfortran ofast

¿Por qué GCC no puede optimizar el par AND bit lógico en "x &&(x & 4242)" a "x & 4242"?

Question

Aquí hay dos funciones que afirmo que hacen exactamente lo mismo:

bool fast(int x)
{
return x & 4242;
}
bool slow(int x)
{
return x && (x & 4242);
}

Lógicamente hacen lo mismo, y solo para estar 100% seguros de que escribí una prueba que ejecutó los cuatro mil millones de entradas posibles a través de ambos, y coincidieron. Pero el código de ensamblaje es una historia diferente:

fast:
andl $4242, %edi
setne %al
ret
slow:
xorl %eax, %eax
testl %edi, %edi
je .L3
andl $4242, %edi
setne %al
.L3:
rep
ret

Me sorprendió que GCC no pudiera dar el salto de la lógica para eliminar la prueba redundante. Probé g ++ 4.4.3 y 4.7.2 con -O2, -O3 y -Os, todos los cuales generaron el mismo código. La plataforma es Linux x86_64.

¿Alguien puede explicar por qué GCC no debe ser lo suficientemente inteligente como para generar el mismo código en ambos casos? También me gustaría saber si otros compiladores pueden hacerlo mejor.

Editar para agregar arnés de prueba:

#include <cstdlib>
#include <vector>
using namespace std;
int main(int argc, char* argv[])
{
// make vector filled with numbers starting from argv[1]
int seed = atoi(argv[1]);
vector<int> v(100000);
for (int j = 0; j < 100000; ++j)
v[j] = j + seed;
// count how many times the function returns true
int result = 0;
for (int j = 0; j < 100000; ++j)
for (int i : v)
result += slow(i); // or fast(i), try both
return result;
}

Probé lo anterior con clang 5.1 en Mac OS con -O3. Tomó 2.9 segundos usando fast() y 3.8 segundos usando slow() . Si en cambio utilizo un vector de todos los ceros, no hay una diferencia significativa en el rendimiento entre las dos funciones.

Answer 1

¿Por qué debería ser capaz de optimizar el código? Estás asumiendo que cualquier transformación que funcione se hará. Eso no es en absoluto cómo funcionan los optimizadores. No son Inteligencias Artificiales. Simplemente trabajan reemplazando paramétricamente patrones conocidos. Por ejemplo, la "Eliminación común de subexpresión" escanea una expresión para subexpresiones comunes, y las mueve hacia adelante, si eso no cambia los efectos secundarios.

(Por cierto, CSE muestra que los optimizadores ya son bastante conscientes del movimiento del código permitido en la posible presencia de efectos secundarios. Saben que debe tener cuidado con && . Si expr && expr puede ser optimizado para CSE o no depende del efectos secundarios de expr .)

Entonces, en resumen: ¿qué patrón crees que se aplica aquí?

Answer 2

Así es como se ve el código en ARM, lo que debería hacer que la ejecución slow más rápida cuando se ingresa 0.

fast(int):
movw r3, #4242
and r3, r0, r3
adds r0, r3, #0
movne r0, #1
bx lr
slow(int):
cmp r0, #0
bxeq lr
movw r3, #4242
and r3, r0, r3
adds r0, r3, #0
movne r0, #1
bx lr

Sin embargo, GCC se optimizaría muy bien cuando empieces a usar funciones tan triviales de todos modos.

bool foo() {
return fast(4242) && slow(42);
}

se convierte

foo():
mov r0, #1
bx lr

Mi punto es que a veces ese código requiere más contexto para ser optimizado aún más así que ¿por qué los implementadores de optimizadores (mejoradores) deberían molestarse?

Otro ejemplo:

bool bar(int c) {
if (fast(c))
return slow(c);
}

se convierte

bar(int):
movw r3, #4242
and r3, r0, r3
cmp r3, #0
movne r0, #1
bxne lr
bx lr

Answer 3

C coloca menos restricciones en el comportamiento de los tipos integrales con signo que los tipos integrales sin signo. Los valores negativos en particular pueden hacer cosas extrañas legalmente con operaciones de bits. Si algún posible argumento para la operación de bit tiene un comportamiento legalmente sin restricciones, el compilador no puede eliminarlos.

Por ejemplo, "x / y == 1 o verdadero" podría bloquear el programa si se divide por cero, por lo que el compilador no puede ignorar la evaluación de la división. Los valores con signo negativo y las operaciones de bits nunca hacen cosas así en un sistema común, pero no estoy seguro de que la definición del lenguaje lo excluya.

Debería probar el código con ints sin firmar y ver si eso ayuda. Si lo hace sabrá que es un problema con los tipos y no con la expresión.

Answer 4

El último compilador en el que trabajé no hizo este tipo de optimizaciones. Escribir un optimizador para aprovechar las optimizaciones relacionadas con la combinación de operadores binarios y lógicos no acelerará las aplicaciones. La razón principal de esto es que la gente no usa operadores binarios así a menudo. Muchas personas no se sienten cómodas con los operadores binarios y quienes lo hacen generalmente no escriben operaciones inútiles que necesitan optimizarse.

Si me tomo la molestia de escribir

return (x & 4242)

y entiendo lo que eso significa por qué me molestaría con el paso adicional. Por la misma razón, no escribiría este código subóptimo

if (x==0) return false;
if (x==1) return true;
if (x==0xFFFEFD6) return false;
if (x==4242) return true;
return (x & 4242)

Simplemente hay un mejor uso del tiempo del desarrollador de compiladores que para optimizar cosas que no hacen la diferencia. Hay muchos peces más grandes para freír en la optimización del compilador.

Answer 5

Es ligeramente interesante observar que esta optimización no es válida en todas las máquinas. Específicamente, si se ejecuta en una máquina que utiliza la representación del complemento de números negativos, entonces:

-0 & 4242 == true
-0 && ( -0 & 4242 ) == false

GCC nunca ha respaldado tales representaciones, pero están permitidas por el estándar C.

Answer 6

Para realizar esta optimización, se necesita estudiar la expresión para dos casos distintos: x == 0 , simplificando a false , y x != 0 , simplificando a x & 4242 . Y luego sea lo suficientemente inteligente como para ver que el valor de la segunda expresión también arroja el valor correcto incluso para x == 0 .

Imaginemos que el compilador realiza un estudio de caso y encuentra simplificaciones.

Si x != 0 , la expresión se simplifica a x & 4242 .

Si x == 0 , la expresión se simplifica a false .

Después de la simplificación, obtenemos dos expresiones completamente sin relación. Para reconciliarlos, el compilador debe hacer preguntas no naturales:

Si x != 0 , ¿puede ser false vez de x & 4242 ? [No]

Si x == 0 , ¿se puede usar x & 4242 lugar de false todos modos? [Sí]

Answer 7

Tiene razón en que esto parece ser una deficiencia, y posiblemente una falla directa, en el optimizador.

Considerar:

bool slow(int x)
{
return x && (x & 4242);
}
bool slow2(int x)
{
return (x & 4242) && x;
}

Asamblea emitida por GCC 4.8.1 (-O3):

slow:
xorl %eax, %eax
testl %edi, %edi
je .L2
andl $4242, %edi
setne %al
.L2:
rep ret
slow2:
andl $4242, %edi
setne %al
ret

En otras palabras, slow2 tiene un nombre erróneo.

Solo he contribuido con el parche ocasional a GCC, por lo que si mi punto de vista tiene algún peso es discutible :-). Pero ciertamente es extraño, en mi opinión, que GCC optimice uno de estos y no el otro. Sugiero archivar un informe de error .

[Actualizar]

Sorprendentemente, los pequeños cambios parecen marcar una gran diferencia. Por ejemplo:

bool slow3(int x)
{
int y = x & 4242;
return y && x;
}

... genera código "lento" de nuevo. No tengo ninguna hipótesis para este comportamiento.

Puede experimentar con todos estos en múltiples compiladores here .