¿En qué punto del ciclo el desbordamiento de enteros se convierte en un comportamiento indefinido?

Este es un ejemplo para ilustrar mi pregunta que involucra un código mucho más complicado que no puedo publicar aquí.

#include <stdio.h>
int main()
{
    int a = 0;
    for (int i = 0; i < 3; i++)
    {
        printf("Hello\n");
        a = a + 1000000000;
    }
}

Este programa contiene un comportamiento indefinido en mi plataforma porque ase desbordará en el tercer ciclo.

¿Eso hace que todo el programa tenga un comportamiento indefinido, o solo después de que ocurra el desbordamiento ? ¿Podría el compilador resolver que a se desbordará para que pueda declarar todo el bucle como indefinido y no se moleste en ejecutar printfs a pesar de que todos ocurren antes del desbordamiento?

_{(Etiquetado C y C ++ aunque son diferentes porque estaría interesado en respuestas para ambos lenguajes si fueran diferentes).}

Si está interesado en una respuesta puramente teórica, el estándar C ++ permite un comportamiento indefinido para "viajar en el tiempo":

[intro.execution]/5: Una implementación conforme que ejecuta un programa bien formado producirá el mismo comportamiento observable que una de las posibles ejecuciones de la instancia correspondiente de la máquina abstracta con el mismo programa y la misma entrada. Sin embargo, si tal ejecución contiene una operación indefinida, esta Norma Internacional no impone ningún requisito a la implementación que ejecuta ese programa con esa entrada (ni siquiera con respecto a las operaciones que preceden a la primera operación indefinida).

Como tal, si su programa contiene un comportamiento indefinido, entonces el comportamiento de todo su programa no está definido.

Primero, déjame corregir el título de esta pregunta:

El comportamiento indefinido no es (específicamente) del ámbito de la ejecución.

El comportamiento indefinido afecta a todos los pasos: compilar, vincular, cargar y ejecutar.

Algunos ejemplos para cimentar esto, tenga en cuenta que ningún apartado es exhaustivo:

• el compilador puede asumir que las porciones de código que contienen un comportamiento indefinido nunca se ejecutan y, por lo tanto, asume que las rutas de ejecución que conducirían a ellas son código muerto. Vea Lo que todo programador de C debería saber sobre el comportamiento indefinido de nada menos que Chris Lattner.
• el enlazador puede asumir que en presencia de múltiples definiciones de un símbolo débil (reconocido por su nombre), todas las definiciones son idénticas gracias a la regla de una definición
• el cargador (en caso de que use bibliotecas dinámicas) puede asumir lo mismo, eligiendo así el primer símbolo que encuentre; esto generalmente se usa (ab) para interceptar llamadas usando LD_PRELOADtrucos en Unixes
• la ejecución podría fallar (SIGSEV) si usa punteros colgantes

Esto es lo que da tanto miedo al comportamiento indefinido: es casi imposible predecir, con anticipación, qué comportamiento exacto ocurrirá, y esta predicción debe revisarse en cada actualización de la cadena de herramientas, el sistema operativo subyacente, ...

Recomiendo ver este video de Michael Spencer (Desarrollador LLVM): CppCon 2016: My Little Optimizer: Undefined Behavior is Magic .

Un compilador C o C ++ de optimización agresiva que inttenga como objetivo un bit de 16 sabrá que el comportamiento al agregar 1000000000a un inttipo no está definido .

Está permitido por cualquiera de los estándares para hacer lo que quiera, lo que podría incluir la eliminación de todo el programa y salir int main(){}.

Pero, ¿qué pasa con las ints más grandes ? No conozco un compilador que haga esto todavía (y no soy un experto en diseño de compiladores C y C ++ de ninguna manera), pero imagino que en algún momento un compilador que inttenga como objetivo 32 bits o superior se dará cuenta de que el bucle es infinito ( ino cambia) y por lo que acon el tiempo se desborde. Entonces, una vez más, puede optimizar la salida a int main(){}. El punto que trato de señalar aquí es que a medida que las optimizaciones del compilador se vuelven progresivamente más agresivas, más y más construcciones de comportamiento indefinidas se manifiestan de formas inesperadas.

El hecho de que su bucle sea infinito no está indefinido en sí mismo, ya que está escribiendo en la salida estándar en el cuerpo del bucle.

