¿Cuándo saltó el comportamiento indefinido en C la barrera de la causalidad?

Algunos compiladores de C hipermodernos inferirán que si un programa invocará Comportamiento indefinido cuando se le den ciertas entradas, tales entradas nunca se recibirán. En consecuencia, cualquier código que sería irrelevante a menos que se reciban tales entradas puede ser eliminado.

Como un simple ejemplo, dado:

void foo(uint32_t);

uint32_t rotateleft(uint_t value, uint32_t amount)
{
  return (value << amount) | (value >> (32-amount));
}

uint32_t blah(uint32_t x, uint32_t y)
{
  if (y != 0) foo(y);
  return rotateleft(x,y);
}

un compilador puede inferir que debido a que la evaluación de value >> (32-amount)producirá Comportamiento indefinido cuando amountes cero, la función blahnunca se llamará con yigual a cero; el llamado a foopuede ser hecho incondicional.

Por lo que puedo decir, esta filosofía parece haberse apoderado en algún momento alrededor de 2010. La evidencia más temprana que he visto de sus raíces se remonta a 2009, y se ha consagrado en el estándar C11 que establece explícitamente que si se produce un comportamiento indefinido en cualquier momento En la ejecución de un programa, el comportamiento de todo el programa retroactivamente se vuelve indefinido.

Fue la idea de que los compiladores deben intentar utilizar un comportamiento indefinido para justificar optimizaciones inversa-causales (es decir, el comportamiento no definido en la rotateleftfunción debe hacer que el compilador de suponer que blahdebe haber sido llamada con un no-cero y, o no lo volvería a hacer que ya mantener un valor distinto de cero) ¿abogó seriamente antes de 2009? ¿Cuándo se propuso por primera vez tal cosa como una técnica de optimización?

[Apéndice]

Algunos compiladores, incluso en el siglo XX, incluyeron opciones para permitir ciertos tipos de inferencias sobre bucles y los valores calculados en ellos. Por ejemplo, dado

int i; int total=0;
for (i=n; i>=0; i--)
{
  doSomething();
  total += i*1000;
}

un compilador, incluso sin las inferencias opcionales, podría reescribirlo como:

int i; int total=0; int x1000;
for (i=n, x1000=n*1000; i>0; i--, x1000-=1000)
{
  doSomething();
  total += x1000;
}

dado que el comportamiento de ese código coincidiría con precisión con el original, incluso si el compilador especificara que los intvalores siempre se ajustan a la moda mod-65536 del complemento a dos . La opción de inferencia adicional permitiría al compilador reconocer que, dado que iy x1000debe cruzar cero al mismo tiempo, la primera variable se puede eliminar:

int total=0; int x1000;
for (x1000=n*1000; x1000 > 0; x1000-=1000)
{
  doSomething();
  total += x1000;
}

En un sistema donde los intvalores envuelven el mod 65536, un intento de ejecutar cualquiera de los dos primeros bucles con un valor nigual a 33 resultaría en doSomething()ser invocado 33 veces. El último bucle, por el contrario, no invocaría doSomething()en absoluto, a pesar de que la primera invocación doSomething()hubiera precedido cualquier desbordamiento aritmético. Tal comportamiento podría considerarse "no causal", pero los efectos están razonablemente bien restringidos y hay muchos casos en los que el comportamiento sería demostrablemente inofensivo (en los casos en que se requiere que una función produzca algún valor cuando se le da cualquier entrada, pero el valor puede ser arbitrario si la entrada no es válida, haciendo que el ciclo finalice más rápido cuando se le da un valor no válido denen realidad sería beneficioso) Además, la documentación del compilador tendía a pedir disculpas por el hecho de que cambiaría el comportamiento de cualquier programa, incluso de aquellos que participan en UB.

Me interesa saber cuándo las actitudes de los escritores de compiladores cambiaron de la idea de que las plataformas deberían, cuando sea práctico, documentar algunas restricciones de comportamiento utilizables, incluso en casos no obligatorios por el Estándar, a la idea de que cualquier construcción que dependería de cualquier comportamiento no ordenado por el Standard debería ser calificado de ilegítimo incluso si en la mayoría de los compiladores existentes funcionaría tan bien o mejor que cualquier código estrictamente compatible que cumpla los mismos requisitos (a menudo permitiendo optimizaciones que no serían posibles en un código estrictamente compatible).

El comportamiento indefinido se usa en situaciones en las que no es factible que la especificación especifique el comportamiento, y siempre se ha escrito para permitir absolutamente cualquier comportamiento posible.

Las reglas extremadamente flexibles para UB son útiles cuando piensa en lo que debe pasar un compilador conforme a las especificaciones. Es posible que tenga suficiente potencia de compilación para emitir un error cuando hace un mal UB en un caso, pero agregue algunas capas de recursión y ahora lo mejor que puede hacer es una advertencia. La especificación no tiene el concepto de "advertencias", por lo que si la especificación hubiera dado un comportamiento, tendría que ser "un error".

