Optimización del compilador

Un compilador optimizador es un compilador diseñado para generar código optimizado en aspectos como minimizar el tiempo de ejecución del programa, el uso de memoria , el tamaño de almacenamiento y el consumo de energía. ^[1] La optimización generalmente se implementa como una secuencia de transformaciones de optimización , algoritmos que transforman el código para producir código semánticamente equivalente optimizado para algún aspecto. Por lo general, es un uso intensivo de la CPU y la memoria . ^[2] En la práctica, factores como la memoria disponible y la disposición de un programador a esperar la compilación limitan las optimizaciones que un compilador podría proporcionar. Las investigaciones indican que algunos problemas de optimización son NP-completos o incluso indecidibles . ^[3]

En general, la optimización no puede producir un resultado óptimo , lo que es imposible en un sentido general, ya que optimizar un aspecto puede degradar el rendimiento de otro. En cambio, las optimizaciones son métodos heurísticos para mejorar el uso de recursos en programas típicos. ^{[4] : 585}

Las optimizaciones se clasifican de formas diversas y superpuestas.

El alcance describe qué parte del código de entrada se considera para aplicar optimizaciones.

Las optimizaciones de alcance local utilizan información local de un bloque básico . ^[5] 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 ninguna información entre saltos.

Las optimizaciones de alcance global, también conocidas como métodos intraprocedimentales , actúan sobre funciones completas. ^[5] Esto les proporciona más información con la que trabajar, pero a menudo hace necesarios cálculos costosos. Es necesario realizar suposiciones de peor caso cuando se producen llamadas de función o se accede a variables globales porque hay poca información disponible sobre ellas.

Las optimizaciones de mirilla suelen realizarse en una fase avanzada del proceso de compilación, una vez que se ha generado el código de máquina . Esta optimización examina algunas instrucciones adyacentes (como "mirar a través de una mirilla" el código) para ver si se pueden reemplazar por una sola instrucción o una secuencia más corta de instrucciones. ^{[4] : 554} Por ejemplo, una multiplicación de un valor por dos se puede ejecutar de forma más eficiente desplazando el valor hacia la izquierda o sumando el valor a sí mismo (este ejemplo también es un ejemplo de reducción de fuerza ).

Las optimizaciones interprocedimentales analizan todo el código fuente de un programa. Cuanto mayor sea la cantidad de información consumida, más efectivas pueden ser las optimizaciones. La información se puede utilizar para diversas optimizaciones, incluida la inserción de funciones , donde una llamada a una función se reemplaza por una copia del cuerpo de la función.

La optimización en tiempo de enlace (LTO), u optimización de todo el programa, es una clase más general de optimización interprocedimental. Durante la LTO, el compilador tiene visibilidad entre las unidades de traducción, lo que le permite realizar optimizaciones más agresivas, como la inserción en línea entre módulos y la desvirtualización .

La optimización de código de máquina utiliza un optimizador de código de objeto para analizar 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 compresión de macros que ahorra espacio al colapsar secuencias comunes de instrucciones, son más efectivas cuando la imagen completa de la tarea ejecutable está disponible para el análisis. ^[6]

La mayoría de los lenguajes de programación de alto nivel comparten construcciones y abstracciones de programación comunes: ramificación (if, switch), bucles (for, while) y encapsulación (estructuras, objetos). Por lo tanto, se pueden utilizar técnicas de optimización similares en todos los lenguajes. Sin embargo, ciertas características del lenguaje dificultan algunas optimizaciones. Por ejemplo, los punteros en C y C++ dificultan la optimización de matrices (consulte el análisis de alias ). Sin embargo, lenguajes como PL/I que también admiten punteros tienen optimizaciones para matrices. Por el contrario, algunas características del lenguaje facilitan ciertas optimizaciones. Por ejemplo, en algunos lenguajes, 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 que el resultado de la función solo necesita calcularse una vez. En lenguajes donde se permite que las funciones tengan efectos secundarios, el compilador puede restringir dicha optimización a funciones que puede determinar que no tienen efectos secundarios.

