Función optimizada para bucle infinito en ''gcc-O2''

optimization undefined-behavior

Question

Contexto
Me fue preguntado el siguiente acertijo por uno de mis amigos:

void fn(void)
{
/* write something after this comment so that the program output is 10 */
/* write something before this comment */
}
int main()
{
int i = 5;
fn();
printf("%d/n", i);
return 0;
}

Sé que puede haber múltiples soluciones, algunas involucrando macro y algunas asumiendo algo sobre la implementación y violando a C.

Una solución particular en la que estaba interesado es hacer ciertas suposiciones sobre la pila y escribir el siguiente código: (entiendo que es un comportamiento indefinido, pero puede funcionar como se espera en muchas implementaciones)

void fn(void)
{
/* write something after this comment so that the program output is 10 */
int a[1] = {0};
int j = 0;
while(a[j] != 5) ++j; /* Search stack until you find 5 */
a[j] = 10; /* Overwrite it with 10 */
/* write something before this comment */
}

Problema
Este programa funcionó bien en MSVC y gcc sin optimización. Pero cuando lo compilé con la bandera gcc -O2 o probé con ideone , se ideone infinitamente en la función fn .

Mi observación
Cuando compilé el archivo con gcc -S vs gcc -S -O2 y lo gcc -S -O2 , muestra claramente que gcc mantuvo un bucle infinito en la función fn .

Pregunta
Entiendo porque el código invoca un comportamiento indefinido, uno no puede llamarlo un error. Pero ¿por qué y cómo el compilador analiza el comportamiento y deja un ciclo infinito en O2 ?

Muchas personas comentaron conocer el comportamiento si algunas de las variables se cambian a volátiles. El resultado esperado es:

• Si i o j se cambia a volatile , el comportamiento del programa permanece igual.
• Si la matriz a se vuelve volatile , el programa no sufre un ciclo infinito.
• Además si aplico el siguiente parche

- int a[1] = {0};
+ int aa[1] = {0};
+ int *a = aa;

El comportamiento del programa sigue siendo el mismo (ciclo infinito)

Si compilo el código con gcc -O2 -fdump-tree-optimized , obtengo el siguiente archivo intermedio:

;; Function fn (fn) (executed once)
Removing basic block 3
fn ()
{
<bb 2>:
<bb 3>:
goto <bb 3>;
}
;; Function main (main) (executed once)
main ()
{
<bb 2>:
fn ();
}
Invalid sum of incoming frequencies 0, should be 10000

Esto verifica las afirmaciones hechas después de las respuestas a continuación.

Answer 1

En la versión optimizada, el compilador ha decidido algunas cosas:

1. La matriz a no cambia antes de esa prueba.
2. La matriz a no contiene un 5 .

Por lo tanto, podemos reescribir el código como:

void fn(void) {
int a[1] = {0};
int j = 0;
while(true) ++j;
a[j] = 10;
}

Ahora, podemos tomar más decisiones:

1. Todo el código después del ciclo while es código inactivo (inalcanzable).
2. j está escrito pero nunca leído. Entonces podemos deshacernos de eso.
3. a nunca se lee.

En este punto, su código se ha reducido a:

void fn(void) {
int a[1] = {0};
while(true);
}

Y podemos hacer que la nota que a no se lea nunca, así que deshagámosla también:

void fn(void) {
while(true);
}

Ahora, el código no optimizado:

En el código generado no optimizado, la matriz permanecerá en la memoria. Y literalmente lo caminarás en tiempo de ejecución. Y es posible que haya un 5 que sea legible después de que haya caminado más allá del final de la matriz.

Por eso, la versión no optimizada a veces no se cuelga ni se quema.

Answer 2

Este es un comportamiento indefinido, por lo que el compilador realmente puede hacer cualquier cosa, podemos encontrar un ejemplo similar en GCC pre-4.8. Rompe los SPEC 2006 Benchmarks , donde gcc toma un ciclo con comportamiento indefinido y lo optimiza para:

L2:
jmp .L2

El artículo dice (el énfasis es mío ):

Por supuesto, este es un ciclo infinito. Como SATD () ejecuta incondicionalmente un comportamiento indefinido (es una función de tipo 3), cualquier traducción (o ninguna) es un comportamiento perfectamente aceptable para un compilador de C correcto . El comportamiento indefinido es acceder a d [16] justo antes de salir del bucle. En C99 es legal crear un puntero a un elemento una posición más allá del final de la matriz, pero ese puntero no se debe desreferenciar . De manera similar, no se debe acceder a la celda de matriz un elemento más allá del final de la matriz.

que si examinamos su programa con godbolt vemos:

fn:
.L2:
jmp .L2

La lógica utilizada por el optimizador probablemente sea más o menos así:

• Todos los elementos de a se inicializan a cero
• a nunca se modifica antes o dentro del ciclo
• Entonces a[j] != 5 siempre es verdadero -> ciclo infinito
• Debido al infinito, a a[j] = 10; es inalcanzable y puede optimizarse, por lo que a y j ya no se necesitan para determinar la condición del bucle.

que es similar al caso en el artículo dado:

int d[16];

analiza el siguiente ciclo:

for (dd=d[k=0]; k<16; dd=d[++k])

Me gusta esto:

al ver d [++ k], se permite suponer que el valor incrementado de k está dentro de los límites de la matriz, ya que de lo contrario se produce un comportamiento indefinido. Para el código aquí, GCC puede inferir que k está en el rango 0..15. Un poco más tarde, cuando GCC ve k <16, se dice a sí mismo: "Aha- esa expresión es siempre cierta, así que tenemos un ciclo infinito".

Quizás un punto secundario interesante es si un ciclo infinito se considera comportamiento observable ( wrt a la regla de si-si ) o no, lo que afecta si un ciclo infinito también puede optimizarse. Podemos ver en C Compiladores refutar el último teorema de Fermat que antes de C11 había al menos algún espacio para la interpretación:

Muchas personas conocedoras (incluyéndome a mí) leen esto diciendo que el comportamiento de terminación de un programa no debe cambiarse. Obviamente, algunos escritores de compiladores no están de acuerdo, o de lo contrario no creen que importe. El hecho de que personas razonables no estén de acuerdo con la interpretación parece indicar que el estándar C es defectuoso.

C11 agrega una aclaración a la sección 6.8.5 Declaraciones de iteración y se trata con más detalle en esta respuesta .

Answer 3

Si el bucle se optimiza en un bucle infinito, podría deberse a un análisis de código estático al ver que su matriz es

1. no volatile

2. contiene solo 0

3. nunca se escribe

y por lo tanto no es posible que contenga el número 5 . Lo que significa un ciclo infinito.

Incluso si no hiciera esto, su enfoque podría fallar fácilmente. Por ejemplo, es posible que algún compilador optimice su código sin hacer que el bucle sea infinito, sino que metería el contenido de i en un registro, lo que lo haría no disponible de la pila.

Como nota al margen, apuesto a que lo que tu amigo realmente esperaba era esto:

void fn(void)
{
/* write something after this comment so that the program output is 10 */
printf("10/n"); /* Output 10 */
while(1); /* Endless loop, function won''t return, i won''t be output */
/* write something before this comment */
}

o esto (si stdlib.h está incluido):

void fn(void)
{
/* write something after this comment so that the program output is 10 */
printf("10/n"); /* Output 10 */
exit(0); /* Exit gracefully */
/* write something before this comment */
}