Técnicamente, según el estándar C ++, si un programa contiene un comportamiento indefinido, el comportamiento de todo el programa, incluso en el momento de la compilación (incluso antes de que se ejecute el programa), no está definido.

En la práctica, debido a que el compilador puede asumir (como parte de una optimización) que el desbordamiento no ocurrirá, al menos el comportamiento del programa en la tercera iteración del ciclo (asumiendo una máquina de 32 bits) no estará definido, aunque Es probable que obtenga resultados correctos antes de la tercera iteración. Sin embargo, dado que el comportamiento de todo el programa no está definido técnicamente, no hay nada que impida que el programa genere una salida completamente incorrecta (incluida la ausencia de salida), se bloquee en tiempo de ejecución en cualquier momento durante la ejecución o incluso no se compile por completo (ya que el comportamiento indefinido se extiende a tiempo de compilación).

El comportamiento indefinido proporciona al compilador más espacio para optimizar porque eliminan ciertas suposiciones sobre lo que debe hacer el código. Al hacerlo, no se garantiza que los programas que se basan en supuestos que implican un comportamiento indefinido funcionen como se esperaba. Como tal, no debe confiar en ningún comportamiento en particular que se considere indefinido según el estándar C ++.

Para entender por qué el comportamiento indefinido puede 'viajar en el tiempo' como lo expresó adecuadamente @TartanLlama , echemos un vistazo a la regla 'como si':

1.9 Ejecución del programa

¹ Las descripciones semánticas de esta Norma Internacional definen una máquina abstracta no determinista parametrizada. Esta Norma Internacional no impone ningún requisito sobre la estructura de las implementaciones conformes. En particular, no necesitan copiar ni emular la estructura de la máquina abstracta. Más bien, se requieren implementaciones conformes para emular (solo) el comportamiento observable de la máquina abstracta como se explica a continuación.

Con esto, podríamos ver el programa como una 'caja negra' con una entrada y una salida. La entrada podría ser la entrada del usuario, archivos y muchas otras cosas. El resultado es el "comportamiento observable" mencionado en el estándar.

El estándar solo define un mapeo entre la entrada y la salida, nada más. Lo hace describiendo una 'caja negra de ejemplo', pero explícitamente dice que cualquier otra caja negra con el mismo mapeo es igualmente válida. Esto significa que el contenido de la caja negra es irrelevante.

Con esto en mente, no tendría sentido decir que un comportamiento indefinido ocurre en un momento determinado. En la implementación de muestra de la caja negra, podríamos decir dónde y cuándo sucede, pero la caja negra real podría ser algo completamente diferente, por lo que ya no podemos decir dónde y cuándo sucede. En teoría, un compilador podría, por ejemplo, decidir enumerar todas las entradas posibles y precalcular las salidas resultantes. Entonces, el comportamiento indefinido habría ocurrido durante la compilación.

El comportamiento indefinido es la inexistencia de un mapeo entre entrada y salida. Un programa puede tener un comportamiento indefinido para algunas entradas, pero un comportamiento definido para otras. Entonces, el mapeo entre entrada y salida es simplemente incompleto; hay una entrada para la que no existe una asignación a la salida.
El programa en la pregunta tiene un comportamiento indefinido para cualquier entrada, por lo que el mapeo está vacío.

Suponiendo que intes de 32 bits, ocurre un comportamiento indefinido en la tercera iteración. Entonces, si, por ejemplo, el bucle solo fuera accesible condicionalmente, o podría terminarse condicionalmente antes de la tercera iteración, no habría un comportamiento indefinido a menos que se alcance la tercera iteración. Sin embargo, en el caso de un comportamiento indefinido, toda la salida del programa no está definida, incluida la salida que está "en el pasado" en relación con la invocación de un comportamiento indefinido. Por ejemplo, en su caso, esto significa que no hay garantía de ver 3 mensajes de "Hola" en la salida.

La respuesta de TartanLlama es correcta. El comportamiento indefinido puede ocurrir en cualquier momento, incluso durante el tiempo de compilación. Esto puede parecer absurdo, pero es una característica clave que permite a los compiladores hacer lo que necesitan hacer. No siempre es fácil ser un compilador. Tienes que hacer exactamente lo que dice la especificación, siempre. Sin embargo, a veces puede resultar tremendamente difícil demostrar que se está produciendo un comportamiento en particular. Si recuerda el problema de la detención, es bastante trivial desarrollar software para el que no puede probar si completa o entra en un bucle infinito cuando se alimenta con una entrada en particular.

