Optimización del compilador - Optimizing compiler

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

La optimización del compilador generalmente se implementa usando una secuencia de optimizaciones de transformaciones , 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 podría proporcionar. La optimización es generalmente un proceso que consume mucha memoria y CPU . 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 un resultado "óptimo" en ningún 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 declaració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 mirilla
Por lo general, estos se realizan al final del proceso de compilación después de que se haya generado el código de máquina . Esta forma de optimización examina algunas instrucciones adyacentes (como "mirar a través de una mirilla" en el código) para ver si pueden ser reemplazadas por una sola instrucción o una secuencia de instrucciones más corta. Por ejemplo, una multiplicación de un valor por 2 podría ejecutarse de manera más eficiente desplazando el valor hacia la izquierda o agregando el valor a sí mismo (este ejemplo también es una instancia de reducción de fuerza ).
Optimizaciones locales
Estos solo consideran información local a un bloque básico . Dado que los bloques básicos no tienen flujo de control, estas optimizaciones necesitan muy poco análisis, lo que ahorra tiempo y reduce los requisitos de almacenamiento, pero esto también significa que no se conserva información en los saltos.
Optimizaciones globales
Estos también se denominan "métodos intraprocedimiento" y actúan sobre funciones completas. Esto les da más información con la que trabajar, pero a menudo hace necesarios cálculos costosos. Se deben hacer suposiciones en el peor de los casos cuando ocurren llamadas a funciones o se accede a variables globales porque hay poca información disponible sobre ellas.
Optimizaciones de bucle
Estos actúan sobre los estados que forman un bucle, tal como por lazo, por ejemplo, el movimiento de código de lazo invariante . Las optimizaciones de bucles pueden tener un impacto significativo porque muchos programas pasan un gran porcentaje de su tiempo dentro de los bucles.
Optimizaciones proféticas de la tienda
Estos permiten que las operaciones de la tienda se realicen antes de lo que se permitiría en el contexto de subprocesos y bloqueos. El proceso necesita alguna forma de saber de antemano qué valor almacenará la asignación que debería haber seguido. El propósito de esta relajación es permitir que la optimización del compilador realice ciertos tipos de reordenamiento de código que preservan la semántica de los programas sincronizados correctamente.
Optimización de tiempo de enlace , de programa completo o de interprocesamiento
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 efectivas en comparación con cuando solo tienen acceso a información local, es decir, dentro de una única función. Este tipo de optimización también puede permitir la realización de nuevas técnicas. Por ejemplo, la función inlining , donde una llamada a una función se sustituye por una copia del cuerpo de la función.
Optimización de código de máquina y optimizador de código objeto
Estos analizan la imagen de la tarea ejecutable del programa después de que se haya vinculado todo el código de máquina ejecutable . Algunas de las técnicas que se pueden aplicar en un ámbito más limitado, como la macrocompresión, que ahorra espacio al contraer secuencias comunes de instrucciones, son más efectivas cuando la imagen completa de la tarea ejecutable está disponible para el análisis.

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

