tipos - ¿Los compiladores tienen permitido eliminar bucles infinitos?

ciclo do while

Question

Puede optimizar el compilador para eliminar bucles infinitos, lo que no cambia ningún dato, como

while(1) 
  /* noop */;

A partir del análisis de un flujo de datos, el compilador gráfico puede derivar que dicho ciclo es "código muerto" sin ningún efecto secundario.

¿Está prohibido eliminar los bucles infinitos prohibidos por los estándares C90 / C99?

¿Los estándares C90 o C99 permiten que el compilador elimine dichos bucles?

Upd: "Microsoft C versión 6.0 hizo esencialmente esta optimización.", Ver el enlace de caf.

label: goto label;
return 0;

será transformado a

return 0;

Answer 1

Creo que los estándares más nuevos proporcionan explícitamente que si un fragmento de código no accede a variables volátiles, realiza E / S, etc., cualquier otro código que no dependa de nada computado en la primera pieza puede ser secuenciado arbitrariamente antes. Si un bucle infinito no realiza ninguna E / S, ni calcula ningún valor que se utilice más adelante en el programa, un compilador puede simplemente diferir la ejecución del bucle hasta que todo lo demás se haya completado.

Answer 2

El bucle no es un código muerto, básicamente está impidiendo que el programa llegue a lo que viene después. Esto no es lo que sucedería si se elimina el bucle, por lo que el compilador no puede eliminar el bucle.

Podría reemplazarlo con una instrucción inactiva dependiente de la plataforma para indicarle al procesador que el hilo ya no va a hacer nada más.

Lo que el compilador puede hacer es eliminar cualquier código que venga después del bucle, porque es inalcanzable y nunca se ejecutará.

Answer 3

Esto ya se ha discutido muchas veces en comp.lang.c (por ejemplo, here ) sin, hasta donde sé, ningún resultado de consenso.

Answer 4

No hay manera de detectar bucles infinitos universalmente: ver el problema de detención . Entonces, lo mejor que cualquier compilador podría hacer es tomar una estimación decente, por ejemplo, el caso obvio mencionado en el PO.

Pero, ¿por qué sería esto deseable? Pude ver emitir una advertencia y aún permitir el comportamiento, pero eliminar el bucle no es una "optimización", ¡cambia el comportamiento del programa!

Answer 5

Son una necesidad al escribir daemons. ¿Por qué quieres llamarlos código muerto?

Answer 6

C11 aclara la respuesta a esta pregunta en el borrador de la sección 6.8.5 estándar C11 6.8.5 Las declaraciones de iteración agregaron el siguiente párrafo:

Una instrucción de iteración cuya expresión de control no es una expresión constante, ¹⁵⁶⁾ que no realiza operaciones de entrada / salida, no accede a objetos volátiles y no realiza sincronizaciones ni operaciones atómicas en su cuerpo, controla la expresión o (en el caso de un declaración) su expresión-3, puede ser asumida por la implementación para terminar. ¹⁵⁷⁾

y la nota al pie 157 dice:

Esto tiene como objetivo permitir las transformaciones del compilador, como la eliminación de bucles vacíos incluso cuando la terminación no puede ser probada.

Entonces tu ejemplo específico:

while(1) 
  /* noop */;

no es un juego justo para la optimización ya que la expresión de control es una expresión constante.

Bucles infinitos como UB

Entonces, ¿por qué se permite a los compiladores optimizar bucles infinitos de distancia con la excepción proporcionada anteriormente? Bueno, Hans Boehm ofrece un fundamento para hacer un comportamiento indefinido de bucles infinitos en: N1528: ¿Por qué comportamiento indefinido para bucles infinitos? , la siguiente cita da una buena sensación para el problema involucrado:

Como correctamente señala el N1509, el borrador actual esencialmente da un comportamiento indefinido a los bucles infinitos en 6.8.5p6. Un problema importante para hacerlo es que permite que el código se mueva a través de un bucle potencialmente no terminable. Por ejemplo, supongamos que tenemos los siguientes bucles, donde count y count2 son variables globales (o se ha tomado su dirección), y p es una variable local, cuya dirección no se ha tomado:

for (p = q; p != 0; p = p -> next) {
    ++count;
}
for (p = q; p != 0; p = p -> next) {
    ++count2;
}

¿Se podrían fusionar estos dos bucles y reemplazarse por el siguiente bucle?

for (p = q; p != 0; p = p -> next) {
        ++count;
        ++count2;
}

