Optimización del compilador

En informática, un compilador optimizador es un compilador que intenta minimizar o maximizar algunos atributos de un programa informático ejecutable. Los requisitos comunes son minimizar el tiempo de ejecución de un programa, el espacio de memoria, el tamaño de almacenamiento y el consumo de energía (los últimos tres son populares para las computadoras portátiles).

La optimización del compilador generalmente se implementa usando una secuencia de transformaciones de optimización, algoritmos que toman un programa y lo transforman para producir un programa de salida semánticamente equivalente que usa menos recursos o se ejecuta más rápido. Se ha demostrado que algunos problemas de optimización de código son NP-completos, o incluso indecidibles. En la práctica, factores como la voluntad del programador de esperar a que el compilador complete su tarea imponen límites superiores a las optimizaciones que un compilador puede proporcionar. La optimización es generalmente un proceso muy intensivo en CPU y memoria. En el pasado, las limitaciones de la memoria de la computadora también eran un factor importante para limitar las optimizaciones que se podían realizar.

Debido a estos factores, la optimización rara vez produce resultados "óptimos" salida en cualquier sentido, y de hecho, una "optimización" puede impedir el rendimiento en algunos casos. Más bien, son métodos heurísticos para mejorar el uso de recursos en programas típicos.

Tipos de optimización

Las técnicas utilizadas en la optimización se pueden dividir entre varios ámbitos que pueden afectar cualquier cosa, desde una sola instrucción hasta el programa completo. En términos generales, las técnicas de alcance local son más fáciles de implementar que las globales, pero dan como resultado ganancias menores. Algunos ejemplos de alcances incluyen:

Optimizaciones de los agujeros

Estos se realizan generalmente tarde en el proceso de compilación después de que el código de máquina se ha generado. Esta forma de optimización examina algunas instrucciones adyacentes (como "mirando a través de un peephole" en el código) para ver si pueden ser reemplazadas por una sola instrucción o una secuencia más corta de instrucciones. Por ejemplo, una multiplicación de un valor por 2 podría ser ejecutada más eficientemente al cambiar el valor o añadiendo el valor a sí mismo (este ejemplo es también una instancia de reducción de la fuerza).

Optimizaciones locales

Estos sólo consideran la información local a un bloque básico. Puesto que los bloques básicos no tienen flujo de control, estas optimizaciones necesitan muy poco análisis, ahorro de tiempo y reducción de los requisitos de almacenamiento, pero esto también significa que no se conserva información a través de los saltos.

Optimizaciones mundiales

Estos también se llaman "métodos de procesamiento" y actúan en funciones enteras. Esto les da más información con la que trabajar, pero a menudo hace necesarios cálculos costosos. Las hipótesis de caso peor tienen que hacerse cuando se producen llamadas de función o se accede a variables globales porque hay poca información sobre ellas.

Optimizaciones de bucle

Esta ley sobre las declaraciones que constituyen un bucle, como un para bucle, por ejemplo movimiento de código invariante. Las optimizaciones de lazo pueden tener un impacto significativo porque muchos programas pasan un gran porcentaje de su tiempo dentro de los lazos.

Optimizaciones de la tienda Prescient

Esto permite que las operaciones de la tienda ocurran antes de lo que se permitiría en el contexto de hilos y cerraduras. El proceso necesita alguna manera de saber con anticipación qué valor se almacenará por la asignación que debería haber seguido. El propósito de esta relajación es permitir la optimización del compilador para realizar ciertos tipos de reorganización de códigos que preservan la semántica de programas debidamente sincronizados.

Optimización interprocedural, de programa completo o de tiempo de conexión

Estos analizan todo el código fuente de un programa. La mayor cantidad de información extraída significa que las optimizaciones pueden ser más eficaces en comparación con cuando sólo tienen acceso a la información local, es decir, dentro de una sola función. Este tipo de optimización también puede permitir la realización de nuevas técnicas. Por ejemplo, la función inlineante, donde una llamada a una función es reemplazada por una copia del cuerpo de función.

Optimizador de código de máquina y optimizador de código de objeto

Estos analizan la imagen de tarea ejecutable del programa después de que todo un código de máquina ejecutable haya sido vinculado. Algunas de las técnicas que se pueden aplicar en un alcance más limitado, como la compresión macro que ahorra espacio al colapsar secuencias comunes de instrucciones, son más eficaces cuando toda la imagen de tarea ejecutable está disponible para análisis.