Podríamos hacer que los compiladores sean pesimistas y compilen constantemente por temor a que la próxima instrucción sea uno de estos problemas parecidos a problemas, pero eso no es razonable. En su lugar, le damos un pase al compilador: en estos temas de "comportamiento indefinido", están liberados de cualquier responsabilidad. El comportamiento indefinido consiste en todos los comportamientos que son tan sutilmente nefastos que tenemos problemas para separarlos de los realmente desagradables y nefastos problemas de detención y demás.

Hay un ejemplo que me encanta publicar, aunque admito que perdí la fuente, así que tengo que parafrasear. Era de una versión particular de MySQL. En MySQL, tenían un búfer circular que estaba lleno de datos proporcionados por el usuario. Ellos, por supuesto, querían asegurarse de que los datos no desbordaran el búfer, por lo que hicieron una verificación:

if (currentPtr + numberOfNewChars > endOfBufferPtr) { doOverflowLogic(); }

Parece bastante cuerdo. Sin embargo, ¿qué pasa si numberOfNewChars es realmente grande y se desborda? Luego se envuelve y se convierte en un puntero más pequeño que endOfBufferPtr, por lo que nunca se llamaría a la lógica de desbordamiento. Entonces agregaron una segunda verificación, antes de esa:

if (currentPtr + numberOfNewChars < currentPtr) { detectWrapAround(); }

Parece que se ocupó del error de desbordamiento del búfer, ¿verdad? Sin embargo, se envió un error que indica que este búfer se desbordó en una versión particular de Debian. Una investigación cuidadosa mostró que esta versión de Debian fue la primera en usar una versión particularmente avanzada de gcc. En esta versión de gcc, el compilador reconoció que currentPtr + numberOfNewChars nunca puede ser un puntero más pequeño que currentPtr porque el desbordamiento de punteros es un comportamiento indefinido. Eso fue suficiente para que gcc optimizara toda la verificación y, de repente, no estaba protegido contra los desbordamientos del búfer a pesar de que escribió el código para verificarlo.

Este fue el comportamiento de las especificaciones. Todo era legal (aunque por lo que escuché, gcc revertió este cambio en la próxima versión). No es lo que yo consideraría un comportamiento intuitivo, pero si estira un poco su imaginación, es fácil ver cómo una ligera variante de esta situación podría convertirse en un problema para el compilador. Debido a esto, los escritores de especificaciones lo convirtieron en "Comportamiento indefinido" y declararon que el compilador podía hacer absolutamente cualquier cosa que quisiera.

Más allá de las respuestas teóricas, una observación práctica sería que durante mucho tiempo los compiladores han aplicado varias transformaciones a los bucles para reducir la cantidad de trabajo realizado dentro de ellos. Por ejemplo, dado:

for (int i=0; i<n; i++)
  foo[i] = i*scale;

un compilador podría transformar eso en:

int temp = 0;
for (int i=0; i<n; i++)
{
  foo[i] = temp;
  temp+=scale;
}

De este modo, se guarda una multiplicación con cada iteración del ciclo. Una forma adicional de optimización, que los compiladores adaptaron con diversos grados de agresividad, lo convertiría en:

if (n > 0)
{
  int temp1 = n*scale;
  int *temp2 = foo;
  do
  {
    temp1 -= scale;
    *temp2++ = temp1;
  } while(temp1);
}

Incluso en máquinas con envoltura silenciosa en desbordamiento, eso podría funcionar mal si hubiera un número menor que n que, cuando se multiplica por la escala, daría como resultado 0. También podría convertirse en un bucle sin fin si la escala se lee de la memoria más de una vez y algo cambió su valor inesperadamente (en cualquier caso donde "scale" pudiera cambiar en medio del ciclo sin invocar a UB, un compilador no podría realizar la optimización).

Si bien la mayoría de estas optimizaciones no tendrían ningún problema en los casos en que dos tipos cortos sin signo se multiplican para producir un valor que se encuentra entre INT_MAX + 1 y UINT_MAX, gcc tiene algunos casos en los que dicha multiplicación dentro de un bucle puede hacer que el bucle salga antes. . No he notado que tales comportamientos provengan de instrucciones de comparación en el código generado, pero es observable en los casos en que el compilador usa el desbordamiento para inferir que un bucle puede ejecutarse como máximo 4 veces o menos; de forma predeterminada, no genera advertencias en los casos en que algunas entradas causarían UB y otras no, incluso si sus inferencias hacen que se ignore el límite superior del bucle.

