Capítulo 05 · Optimización
Hacer menos, más deprisa
Un optimizador reescribe un programa en otro más barato que se comporta exactamente igual. Algunas reescrituras son obvias, como calcular 2 × 60 al compilar; otras exigen analizar con cuidado cómo fluyen los valores por el programa. Todas obedecen una única regla: nadie debe poder notar la diferencia.
Cuando apareció FORTRAN en 1957, los programadores estaban convencidos de que una máquina nunca escribiría código tan bueno como el suyo. John Backus sabía que, si el primer compilador producía programas lentos, la idea entera se descartaría, así que su equipo dedicó gran parte del esfuerzo a la optimización, y el compilador de FORTRAN I sorprendió a sus usuarios con código cercano al de un experto. Desde entonces la optimización es la razón por la que confiamos en los compiladores.
La palabra engaña un poco. Ningún compilador encuentra el programa óptimo; aplica un catálogo de transformaciones seguras que normalmente hacen el programa más pequeño o más rápido. El optimizador de Wahoo (optimizer.rs) trabaja sobre la HIR comprobada, antes de generar código, y puedes encenderlo y apagarlo en el playground.
La regla del «como si»
Un optimizador puede cambiar cualquier cosa de un programa salvo su comportamiento observable: lo que imprime, lo que devuelve, y si falla y cómo. El estándar de C lo llama la regla del as-if: el programa debe comportarse como si se hubiera ejecutado exactamente tal como está escrito.
Qué cuenta como observable lo decide el lenguaje. En Wahoo cuentan la salida y los fallos al ejecutar. Por eso 10 / 0 no se pliega al compilar, aunque el compilador vea los dos números: el programa debe seguir cayendo al foso cuando llegue a esa línea, y solo entonces. Y ruidoso() * 0 no se simplifica a 0, porque ruidoso() podría imprimir algo. Solo las expresiones puras, sin llamadas ni posibles fallos, pueden descartarse.
Qué hace el optimizador de Wahoo
Plegado de constantes. Toda operación cuyos operandos se conocen al compilar se calcula en ese momento: 2 * 60 + 30 se convierte en 150, 3 < 5 en star. El plegado debe usar exactamente la aritmética de la máquina destino: las coins de Wahoo son enteros de 32 bits que dan la vuelta, así que 2147483647 + 1 se pliega a -2147483648, el mismo valor que calcularía el programa al ejecutarse.
Simplificación algebraica. Identidades que se cumplen para cualquier valor: x + 0, x - 0, x * 1 y x / 1 son x; not not s es s; star and s es s; goomba and s es goomba (y s tampoco se habría ejecutado, porque and hace cortocircuito).
Eliminación de ramas. Un question cuya condición se ha plegado a una constante se sustituye por la rama que se ejecutará; un bucle bounce goomba desaparece; un bucle run con límites constantes y vacío (from 5 to 1) también.
Eliminación de código muerto. Las sentencias tras un flag nunca pueden ejecutarse y se eliminan (el comprobador ya avisó de ellas).
question con condición constante o código tras un flag, y míralo desaparecer de la columna de la derecha.Lo que (todavía) no hace
El optimizador de Wahoo es pequeño a propósito. Los compiladores de producción aplican docenas de pasadas, muchas de ellas una y otra vez. Algunas clásicas, cada una con la oportunidad que aprovecha:
| Transformación | Antes | Después |
|---|---|---|
| Propagación de constantes | coin t = 150 … wahoo(t * 2) | wahoo(300) si t nunca cambia |
| Subexpresiones comunes | (a + b) * (a + b) | calcular a + b una vez |
| Sacar invariantes de bucles | bounce i < n { wahoo(i * (w * h)) … } | calcular w * h una vez, antes del bucle |
| Reducción de fuerza | i * 8 en un bucle | un desplazamiento, o sumar 8 en cada vuelta |
| Expansión en línea | una llamada a una pipe corta | el cuerpo de la pipe, en su sitio, lo que abre la puerta a todas las demás optimizaciones |
| Mirilla (peephole) | i32.gt_s seguido de i32.eqz | i32.le_s (¡Wahoo emite esa pareja en cada bounce!) |
| Eliminación de llamadas de cola | una pipe cuyo último acto es llamarse a sí misma | un salto al principio: recursión sin que crezca la pila |
| Vectorización | un bucle que suma dos vectores elemento a elemento | una instrucción que suma cuatro u ocho elementos a la vez |
Cada una es un buen ejercicio: el patrón de bucle del generador de código, por ejemplo, está pidiendo a gritos la regla de mirilla de la tabla.
Análisis de flujo de datos
Plegar 2 * 60 solo exige mirar un nodo del árbol. Propagar constantes a través de variables, encontrar expresiones calculadas dos veces o variables muertas exige saber cómo fluyen los valores por toda la función, a través de ramas y bucles. Los cimientos los pusieron en IBM Frances Allen y John Cocke. El artículo de Allen de 1970, Control Flow Analysis, partía las funciones en bloques básicos (tramos de código en línea recta con una sola entrada y una sola salida) unidos por aristas en un grafo de flujo de control, y en 1971 Allen y Cocke publicaron A Catalogue of Optimizing Transformations, la lista que casi todos los compiladores siguen todavía. En 2006 Allen fue la primera mujer en recibir el premio Turing, por este trabajo.
En 1973 Gary Kildall (más tarde autor del sistema operativo CP/M) unificó los análisis en un único marco: cada uno es un conjunto de hechos que se propaga por el grafo, se combina donde los caminos se juntan y se itera hasta que nada cambia. La teoría de retículos que hay detrás garantiza que la iteración termina. A finales de los ochenta Mark Wegman, Kenneth Zadeck y sus colegas de IBM introdujeron la forma SSA (capítulo 04), que hace muchos de estos análisis más rápidos y sencillos, y que hoy usa casi todo compilador optimizador.
El lado oscuro: el comportamiento indefinido
La regla del «como si» solo protege a los programas cuyo comportamiento está definido. C y C++ dejan muchas cosas indefinidas: el desbordamiento de enteros con signo, leer fuera de un vector, desreferenciar un puntero nulo. El compilador puede suponer que nunca ocurren y optimizar en consecuencia. Quien escribe una comprobación de desbordamiento como
if (x + 1 < x) { /* ¡desbordamiento! */ }puede encontrársela borrada, porque para un int con signo la condición solo puede ser cierta tras un desbordamiento, que «no puede ocurrir». Sorpresas así han causado agujeros de seguridad reales. Wahoo, como Rust en modo release, Java y el propio WebAssembly, define el desbordamiento como una vuelta completa, así que el optimizador no tiene nada que explotar y nadie se lleva sorpresas.
No hay optimizador perfecto
¿Podría un compilador suficientemente listo encontrar siempre el programa equivalente más pequeño? No. Si pudiera, dado cualquier programa que nunca imprime y nunca termina, lo convertiría en el programa más pequeño que nunca imprime y nunca termina, un bucle infinito vacío, y comparar salidas decidiría el problema de la parada. Andrew Appel lo llama el teorema del pleno empleo para quienes escriben compiladores: siempre hay un optimizador mejor por escribir. En la práctica los límites son más económicos que matemáticos: cada pasada cuesta tiempo de compilación, y por eso los compiladores ofrecen niveles (de -O0 a -O3), los JIT solo optimizan el código caliente (capítulo 00) y Wahoo te deja apagarlo y comparar.
Referencias
- J. W. Backus (1978). “The History of FORTRAN I, II, and III”. ACM SIGPLAN Notices, 13(8).
- F. E. Allen (1970). “Control Flow Analysis”. ACM SIGPLAN Notices, 5(7).
- F. E. Allen y J. Cocke (1971). “A Catalogue of Optimizing Transformations”. En Design and Optimization of Compilers, Prentice-Hall.
- G. A. Kildall (1973). “A Unified Approach to Global Program Optimization”. Proceedings of the 1st ACM Symposium on Principles of Programming Languages.
- B. K. Rosen, M. N. Wegman y F. K. Zadeck (1988). “Global Value Numbers and Redundant Computations”. Proceedings of POPL.
- A. W. Appel (1998). Modern Compiler Implementation in ML. Cambridge University Press.
- C. Lattner (2011). “What Every C Programmer Should Know About Undefined Behavior”. LLVM Project Blog.