Además de las optimizaciones de ámbito, existen otras dos categorías generales de optimización:

Programación de lenguaje-independiente vs. idioma-dependiente

La mayoría de los idiomas de alto nivel comparten construcciones de programación y abstracciones comunes: decisión (si, cambio, caso), bucle (para, mientras, repetir... hasta, hacer. mientras), y encapsulación (estructuras, objetos). Así se pueden utilizar técnicas de optimización similares a través de idiomas. Sin embargo, ciertas características de lenguaje hacen que algunos tipos de optimizaciones sean difíciles. Por ejemplo, la existencia de punteros en C y C++ hace difícil optimizar los accesos de array (ver análisis de alias). Sin embargo, idiomas como PL/I (que también soporta punteros) tienen disponibles sofisticados compiladores optimizadores para lograr un mejor rendimiento de varias otras maneras. Por el contrario, algunas características de lenguaje facilitan ciertas optimizaciones. Por ejemplo, en algunos idiomas no se permite que las funciones tengan efectos secundarios. Por lo tanto, si un programa hace varias llamadas a la misma función con los mismos argumentos, el compilador puede inferir inmediatamente que el resultado de la función debe ser calculado sólo una vez. En los idiomas en que se permite que las funciones tengan efectos secundarios, es posible adoptar otra estrategia. El optimizador puede determinar qué función no tiene efectos secundarios y restringir tales optimizaciones a funciones libres de efectos secundarios. Esta optimización sólo es posible cuando el optimizador tiene acceso a la función llamada.

Independiente de la máquina vs. dependiente de la máquina

Muchas optimizaciones que operan en conceptos de programación abstracta (ops, objetos, estructuras) son independientes de la máquina dirigida por el compilador, pero muchas de las optimizaciones más eficaces son aquellas que mejor explotan las características especiales de la plataforma de destino. Ejemplos son instrucciones que hacen varias cosas a la vez, como registro de decremento y rama si no cero.

La siguiente es una instancia de una optimización dependiente de la máquina local. Para establecer un registro en 0, la forma obvia es usar la constante '0' en una instrucción que establece un valor de registro en una constante. Una forma menos obvia es aplicar XOR a un registro consigo mismo. Depende del compilador saber qué variante de instrucción usar. En muchas máquinas RISC, ambas instrucciones serían igualmente apropiadas, ya que ambas tendrían la misma longitud y tomarían el mismo tiempo. En muchos otros microprocesadores como la familia Intel x86, resulta que la variante XOR es más corta y probablemente más rápida, ya que no habrá necesidad de decodificar un operando inmediato, ni usar el "registro de operando inmediato". Un problema potencial con esto es que XOR puede introducir una dependencia de datos en el valor anterior del registro, provocando un bloqueo de la canalización. Sin embargo, los procesadores a menudo tienen XOR de un registro consigo mismo como un caso especial que no provoca bloqueos.

Factores que afectan la optimización

La máquina misma

Muchas de las opciones sobre qué optimizaciones se pueden y deben hacer 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 compilador se puede utilizar para optimizar diferentes máquinas simplemente alterando los parámetros de descripción de la máquina. GCC de GNU Project y Clang de LLVM Compiler Infrastructure son ejemplos de optimización de compiladores que siguen este enfoque.

La arquitectura del objetivo CPU

Número de registros de CPU: En cierta medida, cuanto más registros, más fácil es optimizar el rendimiento. Las variables locales se pueden asignar en los registros y no en la pila. Los resultados temporales/intermedios se pueden dejar en registros sin escribir y leer de nuevo de la memoria.