El comportamiento indefinido es, por definición, un área gris. Simplemente no se puede predecir lo que va o no va a hacer - que es lo que "un comportamiento indefinido" medios .

Desde tiempos inmemoriales, los programadores siempre han tratado de rescatar los restos de definición de una situación indefinida. Ellos tienen algo de código que realmente quieren usar, pero que resulta ser indefinido, por lo que tratan de argumentar: "Sé que es indefinido, pero seguramente serán, en el peor, hacer esto o esto, sino que nunca lo que . " Y a veces estos argumentos son más o menos correctos, pero a menudo están equivocados. Y a medida que los compiladores se vuelven más y más inteligentes (o, algunas personas podrían decir, más astutos y astutos), los límites de la pregunta siguen cambiando.

Entonces, realmente, si desea escribir código que esté garantizado para funcionar, y que seguirá funcionando durante mucho tiempo, solo hay una opción: evitar el comportamiento indefinido a toda costa. Ciertamente, si incursionas en él, volverá a perseguirte.

Una cosa que su ejemplo no considera es la optimización. ase establece en el ciclo pero nunca se usa, y un optimizador podría resolver esto. Como tal, es legítimo que el optimizador descarte por acompleto y, en ese caso, todo comportamiento indefinido se desvanece como una víctima de boojum.

Sin embargo, por supuesto, esto en sí mismo no está definido, porque la optimización no está definida. :)

Dado que esta pregunta es C y C ++ de doble etiqueta, intentaré abordar ambos. C y C ++ adoptan enfoques diferentes aquí.

En C, la implementación debe ser capaz de demostrar que se invocará el comportamiento indefinido para tratar el programa completo como si tuviera un comportamiento indefinido. En el ejemplo de los OP, parecería trivial que el compilador demuestre eso y, por lo tanto, es como si todo el programa no estuviera definido.

Podemos ver esto en el Informe de defectos 109 que en su punto crucial pregunta:

Sin embargo, si el Estándar C reconoce la existencia separada de "valores indefinidos" (cuya mera creación no implica totalmente "comportamiento indefinido"), entonces una persona que realiza pruebas de compilación podría escribir un caso de prueba como el siguiente, y también podría esperar (o posiblemente exigir) que una implementación conforme debería, como mínimo, compilar este código (y posiblemente también permitir que se ejecute) sin "fallas".

int array1[5];
int array2[5];
int *p1 = &array1[0];
int *p2 = &array2[0];

int foo()
{
int i;
i = (p1 > p2); /* Must this be "successfully translated"? */
1/0; /* Must this be "successfully translated"? */
return 0;
}

Entonces, la pregunta de fondo es esta: ¿Debe el código anterior ser "traducido exitosamente" (lo que sea que eso signifique)? (Véase la nota a pie de página adjunta a la subcláusula 5.1.1.3.)

y la respuesta fue:

El Estándar C usa el término "valor indeterminado" y no "valor indefinido". El uso de un objeto de valor indeterminado da como resultado un comportamiento indefinido. La nota a pie de página de la subcláusula 5.1.1.3 señala que una implementación es libre de producir cualquier número de diagnósticos siempre que un programa válido esté correctamente traducido. Si una expresión cuya evaluación resultaría en un comportamiento indefinido aparece en un contexto donde se requiere una expresión constante, el programa contenedor no es estrictamente conforme. Además, si cada posible ejecución de un programa dado resultara en un comportamiento indefinido, el programa dado no es estrictamente conforme. Una implementación conforme no debe dejar de traducir un programa estrictamente conforme simplemente porque alguna posible ejecución de ese programa daría como resultado un comportamiento indefinido. Dado que es posible que nunca se llame a foo, el ejemplo dado debe traducirse correctamente mediante una implementación conforme.

En C ++, el enfoque parece más relajado y sugeriría que un programa tiene un comportamiento indefinido independientemente de si la implementación puede probarlo estáticamente o no.

Tenemos [intro.abstrac] p5 que dice:

Una implementación conforme que ejecuta un programa bien formado producirá el mismo comportamiento observable que una de las posibles ejecuciones de la instancia correspondiente de la máquina abstracta con el mismo programa y la misma entrada. Sin embargo, si tal ejecución contiene una operación indefinida, este documento no impone ningún requisito a la implementación que ejecute ese programa con esa entrada (ni siquiera con respecto a las operaciones que preceden a la primera operación indefinida).

