Por Chris Lattner
Original article: blog.llvm.org/2011/05/what-every-c-programmer-should-know.html
May 13, 2011
La gente de vez en cuando pregunta por qué el código compilado con LLVM a veces genera señales SIGTRAP cuando el optimizador está activado. Después de indagar, encuentran que Clang generó una instrucción "ud2" (suponiendo código X86) - la misma que es generada por __builtin_trap(). Hay varias cuestiones en juego aquí, todas centradas en el comportamiento indefinido en el código C y cómo LLVM lo maneja.
Esta entrada de blog (la primera de una serie de tres) intenta explicar algunos de estos problemas para que puedas entender mejor las compensaciones y complejidades implicadas, y quizás aprender un poco más de los lados oscuros de C. Resulta que C no es un "ensamblador de alto nivel" como a muchos programadores experimentados de C (particularmente gente con un enfoque de bajo nivel) les gusta pensar, y que C++ y Objective-C han heredado directamente un montón de problemas de él.
Introducción al comportamiento indefinido
Tanto el LLVM IR como el lenguaje de programación C tienen el concepto de "comportamiento indefinido". El comportamiento indefinido es un tema amplio con muchos matices. La mejor introducción que he encontrado al respecto es un artículo en el Blog de John Regehr. La versión corta de este excelente artículo es que muchas cosas aparentemente razonables en C en realidad tienen un comportamiento indefinido, y esta es una fuente común de errores en los programas. Más allá de eso, cualquier comportamiento indefinido en C da licencia a la implementación (el compilador y el tiempo de ejecución) para producir código que formatea tu disco duro, hace cosas completamente inesperadas, o cosas peores. De nuevo, recomiendo encarecidamente la lectura del artículo de John.
El comportamiento indefinido existe en los lenguajes basados en C porque los diseñadores de C querían que fuera un lenguaje de programación de bajo nivel extremadamente eficiente. En cambio, lenguajes como Java (y muchos otros lenguajes "seguros") han evitado el comportamiento indefinido porque quieren un comportamiento seguro y reproducible entre implementaciones, y están dispuestos a sacrificar rendimiento para conseguirlo. Aunque ninguno de los dos es "el objetivo correcto al que aspirar", si eres un programador de C realmente deberías entender qué es el comportamiento indefinido.
Antes de entrar en detalles, vale la pena mencionar brevemente lo que se necesita para que un compilador obtenga un buen rendimiento de una amplia gama de aplicaciones C, porque no hay una solución mágica. A un nivel muy alto, los compiladores producen aplicaciones de alto rendimiento a) haciendo un buen trabajo en los algoritmos básicos como la asignación de registros, la programación, etc. b) conociendo montones y montones de "trucos" (por ejemplo, optimizaciones peephole, transformaciones de bucle, etc.), y aplicándolos siempre que sea rentable. c) siendo buenos en la eliminación de abstracciones innecesarias (por ejemplo, redundancia debido a macros en C, funciones inlining, eliminación de objetos temporales en C++, etc.) y d) no arruinando nada. Aunque cualquiera de las optimizaciones siguientes pueda parecer trivial, resulta que ahorrar sólo un ciclo de un bucle crítico puede hacer que algún códec funcione un 10% más rápido o consuma un 10% menos de energía.
Ventajas del Comportamiento Indefinido en C, con Ejemplos
Antes de entrar en el lado oscuro del comportamiento indefinido y la política y el comportamiento de LLVM cuando se utiliza como compilador de C, pensé que sería útil considerar algunos casos específicos de comportamiento indefinido, y hablar de cómo cada uno permite un mejor rendimiento que un lenguaje seguro como Java. Puedes ver esto como "optimizaciones habilitadas" por la clase de comportamiento indefinido o como la "sobrecarga evitada" que se requeriría para hacer cada caso definido. Aunque el optimizador del compilador podría eliminar algunas de estas sobrecargas algunas veces, hacerlo en general (para cada caso) requeriría resolver el problema de detención y muchos otros "retos interesantes".
También vale la pena señalar que tanto Clang como GCC definen algunos comportamientos que el estándar C deja sin definir. Las cosas que voy a describir son a la vez indefinidas según el estándar y tratadas como comportamiento indefinido por ambos compiladores en sus modos por defecto.
Uso de una variable no inicializada: Esto es comúnmente conocido como fuente de problemas en los programas C y existen muchas herramientas para detectarlos: desde advertencias del compilador hasta analizadores estáticos y dinámicos. Esto mejora el rendimiento al no requerir que todas las variables se inicialicen a cero cuando entran en el ámbito (como hace Java). Para la mayoría de las variables escalares, esto causaría poca sobrecarga, pero las matrices de pila y la memoria malloc'd incurrirían en un memset del almacenamiento, lo que podría ser bastante costoso, sobre todo porque el almacenamiento suele sobrescribirse completamente.
Desbordamiento de entero con signo: Si la aritmética en un tipo 'int' (por ejemplo) se desborda, el resultado es indefinido. Un ejemplo es que no se garantiza que "INT_MAX+1" sea INT_MIN. Este comportamiento permite ciertas clases de optimizaciones que son importantes para algunos códigos. Por ejemplo, saber que INT_MAX+1 es indefinido permite optimizar "X+1 > X" a "verdadero". Saber que la multiplicación "no puede" desbordarse (porque hacerlo sería indefinido) permite optimizar "X*2/2" a "X". Aunque esto puede parecer trivial, este tipo de cosas son comúnmente expuestas por inlining y expansión de macros. Una optimización más importante que esto permite es para "<=" bucles como este:
for (i = 0; i <= N; ++i) { ... }
En este bucle, el compilador puede asumir que el bucle iterará exactamente N+1 veces si "i" es indefinido por desbordamiento, lo que permite una amplia gama de optimizaciones de bucle. Por otro lado, si la variable está definida para envolverse en el desbordamiento, entonces el compilador debe asumir que el bucle es posiblemente infinito (lo que ocurre si N es INT_MAX) - lo que deshabilita estas importantes optimizaciones de bucle. Esto afecta particularmente a las plataformas de 64 bits ya que mucho código utiliza "int" como variables de inducción.
Vale la pena señalar que el desbordamiento sin signo está garantizado para ser definido como desbordamiento de complemento a 2 (envolvente), por lo que siempre se pueden utilizar. El coste de definir el desbordamiento de enteros con signo es que este tipo de optimizaciones simplemente se pierden (por ejemplo, un síntoma común es una tonelada de extensiones de signo dentro de bucles en objetivos de 64 bits). Tanto Clang como GCC aceptan la bandera "-fwrapv" que fuerza al compilador a tratar el desbordamiento de enteros con signo como definido (aparte de la división de INT_MIN por -1).
Desbordamiento de cantidades: Desplazar un uint32_t 32 bits o más no está definido. Mi suposición es que esto se originó porque las operaciones de desplazamiento subyacentes en varias CPU hacen cosas diferentes con esto: por ejemplo, X86 trunca la cantidad de desplazamiento de 32 bits a 5 bits (por lo que un desplazamiento de 32 bits es lo mismo que un desplazamiento de 0 bits), pero PowerPC trunca las cantidades de desplazamiento de 32 bits a 6 bits (por lo que un desplazamiento de 32 produce cero). Debido a estas diferencias de hardware, el comportamiento es completamente indefinido por C (por lo tanto, el desplazamiento de 32 bits en PowerPC podría formatear su disco duro, *no* está garantizado que produzca cero). El coste de eliminar este comportamiento indefinido es que el compilador tendría que emitir una operación extra (como una 'y') para los desplazamientos de variables, lo que los haría el doble de caros en CPUs comunes.
Desreferencias de Punteros Salvajes y Accesos a Matrices Fuera de Límites: La desreferenciación de punteros aleatorios (como NULL, punteros a memoria libre, etc) y el caso especial de acceder a un array fuera de límites es un error común en las aplicaciones C que esperemos no necesite explicación. Para eliminar esta fuente de comportamiento indefinido, los accesos a arrays tendrían que ser comprobados por rango, y la ABI tendría que ser cambiada para asegurarse de que la información de rango sigue alrededor de cualquier puntero que pudiera estar sujeto a la aritmética de punteros. Esto tendría un coste extremadamente alto para muchas aplicaciones numéricas y de otro tipo, además de romper la compatibilidad binaria con todas las bibliotecas C existentes.
Desreferenciación de un puntero NULL: contrariamente a la creencia popular, la desreferenciación de un puntero nulo en C no está definida. No está definido para atrapar, y si se mmappea una página en 0, no está definido para acceder a esa página. Esto se sale de las reglas que prohíben la desreferenciación de punteros salvajes y el uso de NULL como centinela. El hecho de que las desreferencias a punteros NULL no estén definidas permite una amplia gama de optimizaciones: por el contrario, Java hace que no sea válido para el compilador mover una operación de efecto secundario a través de cualquier desreferencia a punteros a objetos que el optimizador no pueda probar que no son NULL. Esto penaliza significativamente la programación y otras optimizaciones. En los lenguajes basados en C, la indefinición de NULL permite un gran número de optimizaciones escalares sencillas que quedan expuestas como resultado de la expansión de macros y el inlining.
Si estás usando un compilador basado en LLVM, puedes hacer dereferencia a un puntero nulo "volátil" para obtener un fallo si eso es lo que estás buscando, ya que las cargas y almacenamientos volátiles generalmente no son tocados por el optimizador. Actualmente no existe ninguna bandera que permita que las cargas aleatorias de punteros NULL sean tratadas como accesos válidos o que haga que las cargas aleatorias sepan que su puntero está "autorizado a ser nulo".
Violación de las reglas de tipo: Es un comportamiento indefinido convertir un int* en un float* y desreferenciarlo (accediendo al "int" como si fuera un "float"). C requiere que este tipo de conversiones de tipo se realicen a través de memcpy: usar conversiones de punteros no es correcto y resulta en un comportamiento indefinido. Las reglas para esto son bastante matizadas y no quiero entrar en detalles aquí (hay una excepción para char*, los vectores tienen propiedades especiales, las uniones cambian cosas, etc). Este comportamiento permite un análisis conocido como "Type-Based Alias Analysis" (TBAA) que es utilizado por una amplia gama de optimizaciones de acceso a memoria en el compilador, y puede mejorar significativamente el rendimiento del código generado. Por ejemplo, esta regla permite a clang optimizar esta función:
float *P;
void matriz_cero() {
int i;
for (i = 0; i < 10000; ++i)
P[i] = 0.0f;
}
en "memset(P, 0, 40000)". Esta optimización también permite sacar muchas cargas de los bucles, eliminar subexpresiones comunes, etc. Esta clase de comportamiento indefinido puede desactivarse pasando la bandera -fno-strict-aliasing, que desautoriza este análisis. Cuando se pasa esta bandera, Clang se ve obligado a compilar este bucle en 10000 almacenes de 4 bytes (lo que es varias veces más lento), porque tiene que asumir que es posible que cualquiera de los almacenes cambie el valor de P, como en algo como esto:
int main() {
P = (float*)&P; // la conversión causa una violación TBAA en zero_array.
zero_array();
}
Este tipo de abuso de tipos es bastante infrecuente, razón por la cual el comité del estándar decidió que las significativas ganancias de rendimiento merecían la pena por el resultado inesperado de los lanzamientos de tipos "razonables". Vale la pena señalar que Java obtiene los beneficios de las optimizaciones basadas en tipos sin estos inconvenientes, ya que no tiene ningún tipo de fundido de punteros inseguro en el lenguaje.
De todos modos, espero que esto te dé una idea de algunas de las clases de optimizaciones permitidas por el comportamiento indefinido en C. Hay muchas otras clases, por supuesto, incluyendo violaciones del punto de secuencia como "foo(i, ++i)", condiciones de carrera en programas multihilo, violar 'restrict', dividir por cero, etc.
En nuestro próximo post, discutiremos por qué el comportamiento indefinido en C es algo bastante aterrador si el rendimiento no es tu único objetivo. En nuestro último post de la serie, hablaremos de cómo lo manejan LLVM y Clang.
Comandos de Expresión Regulares
Lo que Todo Programador de C Debe Saber Sobre el Comportamiento Indefinido #2/3
