Compilador optimizador
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.[1] 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.[2]
Generalmente hay varios aspectos que se desean optimizar:[3]
- Optimización temporal: Reducir el tiempo de ejecucion 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).
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.[4] 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.[5]
Se ha demostrado que algunos problemas de optimización de código son NP-completo, o incluso indecidibles.[6][7] 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.[8]
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.[9]
Etapas de un compilador optimizador
Un compilador optimizador tipo consta de tres fases cuando realiza el proceso de optimización:[10]
- 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ásico[11] (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[12]) 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.[13]
Hay varios tipos de optimizaciones locales entre los que se encuentran principalmente:[14]
- 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.[15] 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.[16]
Por último las interprocedurales son las que analizan comportamiento entre procedimientos llegando a analizar el código completo.[17] 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.[18]
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.[19]
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).[20]
Otras optimizaciones
Algunos tipos de optimizaciones son muy comunes debido a sus características y es important 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.[21] 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.[22]
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.[23] 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.[24]
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.[25]
Factores que afectan a la optimización
Hay varios factores externos que afectan al rendimiento de un software a tener en cuenta:[26]
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.[27]
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).[28]
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.[29]
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.[30]
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 utilizado 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.[31]
Velocidad de transferencia de la caché/memoria
Estos datos dan al compilador una indicación de la penalidad por fallos de caché. Esto se usa principalmente en aplicaciones especializadas.
Uso previsto del código generado
Depuración
Mientras se escribe una aplicación, un programador volverá a compilar y poner a prueba muchas veces, por eso la compilación debe ser rápida. Esta es una razón por la cual la mayoría de las optimizaciones se evita deliberadamente durante la fases de prueba/depuración. Además, el código del programa suele intercalare (ver animación de programa), utilizando un depurador simbólico, y las transformaciones de optimización, a menudo reordena el código. Esto puede hacer que sea difícil relacionar el código de salida con los números de línea en el código fuente original y puede confundir tanto a las herramientas de depuración como a los programadores que las utilizan.
Uso de propósitos generales
El software empaquetado, muy a menudo se espera para ser ejecutado en una variedad de máquinas y CPUs que pueden compartir el mismo conjunto de instrucciones, pero tienen diferentes tiempos de caché, o características de memoria. Así, el código no puede ser sintonizado a cualquier CPU particular, o puede ser sintonizado a trabajar mejor en la CPU más popular y aún así funciona aceptablemente bien en otras CPU.
Uso de propósitos especiales
Si el software es compilado para ser utilizado en una o unas pocas máquinas muy similares, con características conocidas, el compilador puede optimizar en gran medida el código generado para esas máquinas específicas (si estas opciones están disponibles). Importantes casos especiales incluyen un código diseñado para los procesadores vectoriales y paralelo, para lo cual compiladores especiales de paralelización son empleados.
Sistemas embebidos
Estos son un caso común de propósito especial de uso. El software embebido puede estar bien sintonizado en una CPU exacta y el tamaño de la memoria. Además, el coste del sistema o la fiabilidad puede ser más importante que la velocidad del código. Así, por ejemplo, los compiladores de software embebido suelen ofrecer opciones que reducen el tamaño del código a expensas de la velocidad, porque la memoria es el costo principal de un sistema embebido. El código de sincronización puede necesitar ser predecible, en lugar de tan rápido como sea posible, el almacenamiento en caché del código puede ser desactivado, junto con las optimizaciones del compilador que lo requieran.
Temas comunes
En gran medida, las técnicas de optimización del compilador tienen los siguientes temas, que a veces en conflicto.
Optimizar el caso más común
El caso común puede tener propiedades únicas que permiten un camino rápido a expensas de un camino lento. Si el camino rápido se toma más a menudo, el resultado es un mejor rendimiento general.
Evitar redundancias
Reutilizar los resultados que ya están calculados y almacenarlos para su uso posterior, en vez de recalcular ellos aumenta significativamente el rendimiento general.
Menos código
Eliminar cálculos innecesarios y los valores intermedios. Menos trabajo para la CPU, la memoria caché y la memoria por lo general resulta en una ejecución más rápida. Por otra parte, en los sistemas embebidos, menos código trae un costo de producto más bajo.
Menos saltos mediante el uso de código de línea recta
Menos código complicado. Los saltos (condicionales o incondicionales) interfieren con fetching previo de instrucciones, lo que ralentiza el código.[32] El uso de expansión en línea o desenrrollamiento de bucle puede reducir de ramificación, a costa de aumentar el tamaño del archivo binario por la longitud del código repetido. Esto tiende a combinar varios elementos básicos en uno solo.
Localidad
El código y datos que son accesibles estrechamente juntos en el tiempo deben ser colocados cerca en la memoria para aumentar la cercanía de referencias.
Utilizar la jerarquía de memoria
Los accesos a memoria son cada vez más caro para cada nivel de la jerarquía de memoria, por lo que se debe colocar los elementos más utilizados en los primeros registros, luego los cachés de memoria principal y, a continuación, antes de entrar en el disco.[33]
Paralelismo
Reordenar las operaciones para permitir que múltiples cálculos se produzcan en paralelo, ya sea en la instrucción, la memoria, o a nivel de hilo.
Uso de información más precisa
Cuanto más precisa sea la información que el compilador tiene, mejor se puede emplear cualquiera o todas estas técnicas de optimización.
Métricas
La información recopilada durante una ejecución de prueba se puede utilizar en una optimización guiada por perfiles. La información obtenida en tiempo de ejecución (a ser posible con un mínimo de overhead) se puede utilizar por un compilador JIT para mejorar la optimización dinámica.
Reducción de potencias
Reducir las operaciones complejas, difíciles o costosos con otras más simples. Por ejemplo, reemplazar la división por una constante con la multiplicación por su recíproco, o realizar un análisis de variables inductivas para sustituir a la multiplicación por un índice de bucle con adición.
Técnicas específicas
Optimización de bucles
Se pueden realizar muchas optimizaciones en los bucles.[34] No todas se pueden llevar a cabo a la vez.
Análisis de variables inductivas
En términos generales, si una variable en un bucle es una función lineal simple de la variable de índice, tal como j:= 4 * i + 1, puede ser actualizado adecuadamente cada vez que la variable de bucle se cambia. Esto es reducción de potencia, y también puede permitir que las definiciones de la variable de índice se convierta en código muerto. Esta información también es útil para la eliminación de los límites de comprobación y el análisis de la dependencia, entre otras cosas.[35][36]
Fisión de bucle
Fisión de bucle es una técnica de optimización del compilador que intenta romper un bucle en múltiples bucles en el rango del mismo índice pero cada uno teniendo sólo una parte del cuerpo del bucle original. El objetivo es derribar el cuerpo del bucle grande en otros más pequeños para lograr una mejor localidad de datos. Es la acción inversa a la fusión de bucle.[37]
Fusión de bucle
Fusión de bucle es una técnica para la optimización del compilador y transformación de bucles, que sustituye a múltiples bucles con uno sola. Es la acción inversa a la fisión bucle.[38]
Inversión de bucles
Inversión de bucles es una técnica en la optimización del compilador, sobre todo en la transformación de bucles. Esta técnica cambia un bucle while estándar, en un do/while con un if condicional, reduciendo el número de saltos entre los dos, para los casos en que se ejecuta el bucle. Si lo hace, duplica la comprobación de la condición (aumentando el tamaño del código), pero es más eficiente porque los saltos suelen causar paradas del pipeline. Además, si la condición inicial es conocida en tiempo de compilación y se sabe que es libre de efectos secundarios, el if protector puede ser omitido.[39]
Intercambio de bucle
Intercambio de bucle, una técnica de optimización del compilador, es el proceso de intercambio del orden de dos variables de iteración. Uno de los propósitos principales de intercambio de bucle es mejorar el rendimiento de la caché para el acceso a elementos de un array. Los fallos de caché ocurren si los elementos accedidos de de un array contiguo dentro del bucle provienen de una línea de caché diferente. Intercambio de bucle puede ayudar a prevenir esto. La eficacia del intercambio de bucle depende y debe ser considerado teniendo en cuenta el modelo de caché utilizado por el hardware subyacente y el modelo de arrays utilizado por el compilador.[40]
Loop-invariant code motion
Si una cantidad se calcula dentro de un bucle en cada iteración, y su valor es el mismo para cada iteración, se puede mejorar enormemente la eficiencia llevándola fuera del bucle y calcular su valor sólo una vez antes de que el bucle comience. Esto es particularmente importante con las expresiones de cálculo de direcciones generadas por bucles sobre arrays. Para la aplicación correcta, esta técnica debe ser utilizado con la técnica inversión de bucles, porque no todo el código es seguro para ser colocado fuera del bucle.[41]
Optimización nido de bucle
Algunos algoritmos generalizados, como la multiplicación de arrays tienen un comportamiento muy pobre en cache y accesos excesivos de memoria. La optimización nido de bucle aumenta el número de coincidencias de memoria caché mediante la realización de la operación a través de pequeños bloques y mediante el uso de un bucle intercambio (por eso el nombre de nido).[42]
Reversión de bucle
Reversión de bucle invierte el orden en el que se asignan valores a la variable del índice. Esta es una optimización sutil que puede ayudar a eliminar dependencias, permitiendo así otras optimizaciones.[43]
Desenrollamiento de bucle
Desenrollamiento de bucle, es una técnica para optimizar partes de los programas de ordenador. La idea es ahorrar tiempo al reducir el número de instrucciones generales que el equipo tiene que ejecutar en un bucle, y así mejorar la tasa de aciertos de caché y reducir la ramificación. Para lograr esto, las instrucciones que se llaman en múltiples iteraciones del bucle se combinan en una sola iteración. Esto acelerará el programa si las instrucciones generales del bucle perjudican el rendimiento de forma significativa.[44]
División de bucle
División de bucle, también conocido como loop peeling, es una técnica de optimización del compilador. Se trata de simplificar un bucle o eliminar dependencias dividiéndola en múltiples lazos que tienen los mismos cuerpos pero iteran sobre diferentes partes contiguas del rango del índice.[45]
Loop unswitching
Loop unswitching es una técnica de optimización del compilador. Se mueve un condicional dentro de un bucle a fuera del mismo mediante la duplicación del cuerpo del bucle, y colocando una versión del mismo en el interior de cada una de las cláusulas if y else. Esto puede mejorar la paralelización del bucle. Dado que los procesadores modernos pueden operar rápido en vectores esto aumenta la velocidad.[46]
Fragmentado de bucle
Fragmentado de bucle, también conocido como loop tiling, es una optimización de bucles utilizada por los compiladores para que la ejecución de ciertos tipos de bucles sea más eficiente. La idea es particionar el espacio de un bucle de iteración en trozos más pequeños o bloques, a fin de ayudar a asegurar que los datos utilizados en un bucle permanece en la caché hasta que se vuelve a utilizar. La división de espacio de un bucle de iteración conduce a la partición de gran variedad en bloques más pequeños, así se pueden cargar pequeños trozos de un array en la cache, rehusar elementos de la misma y se eliminan los requerimientos de tamaño de esta.[47]
Software pipelining
El bucle se reestructura de tal manera que el trabajo realizado en una iteración se divide en varias partes y hecho en varias iteraciones. En un bucle estrecho esta técnica oculta la latencia entre la carga y el uso de valores.
Paralelización automática
Un bucle se convierte en código multi-hilo o vectorizado (o incluso los dos) con el fin de utilizar varios procesadores simultáneamente en una memoria compartida de multiprocesador (SMP) de la máquina, incluyendo núcleos en múltiples máquinas.
Optimización del flujo de datos
Las optimizaciones del flujo de datos, basadas en el análisis de flujo de datos, dependen principalmente de cómo ciertas propiedades de los datos se propagan por las aristas del grafo de control del flujo. Algunos de estos incluyen:
Eliminación de la subexpresión común
Eliminar operaciones que son redundantes en sub-expresiones logra una reducción de código. Así, muchas de las veces a una variable se le asigna un valor y se reutiliza varias veces, ya que dicha variable es común en otras operaciones. Pro ejemplo: X=A*SIN(Y)+(SIN(Y)**2), realmente puede ser vista como: t=SIN(Y); X=A*t+(t**2).[48]
Plegamiento de constantes
De las técnicas de optimización la más trivial es la que se refiere a la compactación del código, es decir que algunas expresiones pueden ser simplificadas mediante la evaluación del compilador como puede ser "8+3+C+d", en la declaración el compilador la dejará como "11+C+d", claramente se observa que el compilador reemplaza los números 8 y 3 por su resultante, por supuesto se aplica casi para cualquier tipo de operación.[49]
Propagación de constantes
Similar el plegamiento ésta constante se sustituye y es reescrita de una forma implícita. Así por ejemplo, cuando hacemos la evaluación de: c = 4; valor = c/2 éste puede ser mejor usado como valor = 4/2, y éste a su vez ser plegado como se mencionó anteriormente.[50]
Reconocimiento y eliminación de variables inductivas
Ver el apartado de análisis de variable de inducción más arriba.
Análisis de punteros y clasificación de alias
En presencia de punteros, es difícil hacer alguna optimización en absoluto, ya que potencialmente cualquier variable se ha de cambiar cuando una ubicación de memoria se la asigna. Mediante la especificación de que punteros pueden tener un alias a una variables, punteros no relacionados pueden ser ignorados.[51]
Eliminación de almacenamiento muerto
Eliminar las asignaciones a variables que no son posteriormente leídas, ya sea por la vida útil de la variable o debido a que se sobrescribirá el primer valor antes de ser usado.
Optimizaciones basadas en SSA
Estas optimizaciones se pretende hacer después de transformar el programa en una static single assignment form, en el que se asigna cada variable en un solo lugar. Aunque alguna función sin SSA, son más eficaces que con SSA. Muchas optimizaciones que figuran en otras secciones también se benefician sin cambios especiales, tales como asignación de registros.
Valor de numeración global
El valor de numeración global elimina la redundancia mediante la construcción de un gráfico de valores del programa y, a continuación determinar qué valores se calculan con expresiones equivalentes. El valor de numeración global es capaz de identificar alguna redundancia que la eliminación de subexpresiones comunes no puede, y viceversa.[52]
Propagación de constantes condicional escasa
Efectivamente equivalente a la realización iterativa de propagación de constantes, el plegamiento constante, y la eliminación de código muerto, pero es mucho más eficiente. Esta optimización simbólicamente ejecuta el programa, al mismo tiempo la propagación de valores constantes y elimina partes del grafo de control de flujo que son inalcanzables.[53][54]
Optimización del código generado
Asignación de registros
El buen uso de los registros es la característica más importante de un código eficiente.Las instrucciones que involucran registros son más rápidasque las que involucran operandos en memoria. Se utiliza la información recolectada en análisis de variables vivas Y se usan técnicas de coloreo de grafos para saber que variable asignar a cada registro.[55]
Selección de instrucciones
La mayoría de las arquitecturas, y en particular las CISC tienen muchos modos de direccionamiento, ofrecen varias formas de llevar a cabo una operación en particular y el uso de secuencias completamente diferentes de instrucciones. La naturaleza del conjunto de instrucciones de la máquina objeto determina la dificultad de la selección de instrucciones. Es importante que el conjunto de instrucciones sea uniforme y completo. Si la máquina objeto no apoya cada tipo de datos de una manera uniforme, entonces cada excepción a la regla general exige un tratamiento especial. Las velocidades de las instrucciones y las expresiones particulares de la máquina son otros factores importantes. Para cada tipo de proposición de tres direcciones, se puede diseñar un esqueleto de código que perfila el código objeto que ha de generarse para esa construcción.[56]
Planificación de instrucciones
La planificación de instrucciones es una optimización importante para los procesadores modernos segmentados, lo que evita paradas o burbujas en el pipeline por instrucciones de agrupamiento sin dependencias juntas, teniendo cuidado de preservar la semántica original.[57][58]
Rematerialización
La rematerialización vuelve a calcular un valor en lugar de utilizar un acceso a memoria. Esto se realiza en conjunto con la asignación de registros para evitar derrames.[59][60]
Factorización de código
Si varias secuencias de código son idénticos, o se puede parametrizar o reordenado para ser idénticas, pueden ser reemplazados con llamadas a una subrutina compartida. Esto a menudo puede compartir código para subrutinas de configuración y algunas veces de cola de recursión.[61]
Trampolines
Muchas CPUs tienen pequelas subrutinas de llamadas a instrucciones para acceder a niveles bajos de memoria. Un compilador puede ahorrar espacio mediante el uso de estas llamadas pequeñas en el cuerpo principal del código. Cambiar instrucciones en la memoria baja puede acceder a las rutinas en cualquier dirección. Esto multiplica el ahorro de espacio de la factorización de código.[62]
Reordenamiento de cálculos
Basado en la Programación de enteros, los compiladores de reestructuración mejoran la localidad de datos y exponen más paralelismo con cálculos reordenados. Optimizando el espacio los compiladores pueden reordenar el código para alargar las secuencias que pueden ser un factor en subrutinas.[63]
Otras optimizaciones
Reducción de potencias
Se busca sustituir operaciones costosas por otras más simples. Por ejemplo: sustituir productos por sumas, evitar la operación append, sustituir productos entre variables inductivas e invariantes de bucle por sumas.[64]
Eliminación de los límites de comprobación
Muchas lenguas, por ejemplo Java, hace cumplir los límites de comprobación de todos los accesos a un array. Esto es un grave cuello de botella en ciertas aplicaciones tales como código científico. La eliminación de los límites de comprobación permite al compilador quitar con seguridad la comprobación de límites en muchas situaciones donde se puede determinar que el índice debe estar dentro de los límites válidos, por ejemplo, si se trata de una variable de bucle simple.[65]
Optimización del desplazamiento de salto
Elije el desplazamiento de la rama más corta que llega a destino.[66]
Reordenamiento de bloques de código
El reordenamiento de bloques de código altera el orden de los bloques básicos en un programa con el fin de reducir los saltos condicionales y mejorar la cercanía de referencias.[67]
Eliminación de código muerto
La eliminación de código muerto incluye quitar del código fuente cualquier tipo de código muerto, código inalcanzable y código redundante.[68]
Expansión en línea o Expansión de macro
La expansión en línea es una técnica de optimización del compilador que reduce la sobrecarga de una llamada a una función, simplemente no haciendo la llamada, por el contrario, el compilador reescribe eficazmente la función en el programa como si la definición de la función llamada se insertó en cada sitio que fue invocada.[69]
Jump threading
En este paso, consecutivos saltos condicionales predecidos total o parcialmente en la misma condición se fusionan.[70] Por ejemplo:
if (c) { foo; } if (c) { bar;}
if (c) { foo; bar;}
orale wey
if (c) { foo; } if (!c) { bar;}
if (c) { foo; } else { bar;}
Compresión de macros
Una optimización de espacio que reconoce secuencias comunes de código, crea subprogramas ("macros de código") que contienen el código común, y reemplaza las ocurrencias de las secuencias de códigos comunes con las llamadas a los subprogramas correspondientes.[71] Esto se realiza más eficazmente como una optimización del código máquina, cuando todo el código está presente. La técnica fue utilizada por primera vez para ahorrar espacio en un flujo de bytes interpretativo utilizado en una implementación de Macro Spitbol en microcomputadoras.[72] El problema de determinar un conjunto óptimo de macros que minimiza el espacio requerido por un segmento de código dado se sabe que es NP-completo,[73] pero las heurísticas eficientes alcanzan casi resultados óptimos.[74]
Reducción de la altura de la pila
Reorganizar árbol de expresión para minimizar los recursos necesarios para la evaluación de la expresión.[75]
Test reordering
Si tenemos dos pruebas que son la condición para algo, lo primero que se hace son las pruebas más simples y sólo después las pruebas complejas. Esta técnica complementa la evaluación perezosa pero sólo se pueden utilizar cuando las pruebas no son dependientes uno del otro.
Problemas con la optimización
Temprano en la historia de los compiladores, las optimizaciones del compilador no eran tan buenos como las escritos a mano. Dado que las tecnologías han mejorado, los compiladores buenos a menudo puede generar un mejor código que los programadores humanos y una buena optimización del código objeto puede mejorar el código altamente optimizado a mano aún más. Para arquitecturas de CPU RISC, y más aún para el hardware de VLIW, un compilador optimizador es clave para obtener un código eficiente, porque los conjuntos de instrucciones RISC son tan compactos que es difícil para un ser humano programar manualmente o combinar pequeñas instrucciones para obtener resultados eficientes. En efecto, estas arquitecturas fueron diseñados para apoyarse en los programadores de compiladores para un rendimiento adecuado.
Sin embargo, los compiladores optimizadores no son de ninguna manera perfectos.[76] No hay manera de que un compilador puede garantizar que, para todo código fuente de un programa, se genera la salida equivalente más rápida o más pequeña; tal compilador es imposible, ya que resolvería el problema de la parada.
Esto puede ser demostrado mediante la consideración de una llamada a una función, foo(). Esta función devuelve nada y no tiene efectos secundarios (no E/S, no modifica las variables globales ni estructuras de datos, etc.) El programa equivalente más rápido posible sería simplemente eliminar la llamada a la función. Sin embargo, si la función foo() en realidad no regresa, entonces el programa con la llamada a foo() sería diferente del programa sin la llamada, el compilador de optimización tendrá entonces que determinar esto resolviendo el problema de la parada.
Además, hay un número de otras cuestiones prácticas con la tecnología de un compilador optimizador:
- La optimización de los compiladores se centran en la mejoras de desempeño relativamente poco profundas y no suelen mejorar la complejidad algorítmica de una solución. Por ejemplo, un compilador no va a cambiar una aplicación de tipo burbuja a un quicksort para mejorar el rendimiento.
- Los compiladores suelen tener que soportar una variedad de objetivos en conflicto, como el coste de la velocidad de compilación ejecución y calidad del código generado.
- Un compilador típicamente sólo se ocupa de una parte de un programa a la vez, a menudo el código contenido dentro de un único archivo o módulo, el resultado es que no puede tener en cuenta información contextual que sólo se puede conseguir mediante el procesamiento de los otros archivos.
- La sobrecarga de optimización del compilador: Cualquier trabajo adicional requiere tiempo, todo el programa de optimización es mucho tiempo para programas grandes.
- La interacción a menudo compleja entre las fases de optimización hace que sea difícil encontrar una secuencia óptima en la que ejecutar las diferentes fases de optimización.
Véase también
Referencias
- ↑ José M. Maria Carrasco. «La optimización: una mejora en la optimización de programas». Consultado el 15 de enero de 2013.
- ↑ Cooper, Keith D., and Torczon, Linda, Engineering a Compiler, Morgan Kaufmann, 2004, ISBN 1-55860-699-8
- ↑ «Optimización de compiladores». Consultado el 15 de enero de 2013.
- ↑ «Optimización de código». Consultado el 15 de enero de 2013.
- ↑ «Optimización de compiladores». Consultado el 15 de enero de 2013.
- ↑ Maggie Johnson (4 de agosto de 2008). «Code Optimization» (en inglés). Consultado el 15 de enero de 2013.
- ↑ «Compilador optimizador». Consultado el 15 de enero de 2013.
- ↑ Maggie Johnson (4 de agosto de 2008). «Code Optimization» (en inglés). Consultado el 15 de enero de 2013.
- ↑ Maggie Johnson (4 de agosto de 2008). «Code Optimization» (en inglés). Consultado el 15 de enero de 2013.
- ↑ «Compilador optimizador». Consultado el 15 de enero de 2013.
- ↑ Cooper, Keith D., and Torczon, Linda, Engineering a Compiler, Morgan Kaufmann, 2004, ISBN 1-55860-699-8 page 404
- ↑ «Optimización de código». Consultado el 15 de enero de 2013.
- ↑ IBM. «Optimizaciones locales». Consultado el 15 de enero de 2013.
- ↑ «Compiladores, optimización». Consultado el 15 de enero de 2013.
- ↑ Cooper, Keith D., and Torczon, Linda, Engineering a Compiler, Morgan Kaufmann, 2004, ISBN 1-55860-699-8 page 407
- ↑ IBM. «Global optimizations» (en inglés). Consultado el 15 de enero de 2013.
- ↑ Universidad de Virginia (8 de abril de 2008). «Interprocedural Optimizations» (en inglés). Consultado el 15 de enero de 2013.
- ↑ Michael Burke y Linda Torczon. «Interprocedural Optimization: Eliminating Unnecessary Recompilation» (en inglés). Consultado el 15 de enero de 2013.
- ↑ «OPTIMIZACIÓN DE CÓDIGO». Consultado el 15 de enero de 2013.
- ↑ Peter Fritzson, Christoph Kessler (2011). [Vector (informática) «Code optimization»]
|url=incorrecta (ayuda) (en inglés). Consultado el 15 de enero de 2013. - ↑ «Optimizing your programs» (en inglés). Consultado el 15 de enero de 2013.
- ↑ «Optimizacion de compiladores». Consultado el 15 de enero de 2013.
- ↑ «Optimizing compilers» (en inglés). Consultado el 15 de enero de 2013.
- ↑ «Optimizing compilers» (en inglés). Consultado el 15 de enero de 2013.
- ↑ Clinton F. Goss (junio de 1986). Machine Code Optimization - Improving Executable Object Code. New York University. Consultado el 24-Mar-2011.
- ↑ Chattopadhiay, Santanu (2005). Compiler Desing. New Delhi: Prentice Hall. p. 225. ISBN 81-203-2726-X
|isbn=incorrecto (ayuda). - ↑ Free Software Foundation. «Options That Control Optimization» (en inglés). Consultado el 16 de enero de 2013.
- ↑ Farhat Masood. «RISC AND CISC Computer Architecture» (en inglés). Consultado el 16 de enero de 2013.
- ↑ «Superescalar processors» (en inglés). Consultado el 16 de enero de 2013.
- ↑ «CPU segmentada (pipeline)». Consultado el 16 de enero de 2013.
- ↑ «Introduction of Cache Memory» (en inglés). Consultado el 16 de enero de 2013.
- ↑ «Pipeline». Consultado el 16 de enero de 2013.
- ↑ «Jerarquía de memorias». Marzo de 2011. Consultado el 16 de enero de 2013.
- ↑ Utpal Barnerjee. «Loop paralelization» (en inglés). Consultado el 16 de enero de 2013.
- ↑ «Induction variables» (en inglés). Consultado el 16 de enero de 2013.
- ↑ Sébastian Pop. «Analysis of induction variables using chains of recurrences: extensions» (en francés). Consultado el 16 de enero de 2013.
- ↑ «Loop Fission» (en inglés). Consultado el 16 de enero de 2013.
- ↑ «Loop Fusion» (en inglés). Consultado el 16 de enero de 2013.
- ↑ «Loop Inversion» (en inglés). Consultado el 16 de enero de 2013.
- ↑ «Loop Interchange» (en inglés). Consultado el 16 de enero de 2013.
- ↑ «Loop-Invariant Code Motion» (en inglés). Consultado el 16 de enero de 2013.
- ↑ «Using Loop Nest Optimization» (en inglés). Consultado el 16 de enero de 2013.
- ↑ «Transfomation loop» (en inglés). Consultado el 16 de enero de 2013.
- ↑ «Loop Unwinding» (en inglés). Consultado el 16 de enero de 2013.
- ↑ «Loop Splitting» (en inglés). Consultado el 16 de enero de 2013.
- ↑ «Loop Unswitching» (en inglés). Consultado el 16 de enero de 2013.
- ↑ «Loop Tiling» (en inglés). Consultado el 16 de enero de 2013.
- ↑ «FUNDAMENTOS DE OPTIMIZACIÓN». Consultado el 16 de enero de 2013.
- ↑ «FUNDAMENTOS DE OPTIMIZACIÓN». Consultado el 16 de enero de 2013.
- ↑ «FUNDAMENTOS DE OPTIMIZACIÓN». Consultado el 16 de enero de 2013.
- ↑ Mike Acton (1 de junio de 2006). «Understanding Strict Aliasing» (en inglés). Consultado el 16 de enero de 2013.
- ↑ Alpern, Bowen, Wegman, Mark N., and Zadeck, F. Kenneth (enero de 1988). "Detecting Equality of Variables in Programs". San Diego, CA, USA: Conference Record of the Fifteenth Annual ACM Symposium on Principles of Programming Languages (POPL), ACM Press. pp. 1-11.
- ↑ Wegman, Mark N. and Zadeck, F. Kenneth. "Constant Propagation with Conditional Branches." ACM Transactions on Programming Languages and Systems, 13(2), April 1991, pages 181-210.
- ↑ Click, Clifford and Cooper, Keith. "Combining Analyses, Combining Optimizations", ACM Transactions on Programming Languages and Systems, 17(2), March 1995, pages 181-196
- ↑ «Code optimization» (en inglés). Consultado el 16 de enero de 2013.
- ↑ «COMPILADORES». Consultado el 16 de enero de 2013.
- ↑ Peter Lee (2009). «Introduction to Instruction Scheduling» (en inglés). Consultado el 16 de enero de 2013.
- ↑ «Instruction Scheduling» (en inglés). Consultado el 16 de enero de 2013.
- ↑ P. Briggs, K. D. Cooper, and L. Torczon. (julio de 1992). Proceedings of the SIGPLAN 92 Conference on Programming Language Design and Implementation. SIGPLAN Notices 27(7). pp. 311-321.
- ↑ Mukta Punjani. «Register Rematerialization In GCC». Consultado el 16 de enero de 2013.
- ↑ Cx51 Compiler Manual, version 09.2001, p155, Keil Software Inc.
- ↑ Cx51 Compiler Manual, version 09.2001, p155, Keil Software Inc.
- ↑ Adams, L. (1986), Reordering computations for parallel execution. Commun. appl. numer. methods, 2: 263–271. doi: 10.1002/cnm.1630020307
- ↑ «Optimización de código». Consultado el 16 de enero de 2013.
- ↑ Xan Gregg (22 de enero de 2006). «Range Check Elimination Optimization» (en inglés). Consultado el 16 de enero de 2013.
- ↑ Yu Chen, Fuxin Zhang (Junio de 2007). Code reordering on limited branch offset. NY, USA: ACM Transactions on Architecture and Code Optimization (TACO). ISBN [[Special:BookSources/doi>10.1145/1250727.1250730|doi>10.1145/1250727.1250730]]
|isbn=incorrecto (ayuda). - ↑ Free software fundation (5 de mayo de 2000). «Basic Block Reordering» (en inglés). Consultado el 16 de enero de 2013.
- ↑ «Code Optimizations: Partial Dead Code Elimination» (en inglés). 13 de abril de 2009. Consultado el 16 de enero de 2013.
- ↑ «Inline Expansion» (en inglés). Consultado el 16 de enero de 2013.
- ↑ «Options That Control Optimization» (en inglés). Consultado el 16 de enero de 2013.
- ↑ Clinton F. Goss (June de 1986). «Machine Code Optimization - Improving Executable Object Code». New York University. Consultado el 24-Mar-2011.
- ↑ Robert B. K. Dewar; Martin Charles Golumbic; Clinton F. Goss (October de 1979). MICRO SPITBOL. Computer Science Department Technical Report. No. 11. Courant Institute of Mathematical Sciences.
- ↑ Clinton F. Goss (June de 1986). «Machine Code Optimization - Improving Executable Object Code». New York University. Consultado el 24-Mar-2011.
- ↑ Martin Charles Golumbic; Robert B. K. Dewar; Clinton F. Goss (1980). «Macro Substitutions in MICRO SPITBOL - a Combinatorial Analysis». Proc. 11th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, Utilitas Math., Winnipeg, Canada 29: 485-495.
- ↑ «Advanced Computer Architecture» (en inglés). Consultado el 16 de enero de 2013.
- ↑ Kent Wilken. «Advanced Compiler Optimization» (en inglés). Consultado el 16 de enero de 2013.
Bibliografía
- A. Aho, R. Sethi, J.D. Ullman, Compilers: Principles, Techniques, and Tools, Reading, MA: Addison-Wesley, 1986.
- J.P. Bennett, Introduction to Compiling Techniques. Berkshire, England: McGraw-Hill, 1990.
- R. Mak, Writing Compilers and Interpreters. New York, NY: Wiley, 1991.
- S. Muchnick, Advanced Compiler Design and Implementation . San Francisco, CA: Morgan Kaufmann, 1997.
- A. Pyster, Compiler Design and Construction. Reinhold, 1988.