• RISC vs CISC: Los conjuntos de instrucciones CISC a menudo tienen longitudes de instrucción variable, a menudo tienen un mayor número de posibles instrucciones que se pueden utilizar, y cada instrucción podría tomar diferentes cantidades de tiempo. Los conjuntos de instrucciones de RISC intentan limitar la variabilidad en cada uno de estos: los conjuntos de instrucciones son generalmente longitud constante, con pocas excepciones, generalmente hay menos combinaciones de registros y operaciones de memoria, y la tasa de emisión de instrucciones (el número de instrucciones completadas por período de tiempo, generalmente un número entero del ciclo del reloj) es generalmente constante en casos en que la la latencia de memoria no es un factor. Puede haber varias maneras de llevar a cabo una determinada tarea, ya que el CISC suele ofrecer más alternativas que el RISC. Los participantes deben conocer los costos relativos entre las diversas instrucciones y elegir la mejor secuencia de instrucciones (ver selección de instrucciones).
• Pipelines: Un oleoducto es esencialmente una CPU rota en una línea de montaje. Permite el uso de partes de la CPU para diferentes instrucciones rompiendo la ejecución de las instrucciones en varias etapas: decodificación de instrucciones, decodificación de direcciones, captura de memoria, captura de registro, computación, almacén de registro, etc. Una instrucción podría estar en la etapa de la tienda de registro, mientras que otra podría estar en la etapa de registro. Los conflictos de tuberías ocurren cuando una instrucción en una etapa del oleoducto depende del resultado de otra instrucción por delante en el oleoducto pero aún no terminada. Los conflictos de tuberías pueden llevar a puestos de oleoductos: donde la CPU desperdicia ciclos esperando que se resuelva un conflicto.

Los competidores pueden Calendario, o reordenar, instrucciones para que los puestos de tubería se produzcan con menos frecuencia.

• Número de unidades funcionales: Algunas CPU tienen varios ALUs y FPU. Esto les permite ejecutar múltiples instrucciones simultáneamente. Puede haber restricciones en las que las instrucciones pueden emparejarse con las cuales otras instrucciones ("pair" es la ejecución simultánea de dos o más instrucciones), y qué unidad funcional puede ejecutar qué instrucción. También tienen problemas similares a los conflictos de oleoductos.

Aquí nuevamente, las instrucciones deben ser programadas para que las diversas unidades funcionales estén completamente alimentadas con instrucciones para ejecutar.

La arquitectura de la máquina

• Tamaño de la caché (256 kiB–12 MiB) y tipo (mapeado directo, 2-/4-/8-/16-way asociativo, totalmente asociativo): Técnicas como la expansión en línea y el desrollo de bucle pueden aumentar el tamaño del código generado y reducir la localización de código. El programa puede disminuir drásticamente si una sección de código altamente utilizada (como bucles interiores en varios algoritmos) de repente no puede caber en la caché. Además, los caches que no son totalmente asociativos tienen mayores posibilidades de colisiones de caché incluso en un caché sin rellenar.
• Tasas de transferencia de caché y memoria: Estos dan al compilador una indicación de la penalidad para las faltas de caché. Esto se utiliza principalmente en aplicaciones especializadas.

Uso previsto del código generado

Debugging

Mientras escribe una aplicación, un programador se recompilará y probará a menudo, y por lo tanto la compilación debe ser rápida. Esta es una razón por la que la mayoría de las optimizaciones se evitan deliberadamente durante la fase de prueba/depuración. Además, el código del programa suele ser "pasado" (ver la animación del programa) utilizando un depurador simbólico y optimizando las transformaciones, en particular las que reordenan el código, pueden dificultar la relación del código de salida con los números de línea en el código fuente original. Esto puede confundir tanto las herramientas de depuración como los programadores que las utilizan.

Uso para fines generales

Prepackaged software es muy a menudo espera que se ejecute en una variedad de máquinas y CPU que pueden compartir el mismo conjunto de instrucciones, pero tienen diferentes características de tiempo, caché o memoria. Como resultado, el código no puede ser ajustado a ninguna CPU en particular, o puede ser sintonizado para trabajar mejor en la CPU más popular y sin embargo todavía trabajar aceptablemente bien en otras CPU.

Uso para fines especiales

Si el software se compila para ser utilizado en una o varias máquinas muy similares, con características conocidas, entonces el compilador puede sintonizar fuertemente el código generado a esas máquinas específicas, siempre que tales opciones estén disponibles. Importantes casos especiales incluyen código diseñado para procesadores paralelos y vectoriales, para los cuales se emplean compiladores paralelizantes especiales.

Sistemas integrados

Se trata de un caso común de uso especial. El software insertado puede ajustarse a una CPU exacta y el tamaño de la memoria. Además, el costo del sistema o la fiabilidad pueden ser más importantes que la velocidad del código. Por ejemplo, los compiladores de software integrado generalmente ofrecen opciones que reducen el tamaño del código a expensas de la velocidad, porque la memoria es el costo principal de un ordenador integrado. El tiempo del código puede necesitar ser predecible, en lugar de lo más rápido posible, por lo que el caché de código puede ser deshabilitado, junto con las optimizaciones del compilador que lo requieren.