La razón por la que vemos más y más efectos secundarios de esto es el impulso para la optimización. Escribir un optimizador de conformidad de especificaciones es difícil. Escribir un optimizador de conformidad de especificaciones que también hace un trabajo notablemente bueno adivinando lo que pretendías cuando saliste de la especificación es brutal. Es mucho más fácil para los compiladores si llegan a suponer que UB significa UB.

Esto es especialmente cierto para gcc, que intenta admitir muchos conjuntos de instrucciones con el mismo compilador. Es mucho más fácil dejar que UB produzca comportamientos UB que tratar de lidiar con todas las formas en que cada código UB podría salir mal en cada plataforma, y ​​tenerlo en cuenta en las primeras frases del optimizador.

"El comportamiento indefinido puede hacer que el compilador reescriba el código" ha sucedido durante mucho tiempo, en optimizaciones de bucle.

Tome un bucle (a y b son punteros para duplicar, por ejemplo)

for (i = 0; i < n; ++i) a [i] = b [i];

Incrementamos un int, copiamos un elemento de matriz, lo comparamos con un límite. Un compilador optimizador primero elimina la indexación:

double* tmp1 = a;
double* tmp2 = b;
for (i = 0; i < n; ++i) *tmp1++ = *tmp2++;

Eliminamos el caso n <= 0:

i = 0;
if (n > 0) {
    double* tmp1 = a;
    double* tmp2 = b;
    for (; i < n; ++i) *tmp1++ = *tmp2++;
}

Ahora eliminamos la variable i:

i = 0;
if (n > 0) {
    double* tmp1 = a;
    double* tmp2 = b;
    double* limit = tmp1 + n;
    for (; tmp1 != limit; tmp1++, tmp2++) *tmp1 = *tmp2;
    i = n;
}

Ahora, si n = 2 ^ 29 en un sistema de 32 bits o 2 ^ 61 en un sistema de 64 bits, en implementaciones típicas tendremos tmp1 == límite, y no se ejecutará ningún código. Ahora reemplace la tarea con algo que lleve mucho tiempo para que el código original nunca se encuentre con el inevitable bloqueo porque lleva demasiado tiempo y el compilador ha cambiado el código.

Siempre ha sido el caso en C y C ++ que, como resultado de un comportamiento indefinido, cualquier cosa puede suceder. Por lo tanto, siempre ha sido el caso de que un compilador puede suponer que su código no invoca un comportamiento indefinido: o no hay un comportamiento indefinido en su código, entonces la suposición fue correcta. O bien, si hay un comportamiento indefinido en su código, lo que suceda como resultado de la suposición incorrecta está cubierto por " cualquier cosa puede suceder".

Si observa la característica "restringir" en C, el punto completo de la característica es que el compilador puede asumir que no hay un comportamiento indefinido, por lo que llegamos al punto en el que el compilador no solo puede sino que debe asumir que no hay indefinido comportamiento.

En el ejemplo que da, las instrucciones del ensamblador que generalmente se usan en las computadoras basadas en x86 para implementar el desplazamiento hacia la izquierda o hacia la derecha cambiarán en 0 bits si el recuento de cambios es 32 para el código de 32 bits o 64 para el código de 64 bits. Esto en la mayoría de los casos prácticos conducirá a resultados no deseados (y resultados que no son los mismos que en ARM o PowerPC, por ejemplo), por lo que el compilador está bastante justificado para suponer que este tipo de comportamiento indefinido no ocurre. Podrías cambiar tu código a

uint32_t rotateleft(uint_t value, uint32_t amount)
{
   return amount == 0 ? value : (value << amount) | (value >> (32-amount));
}

y sugiera a los desarrolladores de gcc o Clang que en la mayoría de los procesadores el compilador debe eliminar el código "cantidad == 0", porque el código ensamblador generado para el código de cambio producirá el mismo resultado que el valor cuando cantidad == 0.

Esto se debe a que hay un error en su código:

uint32_t blah(uint32_t x, uint32_t y)
{
    if (y != 0) 
    {
        foo(y);
        return x; ////// missing return here //////
    }
    return rotateleft(x, y);
}

En otras palabras, solo salta la barrera de la causalidad si el compilador ve que, dadas ciertas entradas, está invocando un comportamiento indefinido fuera de toda duda .

Al regresar justo antes de invocar un comportamiento indefinido, le dice al compilador que está evitando conscientemente que se ejecute ese comportamiento indefinido, y el compilador lo reconoce.

En otras palabras, cuando tiene un compilador que intenta aplicar la especificación de una manera muy estricta, debe implementar todas las validaciones de argumentos posibles en su código. Además, esta validación debe ocurrir antes de la invocación de dicho comportamiento indefinido.

¡Espere! ¡Y hay más!

Ahora, con los compiladores haciendo estas cosas súper locas pero súper lógicas, es imperativo decirle al compilador que no se supone que una función continúe la ejecución. Por lo tanto, la noreturnpalabra clave en la foo()función ahora se vuelve obligatoria .