stringtranslate.com

Optimización del compilador

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

La optimización del compilador generalmente se implementa mediante 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 utiliza 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 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 algú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. [1]

Tipos de optimización

Las técnicas utilizadas en la optimización se pueden dividir en 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 menores ganancias. Algunos ejemplos de alcances incluyen:

Optimizaciones de mirilla
Por lo general, se realizan al final del proceso de compilación, después de que se ha generado el código de máquina . Esta forma de optimización examina algunas instrucciones adyacentes (como "mirar el código a través de una mirilla") para ver si pueden reemplazarse por una sola instrucción o una secuencia más corta de instrucciones. [2] 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 sumando el valor a sí mismo (este ejemplo también es un ejemplo de reducción de fuerza ).
Optimizaciones locales
Estos sólo consideran información local a un bloque básico . [3] Dado que los bloques básicos no tienen un 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 los saltos.
Optimizaciones globales
Estos también se denominan "métodos intraprocedimientos" y actúan sobre funciones completas. [3] 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 se realizan llamadas a funciones o se accede a variables globales porque hay poca información disponible sobre ellas.
Optimizaciones de bucle
Estos actúan sobre las declaraciones que forman un bucle, como un bucle for , por ejemplo , código de movimiento invariante en bucle . Las optimizaciones de bucles pueden tener un impacto significativo porque muchos programas pasan un gran porcentaje de su tiempo dentro de bucles. [4]
Optimizaciones proféticas de la tienda
Estos 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 se almacenará en 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 preserven la semántica de los programas correctamente sincronizados. [5]
Optimización interprocedimiento
Estos 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 sólo se tiene 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, inserción de funciones , donde una llamada a una función se reemplaza por una copia del cuerpo de la función.
Optimización de todo el programa o del tiempo de enlace
La optimización del tiempo de enlace, a menudo denominada LTO, es una clase más general de optimización interprocedimiento. Durante LTO, el compilador/optimizador tiene visibilidad entre las unidades de traducción, lo que le permite realizar optimizaciones más agresivas como inserción entre módulos, desvirtualización , etc.
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 toda la imagen de la tarea ejecutable está disponible para su análisis. [6]

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

Lenguaje de programación : independiente versus dependiente del lenguaje
La mayoría de los lenguajes de alto nivel comparten abstracciones y construcciones de programación comunes: decisión (si, cambiar, caso), bucle (para, mientras, repetir... hasta, hacer... mientras) y encapsulación (estructuras, objetos). Por 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 las matrices (consulte el análisis de alias ). Sin embargo, lenguajes como PL/I (que también soporta punteros) tienen disponibles compiladores de optimización sofisticados para lograr un mejor rendimiento de varias otras maneras. Por el contrario, algunas características del lenguaje 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 sólo 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 libres de efectos secundarios. Esta optimización solo es posible cuando el optimizador tiene acceso a la función llamada.
Independiente de la máquina versus dependiente de la máquina
Muchas optimizaciones que operan sobre 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 mejor aprovechan las características especiales de la plataforma de destino. Algunos ejemplos son instrucciones que hacen varias cosas a la vez, como decrementar registro y bifurcar si no es cero.

El siguiente es un ejemplo de 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 realizar XOR en 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 tardarí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 una parada en la canalización . Sin embargo, los procesadores a menudo tienen XOR de un registro consigo mismo como un caso especial que no causa bloqueos.

Factores que afectan la optimización.