Lenguaje de programación: independiente vs. dependiente del lenguaje
La mayoría de los lenguajes de alto nivel comparten construcciones y abstracciones de programación comunes: decisión (if, switch, case), bucle (for, while, repeat .. until, do .. while) y encapsulación (estructuras, objetos). Por lo tanto, se pueden utilizar técnicas de optimización similares en todos los idiomas. Sin embargo, ciertas características del lenguaje dificultan algunos tipos de optimizaciones. Por ejemplo, la existencia de punteros en C y C ++ dificulta la optimización de los accesos a la matriz (ver análisis de alias ). Sin embargo, lenguajes como PL / 1 (que también admite punteros) tienen disponibles compiladores de optimización sofisticados para lograr un mejor rendimiento de varias otras formas. Por el contrario, algunas funciones del idioma facilitan determinadas optimizaciones. Por ejemplo, en algunos idiomas no se permite que las funciones tengan efectos secundarios . Por lo tanto, si un programa realiza varias llamadas a la misma función con los mismos argumentos, el compilador puede inferir inmediatamente que el resultado de la función debe calcularse solo una vez. En lenguajes donde se permite que las funciones tengan efectos secundarios, es posible otra estrategia. El optimizador puede determinar qué función no tiene efectos secundarios y restringir dichas optimizaciones a funciones sin efectos secundarios. Esta optimización solo es posible cuando el optimizador tiene acceso a la función llamada.
Independiente de la máquina frente a dependiente de la máquina
Muchas optimizaciones que operan en conceptos de programación abstractos (bucles, objetos, estructuras) son independientes de la máquina a la que apunta el compilador, pero muchas de las optimizaciones más efectivas son aquellas que aprovechan mejor las características especiales de la plataforma de destino. Los ejemplos son instrucciones que hacen varias cosas a la vez, como disminuir el registro y bifurcar si no es 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 XOR un registro consigo mismo. Depende del compilador saber qué variante de instrucción utilizar. 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 será necesario decodificar un operando inmediato, ni utilizar el "registro de operando inmediato" interno. 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 tubería . Sin embargo, los procesadores a menudo tienen XOR de un registro consigo mismo como un caso especial que no causa paradas.

Factores que afectan la optimización

La propia maquina
Muchas de las opciones sobre qué optimizaciones pueden y deben realizarse 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 pueda usarse para optimizar diferentes máquinas simplemente modificando 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 de la CPU de destino
Número de registros de CPU : hasta cierto punto, cuantos 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 los registros sin tener que escribir y volver a leer de la memoria.
  • RISC vs CISC : Los conjuntos de instrucciones CISC a menudo tienen longitudes de instrucción variables, a menudo tienen una mayor cantidad de instrucciones posibles que se pueden usar y cada instrucción puede tomar diferentes cantidades de tiempo. Los conjuntos de instrucciones RISC intentan limitar la variabilidad en cada uno de estos: los conjuntos de instrucciones suelen tener una 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, normalmente un múltiplo entero del ciclo del reloj) suele ser constante en los casos en que la latencia de la memoria no es un factor. Puede haber varias formas de realizar una determinada tarea, y CISC suele ofrecer más alternativas que RISC. Los compiladores deben conocer los costos relativos entre las diversas instrucciones y elegir la mejor secuencia de instrucciones (ver selección de instrucciones ).
  • Pipelines : un pipeline es esencialmente una CPU dividida en una línea de montaje . Permite el uso de partes de la CPU para diferentes instrucciones al dividir la ejecución de las instrucciones en varias etapas: decodificación de instrucciones, decodificación de direcciones, búsqueda de memoria, búsqueda de registros, cálculo, almacenamiento de registros, etc. Una instrucción podría estar en la etapa de almacenamiento de registros , mientras que otro podría estar en la etapa de búsqueda de registros. Los conflictos de canalización ocurren cuando una instrucción en una etapa de la canalización depende del resultado de otra instrucción anterior a ella en la canalización, pero aún no se ha completado. Los conflictos de canalización pueden llevar a paradas de canalización : donde la CPU desperdicia ciclos esperando que se resuelva un conflicto.