Sin la dispensación especial en 6.8.5p6 para bucles infinitos, esto no se permitiría: si el primer bucle no termina porque q apunta a una lista circular, el original nunca escribe en count2. Por lo tanto, podría ejecutarse en paralelo con otro hilo que acceda o actualice count2. Esto ya no es seguro con la versión transformada que accede a count2 a pesar del bucle infinito. Por lo tanto, la transformación potencialmente introduce una raza de datos.

En casos como este, es muy poco probable que un compilador pueda probar la terminación del ciclo; Tendría que entender que q apunta a una lista acíclica, que creo que está más allá de la capacidad de la mayoría de los compiladores convencionales, y a menudo es imposible sin toda la información del programa.

C99

Como C99 no tiene esta excepción, deberíamos considerar la regla de si-si cubierta en la sección 5.1.2.3 que básicamente dice que el compilador solo tiene que emular el comportamiento observable de un programa, los requisitos son los siguientes:

Los requisitos mínimos en una implementación conforme son:

• En los puntos de secuencia, los objetos volátiles son estables en el sentido de que los accesos anteriores están completos y los accesos subsiguientes aún no se han producido.
• Al finalizar el programa, todos los datos escritos en los archivos serán idénticos al resultado que la ejecución del programa de acuerdo con la semántica abstracta habría producido.
• La dinámica de entrada y salida de los dispositivos interactivos se llevará a cabo tal como se especifica en 7.19.3. La intención de estos requisitos es que la salida sin buffer o de buffer de línea aparezca tan pronto como sea posible, para garantizar que los mensajes de aviso aparezcan realmente antes de que un programa espere la entrada.

Una lectura estricta de esto parece permitir que una implementación optimice un bucle infinito. Ciertamente podemos pensar en escenarios donde optimizar un bucle infinito causaría un cambio en el comportamiento observable:

while(1) ;
printf( "hello world/n" ) ;

Muchos argumentarían que efectuar la terminación de un proceso también es un comportamiento observable, esta posición se toma en C. Los compiladores refutan el último teorema de Fermat :

Al compilador se le otorga una libertad considerable en la forma en que implementa el programa C, pero su resultado debe tener el mismo comportamiento externo visible que el programa cuando se interpreta por la "máquina abstracta C" que se describe en el estándar. 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.

Actualizar

De alguna manera me perdí el seguimiento del artículo anterior, Recopiladores y revisión de la terminación, que dice lo siguiente sobre la sección 5.1.2.3 :

El segundo requisito es el complicado. Si se trata de la terminación del programa que se ejecuta en la máquina abstracta, entonces se cumple de manera imprecisa porque nuestro programa no finaliza. Si se trata de la terminación del programa real generado por el compilador, entonces la implementación C tiene errores porque los datos escritos en los archivos (stdout es un archivo) difieren de los datos escritos por la máquina abstracta. (Esta lectura se debe a Hans Boehm; no logré burlar esta sutileza del estándar).

También se podría argumentar que la necesidad de crear un corte en C11 para permitir la eliminación del bucle vacío implica que esta no era una optimización permitida anteriormente.

¿Esto se aplica a infinitos goto loops también?

Creo que la intención es que esto también se aplique a infinitos goto loops también. En C ++, este es claramente el caso ya que la sección 1.10 [intro.multithread] dice:

La implementación puede suponer que cualquier hilo eventualmente hará uno de los siguientes

• Terminar,
• hacer una llamada a una función de E / S de la biblioteca,
• acceder o modificar un objeto volátil, o
• realizar una operación de sincronización o una operación atómica.

y luego la intención, tal como se expresa en N1528 es que los estándares de C y C ++ coinciden:

Como los back-ends del compilador suelen compartirse entre los compiladores C y C ++, parece más importante que WG14 y WG21 acuerden la solución que se adopte. Las alternativas serían un tratamiento especial de los dos idiomas por parte del back-end o deshabilitar las optimizaciones al procesar el código C. Ninguno de los dos parece deseable.

y al final dice:

WG21 está considerando una mejor redacción que hace que el tratamiento sea consistente. Es de esperar que WG14 rastree los cambios resultantes.

Actualmente, el estándar C11 no contiene la fraseología similar en la sección 5.1.2.4 multiproceso y carreras de datos, pero considerando N1528 parece prudente suponer que los compiladores tratarán infinitos goto loops como un comportamiento indefinido en C y C ++.

Tenga en cuenta también ver los comentarios de los Estados Unidos 38 aquí y N3196 que es el documento al que se aplicó este cambio.