La respuesta principal es un concepto erróneo (pero común):

El comportamiento no definido es una propiedad en tiempo de ejecución *. ¡ NO PUEDE "viajar en el tiempo"!

Ciertas operaciones están definidas (por el estándar) para tener efectos secundarios y no se pueden optimizar. Las operaciones que realizan E / S o que acceden a volatilevariables entran en esta categoría.

Sin embargo , hay una advertencia: UB puede ser cualquier comportamiento, incluido el comportamiento que deshaga operaciones anteriores. Esto puede tener consecuencias similares, en algunos casos, a la optimización del código anterior.

De hecho, esto es consistente con la cita en la respuesta principal (énfasis mío):

Una implementación conforme que ejecuta un programa bien formado producirá el mismo comportamiento observable que una de las posibles ejecuciones de la instancia correspondiente de la máquina abstracta con el mismo programa y la misma entrada.
Sin embargo, si tal ejecución contiene una operación no definida, esta Norma Internacional no impone ningún requisito a la implementación que ejecuta ese programa con esa entrada (ni siquiera con respecto a las operaciones que preceden a la primera operación no definida).

Sí, esta cita hace decir "ni siquiera en lo que respecta a las operaciones anteriores a la primera operación indefinido" , pero aviso de que se trata específicamente sobre el código que está siendo ejecutado , no sólo compila.
Después de todo, el comportamiento indefinido que no se alcanza en realidad no hace nada, y para que se alcance la línea que contiene UB, ¡el código que la precede debe ejecutarse primero!

Entonces sí, una vez que se ejecuta UB , cualquier efecto de las operaciones anteriores se vuelve indefinido. Pero hasta que eso suceda, la ejecución del programa está bien definida.

Sin embargo, tenga en cuenta que todas las ejecuciones del programa que provoquen que esto suceda se pueden optimizar para programas equivalentes , incluidos los que realizan operaciones anteriores pero luego deshacen sus efectos. En consecuencia, el código anterior puede optimizarse siempre que hacerlo equivalga a deshacer sus efectos ; de lo contrario, no puede. Vea a continuación un ejemplo.

* Nota: Esto no es incompatible con UB que ocurre en tiempo de compilación . Si el compilador puede incluso resultar que el código UB será cuestión se realizará para todas las entradas, a continuación, UB se puede extender a tiempo de compilación. Sin embargo, esto requiere saber que todo el código anterior eventualmente regresa , lo cual es un requisito importante. Nuevamente, vea a continuación un ejemplo / explicación.

Para que esto sea concreto, tenga en cuenta que el siguiente código debe imprimirse fooy esperar su entrada independientemente de cualquier comportamiento indefinido que le siga:

printf("foo");
getchar();
*(char*)1 = 1;

Sin embargo, también tenga en cuenta que no hay garantía de que foopermanecerá en la pantalla después de que se produzca la UB, o que el carácter que escribió ya no estará en el búfer de entrada; Ambas operaciones se pueden "deshacer", lo que tiene un efecto similar al "viaje en el tiempo" de UB.

Si la getchar()línea no estuviera allí, sería legal que las líneas se optimizaran si y solo si eso fuera indistinguible de generar fooy luego " deshacer ".

Si los dos serían indistinguibles o no dependería enteramente de la implementación (es decir, de su compilador y biblioteca estándar). Por ejemplo, ¿puede printf bloquear su hilo aquí mientras espera que otro programa lea el resultado? ¿O volverá inmediatamente?

• Si se puede bloquear aquí, entonces otro programa puede negarse a leer su salida completa y es posible que nunca regrese y, en consecuencia, UB nunca ocurra.

• Si puede regresar inmediatamente aquí, entonces sabemos que debe regresar y, por lo tanto, optimizarlo es completamente indistinguible de ejecutarlo y luego deshacer sus efectos.

Por supuesto, dado que el compilador sabe qué comportamiento está permitido para su versión particular de printf, puede optimizar en consecuencia y, en consecuencia, printfpuede optimizarse en algunos casos y no en otros. Pero, de nuevo, la justificación es que esto sería indistinguible de las operaciones anteriores de deshacer UB, no que el código anterior esté "envenenado" debido a UB.