En ciencias de la computación, un compilador optimizador es un compilador que trata de minimizar ciertos atributos de un programa informático con el fin de aumentar la eficiencia y rendimiento. Las optimizaciones del compilador se aplican generalmente mediante una secuencia de transformaciones de optimización, algoritmos que transforman un programa para producir otro con una salida semánticamente equivalente pero optimizado.Cooper, Keith D., and Torczon, Linda, Engineering a Compiler, Morgan Kaufmann, 2004, ISBN 1-55860-699-8
Generalmente hay varios aspectos que se desean optimizar: Optimización temporal: Reducir el tiempo de ejecución del programa. Optimización espacial: Reducir la cantidad de espacio en memoria que ocupa el programa en ejecución. Reducir el tamaño del programa. Minimizar la potencia consumida por un programa (debido a las computadoras portátiles).
marco|derecha|Etapas de compilación La optimización se realiza después de la generación de código de todo el programa o de un elemento ejecutable del programa (función, procedimiento, etc), por ende es dependiente del contexto. La condición que ha de cumplir es que el código optimizado se ha de comportar igual que el código de partida, excepto por ser más rápido o ocupar menos espacio.
Se ha demostrado que algunos problemas de optimización de código son NP-completo, o incluso indecidibles. En la práctica, factores como la voluntad del programador que debe esperar a que el compilador complete sus tareas, imponen límites superiores en las optimizaciones que las que una simple implementación del compilador puede proporcionar (la optimización es un proceso muy intensivo que generalmente necesita mucho procesamiento y memoria para llevarse a cabo). En el pasado, las limitaciones de memoria de las computadoras también eran un factor importante en la limitación de las optimizaciones que se podían realizar. Debido a todos estos factores, la optimización rara vez produce una salida de forma óptima (valga la redundancia), y el hecho de que una optimización pueda impedir el rendimiento en algunos casos, hace que, sean métodos heurísticos para mejorar el uso de los recursos en los programas típicos.
La optimización es el campo donde se hace más investigación en los compiladores hoy en día. Las tareas del front-end (exploración, análisis sintáctico, análisis léxico, análisis semántico) son bien conocidas y, sin optimizar, la generación de código es relativamente sencilla. La optimización, por otra parte, aún es un campo que no se ha terminado de desarrollar de forma completa.
Etapas de un compilador optimizador
Un compilador optimizador tipo consta de tres fases cuando realiza el proceso de optimización:
Análisis de control del flujo: construcción de grafos de control del flujo útiles para juntar información para realizar análisis. Se identifican los bucles. Análisis de flujo de datos: proceso de recolectar la información acerca de como se usan las variables en el programa. Asociadas a cada bloque básico y estructuras de control (if/else, bucles, etc). Transformaciones: a partir de la información recolectada, se hacen las transformaciones convenientes para optimizar el código
Tipos de optimización
Las técnicas utilizadas en la optimización se puede dividir entre varios tipos que pueden afectar cualquier propiedad, desde una sola instrucción, a todo el programa.
Técnicas globales, locales e interprocedurales
En términos generales, las técnicas de ámbito local son más fáciles de aplicar que las globales pero que resultan en menores ganancias.
Las técnicas locales se aplican en el bloque básicoCooper, Keith D., and Torczon, Linda, Engineering a Compiler, Morgan Kaufmann, 2004, ISBN 1-55860-699-8 page 404 (Un bloque básico es un fragmento de código que tiene una única entrada y salida, y cuyas instrucciones se ejecutan secuencialmente. Si se ejecuta una instrucción del bloque se ejecutan todas en un orden conocido en tiempo de compilación) dado que los bloques básicos no tienen control de flujo, estas optimizaciones necesitan muy poco análisis (lo que ahorra tiempo y reduce los requisitos de almacenamiento), pero esto también significa que ninguna información se conserva a través de saltos, y las optimizaciones al ser tan puntuales no tienen gran impacto sobre el programa.
Hay varios tipos de optimizaciones locales entre los que se encuentran principalmente:
Plegamiento de constantes (Constant floding) Propagación de constantes (Constat propagation) Reducción de potencia (Strength reduction) Reducción de subexpresiones comunes (Common subexpression elimination)
Las técnicas globales, también llamadas intraprocedurales, se realizan en una función o procedimiento entero.Cooper, Keith D., and Torczon, Linda, Engineering a Compiler, Morgan Kaufmann, 2004, ISBN 1-55860-699-8 page 407 Estas técnicas son más costosas, lo que requiere grandes cantidades de tiempo de compilación, pero puede proporcionar un gran aumento en el rendimiento ya que posee mucho más conocimiento del programa que las locales.
Por último las interprocedurales son las que analizan comportamiento entre procedimientos llegando a analizar el código completo. Lógicamente estas técnicas son las que más tiempo de compilación necesitan debido a la gran cantidad y costo de los análisis, pero las mejoras pueden ser notables.
Dependientes e independientes de máquina
Muchas optimizaciones que operan en conceptos abstractos de programación (bucles, estructuras, objetos) son independientes de la máquina prevista por el compilador, pero muchas de las optimizaciones más eficaces son las que mejor explotan las particularidades de la plataforma de destino.
Dependientes e independientes del lenguaje de programación
La mayoría de los lenguajes de alto nivel comparten estructuras comunes de programación y abstracciones: decisión (if, switch, case), bucle (for, while, repeat.. until, do.. while), y la encapsulación (estructuras, objetos). Dado esto, varias técnicas de optimización similares pueden ser utilizadas en todos los lenguajes. Sin embargo, algunas características de los mismos hacen algunos tipos de optimizaciones difícil. Por ejemplo, la existencia de los punteros en C y C++ hace que sea difícil optimizar accesos de arreglos (ver análisis de alias).
Otras optimizaciones
Algunos tipos de optimizaciones son muy comunes debido a sus características y es importante nombrarlos individualmente.
Optimizaciones de ciclos
En prácticamente cualquier libro/publicación sobre optimización de código se habla del principio de 90/10 que asegura que se utiliza el 90% del tiempo de ejecución de un programa en ejecutar el 10% del código del mismo. Esto es debido a los bucles y la reutilización de código, por ende, la optimización de código dentro de los bucles suele dar resultados muy convenientes teniendo en cuenta la poca cantidad de código que se optimiza.
Existen muchas técnicas de optimización de bucles que se explicaran más adelante.
Optimizaciones peephole
Las optimizaciones peephole son transformaciones simples que dan un beneficio suficiente como para ser implementadas en cualquier compilador. Básicamente, examina el código assembler por secuencias pequeñas y las reemplaza por secuencias más corta y que ejecuten más rápido si es posible.
Optimización del código máquina
Este tipo de optimización analiza la imagen ejecutable de la tarea del programa después de que todo el código máquina ejecutable ha sido enlazado. Algunas de las técnicas que se pueden aplicar tienen un alcance más limitado, tales como la compresión de macro (que ahorra espacio por el colapso de secuencias comunes de instrucciones), son más eficaces cuando la imagen ejecutable de la tarea completa está disponible para el análisis.
Factores que afectan a la optimización Hay varios factores externos que afectan al rendimiento de un software a tener en cuenta:
La propia máquina
Muchas de las decisiones acerca de qué optimizaciones pueden y deben hacerse dependen de las características de la máquina de destino. A veces es posible parametrizar algunos de estos factores dependientes de la máquina, de modo que una sola pieza de código del compilador se puede utilizar para optimizar diferentes máquinas simplemente mediante la alteración de los parámetros de la descripción de la máquina. GCC es un compilador que es un ejemplo de este enfoque.
La arquitectura de la CPU objetivo
El número de registros de CPU: Hasta cierto punto, cuanto más registros, más fácil es optimizar el rendimiento. Las variables locales pueden ser asignadas en los registros y no en la pila. Resultados temporales/intermedios se puede dejar en registros sin escribir y leer desde la memoria.
RISC vs. CISC
El conjunto de instrucciones CISC a menudo tienen longitud de instrucciones variables, tienen un mayor número de instrucciones posibles que se pueden utilizar, y cada instrucción podría tomar distintas cantidades de tiempo. El conjunto de instrucciones RISC intenta limitar la variabilidad de cada una de ellas: conjuntos de instrucciones son generalmente de longitud constante, con pocas excepciones, por lo general hay menos combinaciones de los registros y en las operaciones de memoria, además la tasa de emisión de instrucciones (el número de instrucciones completadas por período de tiempo, normalmente un múltiplo entero del ciclo de reloj) es generalmente constante en los casos en que la latencia de memoria no es un factor. Puede haber varias formas de llevar a cabo una tarea determinada, con CISC suelen ofrecer más alternativas que RISC. Los compiladores tienen que conocer los costos relativos entre las diversas instrucciones y elegir la mejor secuencia de instrucciones (ver selección de instrucción).
Número de unidades funcionales
Algunas CPUs tienen varias ALU y FPU. Esto les permite ejecutar múltiples instrucciones simultáneamente. Puede haber restricciones en la cual las instrucciones se pueden emparejar con los que otras instrucciones ("emparejamiento" es la ejecución simultánea de dos o más instrucciones), y sobre que unidad funcional puede ejecutar que instrucción. También tienen problemas similares a los conflictos de los pipelines. De forma similar, las instrucciones deben ser programadas de modo que las diversas unidades funcionales están completamente alimentadas con las instrucciones a ejecutar.
Pipeline
Un pipeline es esencialmente una CPU dividida en una línea de montaje. Permite el uso de piezas de la CPU para diferentes instrucciones mediante la ruptura de la ejecución de instrucciones en varias etapas: decodificación de instrucciones, decodificación de direcciones, fetch de memoria, fetch de registro, calcular, guardar registros, etc. Una instrucción podría estar en la etapa de almacenar en registros, mientras que otra podría estar en la etapa de fetching. Los conflictos de pipeline se producen cuando una instrucción en una etapa del pipeline depende del resultado de otra instrucción por delante de él en el pipeline, pero todavía no ha finalizado. Los conflictos pueden llevar a paradas del pipeline: donde la CPU consume ciclos de espera para resolver un conflicto. Los compiladores pueden programar o reordenar, las instrucciones para que las paradas del pipeline se produzcan con menos frecuencia.
La arquitectura de la máquina
Tamaño y tipo de caché
Técnicas tales como expansión en línea y desenrollamiento de bucle pueden aumentar el tamaño del código generado y reducir la localidad código. El programa puede disminuir drásticamente si una sección muy utilizada de código (como los bucles internos en varios algoritmos) de repente no puede entrar en la memoria caché. Además, las memorias caché que no son totalmente asociativas tienen mayores probabilidades de colisiones caché incluso en una memoria caché de vacantes.
Velocidad de transferencia de la caché/memoria