La maquina en si
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 se pueda utilizar una sola pieza de código compilador para optimizar diferentes máquinas simplemente alterando los parámetros de descripción de la máquina. GCC del Proyecto GNU 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 será optimizar el rendimiento. Las variables locales se pueden asignar en los registros y no en la pila . Los resultados temporales/intermedios se pueden dejar en registros sin escribir ni volver a leer desde la memoria.
Los compiladores pueden programar o reordenar instrucciones para que las paradas en la canalización se produzcan con menos frecuencia.
Una vez más, las instrucciones deben programarse de modo que las distintas unidades funcionales estén completamente alimentadas con instrucciones para ejecutar.
La arquitectura de la máquina.
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 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 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 que esté ajustado para funcionar mejor en la CPU más popular y aun así funcionar aceptablemente bien en otras CPU.
Uso para fines especiales
Si el software se compila para ser utilizado en una o varias máquinas muy similares, con características conocidas, entonces el compilador puede ajustar en gran medida el código generado a esas máquinas específicas, siempre que dichas opciones estén disponibles. Casos especiales importantes incluyen código diseñado para procesadores paralelos y vectoriales , para los cuales se emplean compiladores de paralelización especiales.
Sistemas embebidos
Estos son un caso común de uso para fines especiales. El software integrado se puede ajustar estrictamente 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 coste 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 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ú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 que ya están calculados 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, el caché y la memoria generalmente resulta en una ejecución más rápida. Alternativamente, en los sistemas integrados , menos código genera un menor costo del producto.
Menos saltos mediante el uso de código de línea recta , también llamado código sin ramas
Código menos complicado. Los saltos ( ramificaciones condicionales o incondicionales ) interfieren con la búsqueda previa de instrucciones, lo que ralentiza el código. El uso de líneas en línea o desenrollado de bucles puede reducir la ramificación, a costa de aumentar el tamaño del archivo binario según 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 estrechamente 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 caros para cada nivel de la jerarquía de la memoria , por lo que los elementos más utilizados se colocan primero en los registros, luego en las cachés, luego en la memoria principal, antes de ir al disco.
paralelizar
Reordene las operaciones para permitir que se realicen múltiples cálculos en paralelo, ya sea a nivel de instrucción, memoria o subproceso.
La 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 . Un compilador JIT puede utilizar la información recopilada en tiempo de ejecución, idealmente con una sobrecarga mínima, para mejorar dinámicamente la optimización.
Reducción de fuerza
Reemplazar 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ó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 adecuadamente cada vez que se cambia la variable del bucle. Esto 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 muerto . [7] 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 en bucle o distribución en bucle
La fisión de bucles intenta dividir un bucle en múltiples bucles en 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 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 interferencia de bucles
Otra técnica que intenta reducir la sobrecarga del bucle. Cuando dos bucles adyacentes iteran 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 a dos, para los casos en los 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 una parada en 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, dependiendo del 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 sólo una vez antes de que comience el bucle. [4] 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 sacarlo fuera del bucle.
Optimización del nido de bucles
Algunos algoritmos generalizados, como la multiplicación de matrices, tienen un comportamiento de caché muy pobre y accesos excesivos a la memoria. La optimización del nido de bucles aumenta el número de visitas a la caché al realizar la operación en bloques pequeños y utilizar un intercambio de bucles.
inversión de bucle
La 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 bucle contribuye a un código más pequeño, ya que cuando se reduce el índice del bucle, la condición que debe cumplirse para que el programa en ejecución salga del bucle es una comparación con cero. Suele ser 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 guarda mediante la inversión del bucle. Además, si el número de comparación excede el tamaño de palabra de la plataforma, en el orden de bucle estándar, sería necesario ejecutar varias instrucciones para evaluar la comparación, lo que no ocurre con la inversión de bucle.
Desenrollado del bucle
El desenrollado duplica el cuerpo del bucle varias veces, para 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. Una 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 del í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.
Desconexión de bucle
La desconexión mueve un condicional 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 del condicional.
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 varios procesadores simultáneamente en una máquina multiprocesador de memoria compartida (SMP), incluidas las máquinas multinúcleo.

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 los bordes de control propagan ciertas propiedades de los datos en el gráfico de flujo de control . Algunos de estos incluyen:

Eliminación de 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 eso (a + b)no cambiará y, por lo tanto, solo calculan su valor una vez. [8]
Plegado y propagación constantes.
[9] reemplazar expresiones que consisten en constantes (por ejemplo, 3 + 5) con su valor final ( 8) en tiempo de compilación, en lugar de realizar el cálculo en tiempo de ejecución. Utilizado en la mayoría de los idiomas 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 puntero.
En presencia de punteros , es difícil realizar optimizaciones, ya que potencialmente cualquier variable puede haberse cambiado cuando se asigna una ubicación de memoria. Al especificar qué punteros pueden crear alias sobre 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 deben realizarse después de transformar el programa en una forma especial llamada Static Single Assignment , 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 valores globales
GVN 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 escasa
Combina propagación constante, plegado constante y eliminación de código muerto , y mejora lo que es posible ejecutándolos por separado. [10] [11] 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

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 de vida que se cruza) tienen un borde entre ellas. Este gráfico se colorea usando, por ejemplo, el algoritmo de Chaitin usando tantos colores como registros. Si la coloración falla, una variable se "derrama" en la memoria y se vuelve a intentar la coloración.
Selección de instrucciones
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 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 canalizados modernos, que evita paradas o burbujas en el canal al agrupar instrucciones sin dependencias, teniendo cuidado de preservar la semántica original.
Rematerialización
La rematerialización recalcula un valor en lugar de cargarlo desde la memoria, impidiendo 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. A menudo, esto puede compartir código para la configuración de subrutinas y, a veces, la recursividad de cola. [12]
Trampolines
Muchas [ cita necesaria ] 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 generado por la factorización de código. [12]
Reordenar cálculos
Basados ​​en programación lineal entera , los compiladores de reestructuración mejoran la localidad 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 incluirse 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 finales
Una llamada a función consume espacio en la pila e implica cierta sobrecarga relacionada con el paso de parámetros y el vaciado del caché de instrucciones. Los algoritmos recursivos de cola se pueden convertir en iteración mediante 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ímites
Muchos lenguajes, como Java , imponen la verificación de límites de todos los accesos a matrices. Este es un grave cuello de botella en el rendimiento de determinadas aplicaciones, como el código científico. La eliminación de la verificación de límites permite al compilador eliminar 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 del desplazamiento de ramas (dependiente 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 usos, llamadas código muerto . Esto reduce el tamaño del código y elimina cálculos innecesarios.
Factorización de invariantes ( invariantes de bucle )
Si una expresión se lleva a cabo tanto cuando se cumple como cuando no se cumple una condición, 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 total de la redundancia. Una optimización similar pero más potente 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 la sobrecarga relacionada con las llamadas a procedimientos, además de brindar la oportunidad de realizar 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 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 frase ] . Los enunciados de los lenguajes de programación imperativos también son un ejemplo de dicha optimización. Aunque las declaraciones podrían implementarse con llamadas a funciones, casi siempre se implementan con código integrado.
Saltar enhebrado
En esta optimización, se fusionan 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 para .if (c) { foo; } if (!c) { bar; }if (c) { foo; } else { bar; }
Compresión de macros
Una optimización del espacio que reconoce secuencias comunes de código, crea subprogramas ("macros de código") que contienen el código común y reemplaza las apariciones de las secuencias de código común con llamadas a los subprogramas correspondientes. [6] Esto se hace más eficazmente como optimización del 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 . [13] Se sabe que el problema de determinar un conjunto óptimo de macros que minimice el espacio requerido por un segmento de código determinado es NP-completo , [6] pero las heurísticas eficientes logran resultados casi óptimos. [14]
Reducción de colisiones de caché
(por ejemplo, al alterar la alineación dentro de una página)
Reducción de altura de pila
Reorganice el árbol de expresiones para minimizar los recursos necesarios para la evaluación de expresiones. [ se necesita aclaración ]
Reordenamiento de pruebas
Si tenemos dos pruebas que son la condición para algo, primero podemos tratar con las pruebas más simples (por ejemplo, comparar una variable con algo) y sólo después con las pruebas complejas (por ejemplo, aquellas que requieren una llamada a función). Esta técnica complementa la evaluación diferida , pero sólo se puede utilizar cuando las pruebas no dependen unas de otras. La semántica de cortocircuito puede dificultar esto.

Optimizaciones interprocedimientos

La optimización entre procedimientos funciona en todo el programa, más allá de los límites de procedimientos y archivos. Trabaja estrechamente con contrapartes intraprocedimientos, llevado a cabo con la cooperación de una parte local y una parte global. Las optimizaciones interprocedurales típicas son: inserción de procedimientos , eliminación de códigos muertos entre procedimientos, propagación constante entre procedimientos y reordenamiento de procedimientos. Como es habitual, el compilador necesita realizar un análisis interprocedimiento antes de realizar las optimizaciones reales. Los análisis interprocedimentales incluyen análisis de alias, análisis de acceso a matrices y la construcción de un gráfico de llamadas .

La optimización interprocedimiento 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 [ cita necesaria ] por la falta de optimizaciones y análisis interprocedimientos potentes, aunque esto ahora está mejorando. [ cita necesaria ] 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 interprocedimiento, 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 interprocedimiento y otras optimizaciones costosas.

Consideraciones prácticas

Puede haber una amplia gama de optimizaciones que un compilador puede realizar, desde las simples y directas que requieren poco tiempo de compilación hasta las elaboradas y complejas que implican cantidades considerables de tiempo de compilación. [15] En consecuencia, los compiladores a menudo proporcionan opciones a su comando o procedimiento de control para permitir al usuario del compilador elegir 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. [16] En la década de 2000, era común que los compiladores, como Clang , tuvieran una serie de opciones de comando del compilador que podían afectar una variedad de opciones de optimización, comenzando con el conocido -O2interruptor. [17]

An approach to isolating optimization is the use of so-called post-pass optimizers (some commercial versions of which date back to mainframe software of the late 1970s).[18] These tools take the executable output by an optimizing compiler and optimize it even further. Post-pass optimizers usually work on the assembly language or machine code level (in contrast with compilers that optimize intermediate representations of programs). One such example is the Portable C Compiler (pcc) of the 1980s, which had an optional pass that would perform post-optimizations on the generated assembly code.[19]

Another consideration is that optimization algorithms are complicated and, especially when being used to compile large, complex programming languages, can contain bugs that introduce errors in the generated code or cause internal errors during compilation. Compiler errors of any kind can be disconcerting to the user, but especially so in this case, since it may not be clear that the optimization logic is at fault.[20] In the case of internal errors, the problem can be partially ameliorated by a "fail-safe" programming technique in which the optimization logic in the compiler is coded such that a failure is trapped, a warning message issued, and the rest of the compilation proceeds to successful completion.[21]

