c++ - Programa de comportamiento extraño en IDEs en línea

undefined-behavior integer-overflow

Question

Me he encontrado con el siguiente programa C ++ ( source ):

#include <iostream>
int main()
{
    for (int i = 0; i < 300; i++)
        std::cout << i << " " << i * 12345678 << std::endl;
}

Parece un programa simple y proporciona la salida correcta en mi máquina local, es decir, algo como:

0 0
1 12345678
2 24691356
...
297 -628300930
298 -615955252
299 -603609574

Pero, en IDEs en línea como codechef , da el siguiente resultado:

0 0
1 12345678
2 24691356
...
4167 -95167326
4168 -82821648
4169 -7047597

¿Por qué el ciclo for no termina en 300? Además, este programa siempre termina en 4169 . ¿Por qué 4169 y no algún otro valor?

Answer 1

Asumiré que los compiladores en línea usan GCC o un compilador compatible. Por supuesto, cualquier otro compilador también puede hacer la misma optimización, pero la documentación de GCC explica bien lo que hace:

-faggressive-loop-optimizations

Esta opción le dice al optimizador de bucles que use restricciones de lenguaje para derivar límites para la cantidad de iteraciones de un bucle. Esto supone que el código de bucle no invoca un comportamiento indefinido, por ejemplo, causando desbordamientos de enteros firmados o accesos de matriz fuera del límite. Los límites para el número de iteraciones de un bucle se usan para guiar las optimizaciones de desenrollado y pelado del bucle y la prueba de salida del bucle. Esta opción está activada de forma predeterminada.

Esta opción simplemente permite hacer suposiciones basadas en casos donde UB está probado. Para aprovechar esas suposiciones, es posible que sea necesario habilitar otras optimizaciones, como el plegado constante.

El desbordamiento de entero firmado tiene un comportamiento indefinido. El optimizador pudo probar que cualquier valor de i mayor que 173 causaría UB, y debido a que puede suponer que no hay UB, también puede suponer que nunca es mayor que 173. Luego puede demostrar que i < 300 siempre es cierto, por lo que la condición del bucle se puede optimizar.

¿Por qué 4169 y no algún otro valor?

Esos sitios probablemente limitan el número de líneas de salida (o caracteres o bytes) que muestran y comparten el mismo límite.

Answer 2

El compilador puede suponer que no se producirá un comportamiento indefinido y, dado que el desbordamiento firmado es UB, puede suponer que nunca i * 12345678 > INT_MAX , por lo tanto, también i <= INT_MAX / 12345678 < 300 y, por lo tanto, elimine la comprobación i < 300 .

Answer 3

Está invocando un comportamiento indefinido probablemente en la iteración 174 dentro de su bucle for ya que el valor int máximo probablemente es 2147483647 pero la expresión 174 * 123456789 evalúa como 2148147972 que es un comportamiento indefinido ya que no hay un desbordamiento de entero con signo. Entonces está observando los efectos de UB, particularmente con el compilador GCC con banderas de optimización establecidas en su caso. Es probable que el compilador lo haya advertido al emitir la siguiente advertencia:

warning: iteration 174 invokes undefined behavior [-Waggressive-loop-optimizations]

Elimine los -O2 optimización ( -O2 ) para observar resultados diferentes.

Answer 4

"El comportamiento indefinido es indefinido". (do)

Un compilador utilizado en codechef parece usar la siguiente lógica:

1. El comportamiento indefinido no puede suceder.
2. i * 12345678 desborda y da como resultado UB si i > 173 (suponiendo int s de 32 bits).
3. Por lo tanto, nunca puedo exceder 173 .
4. Por lo tanto, i < 300 es superfluo y puede reemplazarse por true .

El bucle en sí parece ser infinito. Aparentemente, codechef simplemente detiene el programa después de un período de tiempo específico o trunca la salida.