Compilador-optimizador

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, la huella 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 utilizando 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 tales 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 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 todo el programa. 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 mirillaPor lo general, se realizan tarde en el 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 más corta de instrucciones. Por ejemplo, una multiplicación de un valor por 2 podría ejecutarse de manera más eficiente desplazando el valor a la izquierda o sumando el valor a sí mismo (este ejemplo también es una instancia de reducción de fuerza).Optimizaciones localesEstos 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 entre saltos.Optimizaciones globalesEstos 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Éstos actúan sobre las sentencias que componen un bucle, como un bucle for, por ejemplo, un movimiento de código invariable en bucle. Las optimizaciones de bucle pueden tener un impacto significativo porque muchos programas pasan un gran porcentaje de su tiempo dentro de los bucles.Optimizaciones de tiendas proféticasEstos permiten que las operaciones de almacenamiento ocurran 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 reorganización de código que preservan la semántica de los programas correctamente sincronizados.Optimización interprocedimiento, de programa completo o de tiempo de enlaceEstos analizan todo el código fuente de un programa. La mayor cantidad de información extraída hace que las optimizaciones puedan ser más efectivas que cuando solo se tiene acceso a información local, es decir, dentro de una sola función. Este tipo de optimización también puede permitir que se realicen nuevas técnicas. Por ejemplo, función en línea, donde una llamada a una función se reemplaza por una copia del cuerpo de la función.Optimización de código máquina y optimizador de código objetoEstos analizan la imagen de la tarea ejecutable del programa después de que se haya vinculado todo un 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.

Además de las optimizaciones de ámbito, existen otras dos categorías generales de optimización:Lenguaje de programación independiente frente a dependiente del lenguajeLa mayoría de los lenguajes de alto nivel comparten construcciones y abstracciones de programación comunes: decisión (si, interruptor, caso), bucle (para, mientras, repetir... hasta, hacer... mientras) y encapsulación (estructuras, objetos). Por lo tanto, se pueden usar 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 matrices (ver análisis de alias). Sin embargo, lenguajes como PL/I (que también admite punteros) tienen compiladores de optimización sofisticados disponibles para lograr un mejor rendimiento de otras formas. Por el contrario, algunas características del idioma facilitan ciertas 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áquinaMuchas optimizaciones que operan sobre conceptos abstractos de programación (bucles, objetos, estructuras) son independientes de la máquina objetivo del compilador, pero muchas de las optimizaciones más efectivas son aquellas que aprovechan mejor las características especiales de la plataforma objetivo. Los ejemplos son instrucciones que hacen varias cosas a la vez, como decrementar el registro y la bifurcación 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 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" 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 canalización. Sin embargo,

Factores que afectan la optimización

la maquina en siMuchas 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 compilador se pueda usar 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 compiladores optimizados que siguen este enfoque.La arquitectura de la CPU de destinoNúmero de registros de la 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 escribir ni 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 (la cantidad de instrucciones completadas por período de tiempo, generalmente 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 llevar a cabo una determinada tarea, y el CISC suele ofrecer más alternativas que el RISC.
• Tuberías: una tubería 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 las instrucciones en varias etapas: decodificación de instrucciones, decodificación de direcciones, recuperación de memoria, recuperación de registros, cómputo, 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 en la canalización pero que aún no se ha completado. Los conflictos de canalización pueden provocar bloqueos de canalización: donde la CPU desperdicia ciclos esperando que se resuelva un conflicto.

Los compiladores pueden programar o reordenar las instrucciones para que las paradas de la canalización 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 canalización.

Aquí nuevamente, las instrucciones deben programarse 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 (asignación directa, asociativo de 2/4/8/16 vías, totalmente asociativo): las 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 los bucles internos en varios algoritmos) de repente no cabe en la memoria caché. Además, las cachés que no son totalmente asociativas tienen mayores posibilidades de colisiones de caché, incluso en una caché sin llenar.
• Tasas de transferencia de caché/memoria: dan al compilador una indicación de la penalización por errores de caché. Esto se utiliza principalmente en aplicaciones especializadas.

