c++ - programa - (A+B+C) ≠(A+C+B) y reordenamiento del compilador

gcc linux

Question

Agregar dos enteros de 32 bits puede provocar un desbordamiento de enteros:

uint64_t u64_z = u32_x + u32_y;

Este desbordamiento se puede evitar si uno de los enteros de 32 bits se convierte primero o se agrega a un entero de 64 bits.

uint64_t u64_z = u32_x + u64_a + u32_y;

Sin embargo, si el compilador decide reordenar la adición:

uint64_t u64_z = u32_x + u32_y + u64_a;

el desbordamiento de enteros aún podría suceder.

¿Se les permite a los compiladores hacer un reordenamiento de este tipo o podemos confiar en ellos para notar la inconsistencia del resultado y mantener el orden de expresión tal como está?

Answer 1

¿Se les permite a los compiladores hacer un reordenamiento de este tipo o podemos confiar en ellos para notar la inconsistencia del resultado y mantener el orden de expresión tal como está?

El compilador puede reordenar solo si da el mismo resultado; aquí, como observó, no lo hace.

Es posible escribir una plantilla de función, si lo desea, que promueva todos los argumentos a std::common_type antes de agregar; esto sería seguro y no dependería del orden de los argumentos o la conversión manual, pero es bastante torpe.

Answer 2

Citando de los standards :

[Nota: Los operadores pueden reagruparse de acuerdo con las reglas matemáticas habituales solo cuando los operadores realmente son asociativos o conmutativos.7 Por ejemplo, en el siguiente fragmento int a, b;

/∗ ... ∗/
a = a + 32760 + b + 5;

la declaración de expresión se comporta exactamente igual que

a = (((a + 32760) + b) + 5);

debido a la asociatividad y precedencia de estos operadores. Por lo tanto, el resultado de la suma (a + 32760) se agrega a continuación a b, y ese resultado se agrega a 5, lo que da como resultado el valor asignado a a. En una máquina en la que los desbordamientos producen una excepción y en la que el rango de valores representables por un int es [-32768, + 32767], la implementación no puede reescribir esta expresión como

a = ((a + b) + 32765);

ya que si los valores para a y b fueran, respectivamente, -32754 y -15, la suma a + b produciría una excepción mientras que la expresión original no lo haría; ni la expresión puede reescribirse como

a = ((a + 32765) + b);

o

a = (a + (b + 32765));

dado que los valores para ayb podrían haber sido, respectivamente, 4 y -8 o -17 y 12. Sin embargo, en una máquina en la que los desbordamientos no producen una excepción y en los que los resultados de los desbordamientos son reversibles, la declaración de expresión anterior puede ser reescrito por la implementación en cualquiera de las formas anteriores porque se producirá el mismo resultado. - nota final]

Answer 3

Depende del ancho de bits de unsigned/int .

Los siguientes 2 no son lo mismo (cuando unsigned <= 32 bits). u32_x + u32_y convierte en 0.

u64_a = 0; u32_x = 1; u32_y = 0xFFFFFFFF;
uint64_t u64_z = u32_x + u64_a + u32_y;
uint64_t u64_z = u32_x + u32_y + u64_a;  // u32_x + u32_y carry does not add to sum.

Son lo mismo (cuando unsigned >= 34 bits). Las promociones de u32_x + u32_y enteros causaron que la u32_x + u32_y ocurriera en matemáticas de 64 bits. El orden es irrelevante.

Es UB (cuando unsigned == 33 bits). Las promociones de enteros provocaron que se produjera una suma en las matemáticas de 33 bits con signo y el desbordamiento firmado es UB.

¿Se les permite a los compiladores hacer tal reordenamiento ...?

(Matemáticas de 32 bits): reordenar sí, pero deben producirse los mismos resultados, por lo que no se debe reordenar OP A continuación son los mismos

// Same
u32_x + u64_a + u32_y;
u64_a + u32_x + u32_y;
u32_x + (uint64_t) u32_y + u64_a;
...

// Same as each other below, but not the same as the 3 above.
uint64_t u64_z = u32_x + u32_y + u64_a;
uint64_t u64_z = u64_a + (u32_x + u32_y);

... ¿podemos confiar en ellos para notar la inconsistencia del resultado y mantener el orden de expresión tal como está?

Confíe en sí, pero el objetivo de codificación de OP no es claro como el cristal. ¿ u32_x + u32_y contribuir u32_x + u32_y ? Si OP quiere esa contribución, el código debe ser

uint64_t u64_z = u64_a + u32_x + u32_y;
uint64_t u64_z = u32_x + u64_a + u32_y;
uint64_t u64_z = u32_x + (u32_y + u64_a);

Pero no

uint64_t u64_z = u32_x + u32_y + u64_a;

Answer 4

Existe la regla "como si" en C, C ++ y Objective-C: el compilador puede hacer lo que quiera siempre que ningún programa conforme pueda notar la diferencia.

En estos lenguajes, a + b + c se define como (a + b) + c. Si puede ver la diferencia entre esto y, por ejemplo, a + (b + c), entonces el compilador no puede cambiar el orden. Si no puede ver la diferencia, entonces el compilador puede cambiar el orden, pero está bien, porque no puede ver la diferencia.

En su ejemplo, con b = 64 bit, a y c 32 bit, el compilador podría evaluar (b + a) + c o incluso (b + c) + a, porque no podía notar la diferencia, pero no (a + c) + b porque puedes notar la diferencia.

En otras palabras, el compilador no puede hacer nada que haga que su código se comporte de forma diferente a lo que debería. No es necesario que produzca el código que cree que produciría, o que cree que debería producir, pero el código le dará exactamente los resultados que debería.

Answer 5

Si el optimizador realiza dicho reordenamiento, todavía está vinculado a la especificación C, por lo que dicho reordenamiento sería:

uint64_t u64_z = (uint64_t)u32_x + (uint64_t)u32_y + u64_a;

Razón fundamental o base lógica:

Empezamos con

uint64_t u64_z = u32_x + u64_a + u32_y;

La suma se realiza de izquierda a derecha.

Las reglas de promoción de enteros establecen que en la primera adición en la expresión original, u32_x se promocionará a uint64_t . En la segunda adición, u32_y también será promovido a uint64_t .

Entonces, para cumplir con la especificación C, cualquier optimizador debe promover u32_x y u32_y a valores sin signo de 64 bits. Esto es equivalente a agregar un reparto. (La optimización real no se realiza en el nivel C, pero uso la notación C porque esa es una notación que entendemos).

Answer 6

Un compilador solo puede reordenar bajo la regla como si lo fuera. Es decir, si el reordenamiento siempre dará el mismo resultado que el pedido especificado, entonces está permitido. De lo contrario (como en su ejemplo), no.

Por ejemplo, dada la siguiente expresión

i32big1 - i32big2 + i32small

que ha sido cuidadosamente construido para restar los dos valores que se sabe que son grandes pero similares, y solo luego agrega el otro valor pequeño (evitando así cualquier desbordamiento), el compilador puede optar por reordenar en:

(i32small - i32big2) + i32big1

y confíe en el hecho de que la plataforma de destino está usando aritmética de dos complementos con envoltura para evitar problemas. (Tal reordenamiento podría ser sensato si se presiona el compilador para registros, y resulta que ya tiene i32small en un registro).