Los compiladores pueden programar o reordenar instrucciones para que los bloqueos de la tubería se produzcan con menos frecuencia.
  • Número de unidades funcionales : algunas CPU tienen varias ALU y FPU . Esto les permite ejecutar múltiples instrucciones simultáneamente. Puede haber restricciones sobre qué instrucciones pueden emparejarse con qué otras instrucciones ("emparejamiento" 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 caché (256 kiB – 12 MiB) y tipo (mapeado directo, asociativo de 2 / 4- / 8- / 16 vías, totalmente asociativo): técnicas como la expansión en línea y el desenrollado de bucles pueden aumentar el tamaño del código generado y reducir la localidad del código. El programa puede ralentizarse drásticamente si una sección de código muy utilizada (como bucles internos en varios algoritmos) de repente no puede caber en la caché. Además, los cachés que no son completamente asociativos tienen mayores posibilidades de colisiones de caché incluso en un caché vacío.
  • Tasas de transferencia de caché / memoria: le dan al compilador una indicación de la penalización por fallas de caché. Se utiliza principalmente en aplicaciones especializadas.
Uso previsto del código generado
Depuración
Mientras escribe una aplicación, un programador recompilará y probará con frecuencia, por lo que la compilación debe ser rápida. Esta es una de las razones por las que la mayoría de las optimizaciones se evitan deliberadamente durante la fase de prueba / depuración. Además, el código del programa generalmente se "recorre paso a paso" (ver Animación del programa ) usando un depurador simbólico , y la optimización de las transformaciones, particularmente aquellas que reordenan el código, puede 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 a las herramientas de depuración como a los programadores que las utilizan.
Uso de propósito general
Muy a menudo, se espera que el software preempaquetado 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, es posible que el código no se ajuste a ninguna CPU en particular, o que funcione mejor en la CPU más popular y, sin embargo, funcione aceptablemente bien en otras CPU.
Uso para fines especiales
Si el software se compila para ser utilizado en una o pocas máquinas muy similares, con características conocidas, entonces el compilador puede ajustar en gran medida el código generado a esas máquinas específicas, siempre que tales opciones estén disponibles. Los casos especiales importantes incluyen código diseñado para procesadores paralelos y vectoriales , para los cuales se emplean compiladores especiales de paralelización .
Sistemas embebidos
Estos son un caso común de uso para fines especiales. El software integrado se puede ajustar con precisión a un tamaño exacto de CPU y memoria. Además, el costo o la confiabilidad del sistema pueden ser más importantes que la velocidad del código. Por ejemplo, los compiladores de software integrado suelen ofrecer opciones que reducen el tamaño del código a expensas de la velocidad, porque la memoria es el principal costo de una computadora integrada. Es posible que el tiempo del código deba ser predecible, en lugar de lo más rápido posible, por lo que el almacenamiento en caché del código puede estar deshabilitado, 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 entran en conflicto.

Optimizar el caso común
El caso común puede tener propiedades únicas que permitan una ruta rápida a expensas de una ruta lenta . Si se toma la ruta rápida con mayor frecuencia, el resultado es un mejor rendimiento general.
Evite la redundancia
Reutilice los resultados que ya se han calculado y guárdelos para su uso posterior, en lugar de volver a calcularlos.
Menos código
Elimine cálculos innecesarios y valores intermedios. Menos trabajo para la CPU, la memoria caché y la memoria generalmente resulta en una ejecución más rápida. Alternativamente, en los sistemas integrados , menos código trae un costo de producto más bajo.
Menos saltos mediante el uso de código de línea recta , también llamado código sin rama
Código menos complicado. Los saltos ( bifurcaciones condicionales o incondicionales ) interfieren con la captación previa de instrucciones, lo que ralentiza el código. El uso de inlining o bucle de desenrollado puede reducir la ramificación, a costa de aumentar el tamaño del 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 a los que se accede de forma cercana en el tiempo deben colocarse juntos en la memoria para aumentar la localidad espacial de referencia .
Explotar la jerarquía de la memoria
Los accesos a la memoria son cada vez más costosos para cada nivel de la jerarquía de la memoria , por lo tanto, coloque los elementos más utilizados en los registros primero, luego en las cachés y luego en la memoria principal, antes de ir al disco.
Paralelizar
Reordene las operaciones para permitir que se realicen varios cálculos en paralelo, ya sea a nivel de instrucción, memoria o subproceso.
Una información más precisa es mejor
Cuanto más precisa sea la información que tenga el compilador, mejor podrá emplear cualquiera o todas estas técnicas de optimización.
Las métricas de tiempo de ejecución pueden ayudar
La información recopilada durante una ejecución de prueba se puede utilizar en la optimización guiada por perfiles . La información recopilada 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 fuerza
Reemplace las operaciones complejas, difíciles o costosas por otras más simples. Por ejemplo, reemplazando la división por una constante con la multiplicación por su recíproco, o usando el análisis de variables de inducción para reemplazar la multiplicación por un índice de bucle con la suma.

Técnicas específicas

Optimizaciones de bucle

Artículo principal: optimización de bucle

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

Análisis de variables de inducción
Aproximadamente, si una variable en un bucle es una función lineal simple de la variable de índice, por ejemplo j := 4*i + 1, se puede actualizar adecuadamente cada vez que se cambia la variable del bucle. Esta es una reducción de fuerza y también puede permitir que las definiciones de la variable de índice se conviertan en código muerto . Esta información también es útil para la eliminación de verificación de límites y el análisis de dependencia , entre otras cosas.
Fisión de bucle o distribución de bucle
La fisión de bucle intenta dividir un bucle en varios bucles sobre el mismo rango de índice, pero cada uno de ellos toma solo una parte del cuerpo del bucle. Esto puede mejorar la localidad de referencia , tanto a los datos a los que se accede en el bucle como al código en el cuerpo del bucle.
Fusión de bucle o combinación de bucle o apisonamiento de bucle o bloqueo de bucle
Otra técnica que intenta reducir la sobrecarga del bucle. Cuando dos bucles adyacentes iterarían el mismo número de veces, independientemente de si ese número se conoce en el momento de la compilación, sus cuerpos se pueden combinar siempre que no hagan referencia a los datos del otro.
Inversión de bucle
Esta técnica cambia un bucle while estándar en un bucle do / while (también conocido como repetir / hasta ) envuelto en un condicional if , reduciendo el número de saltos en dos, para los casos en que se ejecuta el bucle. Hacerlo duplica la verificación de condición (aumentando el tamaño del código), pero es más eficiente porque los saltos generalmente causan un bloqueo de la tubería . Además, si se conoce la condición inicial en tiempo de compilación y se sabe que no tiene efectos secundarios , se puede omitir la protección if .
Intercambio de bucle
Estas optimizaciones intercambian bucles internos con bucles externos. Cuando las variables de bucle se indexan en una matriz, dicha transformación puede mejorar la localidad de referencia, dependiendo del diseño de la matriz.
Movimiento de código invariante en bucle
Si se calcula una cantidad dentro de un bucle durante cada iteración, y su valor es el mismo para cada iteración, puede mejorar enormemente la eficiencia para sacarla del bucle y calcular su valor solo una vez antes de que comience el bucle. Esto es particularmente importante con las expresiones de cálculo de direcciones generadas por bucles sobre matrices. Para una implementación correcta, esta técnica debe usarse con inversión de bucle , porque no todo el código es seguro para ser izado fuera del bucle.
Optimización del nido de bucles
Algunos algoritmos generalizados, como la multiplicación de matrices, tienen un comportamiento de caché muy deficiente y un acceso excesivo a la memoria. La optimización del nido de bucles aumenta el número de aciertos de caché al realizar la operación en bloques pequeños y al utilizar un intercambio de bucles.
Inversión de bucle
La inversión de bucle invierte el orden en el que se asignan los valores a la variable de índice. Esta es una optimización sutil que puede ayudar a eliminar dependencias y, por lo tanto, habilitar otras optimizaciones. Además, en algunas arquitecturas, la inversión de bucle contribuye a un código más pequeño, como cuando el índice de bucle se reduce, la condición que debe cumplirse para que el programa en ejecución salga del bucle es una comparación con cero. Esta 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 guarda mediante la inversión de bucle. Además, si el número de comparación excede el tamaño de la palabra de la plataforma, en el orden de bucle estándar, sería necesario ejecutar varias instrucciones para evaluar la comparación, lo cual no es el caso con la inversión de bucle.
Desenrollar bucle
Al desenrollar, se duplica el cuerpo del bucle varias veces, con el fin de disminuir la cantidad de veces que se prueba la condición del bucle y la cantidad de saltos, lo que perjudica el rendimiento al afectar la canalización de instrucciones. Optimización de "menos saltos". Desenrollar completamente un bucle elimina toda la sobrecarga, pero requiere que se conozca el número de iteraciones en el momento de la compilación.
División de bucle
La división de bucles intenta simplificar un bucle o eliminar dependencias dividiéndolo en múltiples bucles que tienen los mismos cuerpos pero que iteran sobre diferentes porciones contiguas del rango de índice. Un caso especial útil es el pelado de bucles , que puede simplificar un bucle con una primera iteración problemática al realizar esa iteración por separado antes de ingresar al bucle.
Loop unswitching
Unswitching mueve un condicional desde dentro de un bucle hacia fuera del bucle duplicando el cuerpo del bucle dentro de cada una de las cláusulas if y else del condicional.
Canalización de software
El ciclo se reestructura de tal manera que el trabajo realizado en una iteración se divide en varias partes y se realiza en varias iteraciones. En un circuito cerrado, 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 multiproceso o vectorizado (o incluso en ambos) para utilizar varios procesadores simultáneamente en una máquina de multiprocesador de memoria compartida (SMP), incluidas las máquinas de varios núcleos.

Optimizaciones del flujo de datos

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

Eliminación de subexpresiones comunes
En la expresión (a + b) - (a + b)/4, "subexpresión común" se refiere al duplicado (a + b). Los compiladores que implementan esta técnica se dan cuenta de que (a + b)no cambiará, por lo que solo calculan su valor una vez.
Plegado y propagación constantes
reemplazar expresiones que constan de 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. Usado en la mayoría de los lenguajes modernos.
Reconocimiento y eliminación de variables de inducción
consulte la discusión anterior sobre el análisis de variables de inducción .
Clasificación de alias y análisis de punteros
en presencia de punteros , es difícil realizar optimizaciones, ya que potencialmente se puede haber cambiado cualquier variable cuando se asigna una ubicación de memoria. Al especificar qué punteros pueden alias qué variables, se pueden ignorar los punteros no relacionados.
Eliminación de tiendas muertas
eliminación de asignaciones a variables que no se leen posteriormente, ya sea porque finaliza la vida útil de la variable 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 una forma especial llamada Asignación única estática , en la 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.

Numeración de valor global
GVN elimina la redundancia al construir un gráfico de valores del programa y luego determinar qué valores se calculan mediante expresiones equivalentes. GVN puede identificar alguna redundancia que la eliminación de subexpresiones comunes no puede, y viceversa.
Propagación constante condicional dispersa
Combina propagación constante, plegado constante y eliminación de código muerto , y mejora lo que es posible ejecutándolos 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 utilizadas con más frecuencia deben mantenerse en los registros del procesador para un acceso más rápido. Para encontrar qué variables poner en los registros, se crea un gráfico de interferencia. Cada variable es un vértice y cuando se usan dos variables al mismo tiempo (tienen un rango vivo que se cruza), tienen un borde entre ellas. Este gráfico se colorea utilizando, por ejemplo, el algoritmo de Chaitin utilizando el mismo número de colores que los registros. Si la coloración falla, una variable se "derrama" en la memoria y se vuelve a intentar la coloración.
Selección de instrucción
La mayoría de las arquitecturas, particularmente las arquitecturas CISC y aquellas con muchos modos de direccionamiento , ofrecen varias formas diferentes de realizar una operación en particular, utilizando secuencias de instrucciones completamente diferentes. El trabajo del selector de instrucciones es hacer un buen trabajo en general al elegir qué instrucciones implementar con qué operadores en la representación intermedia de bajo nivel . Por ejemplo, en muchos procesadores de la familia 68000 y en la arquitectura x86, se pueden usar modos de direccionamiento complejos en declaraciones como "lea 25 (a1, d5 * 4), a0", lo que permite que una sola instrucción realice 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 en canalización modernos, que evita paradas o burbujas en la canalización mediante la agrupación de instrucciones sin dependencias, al tiempo que se tiene cuidado de preservar la semántica original.
Rematerialización
La rematerialización recalcula un valor en lugar de cargarlo desde la memoria, lo que evita el acceso a la memoria. Esto se realiza en conjunto con la asignación de registros para evitar derrames.
Factorización de código
Si varias secuencias de código son idénticas, o se pueden parametrizar o reordenar para que sean idénticas, se pueden reemplazar con llamadas a una subrutina compartida. Esto a menudo puede compartir código para la configuración de subrutinas y, a veces, la recursividad de cola.
Trampolines
Muchas CPU tienen instrucciones de llamada de subrutina más pequeñas para acceder a poca memoria. Un compilador puede ahorrar espacio utilizando estas pequeñas llamadas en el cuerpo principal del código. Las instrucciones de salto con poca memoria pueden acceder a las rutinas en cualquier dirección. Esto multiplica el ahorro de espacio de la factorización de código.
Reordenación de cálculos
Con base en la programación lineal de enteros , los compiladores de reestructuración mejoran la ubicación de los datos y exponen más paralelismo al reordenar los cálculos. Los compiladores que optimizan el espacio pueden reordenar el código para alargar las secuencias que se pueden factorizar en subrutinas.

Optimizaciones del 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 llamadas de cola
Una llamada a función consume espacio en la pila e implica algunos gastos generales relacionados con el paso de parámetros y el vaciado de la caché de instrucciones. Los algoritmos recursivos de cola se pueden convertir en iteración a través de un proceso llamado eliminación de recursividad de cola u optimización de llamadas de cola.
Deforestación ( fusión de estructura de datos )
En idiomas donde 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

Eliminación de comprobación de límites
Muchos lenguajes, como Java , imponen la verificación de límites de todos los accesos a las matrices. Se trata de un cuello de botella severo en el rendimiento de determinadas aplicaciones, como el código científico. La eliminación de la comprobación de límites permite al compilador eliminar de forma segura la comprobación de límites en muchas situaciones en las que puede determinar que el índice debe estar dentro de límites válidos; por ejemplo, si es una variable de ciclo simple.
Optimización de desvío de rama (depende de la máquina)
Elija el desplazamiento de rama más corto que alcance el objetivo.
Reordenación de bloques de código
El reordenamiento de bloques 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 instrucciones que no afectarán el comportamiento del programa, por ejemplo, definiciones que no tienen uso, llamadas código muerto . Esto reduce el tamaño del código y elimina los cálculos innecesarios.
Factorización de invariantes ( invariantes de bucle )
Si una expresión se lleva a cabo tanto cuando se cumple una condición como cuando no se cumple, se puede escribir solo una vez fuera de la declaración condicional. De manera similar, si ciertos tipos de expresiones (por ejemplo, la asignación de una constante a una variable) aparecen dentro de un ciclo, se pueden mover fuera de él porque su efecto será el mismo sin importar si se ejecutan muchas veces o solo una vez. . Esto también se conoce como eliminación de redundancia total. Una optimización similar pero más poderosa es la eliminación de redundancia parcial (PRE).
Expansió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 transferirle el control. Esto ahorra los gastos generales relacionados con las llamadas a procedimientos, además de brindar una oportunidad para muchas optimizaciones específicas de parámetros diferentes, pero tiene un costo de espacio; el cuerpo del procedimiento se duplica cada vez que se llama al procedimiento en línea. Generalmente, la inserción es útil en código de rendimiento crítico que realiza una gran cantidad de llamadas a procedimientos pequeños. Optimización de "menos saltos". Las declaraciones de los lenguajes de programación imperativos también son un ejemplo de dicha optimización. Aunque las declaraciones se pueden implementar con llamadas a funciones , casi siempre se implementan con código insertado.
Saltar enhebrado
En esta optimización, se fusionan los saltos condicionales consecutivos predicados total o parcialmente en la misma condición.
Por ejemplo, a ,if (c) { foo; } if (c) { bar; }if (c) { foo; bar; }
y para .if (c) { foo; } if (!c) { bar; }if (c) { foo; } else { bar; }
Compresión macro
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ódigo común con llamadas a los subprogramas correspondientes. Esto se realiza de forma más eficaz como 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 espacio en un flujo de bytes 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 dado es NP-completo , pero las heurísticas eficientes logran resultados casi óptimos.
Reducción de colisiones de caché
(por ejemplo, interrumpiendo la alineación dentro de una página)
Reducción de la altura de la pila
Reorganice el árbol de expresiones para minimizar los recursos necesarios para la evaluación de expresiones.
Prueba de reordenación
Si tenemos dos pruebas que son la condición para algo, primero podemos ocuparnos de las pruebas más simples (por ejemplo, comparar una variable con algo) y solo entonces con las pruebas complejas (por ejemplo, aquellas que requieren una llamada de función). Esta técnica complementa la evaluación perezosa , pero solo se puede utilizar cuando las pruebas no dependen unas de otras. La semántica de cortocircuito puede dificultar esto.

Optimizaciones entre procedimientos

La optimización entre procedimientos funciona en todo el programa, a través de los límites de procedimientos y archivos. Trabaja estrechamente con contrapartes intraprocedimiento, realizado con la cooperación de una parte local y una parte global. Las optimizaciones típicas entre procedimientos son: inserción de procedimientos , eliminación de código muerto entre procedimientos , propagación constante entre procedimientos y reordenación de procedimientos . 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, la GCC de código abierto fue criticada por la falta de optimizaciones y análisis interprocedimiento potentes, aunque esto ahora está mejorando. Otro compilador de código abierto con una completa infraestructura de análisis y optimización es Open64 .

Debido al tiempo y espacio extra 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 simples y directas que requieren poco tiempo de compilación hasta las elaboradas y complejas que involucran cantidades considerables de tiempo de compilación. En consecuencia, los compiladores a menudo proporcionan 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 no especificar 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 de compilador que podrían afectar una variedad de opciones de optimización, comenzando con el conocido -O2conmutador.

Un enfoque para aislar la optimización es el uso de los llamados optimizadores post-pass (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 mediante un compilador optimizador y la optimizan aún más. Los optimizadores posteriores a la pasada suelen trabajar 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 compilador portátil de C (pcc) de la década de 1980, que tenía un pase opcional que realizaría optimizaciones posteriores en el código ensamblador generado.

Otra consideración es que los algoritmos de optimización son complicados y, especialmente cuando se utilizan 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 que no quede claro que la lógica de optimización esté fallando. En el caso de errores internos, el problema se puede mejorar parcialmente mediante una técnica de programación "a prueba de fallas" en la que la lógica de optimización en el compilador se codifica de tal manera que se detecta una falla, se emite un mensaje de advertencia y el resto de la compilación. procede a la finalización con éxito.

Historia

Los primeros compiladores de la década de 1960 a menudo se preocupaban principalmente por compilar código de manera correcta o eficiente, de modo que los tiempos de compilación eran una preocupación importante. Un compilador de optimización temprano notable 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 decayera. Esto co-evolucionó con el desarrollo de chips RISC y características avanzadas del procesador como la programación de instrucciones y la ejecución especulativa, que fueron diseñadas para ser dirigidas a la optimización de compiladores en lugar de código ensamblador escrito por humanos.

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

Ver también

Referencias

enlaces externos