Uso previsto del código generadodepuraciónMientras 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 "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 generalCon mucha frecuencia, 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 que tienen diferentes características de temporización, caché o memoria. Como resultado, es posible que el código no esté ajustado a ninguna CPU en particular, o puede estar ajustado para funcionar mejor en la CPU más popular y aún así funcionar aceptablemente bien en otras CPU.Uso especialSi el software se compila para usarse en una o varias máquinas muy similares, con características conocidas, entonces el compilador puede ajustar en gran medida el código generado para 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 de paralelización especiales.Sistemas embebidosEstos son un caso común de uso especial. El software integrado se puede ajustar con precisión a una CPU y un tamaño de memoria exactos. Además, el costo o la confiabilidad del sistema pueden ser más importantes que la velocidad del código. Por ejemplo, los compiladores para software embebido 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 embebida. 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 podría 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únEl caso común puede tener propiedades únicas que permitan un camino rápido a expensas de un camino lento. Si se toma la ruta rápida con mayor frecuencia, el resultado es un mejor rendimiento general.Evite la redundanciaReutilice los resultados que ya están calculados y guárdelos para su uso posterior, en lugar de volver a calcularlos.Menos códigoElimine los cálculos innecesarios y los valores intermedios. Menos trabajo para la CPU, el caché y la memoria generalmente da como resultado una ejecución más rápida. Alternativamente, en los sistemas integrados, menos código genera un menor costo del producto.Menos saltos usando código de línea recta, también llamado código sin bifurcacionesCódigo menos complicado. Los saltos (ramificaciones condicionales o incondicionales) interfieren con la captación previa de instrucciones, lo que ralentiza el código. El uso de la inserción o el desenrollado de bucles puede reducir la bifurcació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.LocalidadEl código y los datos a los que se accede muy juntos en el tiempo deben colocarse juntos en la memoria para aumentar la localidad espacial de referencia.Explotar la jerarquía de la memoriaLos accesos a la memoria son cada vez más caros 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 los cachés, luego en la memoria principal, antes de ir al disco.paralelizarReordene las operaciones para permitir que se realicen múltiples cálculos en paralelo, ya sea a nivel de instrucción, memoria o subproceso.Información más precisa es mejorCuanto 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 ayudarLa 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 fuerzaReemplace operaciones complejas, difíciles o costosas por otras más simples. Por ejemplo, reemplazar la división por una constante con la multiplicación por su recíproco, o usar 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