Muchas optimizaciones que operan sobre conceptos de programación abstracta (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. Algunos ejemplos son las instrucciones que hacen varias cosas a la vez, como decrementar un registro y bifurcar si no es cero.

El siguiente es un ejemplo de una optimización local dependiente de la máquina. 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 realizar una operación XOR de 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 habrá necesidad de decodificar un operando inmediato ni de usar 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, lo que causa 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 bloqueos.

This section possibly contains original research. Please improve it by verifying the claims made and adding inline citations. Statements consisting only of original research should be removed. (August 2020) (Learn how and when to remove this message)

Maquina objetivo

La posibilidad y el deber de aplicar determinadas optimizaciones puede depender de las características de la máquina de destino. Algunos compiladores, como GCC y Clang, parametrizan factores dependientes de la máquina de modo que puedan utilizarse para optimizar para distintas máquinas. ^[7]

Arquitectura de CPU de destino

• Número de registros : los registros se pueden utilizar para optimizar el rendimiento. Las variables locales se pueden almacenar en registros en lugar de en la pila . Se puede acceder a resultados temporales o intermedios en registros en lugar de en una memoria más lenta.

• RISC vs. CISC : Los conjuntos de instrucciones CISC suelen tener longitudes de instrucción variables, ^[8] a menudo tienen un mayor número de instrucciones posibles que se pueden utilizar, y cada instrucción podría 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, normalmente hay menos combinaciones de registros y operaciones de memoria, y la tasa de emisión de instrucciones (la cantidad de instrucciones completadas por período de tiempo, normalmente un múltiplo entero del ciclo de reloj) suele ser constante en los casos en que la latencia de la memoria no es un factor. Puede haber varias formas de llevar a cabo una determinada tarea, y CISC suele ofrecer más alternativas que RISC. Los compiladores tienen que conocer los costos relativos entre las distintas instrucciones y elegir la mejor secuencia de instrucciones (consulte selección de instrucciones ).

• Pipelines : Un pipeline es esencialmente una CPU dividida en una línea de ensamblaje . Permite el uso de partes de la CPU para diferentes instrucciones al dividir la ejecución de instrucciones en varias etapas: decodificación de instrucciones, decodificación de direcciones, obtención de memoria, obtención de registros, cálculo, almacenamiento de registros, etc. Una instrucción podría estar en la etapa de almacenamiento de registros, mientras que otra podría estar en la etapa de obtención de registros. Los conflictos de pipeline ocurren cuando una instrucción en una etapa del pipeline depende del resultado de otra instrucción que está antes en el pipeline pero que aún no se ha completado. Los conflictos de pipeline pueden provocar bloqueos de pipeline : donde la CPU desperdicia ciclos esperando que se resuelva un conflicto. Los compiladores pueden programar o reordenar las instrucciones para que los bloqueos de pipeline ocurran con menos frecuencia.

• Número de unidades funcionales : algunas CPU tienen varias ALU y FPU que les permiten 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 canalización. Las instrucciones se pueden programar de modo que las unidades funcionales estén completamente cargadas.

Arquitectura de la máquina

• Tamaño y tipo de caché de la CPU (asignación directa, asociativa de 2/4/8/16 vías, totalmente asociativa): 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 cabe en la caché. Además, las cachés que no son totalmente asociativas tienen mayores probabilidades de colisiones de caché incluso en una caché vacía.

• Tasas de transferencia de memoria/caché: proporcionan al compilador una indicación de la penalización por errores de caché. Se utilizan principalmente en aplicaciones especializadas.

Uso previsto

• Depuración : durante el desarrollo, las optimizaciones suelen desactivarse para acelerar la compilación o para facilitar la depuración del código ejecutable. Las transformaciones de optimización, en particular las que reordenan el código, pueden dificultar la relación del código ejecutable con el código fuente.

• Uso general: se espera que el software preempaquetado se ejecute en una variedad de máquinas que pueden compartir el mismo conjunto de instrucciones, pero que tienen diferentes características de rendimiento. Es posible que el código no esté optimizado para ninguna máquina en particular, o que esté ajustado para funcionar mejor en la máquina más popular y no de manera óptima en otras.

• Uso especial: si el software se compila para máquinas con características uniformes, entonces el compilador puede optimizar en gran medida el código generado para esas máquinas.

Entre los casos notables se incluyen códigos diseñados para procesadores paralelos y vectoriales , para los cuales se utilizan compiladores paralelizadores especiales.

El firmware de un sistema integrado se puede optimizar para la CPU y la memoria de destino. El costo o la confiabilidad del sistema pueden ser más importantes que la velocidad del código. Por ejemplo, los compiladores para software integrado suelen ofrecer opciones que reducen el tamaño del código a expensas de la velocidad. Es posible que la temporización del código deba ser predecible, en lugar de lo más rápida posible, por lo que se puede deshabilitar el almacenamiento en caché del código, junto con las optimizaciones del compilador que lo requieran.

La optimización incluye los siguientes temas, a veces contradictorios.

Optimizar el caso común

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

Evite la redundancia

Reutilice los resultados ya calculados y almacénelos para usarlos más adelante, en lugar de volver a calcularlos.

Menos código

Elimine los cálculos innecesarios y los valores intermedios. Menos trabajo para la CPU, la memoria caché y la memoria generalmente da como resultado una ejecución más rápida. Por otra parte, en los sistemas integrados , menos código implica un menor costo del producto.

Menos saltos al utilizar código de línea recta , también llamado código sin ramificaciones

Código menos complicado. Los saltos ( ramificaciones condicionales o incondicionales ) interfieren con la precarga de instrucciones, lo que ralentiza el código. El uso de la inserción en línea o el desenrollado de bucles puede reducir las ramificaciones, 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 solo.

Localidad

El código y los datos a los que se accede con poca distancia en el tiempo deben ubicarse próximos entre sí en la memoria para aumentar la localidad espacial de referencia .

Aprovechar 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 memoria , por lo que se deben colocar los elementos más utilizados primero en los registros, luego en los cachés, luego en la memoria principal, antes de ir al disco.

Paralelizar

Reordenar las operaciones para permitir que se realicen múltiples cálculos en paralelo, ya sea a nivel de instrucción, memoria o subproceso.

Es mejor una información más precisa

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 , se puede utilizar mediante un compilador JIT para mejorar dinámicamente la optimización.

Reducción de fuerza

Reemplace operaciones complejas, difíciles o costosas por otras más simples. Por ejemplo, reemplace la división por una constante por la multiplicación por su recíproco, o utilice el análisis de variables por inducción para reemplazar la multiplicación por un índice de bucle por la suma.

La optimización de bucles actúa sobre las instrucciones que forman un bucle, como un bucle for , por ejemplo, código invariante de bucle motion . Las optimizaciones de bucles pueden tener un impacto significativo porque muchos programas pasan un gran porcentaje de su tiempo dentro de bucles. ^{[4] : 596}

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

Análisis de variables de inducción

En términos generales, si una variable en un bucle es una función lineal simple de la variable de índice, como j := 4*i + 1, se puede actualizar apropiadamente cada vez que se cambia la variable de bucle. Esto 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 . ^{[4] : 596–598} Esta información también es útil para la eliminación de comprobació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 bucles intenta dividir un bucle en varios bucles sobre el mismo rango de índices, y cada nuevo bucle ocupa solo una parte del cuerpo del bucle original. Esto puede mejorar la localidad de referencia tanto para los datos a los que se accede dentro del bucle como para el código en el cuerpo del bucle.

Fusión de bucles o combinación de bucles o embestida de bucles o bloqueo de bucles

Otra técnica que intenta reducir la sobrecarga de los bucles. Cuando dos bucles adyacentes se repiten la misma cantidad de veces independientemente de si se conoce esa cantidad 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 convierte un bucle while estándar en un bucle do/while (también conocido como repeat/until ) envuelto en una condición if , lo que reduce la cantidad de saltos en dos, para los casos en que se ejecuta el bucle. Al hacerlo, se duplica la verificación de la condición (lo que aumenta 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 la condición inicial se conoce 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 del bucle se indexan en una matriz, dicha transformación puede mejorar la localidad de referencia, según el diseño de la matriz.

Movimiento de código invariante en bucle

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 sacarla del bucle y calcular su valor solo una vez antes de que comience el bucle. ^{[4] : 596} 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 sacado del bucle.

Optimización de anidación de bucles

Algunos algoritmos generalizados, como la multiplicación de matrices, tienen un comportamiento de caché muy deficiente y accesos excesivos a la memoria. La optimización del anidamiento de bucles aumenta la cantidad de accesos a la memoria caché al operar sobre 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. Se trata de una optimización sutil que puede ayudar a eliminar dependencias y, por lo tanto, permitir otras optimizaciones. Además, en algunas arquitecturas, la inversión de bucle contribuye a que el código sea más pequeño, ya que cuando se reduce el índice del bucle, la condición que se debe cumplir para que el programa en ejecución salga del bucle es una comparación con cero. A menudo, se trata de una instrucción especial sin parámetros, a diferencia de una comparación con un número, que necesita el número con el que comparar. Por lo tanto, la cantidad de bytes necesarios para almacenar el parámetro se ahorra utilizando la inversión de bucle. Además, si el número de comparación supera el tamaño de la palabra de la plataforma, en el orden de bucle estándar, se necesitarían ejecutar varias instrucciones para evaluar la comparación, lo que no es el caso con la inversión de bucle.

Desenrollado de bucle

El desenrollado duplica el cuerpo del bucle varias veces para reducir la cantidad de veces que se prueba la condición del bucle y la cantidad de saltos; las pruebas y los saltos pueden afectar el rendimiento al afectar la secuencia de instrucciones. Optimización de "menos saltos". El desenrollado completo de un bucle elimina toda la sobrecarga, pero requiere que se conozca la cantidad 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 al dividirlo en múltiples bucles que tienen los mismos cuerpos pero que iteran sobre diferentes porciones contiguas del rango de índices. Un caso especial útil es la separación 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.

Desconmutación de bucle

Al deshacer la conmutación se mueve una condición desde el interior de un bucle hacia fuera del bucle duplicando el cuerpo del bucle dentro de cada una de las cláusulas if y else de la condición.

Canalización de software

El bucle 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 bucle 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 ambos) para utilizar múltiples procesadores simultáneamente en una máquina multiprocesador de memoria compartida (SMP), incluidas las máquinas de múltiples núcleos.

Las optimizaciones de almacenamiento premonitorias permiten que las operaciones de almacenamiento 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 se almacenará mediante 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 reordenamientos de código que preserven la semántica de los programas sincronizados correctamente. ^[9]

Las optimizaciones del flujo de datos , basadas en el análisis del flujo de datos , dependen principalmente de cómo se propagan determinadas propiedades de los datos mediante los bordes de control en el gráfico del flujo de control . Algunas de ellas son:

Eliminación de subexpresiones comunes

En la expresión (a + b) - (a + b)/4, "subexpresión común" se refiere a la duplicada (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. ^{[4] : 592–594}

Plegado y propagación constante

^[10] reemplazar expresiones que consisten 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 lenguajes modernos.

Reconocimiento y eliminación de variables de inducción

Véase 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 cualquier optimización, ya que potencialmente cualquier variable puede haber cambiado cuando se le asigna una ubicación de memoria. Al especificar qué punteros pueden crear alias de 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 porque una asignación posterior sobrescribirá el primer valor.

Estas optimizaciones están pensadas para 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 algunas funcionan sin Asignación Única Estática, son más efectivas con Asignación Única Estática. Muchas optimizaciones enumeradas en otras secciones también se benefician sin cambios especiales, como la asignación de registros.

Numeración de valores globales

GVN elimina la redundancia mediante la construcción de un gráfico de valores del programa y luego determinando qué valores se calculan mediante expresiones equivalentes. GVN puede identificar cierta 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 al ejecutarlos por separado. ^{[11] [12]} Esta optimización ejecuta simbólicamente el programa, propagando simultáneamente valores constantes y eliminando partes del gráfico de flujo de control que esto hace inalcanzables.

Asignación de registros

Las variables que se usan con más frecuencia se deben guardar en los registros del procesador para que el acceso sea 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 de intersección) tienen una arista entre ellas. Este gráfico se colorea utilizando, por ejemplo, el algoritmo de Chaitin, utilizando la misma cantidad de colores que registros. Si la coloración falla, una variable se "vierte" en la memoria y se vuelve a intentar la coloración.

Selección de instrucciones

La mayoría de las arquitecturas, en particular las arquitecturas CISC y aquellas con muchos modos de direccionamiento , ofrecen varias formas diferentes de realizar una operación 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 la arquitectura x86, se pueden usar modos de direccionamiento complejos en instrucciones 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 canalizados modernos, que evita bloqueos o burbujas en la canalización al agrupar instrucciones sin dependencias, al mismo 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 elimina 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 la subrutina y, a veces, la recursión de cola. ^[13]

Trampolines

Muchas CPU ^{[ cita requerida ]} tienen instrucciones de llamada a subrutinas más pequeñas para acceder a memoria baja. Un compilador puede ahorrar espacio utilizando estas pequeñas llamadas en el cuerpo principal del código. Las instrucciones de salto en memoria baja pueden acceder a las rutinas en cualquier dirección. Esto multiplica los ahorros de espacio a partir de la factorización de código. ^[13]

Reordenamiento de cálculos

Basados ​​en la programación lineal entera , los compiladores de reestructuración mejoran la localizació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.

Aunque muchos de ellos 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 de función consume espacio en la pila e implica cierta sobrecarga relacionada 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 recursión de cola u optimización de llamada de cola.

Deforestación ( fusión de estructuras de datos )

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

Evaluación parcial

Eliminación de comprobación de límites

Muchos lenguajes, como Java , exigen la comprobación de límites en todos los accesos a matrices. Esto supone un grave obstáculo para el rendimiento en 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 bucle simple.

Optimización del desplazamiento de la rama (dependiendo de la máquina)

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

Reordenamiento de bloques de código

La reordenación de bloques de código altera el orden de los bloques básicos de un programa para reducir las bifurcaciones condicionales y mejorar la localidad de referencia.

Eliminación de código muerto

Elimina las instrucciones que no afectan 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 los cálculos innecesarios.

Factorización de invariantes ( invariantes de bucle )

Si una expresión se ejecuta tanto cuando se cumple una condición como cuando no, 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 bucle, se pueden sacar 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 que lo invoca en lugar de transferirle el control. Esto ahorra la sobrecarga relacionada con las llamadas a procedimientos, además de brindar una oportunidad para muchas optimizaciones diferentes específicas de parámetros, pero tiene el costo del espacio; el cuerpo del procedimiento se duplica cada vez que se llama al procedimiento en línea. Generalmente, la inserción en línea es útil en código crítico para el rendimiento que realiza una gran cantidad de llamadas a procedimientos pequeños. Una optimización de "menos saltos" ^{[ fragmento de oración ]} . Las declaraciones de lenguajes de programación imperativos también son un ejemplo de tal optimización. Aunque las declaraciones se pueden implementar con llamadas a funciones, casi siempre se implementan con inserción de código.

Salto de subprocesos

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

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

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

Compresión de macros

Una optimización espacial 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 comunes con llamadas a los subprogramas correspondientes. ^[6] Esto se hace de manera más efectiva 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 espacio en un flujo de bytes interpretativo utilizado en una implementación de Macro Spitbol en microcomputadoras . ^[14] Se sabe que el problema de determinar un conjunto óptimo de macros que minimice el espacio requerido por un segmento de código dado es NP-completo , ^[6] pero las heurísticas eficientes alcanzan resultados casi óptimos. ^[15]

Reducción de colisiones de caché

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

Reducción de la altura de la pila

Reorganizar un árbol de expresión para minimizar los recursos necesarios para la evaluación de la expresión. ^{[ aclaración necesaria ]}

Reordenamiento de pruebas

Si tenemos dos pruebas que son la condición para algo, podemos tratar primero con las pruebas más simples (por ejemplo, comparar una variable con algo) y solo después con las pruebas complejas (por ejemplo, aquellas que requieren una llamada a una función). Esta técnica complementa la evaluación diferida , pero se puede utilizar solo cuando las pruebas no dependen una de la otra. La semántica de cortocircuito puede dificultar esto.

La optimización interprocedimental funciona en todo el programa, a través de los límites de los procedimientos y de los archivos. Funciona en estrecha colaboración con las contrapartes intraprocedimentales, y se lleva a cabo con la cooperación de una parte local y una parte global. Las optimizaciones interprocedimentales típicas son la inserción de procedimientos , la eliminación de código muerto interprocedimental, la propagación de constantes interprocedimentales y la reordenación de procedimientos. Como es habitual, el compilador debe realizar un análisis interprocedimental antes de sus optimizaciones reales. Los análisis interprocedimentales incluyen el análisis de alias, el análisis de acceso a matrices y la construcción de un gráfico de llamadas .

La optimización interprocedimental 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 análisis y optimizaciones interprocedimentales potentes, aunque esto ahora está mejorando. ^[16] Otro compilador de código abierto con una infraestructura completa de análisis y optimización es Open64 .

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

Puede haber una amplia gama de optimizaciones que un compilador puede realizar, desde optimizaciones simples y directas que requieren poco tiempo de compilación hasta optimizaciones elaboradas y complejas que involucran cantidades considerables de tiempo de compilación. ^{[4] : 15} 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 permitió al usuario especificar ninguna optimización, optimización solo a nivel de registros u optimización completa. ^{[4] : 737} En la década de 2000, era común que los compiladores, como Clang , tuvieran varias opciones de comando de compilador que pudieran afectar una variedad de opciones de optimización, comenzando con el conocido -O2interruptor. ^[17]

Un método para aislar la optimización es el uso de los denominados optimizadores post-pass (algunas versiones comerciales de los cuales datan del software mainframe de finales de los años 1970). ^[18] Estas herramientas toman la salida ejecutable de un compilador optimizador y la optimizan aún más. Los optimizadores post-pass suelen trabajar en el nivel de lenguaje ensamblador o código máquina (en contraste con los compiladores que optimizan representaciones intermedias de programas). Un ejemplo de ello es el Portable C Compiler (pcc) de los años 1980, que tenía un pase opcional que realizaba optimizaciones posteriores en el código ensamblador generado. ^{[4] : 736}

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 causan 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 sea la que falla. ^[19] En el caso de errores internos, el problema se puede mejorar parcialmente mediante una técnica de programación "a prueba de fallos" en la que la lógica de optimización en el compilador se codifica de tal manera que se detecta un fallo, se emite un mensaje de advertencia y el resto de la compilación continúa hasta completarse con éxito. ^[20]

Los primeros compiladores de la década de 1960 se preocupaban principalmente de compilar código de manera correcta o eficiente, de modo que los tiempos de compilación eran una preocupación importante. Un compilador optimizador notable fue el compilador IBM FORTRAN H de finales de la década de 1960. ^{[4] : 737} Otro de los primeros e importantes compiladores optimizadores, que fue pionero en varias técnicas avanzadas, fue el de BLISS (1970), que se describió en The Design of an Optimizing Compiler (1975). ^{[4] : 740, 779} A finales de la década de 1980, los compiladores optimizadores eran lo suficientemente efectivos como para que la programación en lenguaje ensamblador decayera. Esto coevolucionó con el desarrollo de chips RISC y funciones avanzadas de procesador como procesadores superescalares , ejecución fuera de orden y ejecución especulativa , que fueron diseñados para ser el objetivo de compiladores optimizadores en lugar de código ensamblador escrito por humanos. ^{[ cita requerida ]}

• Análisis de alias
• Análisis de punteros
• Análisis de forma
• Análisis de escape
• Análisis de acceso a matrices
• Análisis de dependencia
• Análisis del flujo de control
• Análisis del flujo de datos
  • Análisis de la cadena de uso-definición
  • Análisis de variables en vivo
  • Análisis de expresión disponible

• Eficiencia algorítmica
• Ejecución de funciones en tiempo de compilación
• Teorema del pleno empleo
• Compilación justo a tiempo (JIT)
• El método de Kildall
• Optimización guiada por perfiles
• Optimización de programas

• Manuales de optimización de Agner Fog  : documentación sobre la arquitectura del procesador x86 y la optimización de código de bajo nivel