Temas comunes

En gran medida, las técnicas de optimización del compilador tienen los siguientes temas, que a veces entran en conflicto.

Optimize the common case

El caso común puede tener propiedades únicas que permiten sendero rápido a expensas de un camino lento. Si el camino rápido se toma con más frecuencia, el resultado es un mejor rendimiento general.

Evite la redundancia

Reutilizar los resultados que ya están computados y almacenarlos para uso posterior, en lugar de recomputarlos.

Menos código

Eliminar cálculos innecesarios y valores intermedios. Menos trabajo para la CPU, caché y memoria generalmente resulta en una ejecución más rápida. Alternativamente, en sistemas integrados, menos código trae un menor costo de producto.

Menos saltos utilizando línea recta código, también llamado código libre de rama

Código menos complicado. Los saltos (las ramas condicionales o incondicionales) interfieren con el prefetching de instrucciones, disminuyendo así el código. El uso de la insignia o desbloqueo puede reducir la ramificación, a costa de aumentar el tamaño de archivo binario por la longitud del código repetido. Esto tiende a fusionar varios bloques básicos en uno.

Localidad

El código y los datos que se accedan de cerca en el tiempo deben estar unidos en memoria para aumentar la localización espacial de referencia.

Explotar la jerarquía de memoria

Los accesos a la memoria son cada vez más caros para cada nivel de la jerarquía de memoria, así que coloca los elementos más utilizados en los registros primero, luego caches, luego la memoria principal, antes de ir al disco.

Parallelize

Operaciones de reordenamiento para permitir que ocurran múltiples computaciones en paralelo, ya sea a nivel de instrucción, memoria o hilo.

Más información precisa es mejor

Cuanto más precisa sea la información que tiene el compilador, mejor puede emplear cualquiera o todas estas técnicas de optimización.

Las métricas de tiempo de ejecución pueden ayudar

La información reunida durante una prueba puede utilizarse en optimización guiada por perfiles. La información reunida en tiempo de ejecución, idealmente con una sobrecarga mínima, puede ser utilizada por un compilador JIT para mejorar dinámicamente la optimización.

Reducción de la fuerza

Reemplazar operaciones complejas o difíciles o costosas con operaciones más simples. Por ejemplo, reemplazar la división por una constante con la multiplicación por su reciproco, o utilizar el análisis variable de inducción para reemplazar la multiplicación por un índice de bucle por adición.

Técnicas específicas

Optimizaciones de bucle

Algunas técnicas de optimización diseñadas principalmente para operar en bucles incluyen:

Análisis de variables de inducción

Roughly, if a variable in a loop is a simple linear function of the index variable, such as j:= 4*i + 1, se puede actualizar apropiadamente cada vez que se cambia la variable de bucle. Esto es una reducción de la fuerza, y también puede permitir que las definiciones de la variable índice se conviertan en código muerto. Esta información también es útil para el análisis de la eliminación y la dependencia, entre otras cosas.

Fisión de bucle o distribución de bucles

La fisión de bucle intenta romper un bucle en múltiples bucles sobre el mismo rango de índice pero cada uno toma sólo una parte del cuerpo del bucle. Esto puede mejorar la localización de referencia, tanto de los datos que se acceden en el bucle como del código en el cuerpo del bucle.

fusión de lazo o lazo combinando o lazo ramming o atasco

Otra técnica que intenta reducir el sobrecabezamiento. Cuando dos bucles adyacentes iteran el mismo número de veces independientemente de si ese número se conoce en el tiempo de compilación, sus cuerpos pueden combinarse mientras no hacen referencia a los datos de los demás.

Inversión de bucle