Algunas técnicas de optimización diseñadas principalmente para operar en bucles incluyen:Análisis de variables de inducciónAproximadamente, 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 adecuadamente cada vez que se cambia la variable de bucle. Esta es una reducción de la fuerza y ​​también puede permitir que las definiciones de la variable de índice se conviertan en código inactivo. Esta información también es útil para la verificación de límites, eliminación y análisis de dependencia, entre otras cosas.Fisión en bucle o distribución en bucleLa fisión de bucles intenta dividir un bucle en múltiples bucles sobre el mismo rango de índice, pero cada uno tomando solo una parte del cuerpo del bucle. Esto puede mejorar la localidad de referencia, tanto de los datos a los que se accede en el bucle como del código en el cuerpo del bucle.Fusión de bucles o combinación de bucles o embestida de bucles o atasco de buclesOtra técnica que intenta reducir la sobrecarga del bucle. Cuando dos bucles adyacentes iteren la misma cantidad 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 bucleEsta técnica cambia un ciclo while estándar en un ciclo do/while (también conocido como repetir/hasta) envuelto en un condicional if, lo que reduce el número de saltos en dos, para los casos en que se ejecuta el ciclo. Hacerlo duplica la verificación de condición (aumentando el tamaño del código), pero es más eficiente porque los saltos generalmente provocan 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 bucleEstas 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, según el diseño de la matriz.Movimiento de código invariable en bucleSi se calcula una cantidad dentro de un ciclo durante cada iteración, y su valor es el mismo para cada iteración, puede mejorar enormemente la eficiencia para sacarlo del ciclo y calcular su valor solo una vez antes de que comience el ciclo. 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 de anidamiento de buclesAlgunos algoritmos generalizados, como la multiplicación de matrices, tienen un comportamiento de caché muy pobre y accesos de memoria excesivos. La optimización de anidamiento de bucles aumenta el número de aciertos de caché realizando la operación en bloques pequeños y utilizando un intercambio de bucles.Inversión de bucleLa inversión de bucle invierte el orden en que se asignan los valores a la variable de í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 del ciclo contribuye a un código más pequeño, ya que cuando el índice del ciclo se reduce, la condición que debe cumplirse para que el programa en ejecución salga del ciclo es una comparación con cero. A menudo, esta es 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 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, sería necesario ejecutar varias instrucciones para evaluar la comparación.Desenrollado de bucleEl desenrollado duplica el cuerpo del ciclo varias veces, para disminuir la cantidad de veces que se prueba la condición del ciclo y la cantidad de saltos, lo que perjudica el rendimiento al afectar la canalización de instrucciones. Una optimización de "menos saltos". Desplegar 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 bucleLa división de bucles intenta simplificar un bucle o eliminar las dependencias dividiéndolo en múltiples bucles que tienen el mismo cuerpo pero iteran sobre diferentes partes contiguas del rango del índice. Un caso especial útil es el pelado de bucles, que puede simplificar un bucle con una primera iteración problemática realizando esa iteración por separado antes de entrar en el bucle.Desconexión de bucleLa desactivación 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 softwareEl 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 ciclo cerrado, esta técnica oculta la latencia entre la carga y el uso de valores.Paralelización automáticaUn bucle se convierte en un código de subprocesos múltiples o vectorizado (o incluso en ambos) para utilizar múltiples procesadores simultáneamente en una máquina multiprocesador de memoria compartida (SMP), incluidas las máquinas de varios núcleos.

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 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 comunesEn 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)eso no cambiará, por lo que solo calculan su valor una vez.Plegado y propagación constantes.reemplazar expresiones que consisten en constantes (p. ej., 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 de variables de inducciónconsulte la discusión anterior sobre el análisis de variables de inducción.Clasificación de alias y análisis de punterosen presencia de punteros, es difícil realizar optimizaciones, ya que potencialmente cualquier variable puede haber cambiado cuando se asigna una ubicación de memoria. Al especificar qué punteros pueden alias de qué variables, los punteros no relacionados pueden ignorarse.Eliminación de tiendas muertaseliminación de asignaciones a variables que no se leen posteriormente, ya sea porque finaliza el tiempo de vida 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 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.Numeración de valores globalesGVN elimina la redundancia al construir un gráfico de valores del programa y luego determinar qué valores se calculan mediante expresiones equivalentes. GVN es capaz de identificar alguna redundancia que la eliminación de subexpresiones comunes no puede, y viceversa.Propagación constante condicional dispersaCombina propagación constante, plegamiento constante y eliminación de código inactivo, y mejora lo que es posible al ejecutarlos por separado. 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.

Optimizaciones del generador de código

Registrar asignaciónLas variables utilizadas con mayor frecuencia deben mantenerse en los registros del procesador para un acceso más rápido. Para encontrar qué variables colocar 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 está coloreado usando, por ejemplo, el algoritmo de Chaitin usando la misma cantidad de colores que 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ónLa 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 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 operaciones aritméticas. con menos almacenamiento.Programación de instruccionesLa programación de instrucciones es una optimización importante para los procesadores canalizados modernos, que evita estancamientos o burbujas en la canalización al agrupar instrucciones sin dependencias juntas, mientras se tiene cuidado de preservar la semántica original.RematerializaciónLa rematerialización recalcula un valor en lugar de cargarlo desde la memoria, evitando el acceso a la memoria. Esto se realiza junto con la asignación de registros para evitar derrames.factorización de códigoSi 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. A menudo, esto puede compartir código para la configuración de subrutinas y, a veces, recurrencia de cola.TrampolinesMuchas CPU tienen instrucciones de llamada a subrutinas 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 en poca memoria pueden acceder a las rutinas en cualquier dirección. Esto multiplica el ahorro de espacio de la factorización de código.Cálculos de reordenaciónBasados ​​en la programación lineal entera, 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 secuencias que pueden factorizarse 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 llamadas de seguimientoUna llamada de función consume espacio de pila e implica cierta sobrecarga relacionada con el paso de parámetros y el vaciado de la memoria 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 llamada de cola.Deforestación (fusión de estructuras de datos)En lenguajes donde es común que se aplique una secuencia de transformaciones a una lista, la deforestación intenta eliminar la construcción de estructuras de datos intermedias.Evaluación parcial

Otras optimizaciones

Eliminación de verificación de límitesMuchos lenguajes, como Java, imponen la verificación de límites de todos los accesos a matrices. Este es un cuello de botella de rendimiento grave en ciertas aplicaciones, como el código científico. La eliminación de la verificación de límites permite que el compilador elimine de manera segura la verificació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 de desfase 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ódigoEl reordenamiento de bloques de código altera el orden de los bloques básicos en un programa para reducir las ramificaciones condicionales y mejorar la localidad de referencia.Eliminación de código muertoElimina instrucciones que no afectarán el comportamiento del programa, por ejemplo, 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 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 (p. ej., la asignación de una constante a una variable) aparecen dentro de un ciclo, se pueden sacar 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 macroexpansiónCuando 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 la sobrecarga relacionada 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. En general, la inserción es útil en el código crítico para el rendimiento que realiza una gran cantidad de llamadas a procedimientos pequeños. Una optimización de "menos saltos". Las declaraciones de los lenguajes de programación imperativos también son un ejemplo de tal optimización. Aunque las declaraciones podrían implementarse con llamadas a funciones, casi siempre se implementan con código en línea.Saltar enhebradoEn 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 macrosUna 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 comunes con llamadas a los subprogramas correspondientes. 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. 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, pero las heurísticas eficientes alcanzan resultados casi óptimos.Reducción de colisiones de caché(por ejemplo, interrumpiendo la alineación dentro de una página)Reducción de altura de pilaReorganice el árbol de expresiones para minimizar los recursos necesarios para la evaluación de expresiones.Prueba de reordenaciónSi tenemos dos pruebas que son la condición de algo, primero podemos tratar con las pruebas más simples (p. ej., comparar una variable con algo) y solo luego con las pruebas complejas (p. ej., aquellas que requieren una llamada de función). Esta técnica complementa la evaluación perezosa, pero solo se puede usar cuando las pruebas no dependen unas de otras. La semántica de cortocircuito puede dificultar esto.

Optimizaciones interprocedimiento

La optimización entre procedimientos 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 manera 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 toman 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 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 varias opciones de comandos del compilador que podían afectar una variedad de opciones de optimización, comenzando con el -O2interruptor familiar.

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 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 no estar claro que la lógica de optimización tiene la culpa. En el caso de errores internos, el problema puede mejorarse 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 atrapa una falla, se emite un mensaje de advertencia y el resto de la compilación. procede a la finalización exitosa.

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 puntero
• Análisis de forma
• Análisis de escape
• Análisis de acceso a matrices
• Análisis de dependencia
• Análisis de flujo de control
• Análisis de flujo de datos
  • Análisis de cadena de definición de uso
  • Análisis de variables en vivo
  • Análisis de expresión disponible