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 ciclo durante cada iteración, y su valor es el mismo para cada iteración, puede mejorar enormemente la eficiencia sacarla del ciclo y calcular su valor solo una vez antes de que comience el ciclo. [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 dentro de un bucle hacia fuera del bucle duplicando el cuerpo del bucle dentro de cada una de las cláusulas if y else del condicional.
canalización de software
El 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 cualquier optimización, 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 agrupando 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]

Un enfoque para aislar la optimización es el uso de los llamados optimizadores post-paso (algunas de las cuales versiones comerciales se remontan al software mainframe de finales de los años 1970). [18] 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 nivel de lenguaje ensamblador o código de máquina (a diferencia de los compiladores que optimizan representaciones intermedias de programas). Un ejemplo de ello es el compilador portátil de C (pcc) de la década de 1980, que tenía un pase opcional que realizaría optimizaciones posteriores en el código ensamblador generado. [19]

Otra consideración es que los algoritmos de optimización son complicados y, especialmente cuando se usan para compilar lenguajes de programación grandes y complejos, pueden contener errores que introducen errores en el código generado o causan errores internos durante la compilación. Los errores del compilador de cualquier tipo pueden resultar desconcertantes para el usuario, pero especialmente en este caso, ya que puede no estar claro que la lógica de optimización sea la culpable. [20] En el caso de errores internos, el problema se puede solucionar 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 manera que se detecte un fallo, se emita un mensaje de advertencia y el resto de la compilación continúa hasta su finalización exitosa. [21]

Historia

Los primeros compiladores de la década de 1960 a menudo se preocupaban principalmente simplemente por compilar código de manera correcta o eficiente, de modo que los tiempos de compilación eran una preocupación importante. Uno de los primeros compiladores de optimización notables fue el compilador IBM FORTRAN H de finales de la década de 1960. [16] 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). [22] A finales de la década de 1980, la optimización de los compiladores era lo suficientemente efectiva como para que la programación en lenguaje ensamblador disminuyera. 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 fueron diseñados para ser atacados por compiladores optimizadores en lugar de código ensamblador escrito por humanos. [ cita necesaria ]

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

Ver también

Referencias

  1. ^ Ah, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1986). Compiladores: principios, técnicas y herramientas . Reading, Massachusetts: Addison-Wesley. pag. 585.ISBN​ 0-201-10088-6.
  2. ^ Aho, Sethi y Ullman, Compiladores , p. 554.
  3. ^ ab Cooper, Keith D .; Torczon, Linda (2003) [1 de enero de 2002]. Ingeniería de un compilador . Morgan Kaufman . págs.404, 407. ISBN 978-1-55860-698-2.
  4. ^ ab Aho, Sethi y Ullman, Compiladores , p. 596.
  5. ^ "Microsoft Learn: acciones proféticas de la tienda". Microsoft .
  6. ^ abc Clinton F. Goss (agosto de 2013) [Publicado por primera vez en junio de 1986]. Optimización del código de máquina: mejora del código objeto ejecutable (PDF) (tesis doctoral). vol. Informe técnico n.° 246 del Departamento de Informática. Instituto Courant, Universidad de Nueva York. arXiv : 1308.4815 . Código Bib : 2013arXiv1308.4815G. Archivado (PDF) desde el original el 9 de octubre de 2022 . Consultado el 22 de agosto de 2013 .
    • Clinton F. Goss (2013) [1986]. Optimización del código de máquina: mejora del código objeto ejecutable (tesis doctoral). Instituto Courant, Universidad de Nueva York.
  7. ^ Aho, Sethi y Ullman, Compiladores , págs. 596–598.
  8. ^ Aho, Sethi y Ullman, Compiladores , págs. 592–594.
  9. ^ Steven Muchnick; Muchnick y asociados (15 de agosto de 1997). Implementación de diseño de compilador avanzado . Morgan Kaufman. págs. 329–. ISBN 978-1-55860-320-2. plegado constante.
  10. ^ Wegman, Mark N. y Zadeck, F. Kenneth. "Propagación constante con ramas condicionales". Transacciones ACM sobre lenguajes y sistemas de programación , 13 (2), abril de 1991, páginas 181-210.
  11. ^ Haga clic, Clifford y Cooper, Keith. "Combinando análisis, combinando optimizaciones", ACM Transactions on Programming Languages ​​and Systems , 17(2), marzo de 1995, páginas 181-196
  12. ^ ab Manual del compilador Cx51, versión 09.2001, p155, Keil Software Inc.
  13. ^ Robert BK Dewar ; Martín Carlos Golumbic ; Clinton F. Goss (agosto de 2013) [Publicado por primera vez en octubre de 1979]. MICRO ESCUPITBOL . Informe Técnico del Departamento de Informática. vol. 11. Instituto Courant de Ciencias Matemáticas. arXiv : 1308.6096 . Código Bib : 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