History

Early compilers of the 1960s were often primarily concerned with simply compiling code correctly or efficiently, such that compile times were a major concern. One notable early optimizing compiler was the IBM FORTRAN H compiler of the late 1960s.[16] Another of the earliest and important optimizing compilers, that pioneered several advanced techniques, was that for BLISS (1970), which was described in The Design of an Optimizing Compiler (1975).[22] By the late 1980s, optimizing compilers were sufficiently effective that programming in assembly language declined. This co-evolved with the development of RISC chips and advanced processor features such as instruction scheduling and speculative execution, which were designed to be targeted by optimizing compilers rather than by human-written assembly code.[citation needed]

List of static code analyses

See also

References

  1. ^ Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1986). Compilers: Principles, Techniques, and Tools. Reading, Massachusetts: Addison-Wesley. p. 585. ISBN 0-201-10088-6.
  2. ^ Aho, Sethi, and Ullman, Compilers, p. 554.
  3. ^ a b Cooper, Keith D.; Torczon, Linda (2003) [2002-01-01]. Engineering a Compiler. Morgan Kaufmann. pp. 404, 407. ISBN 978-1-55860-698-2.
  4. ^ a b Aho, Sethi, and Ullman, Compilers, p. 596.
  5. ^ "Microsoft Learn - Prescient Store Actions". Microsoft.
  6. ^ a b c Clinton F. Goss (August 2013) [First published June 1986]. Machine Code Optimization - Improving Executable Object Code (PDF) (Ph.D. dissertation). Vol. Computer Science Department Technical Report #246. Courant Institute, New York University. arXiv:1308.4815. Bibcode:2013arXiv1308.4815G. Archived (PDF) from the original on 2022-10-09. Retrieved 22 Aug 2013.
    • Clinton F. Goss (2013) [1986]. Machine Code Optimization - Improving Executable Object Code (PhD thesis). Courant Institute, New York University.
  7. ^ Aho, Sethi, and Ullman, Compilers, pp. 596–598.
  8. ^ Aho, Sethi, and Ullman, Compilers, pp. 592–594.
  9. ^ Steven Muchnick; Muchnick and Associates (15 August 1997). Advanced Compiler Design Implementation. Morgan Kaufmann. pp. 329–. ISBN 978-1-55860-320-2. constant folding.
  10. ^ Wegman, Mark N. and Zadeck, F. Kenneth. "Constant Propagation with Conditional Branches." ACM Transactions on Programming Languages and Systems, 13(2), April 1991, pages 181-210.
  11. ^ Click, Clifford and Cooper, Keith. "Combining Analyses, Combining Optimizations", ACM Transactions on Programming Languages and Systems, 17(2), March 1995, pages 181-196
  12. ^ a b Cx51 Compiler Manual, version 09.2001, p155, Keil Software Inc.
  13. ^ Robert B. K. Dewar; Martin Charles Golumbic; Clinton F. Goss (August 2013) [First published October 1979]. MICRO SPITBOL. Computer Science Department Technical Report. Vol. No. 11. Courant Institute of Mathematical Sciences. arXiv:1308.6096. Bibcode:2013arXiv1308.6096D.
  14. ^ Martín Charles Golumbic ; Robert BK Dewar ; Clinton F. Goss (1980). "Macrosustituciones en MICRO SPITBOL - un análisis combinatorio". Proc. XI Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación, Congressus Numerantium, Utilitas Math., Winnipeg, Canadá . 29 : 485–495.
  15. ^ Aho, Sethi y Ullman, Compiladores , p. 15.
  16. ^ ab Aho, Sethi y Ullman, Compiladores , p. 737.
  17. ^ Guelton, Serge (5 de agosto de 2019). "Personaliza el proceso de compilación con Clang: opciones de optimización". Sombrero rojo.
  18. ^ Ingeniería de software para el entorno Cobol. Portal.acm.org. Recuperado el 10 de agosto de 2013.
  19. ^ Aho, Sethi y Ullman, Compiladores , p. 736.
  20. ^ Sol, Chengnian; et al. (18 al 20 de julio de 2016). "Hacia la comprensión de los errores del compilador en GCC y LLVM". Actas del 25º Simposio internacional sobre pruebas y análisis de software . Issta 2016. págs. doi :10.1145/2931037.2931074. ISBN 9781450343909. S2CID  8339241.
  21. ^ Schilling, Jonathan L. (agosto de 1993). "Programación a prueba de fallos en la optimización del compilador". Avisos ACM SIGPLAN . 28 (8): 39–42. doi :10.1145/163114.163118. S2CID  2224606.
  22. ^ Aho, Sethi y Ullman, Compiladores , págs.740, 779.

enlaces externos