Esta técnica cambia un estándar mientras en un bucle hacer/mientras (también conocido como repetido/hastaLoop envuelto en un si condicional, reduciendo el número de saltos por dos, para casos cuando se ejecuta el bucle. Hacerlo duplica el control de condiciones (aumentando el tamaño del código), pero es más eficiente porque los saltos generalmente causan un estancamiento de tubería. Además, si la condición inicial se conoce en tiempo de compilación y se sabe que está libre de efectos secundarios, si El guardia puede ser saltado.

Intercambio de bucle

Estas optimizaciones intercambian bucles interiores con bucles externos. Cuando el índice de variables de bucle en un array, tal transformación puede mejorar la localidad de referencia, dependiendo del diseño del array.

movimiento de código invariante

Si una cantidad se calcula dentro de un bucle durante cada iteración, y su valor es el mismo para cada iteración, puede mejorar enormemente la eficiencia para clavarla fuera del bucle y calcular su valor una vez antes de que comience el bucle. Esto es particularmente importante con las expresiones de cálculo de direcciones generadas por bucles sobre arrays. Para la correcta implementación, esta técnica debe usarse con la inversión de bucle, porque no todo el código es seguro para ser colocado fuera del bucle.

Optimización de nido de bucle

Algunos algoritmos pervasivos como la multiplicación de matriz tienen muy mal comportamiento de caché y accesos excesivos de memoria. La optimización del nido de bucle aumenta el número de golpes de caché realizando la operación sobre bloques pequeños y utilizando un intercambio de bucles.

Reversión de bucle

La inversión de bucle revierte el orden en el que los valores se asignan a la variable índice. Esta es una optimización sutil que puede ayudar a eliminar dependencias y así permitir otras optimizaciones. Además, en algunas arquitecturas, la inversión de bucle contribuye a un código más pequeño, ya que cuando el índice de bucle está siendo decrementado, la condición que necesita ser cumplida para que el programa de ejecución salga del bucle es una comparación con cero. Esto es a menudo una instrucción especial, sin parámetros, a diferencia de una comparación con un número, que necesita el número para comparar. Por lo tanto, la cantidad de bytes necesarios para almacenar el parámetro se salva utilizando el reversal de bucle. Además, si el número de comparación supera el tamaño de la palabra de la plataforma, en orden de bucle estándar, habría que ejecutar varias instrucciones para evaluar la comparación, que no es el caso con reversión de bucle.

Loop unrolling

Desrollar duplica el cuerpo del bucle varias veces, con el fin de disminuir el número de veces que se prueba la condición del bucle y el número de saltos, que dolió el rendimiento al dañar el oleoducto de instrucción. Una optimización de "menos saltos". Completamente desenrollar un bucle elimina todo el sobrecabezamiento, pero requiere que el número de iteraciones sea conocido en el tiempo de compilación.

Loop splitting

Los intentos de división de bucles para simplificar un bucle o eliminar las dependencias rompiéndolo en múltiples bucles que tienen los mismos cuerpos pero que se iteran sobre diferentes porciones contiguas del rango de índice. Un caso especial útil loop peeling, que puede simplificar un bucle con una primera iteración problemática al realizar esa iteración por separado antes de entrar en el bucle.

Loop unswitching

Unswitching mueve un condicional desde dentro de un bucle hasta fuera del bucle duplicando el cuerpo del bucle dentro de cada una de las cláusulas de si y de otro tipo del condicional.

Flujo de software

El bucle es reestructurado de tal manera que el trabajo realizado en una iteración se divide en varias partes y se hace sobre varias iteraciones. En un bucle ajustado, 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-treaded o vectorizado (o incluso ambos) para utilizar varios procesadores simultáneamente en una máquina multiprocesador de memoria compartida (SMP), incluyendo máquinas multi-core.

Optimizaciones de flujo de datos

Las optimizaciones de flujo de datos, basadas en el análisis de flujo de datos, dependen principalmente de cómo los bordes de control propagan ciertas propiedades de los datos en el gráfico de flujo de control. Algunos de estos incluyen:

Eliminación de la subexpresión común

En la expresión (a + b) - (a + b)/4, "subexpresión común" se refiere a la duplicada (a + b). Los participantes que implementan esta técnica se dan cuenta de que (a + b) no cambiará, y por lo tanto sólo calcular su valor una vez.

Pliegue constante y propagación

sustitución de expresiones consistentes en constantes (por ejemplo, 3 + 5) con su valor final (8) en tiempo de compilación, en lugar de hacer el cálculo en tiempo de ejecución. Se utiliza en la mayoría de los idiomas modernos.

Reconocimiento y eliminación variable de inducción

ver discusión arriba sobre análisis variable de inducción.

Clasificación de Alias y análisis de punteros

en presencia de punteros, es difícil hacer cualquier optimización en absoluto, ya que potencialmente cualquier variable se puede haber cambiado cuando se asigna una ubicación de memoria. Al especificar qué punteros pueden aliar qué variables, los punteros no relacionados pueden ser ignorados.

Eliminación de la calle

eliminación de asignaciones a variables que no se leen posteriormente, ya sea porque la vida útil de la variable termina o debido a una asignación posterior que sobrescribirá el primer valor.

Optimizaciones basadas en SSA

Estas optimizaciones están destinadas a realizarse después de transformar el programa en un formulario especial llamado Asignación única estática, en el que cada variable se asigna en un solo lugar. Aunque algunos funcionan sin SSA, son más efectivos con SSA. Muchas optimizaciones enumeradas en otras secciones también se benefician sin cambios especiales, como la asignación de registros.

Número de valores mundiales

GVN elimina la redundancia mediante la construcción de un gráfico de valor del programa, y luego determina qué valores se calculan por expresiones equivalentes. GVN es capaz de identificar alguna redundancia que la eliminación común de subexpresión no puede, y viceversa.

Propagación constante de la enfermedad

Combina la propagación constante, el plegamiento constante y la eliminación de código muerto, y mejora sobre lo que es posible al ejecutarlos por separado. Esta optimización ejecuta simbólicamente el programa, propagando simultáneamente valores constantes y eliminando porciones del gráfico de flujo de control que esto hace inalcanzable.

Optimizaciones del generador de código

Asignación de registros

Las variables más utilizadas deben mantenerse en registros de procesadores para un acceso más rápido. Para encontrar qué variables poner en registros, se crea un gráfico de interferencia. Cada variable es un vértice y cuando se utilizan dos variables al mismo tiempo (tienen un rango de vida intersecante) tienen un borde entre ellas. Este gráfico se colorea usando por ejemplo el algoritmo de Chaitin usando el mismo número de colores que hay registros. Si la coloración falla una variable es "spilled" a la memoria y la coloración es retriada.

Selección de instrucciones

La mayoría de las arquitecturas, en particular las arquitecturas del CISC y las que tienen muchos modos de abordar, ofrecen varias formas diferentes de realizar una operación particular, utilizando secuencias completamente diferentes de instrucciones. El trabajo del selector de instrucciones es hacer un buen trabajo en general de elegir qué instrucciones para implementar con qué operadores en la representación intermedia de bajo nivel. Por ejemplo, en muchos procesadores en la familia 68000 y en la arquitectura x86, los modos de abordaje complejos se pueden utilizar en declaraciones como "lea 25(a1,d5*4), a0", permitiendo una sola instrucción para realizar una cantidad significativa de aritmética con menos almacenamiento.

Programación de instrucciones

La programación de instrucciones es una optimización importante para los procesadores modernos oleoductos, que evita puestos o burbujas en el oleoducto agrupando instrucciones sin dependencias juntas, mientras se cuida de preservar la semántica original.

Rematerialización

La rematerialización recalcula un valor en lugar de cargarlo de la memoria, evitando el acceso a la memoria. Esto se realiza en tándem con asignación de registro para evitar derrames.

Factores de código

Si varias secuencias de código son idénticas, o pueden ser parametizadas o reordenadas para ser idénticas, pueden ser reemplazadas por llamadas a una subrutina compartida. Esto a menudo puede compartir el código para la configuración de la subrutina y a veces la recursión de la cola.

Trampolines

Muchos Las CPU tienen instrucciones de llamada de subrutina más pequeñas para acceder a la memoria baja. Un compilador puede ahorrar espacio utilizando estas pequeñas llamadas en el cuerpo principal del código. Saltar instrucciones en memoria baja puede acceder a las rutinas en cualquier dirección. Esto multiplica los ahorros espaciales de factorización de código.

Reordenar los cálculos

Basándose en la programación lineal entero, los compiladores de reestructuración aumentan la localización de datos y exponen más paralelismo reordenando computaciones. Los compiladores optimizadores de espacio pueden reordenar código para alargar secuencias que pueden ser factorizadas en subrutinas.

Optimizaciones de lenguaje funcional

Aunque muchos de estos también se aplican a lenguajes no funcionales, se originan o son particularmente críticos en lenguajes funcionales como Lisp y ML.

Optimización de colas

Una llamada de función consume espacio de apilación e implica un poco de sobrecabezamiento relacionado con el parámetro que pasa y esparce el caché de instrucciones. Los algoritmos recursivos de cola se pueden convertir en iteración a través de un proceso llamado eliminación de recursión trasera o optimización de la cola.

Deforestación (función de la estructura de datos)

En los idiomas en que es común que una secuencia de transformaciones se aplique a una lista, la deforestación intenta eliminar la construcción de estructuras de datos intermedias.

Evaluación parcial

Otras optimizaciones

Erradicación de los golpes

Muchos idiomas, como Java, imponen la verificación de límites de todos los accesos de matriz. Este es un problema de rendimiento severo en ciertas aplicaciones como el código científico. La eliminación de los límites permite al compilador eliminar los límites de forma segura en muchas situaciones donde puede determinar que el índice debe caer dentro de límites válidos; por ejemplo, si es una variable de bucle simple.

Optimización de sucursales (dependiente de máquina)

Elija el desplazamiento de rama más corto que alcanza el objetivo.

Reordenamiento del bloqueo

El reordenamiento del bloque de código altera el orden de los bloques básicos en un programa para reducir las ramas condicionales y mejorar la localidad de referencia.

Eliminación de código muerto

Elimina las instrucciones que no afectarán el comportamiento del programa, por ejemplo las definiciones que no tienen usos, llamadas código muerto. Esto reduce el tamaño del código y elimina la computación innecesaria.

Factoring out of invariants (loop invariants)

Si se realiza una expresión tanto cuando se cumple una condición como no se cumple, se puede escribir una vez fuera de la declaración condicional. Del mismo modo, si ciertos tipos de expresiones (por ejemplo, la asignación de una constante a una variable) aparecen dentro de un bucle, se pueden mover fuera de él porque su efecto será el mismo no importa si se ejecutan muchas veces o sólo una vez. Esto también se conoce como eliminación total de la redundancia. Una optimización similar pero más poderosa es la eliminación parcial-redundancia (PRE).

Ampliación en línea o expansión macro

Cuando algún código invoca un procedimiento, es posible insertar directamente el cuerpo del procedimiento dentro del código de llamada en lugar de transferir el control a él. Esto ahorra la sobrecarga relacionada con las llamadas de procedimiento, así como ofrecer una oportunidad para muchas optimizaciones específicas para parámetros diferentes, pero viene al costo del espacio; el cuerpo de procedimiento se duplica cada vez que el procedimiento se llama inline. Por lo general, la inclusión es útil en el código crítico de rendimiento que hace un gran número de llamadas a procedimientos pequeños. Una optimización de "menos saltos". Las declaraciones de lenguajes de programación imperativos son también un ejemplo de tal optimización. Aunque las declaraciones podrían aplicarse con las llamadas de funciones, casi siempre se aplican con la inclusión de códigos.

Corrección de salto

En esta optimización, se fusionan saltos condicionales consecutivos predicados total o parcialmente en la misma condición.

Por ejemplo, if (c) { foo; } if (c) { bar; } a if (c) { foo; bar; },

y if (c) { foo; } if (!c) { bar; } a if (c) { foo; } else { bar; }.

Compresión de macro

Una optimización espacial que reconoce secuencias comunes de código, crea subprogramas ("código macros") que contienen el código común, y reemplaza las ocurrencias de las secuencias de código común con llamadas a los subprogramas correspondientes. Esto se hace más eficazmente como una optimización de código de máquina, cuando todo el código está presente. La técnica se utilizó por primera vez para conservar el espacio en un flujo de byte interpretativo utilizado en una implementación de Macro Spitbol en microcomputadoras. Se sabe que el problema de determinar un conjunto óptimo de macros que minimiza el espacio requerido por un segmento de código determinado es completo, pero las heurísticas eficientes alcanzan resultados casi óptimos.

Reducción de las colisiones de caché

(por ejemplo, alterando la alineación en una página)

Reducción de altura

Rearrange expression tree to minimize resources needed for expression evaluation.

Reordenación de pruebas

Si tenemos dos pruebas que son la condición para algo, primero podemos tratar las pruebas más simples (por ejemplo, comparando una variable con algo) y sólo entonces con las pruebas complejas (por ejemplo, las que requieren una llamada de función). Esta técnica complementa la evaluación perezosa, pero sólo se puede utilizar cuando las pruebas no dependen unos de otros. La semántica de cortocircuito puede hacer esto difícil.

Optimizaciones interprocedimiento

La optimización interprocedimiento funciona en todo el programa, a través de los límites del procedimiento y del archivo. Trabaja estrechamente con contrapartes intraprocesales, realizado con la cooperación de una parte local y una parte global. Las optimizaciones interprocedimiento típicas son: alineamiento de procedimiento, eliminación de código muerto interprocedimiento, propagación constante interprocedimiento y reordenamiento de procedimiento. Como de costumbre, el compilador necesita realizar un análisis entre procedimientos antes de sus optimizaciones reales. Los análisis entre procedimientos incluyen análisis de alias, análisis de acceso a matrices y la construcción de un gráfico de llamadas.

La optimización entre procedimientos es común en los compiladores comerciales modernos de SGI, Intel, Microsoft y Sun Microsystems. Durante mucho tiempo, el GCC de código abierto fue criticado por la falta de potentes análisis y optimizaciones entre procedimientos, aunque ahora esto está mejorando. Otro compilador de código abierto con infraestructura completa de análisis y optimización es Open64.

Debido al tiempo y espacio adicional que requiere el análisis entre procedimientos, la mayoría de los compiladores no lo realizan de forma predeterminada. Los usuarios deben usar las opciones del compilador explícitamente para decirle al compilador que habilite el análisis entre procedimientos y otras optimizaciones costosas.

Consideraciones prácticas

Puede haber una amplia gama de optimizaciones que puede realizar un compilador, que van desde las sencillas y directas que requieren poco tiempo de compilación hasta las elaboradas y complejas que implican cantidades considerables de tiempo de compilación. En consecuencia, los compiladores a menudo brindan opciones a su comando o procedimiento de control para permitir que el usuario del compilador elija cuánta optimización solicitar; por ejemplo, el compilador IBM FORTRAN H permitía al usuario especificar sin optimización, optimización solo a nivel de registros u optimización completa. En la década de 2000, era común que los compiladores, como Clang, tuvieran una serie de opciones de comandos del compilador que podían afectar una variedad de opciones de optimización, comenzando con el interruptor familiar -O2.

Un enfoque para aislar la optimización es el uso de los llamados optimizadores posteriores al paso (algunas versiones comerciales de los cuales se remontan al software de mainframe de finales de la década de 1970). Estas herramientas toman la salida ejecutable de un compilador de optimización y la optimizan aún más. Los optimizadores posteriores al paso generalmente funcionan en el lenguaje ensamblador o en el nivel de código de máquina (en contraste con los compiladores que optimizan las representaciones intermedias de los programas). Un ejemplo de ello es el Portable C Compiler (pcc) de la década de 1980, que tenía un pase opcional que realizaba optimizaciones posteriores en el código ensamblador generado.

Otra consideración es que los algoritmos de optimización son complicados y, especialmente cuando se usan para compilar lenguajes de programación grandes y complejos, pueden contener errores que introducen errores en el código generado o provocan errores internos durante la compilación. Los errores del compilador de cualquier tipo pueden ser desconcertantes para el usuario, pero especialmente en este caso, ya que puede no estar claro que la lógica de optimización tiene la culpa. En el caso de errores internos, el problema se puede mejorar parcialmente con un "a prueba de fallas" técnica de programación en la que la lógica de optimización en el compilador se codifica de tal manera que se atrapa una falla, se emite un mensaje de advertencia y el resto de la compilación continúa hasta completarse con éxito.

Historia

Los primeros compiladores de la década de 1960 a menudo se preocupaban principalmente por compilar el código de manera correcta o eficiente, por lo que los tiempos de compilación eran una preocupación importante. Uno de los primeros compiladores optimizadores notables fue el compilador IBM FORTRAN H de finales de la década de 1960. Otro de los primeros e importantes compiladores de optimización, que fue pionero en varias técnicas avanzadas, fue el de BLISS (1970), que se describió en The Design of an Optimizing Compiler (1975). A fines de la década de 1980, la optimización de los compiladores fue lo suficientemente efectiva como para que la programación en lenguaje ensamblador declinara. Esto coevolucionó con el desarrollo de chips RISC y características avanzadas del procesador, como la programación de instrucciones y la ejecución especulativa, que se diseñaron para optimizar compiladores en lugar de código ensamblador escrito por humanos.

Lista de análisis de código estático

• Análisis de Alias
• Análisis de puntos
• Análisis de la forma
• Análisis de escape
• Análisis del acceso a la radiación
• Análisis de dependencia
• Análisis del flujo de control
• Análisis de la corriente de datos
  • Análisis de la cadena de uso-define
  • Análisis variable en vivo
  • Análisis de la expresión disponible