stringtranslate.com

Optimización del compilador

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

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

Categorización

Las optimizaciones se clasifican de formas diversas y superpuestas.

Ámbito local vs. ámbito global

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

Las optimizaciones de alcance local utilizan información local de un bloque básico . [5] Dado que los bloques básicos no tienen flujo de control, estas optimizaciones necesitan muy poco análisis, lo que ahorra tiempo y reduce los requisitos de almacenamiento, pero esto también significa que no se conserva ninguna información entre saltos.

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

Optimización de mirillas

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

Optimización interprocedimental

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

Optimización del tiempo de enlace

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

Optimización de código de máquina y de objeto

La optimización de código de máquina utiliza un optimizador de código de objeto para analizar la imagen de la tarea ejecutable del programa después de que se haya vinculado todo el código de máquina ejecutable . Algunas de las técnicas que se pueden aplicar en un ámbito más limitado, como la compresión de macros que ahorra espacio al colapsar secuencias comunes de instrucciones, son más efectivas cuando la imagen completa de la tarea ejecutable está disponible para el análisis. [6]

Independiente del lenguaje vs. dependiente del lenguaje

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

Independiente de la máquina vs. dependiente de la máquina

Muchas optimizaciones que operan sobre conceptos de programación abstracta (bucles, objetos, estructuras) son independientes de la máquina a la que apunta el compilador, pero muchas de las optimizaciones más efectivas son aquellas que aprovechan mejor las características especiales de la plataforma de destino. Algunos ejemplos son las instrucciones que hacen varias cosas a la vez, como decrementar un registro y bifurcar si no es cero.

El siguiente es un ejemplo de una optimización local dependiente de la máquina. Para establecer un registro en 0, la forma obvia es usar la constante '0' en una instrucción que establece un valor de registro en una constante. Una forma menos obvia es realizar una operación XOR de un registro consigo mismo. Depende del compilador saber qué variante de instrucción utilizar. En muchas máquinas RISC , ambas instrucciones serían igualmente apropiadas, ya que ambas tendrían la misma longitud y tomarían el mismo tiempo. En muchos otros microprocesadores , como la familia Intel x86 , resulta que la variante XOR es más corta y probablemente más rápida, ya que no habrá necesidad de decodificar un operando inmediato ni de usar el "registro de operando inmediato" interno. Un problema potencial con esto es que XOR puede introducir una dependencia de datos en el valor anterior del registro, lo que causa un bloqueo de la tubería . Sin embargo, los procesadores a menudo tienen XOR de un registro consigo mismo como un caso especial que no causa bloqueos.

Factores que afectan la optimización

Maquina objetivo
La posibilidad y el deber de aplicar determinadas optimizaciones puede depender de las características de la máquina de destino. Algunos compiladores, como GCC y Clang, parametrizan factores dependientes de la máquina de modo que puedan utilizarse para optimizar para distintas máquinas. [7]
Arquitectura de CPU de destino
Arquitectura de la máquina
Uso previsto
Entre los casos notables se incluyen códigos diseñados para procesadores paralelos y vectoriales , para los cuales se utilizan compiladores paralelizadores especiales.
El firmware de un sistema integrado se puede optimizar para la CPU y la memoria de destino. El costo o la confiabilidad del sistema pueden ser más importantes que la velocidad del código. Por ejemplo, los compiladores para software integrado suelen ofrecer opciones que reducen el tamaño del código a expensas de la velocidad. Es posible que la temporización del código deba ser predecible, en lugar de lo más rápida posible, por lo que se puede deshabilitar el almacenamiento en caché del código, junto con las optimizaciones del compilador que lo requieran.

Temas comunes

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

Optimizar el caso común
El caso común puede tener propiedades únicas que permitan un camino rápido a expensas de un camino lento . Si se toma el camino rápido con mayor frecuencia, el resultado es un mejor rendimiento general.
Evite la redundancia
Reutilice los resultados ya calculados y almacénelos para usarlos más adelante, en lugar de volver a calcularlos.
Menos código
Elimine los cálculos innecesarios y los valores intermedios. Menos trabajo para la CPU, la memoria caché y la memoria generalmente da como resultado una ejecución más rápida. Por otra parte, en los sistemas integrados , menos código implica un menor costo del producto.
Menos saltos al utilizar código de línea recta , también llamado código sin ramificaciones
Código menos complicado. Los saltos ( ramificaciones condicionales o incondicionales ) interfieren con la precarga de instrucciones, lo que ralentiza el código. El uso de la inserción en línea o el desenrollado de bucles puede reducir las ramificaciones, a costa de aumentar el tamaño del archivo binario por la longitud del código repetido. Esto tiende a fusionar varios bloques básicos en uno solo.
Localidad
El código y los datos a los que se accede con poca distancia en el tiempo deben ubicarse próximos entre sí en la memoria para aumentar la localidad espacial de referencia .
Aprovechar la jerarquía de la memoria
Los accesos a la memoria son cada vez más costosos para cada nivel de la jerarquía de memoria , por lo que se deben colocar los elementos más utilizados primero en los registros, luego en los cachés, luego en la memoria principal, antes de ir al disco.
Paralelizar
Reordenar las operaciones para permitir que se realicen múltiples cálculos en paralelo, ya sea a nivel de instrucción, memoria o subproceso.
Es mejor una información más precisa
Cuanto más precisa sea la información que tenga el compilador, mejor podrá emplear cualquiera o todas estas técnicas de optimización.
Las métricas de tiempo de ejecución pueden ayudar
La información recopilada durante una ejecución de prueba se puede utilizar en la optimización guiada por perfiles . La información recopilada en tiempo de ejecución, idealmente con una sobrecarga mínima , se puede utilizar mediante un compilador JIT para mejorar dinámicamente la optimización.
Reducción de fuerza
Reemplace operaciones complejas, difíciles o costosas por otras más simples. Por ejemplo, reemplace la división por una constante por la multiplicación por su recíproco, o utilice el análisis de variables por inducción para reemplazar la multiplicación por un índice de bucle por la suma.

Técnicas específicas

Optimizaciones de bucle

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

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

Análisis de variables de inducción
En términos generales, si una variable en un bucle es una función lineal simple de la variable de índice, como j := 4*i + 1, se puede actualizar apropiadamente cada vez que se cambia la variable de bucle. Esto es una reducción de fuerza y ​​también puede permitir que las definiciones de la variable de índice se conviertan en código muerto . [4] : 596–598  Esta información también es útil para la eliminación de comprobación de límites y el análisis de dependencia , entre otras cosas.
Fisión de bucle o distribución de bucle
La fisión de bucles intenta dividir un bucle en varios bucles sobre el mismo rango de índices, y cada nuevo bucle ocupa solo una parte del cuerpo del bucle original. Esto puede mejorar la localidad de referencia tanto para los datos a los que se accede dentro del bucle como para el código en el cuerpo del bucle.
Fusión de bucles o combinación de bucles o embestida de bucles o bloqueo de bucles
Otra técnica que intenta reducir la sobrecarga de los bucles. Cuando dos bucles adyacentes se repiten la misma cantidad de veces independientemente de si se conoce esa cantidad en el momento de la compilación, sus cuerpos se pueden combinar siempre que no hagan referencia a los datos del otro.
Inversión de bucle
Esta técnica convierte un bucle while estándar en un bucle do/while (también conocido como repeat/until ) envuelto en una condición if , lo que reduce la cantidad de saltos en dos, para los casos en que se ejecuta el bucle. Al hacerlo, se duplica la verificación de la condición (lo que aumenta el tamaño del código), pero es más eficiente porque los saltos generalmente causan un bloqueo de la canalización . 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 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 invariante en bucle
Si una cantidad se calcula dentro de un bucle durante cada iteración, y su valor es el mismo para cada iteración, puede mejorar enormemente la eficiencia sacarla del bucle y calcular su valor solo una vez antes de que comience el bucle. [4] : 596  Esto es particularmente importante con las expresiones de cálculo de direcciones generadas por bucles sobre matrices. Para una implementación correcta, esta técnica debe usarse con inversión de bucle , porque no todo el código es seguro para ser sacado del bucle.
Optimización de anidación de bucles
Algunos algoritmos generalizados, como la multiplicación de matrices, tienen un comportamiento de caché muy deficiente y accesos excesivos a la memoria. La optimización del anidamiento de bucles aumenta la cantidad de accesos a la memoria caché al operar sobre bloques pequeños y al utilizar un intercambio de bucles.
Inversión de bucle
La inversión de bucle invierte el orden en el que se asignan los valores a la variable de índice. Se trata de una optimización sutil que puede ayudar a eliminar dependencias y, por lo tanto, permitir otras optimizaciones. Además, en algunas arquitecturas, la inversión de bucle contribuye a que el código sea más pequeño, ya que cuando se reduce el índice del bucle, la condición que se debe cumplir para que el programa en ejecución salga del bucle es una comparación con cero. A menudo, se trata de una instrucción especial sin parámetros, a diferencia de una comparación con un número, que necesita el número con el que comparar. Por lo tanto, la cantidad de bytes necesarios para almacenar el parámetro se ahorra utilizando la inversión de bucle. Además, si el número de comparación supera el tamaño de la palabra de la plataforma, en el orden de bucle estándar, se necesitarían ejecutar varias instrucciones para evaluar la comparación, lo que no es el caso con la inversión de bucle.
Desenrollado de bucle
El desenrollado duplica el cuerpo del bucle varias veces para reducir la cantidad de veces que se prueba la condición del bucle y la cantidad de saltos; las pruebas y los saltos pueden afectar el rendimiento al afectar la secuencia de instrucciones. Optimización de "menos saltos". El desenrollado completo de un bucle elimina toda la sobrecarga, pero requiere que se conozca la cantidad de iteraciones en el momento de la compilación.
División de bucle
La división de bucles intenta simplificar un bucle o eliminar dependencias al dividirlo en múltiples bucles que tienen los mismos cuerpos pero que iteran sobre diferentes porciones contiguas del rango de índices. Un caso especial útil es la separación de bucles , que puede simplificar un bucle con una primera iteración problemática al realizar esa iteración por separado antes de ingresar al bucle.
Desconmutación de bucle
Al deshacer la conmutación se mueve una condición desde el interior de un bucle al exterior del bucle duplicando el cuerpo del bucle dentro de cada una de las cláusulas if y else de la condición.
Canalización de software
El bucle se reestructura de tal manera que el trabajo realizado en una iteración se divide en varias partes y se realiza en varias iteraciones. En un bucle cerrado, esta técnica oculta la latencia entre la carga y el uso de valores.
Paralelización automática
Un bucle se convierte en código multiproceso o vectorizado (o incluso ambos) para utilizar múltiples procesadores simultáneamente en una máquina multiprocesador de memoria compartida (SMP), incluidas las máquinas de múltiples núcleos.

Optimizaciones de tiendas Prescient

Las optimizaciones de almacenamiento premonitorias permiten que las operaciones de almacenamiento se realicen antes de lo que se permitiría en el contexto de subprocesos y bloqueos. El proceso necesita alguna forma de saber de antemano qué valor se almacenará mediante la asignación que debería haber seguido. El propósito de esta relajación es permitir que la optimización del compilador realice ciertos tipos de reordenamientos de código que preserven la semántica de los programas sincronizados correctamente. [9]

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 se propagan determinadas propiedades de los datos mediante los bordes de control en el gráfico del flujo de control . Algunas de ellas son:

Eliminación de subexpresiones comunes
En la expresión (a + b) - (a + b)/4, "subexpresión común" se refiere a la duplicada (a + b). Los compiladores que implementan esta técnica se dan cuenta de que (a + b)no cambiará, por lo que solo calculan su valor una vez. [4] : 592–594 
Plegado y propagación constante
[10] reemplazar expresiones que consisten en constantes (por ejemplo, 3 + 5) con su valor final ( 8) en tiempo de compilación, en lugar de hacer el cálculo en tiempo de ejecución. Se utiliza en la mayoría de los lenguajes modernos.
Reconocimiento y eliminación de variables de inducción
Véase la discusión anterior sobre el análisis de variables de inducción .
Clasificación de alias y análisis de punteros
En presencia de punteros , es difícil realizar cualquier optimización, ya que potencialmente cualquier variable puede haber cambiado cuando se le asigna una ubicación de memoria. Al especificar qué punteros pueden crear alias de qué variables, se pueden ignorar los punteros no relacionados.
Eliminación de tiendas muertas
eliminación de asignaciones a variables que no se leen posteriormente, ya sea porque finaliza la vida útil de la variable o porque una asignación posterior sobrescribirá el primer valor.

Optimizaciones basadas en SSA

Estas optimizaciones están pensadas para realizarse después de transformar el programa en una forma especial llamada Asignación Única Estática , en la que cada variable se asigna en un solo lugar. Aunque algunas funcionan sin Asignación Única Estática, son más efectivas con Asignación Única Estática. Muchas optimizaciones enumeradas en otras secciones también se benefician sin cambios especiales, como la asignación de registros.

Numeración de valores globales
GVN elimina la redundancia mediante la construcción de un gráfico de valores del programa y luego determinando qué valores se calculan mediante expresiones equivalentes. GVN puede identificar cierta redundancia que la eliminación de subexpresiones comunes no puede, y viceversa.
Propagación constante condicional dispersa
Combina propagación constante, plegado constante y eliminación de código muerto , y mejora lo que es posible al ejecutarlos por separado. [11] [12] Esta optimización ejecuta simbólicamente el programa, propagando simultáneamente valores constantes y eliminando partes del gráfico de flujo de control que esto hace inalcanzables.

Optimizaciones del generador de código

Asignación de registros
Las variables que se usan con más frecuencia se deben guardar en los registros del procesador para que el acceso sea más rápido. Para encontrar qué variables poner en los registros, se crea un gráfico de interferencia. Cada variable es un vértice y cuando se usan dos variables al mismo tiempo (tienen un rango de intersección) tienen una arista entre ellas. Este gráfico se colorea utilizando, por ejemplo, el algoritmo de Chaitin, utilizando la misma cantidad de colores que registros. Si la coloración falla, una variable se "vierte" en la memoria y se vuelve a intentar la coloración.
Selección de instrucciones
La mayoría de las arquitecturas, en particular las arquitecturas CISC y aquellas con muchos modos de direccionamiento , ofrecen varias formas diferentes de realizar una operación particular, utilizando secuencias de instrucciones completamente diferentes. El trabajo del selector de instrucciones es hacer un buen trabajo en general al elegir qué instrucciones implementar con qué operadores en la representación intermedia de bajo nivel . Por ejemplo, en muchos procesadores de la familia 68000 y la arquitectura x86, se pueden usar modos de direccionamiento complejos en instrucciones como lea 25(a1,d5*4), a0, lo que permite que una sola instrucción realice una cantidad significativa de aritmética con menos almacenamiento.
Programación de instrucciones
La programación de instrucciones es una optimización importante para los procesadores canalizados modernos, que evita bloqueos o burbujas en la canalización al agrupar instrucciones sin dependencias, al mismo tiempo que se tiene cuidado de preservar la semántica original.
Rematerialización
La rematerialización recalcula un valor en lugar de cargarlo desde la memoria, lo que elimina el acceso a la memoria. Esto se realiza en conjunto con la asignación de registros para evitar derrames.
Factorización de código
Si varias secuencias de código son idénticas, o se pueden parametrizar o reordenar para que sean idénticas, se pueden reemplazar con llamadas a una subrutina compartida. Esto a menudo puede compartir código para la configuración de la subrutina y, a veces, la recursión de cola. [13]
Trampolines
Muchas CPU [ cita requerida ] tienen instrucciones de llamada a subrutinas más pequeñas para acceder a memoria baja. Un compilador puede ahorrar espacio utilizando estas pequeñas llamadas en el cuerpo principal del código. Las instrucciones de salto en memoria baja pueden acceder a las rutinas en cualquier dirección. Esto multiplica los ahorros de espacio a partir de la factorización de código. [13]
Reordenamiento de cálculos
Basados ​​en la programación lineal entera , los compiladores de reestructuración mejoran la localización de los datos y exponen más paralelismo al reordenar los cálculos. Los compiladores que optimizan el espacio pueden reordenar el código para alargar las secuencias que se pueden factorizar en subrutinas.

Optimizaciones del lenguaje funcional

Aunque muchos de ellos también se aplican a lenguajes no funcionales, se originan o son particularmente críticos en lenguajes funcionales como Lisp y ML .

Optimización de llamadas de cola
Una llamada de función consume espacio en la pila e implica cierta sobrecarga relacionada con el paso de parámetros y el vaciado de la caché de instrucciones. Los algoritmos recursivos de cola se pueden convertir en iteración a través de un proceso llamado eliminación de recursión de cola u optimización de llamada de cola.
Deforestación ( fusión de estructuras de datos )
En los idiomas donde es común aplicar una secuencia de transformaciones a una lista, la deforestación intenta eliminar la construcción de estructuras de datos intermedias.
Evaluación parcial

Otras optimizaciones

Eliminación de comprobación de límites
Muchos lenguajes, como Java , exigen la comprobación de límites en todos los accesos a matrices. Esto supone un grave obstáculo para el rendimiento en determinadas aplicaciones, como el código científico. La eliminación de la comprobación de límites permite al compilador eliminar de forma segura la comprobación de límites en muchas situaciones en las que puede determinar que el índice debe estar dentro de límites válidos; por ejemplo, si se trata de una variable de bucle simple.
Optimización del desplazamiento de la rama (dependiendo de la máquina)
Elija el desplazamiento de rama más corto que alcance el objetivo.
Reordenamiento de bloques de código
El reordenamiento de bloques de código altera el orden de los bloques básicos de un programa para reducir las ramas condicionales y mejorar la localidad de referencia.
Eliminación de código muerto
Elimina las instrucciones que no afectan el comportamiento del programa, por ejemplo, las definiciones que no tienen usos, llamadas código muerto . Esto reduce el tamaño del código y elimina los cálculos innecesarios.
Factorización de invariantes ( invariantes de bucle )
Si una expresión se ejecuta tanto cuando se cumple una condición como cuando no, se puede escribir solo una vez fuera de la declaración condicional. De manera similar, si ciertos tipos de expresiones (por ejemplo, la asignación de una constante a una variable) aparecen dentro de un bucle, se pueden sacar de él porque su efecto será el mismo sin importar si se ejecutan muchas veces o solo una vez. Esto también se conoce como eliminación de redundancia total. Una optimización similar pero más poderosa es la eliminación de redundancia parcial (PRE).
Expansión en línea o expansión macro
Cuando algún código invoca un procedimiento , es posible insertar directamente el cuerpo del procedimiento dentro del código que lo invoca en lugar de transferirle el control. Esto ahorra la sobrecarga relacionada con las llamadas a procedimientos, además de brindar una oportunidad para muchas optimizaciones diferentes específicas de parámetros, pero tiene el costo del espacio; el cuerpo del procedimiento se duplica cada vez que se llama al procedimiento en línea. Generalmente, la inserción en línea es útil en código crítico para el rendimiento que realiza una gran cantidad de llamadas a procedimientos pequeños. Una optimización de "menos saltos" [ fragmento de oración ] . Las declaraciones de lenguajes de programación imperativos también son un ejemplo de tal optimización. Aunque las declaraciones se pueden implementar con llamadas a funciones, casi siempre se implementan con inserción de código.
Salto de subprocesos
En esta optimización, se fusionan los saltos condicionales consecutivos basados ​​total o parcialmente en la misma condición.
Por ejemplo, a ,if (c) { foo; } if (c) { bar; }if (c) { foo; bar; }
y a .if (c) { foo; } if (!c) { bar; }if (c) { foo; } else { bar; }
Compresión de macros
Una optimización espacial que reconoce secuencias comunes de código, crea subprogramas ("macros de código") que contienen el código común y reemplaza las ocurrencias de las secuencias de código comunes con llamadas a los subprogramas correspondientes. [6] Esto se hace de manera más efectiva como una optimización de código de máquina , cuando todo el código está presente. La técnica se utilizó por primera vez para conservar espacio en un flujo de bytes interpretativo utilizado en una implementación de Macro Spitbol en microcomputadoras . [14] Se sabe que el problema de determinar un conjunto óptimo de macros que minimice el espacio requerido por un segmento de código dado es NP-completo , [6] pero las heurísticas eficientes alcanzan resultados casi óptimos. [15]
Reducción de colisiones de caché
(por ejemplo, alterando la alineación dentro de una página)
Reducción de la altura de la pila
Reorganizar un árbol de expresión para minimizar los recursos necesarios para la evaluación de la expresión. [ aclaración necesaria ]
Reordenamiento de pruebas
Si tenemos dos pruebas que son la condición para algo, podemos tratar primero con las pruebas más simples (por ejemplo, comparar una variable con algo) y solo después con las pruebas complejas (por ejemplo, aquellas que requieren una llamada a una función). Esta técnica complementa la evaluación diferida , pero se puede utilizar solo cuando las pruebas no dependen una de la otra. La semántica de cortocircuito puede dificultar esto.

Optimizaciones interprocedimentales

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

La optimización interprocedimental es común en los compiladores comerciales modernos de SGI , Intel , Microsoft y Sun Microsystems . Durante mucho tiempo, el GCC de código abierto fue criticado por la falta de análisis y optimizaciones interprocedimentales potentes, aunque esto ahora está mejorando. [16] Otro compilador de código abierto con una infraestructura completa de análisis y optimización es Open64 .

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

Consideraciones prácticas

Puede haber una amplia gama de optimizaciones que un compilador puede realizar, desde optimizaciones simples y directas que requieren poco tiempo de compilación hasta optimizaciones elaboradas y complejas que involucran cantidades considerables de tiempo de compilación. [4] : 15  En consecuencia, los compiladores a menudo proporcionan opciones a su comando o procedimiento de control para permitir que el usuario del compilador elija cuánta optimización solicitar; por ejemplo, el compilador IBM FORTRAN H permitió al usuario especificar ninguna optimización, optimización solo a nivel de registros u optimización completa. [4] : 737  En la década de 2000, era común que los compiladores, como Clang , tuvieran varias opciones de comando de compilador que pudieran afectar una variedad de opciones de optimización, comenzando con el conocido -O2interruptor. [17]

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

Otra consideración es que los algoritmos de optimización son complicados y, especialmente cuando se utilizan para compilar lenguajes de programación grandes y complejos, pueden contener errores que introducen errores en el código generado o causan errores internos durante la compilación. Los errores del compilador de cualquier tipo pueden ser desconcertantes para el usuario, pero especialmente en este caso, ya que puede no estar claro que la lógica de optimización sea la que falla. [19] En el caso de errores internos, el problema se puede mejorar parcialmente mediante una técnica de programación "a prueba de fallos" en la que la lógica de optimización en el compilador se codifica de tal manera que se detecta un fallo, se emite un mensaje de advertencia y el resto de la compilación continúa hasta completarse con éxito. [20]

Historia

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

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

Véase también

Referencias

  1. ^ Godbolt, Matt (12 de noviembre de 2019). "Optimizaciones en compiladores de C++". ACM Queue . Vol. 17, núm. 5.
  2. ^ "Optimización de código en el diseño de compiladores - Notas de GATE CSE".
  3. ^ "Conferencia 15: NP-completitud, optimización y separación" (PDF) . IE 511: Programación entera, primavera de 2021 .
  4. ^ abcdefghijk Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1986). Compiladores: principios, técnicas y herramientas . Reading, Massachusetts: Addison-Wesley. ISBN 0-201-10088-6.
  5. ^ ab Cooper, Keith D. ; Torczon, Linda (2003) [1 de enero de 2002]. Ingeniería de un compilador . Morgan Kaufmann . págs. 404, 407. ISBN 978-1-55860-698-2.
  6. ^ abc Clinton F. Goss (agosto de 2013) [Publicado por primera vez en junio de 1986]. Optimización de código de máquina: mejora del código de objeto ejecutable (PDF) (tesis doctoral). Vol. Informe técnico n.° 246 del Departamento de Ciencias de la Computación. Courant Institute, Universidad de Nueva York. arXiv : 1308.4815 . Bibcode :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 de código máquina: mejora del código de objeto ejecutable (tesis doctoral). Courant Institute, New York University.
  7. ^ "GCC - Opciones dependientes de la máquina". Proyecto GNU .
  8. ^ "RISC vs. CISC". cs.stanford.edu . Consultado el 15 de octubre de 2024 .
  9. ^ James Gosling ; Bill Joy ; Guy Steele . "17 subprocesos y bloqueos". La especificación del lenguaje Java (1.0 ed.). 17.8 Acciones de almacenamiento prescientes.
  10. ^ Steven Muchnick; Muchnick and Associates (15 de agosto de 1997). Implementación del diseño avanzado de compiladores . Morgan Kaufmann. págs. 329–. ISBN 978-1-55860-320-2. plegado constante.
  11. ^ Wegman, Mark N.; Zadeck, F. Kenneth (abril de 1991). "Propagación constante con ramas condicionales" (PDF) . ACM Transactions on Programming Languages ​​and Systems . 13 (2): 181–210. doi :10.1145/103135.103136.
  12. ^ Click, Clifford; Cooper, Keith. (marzo de 1995). "Combining Analyses, Combining Optimizations" (PDF) . ACM Transactions on Programming Languages ​​and Systems . 17 (2): 181–196. doi :10.1145/201059.201061.
  13. ^ ab Cx51 Manual del compilador, versión 09.2001, p155, Keil Software Inc.
  14. ^ Robert BK Dewar ; Martin Charles Golumbic ; Clinton F. Goss (agosto de 2013) [Publicado por primera vez en octubre de 1979]. MICRO SPITBOL . Informe técnico del Departamento de Ciencias de la Computación. Vol. 11. Courant Institute of Mathematical Sciences. arXiv : 1308.6096 . Código Bibliográfico :2013arXiv1308.6096D.
  15. ^ Martin Charles Golumbic ; Robert BK Dewar ; Clinton F. Goss (1980). "Macro Substitutions in MICRO SPITBOL - a Combinatorial Analysis". Proc. 11th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, Utilitas Math., Winnipeg, Canadá . Vol. 29. págs. 485–495.
  16. ^ Glazunov, NM (25 de noviembre de 2012). "Fundamentos de la investigación científica". arXiv : 1212.1651 [cs.OH].
  17. ^ Guelton, Serge (5 de agosto de 2019). "Personalizar el proceso de compilación con Clang: opciones de optimización". Red Hat.
  18. ^ Michael Evans (diciembre de 1982). "Ingeniería de software para el entorno Cobol". Comunicaciones de la ACM . 25 (12): 874–882. ​​doi :10.1145/358728.358732 . Consultado el 10 de agosto de 2013 .
  19. ^ Sun, Chengnian; et al. (18-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. 294-305. doi :10.1145/2931037.2931074. ISBN 9781450343909.S2CID8339241  .​
  20. ^ Schilling, Jonathan L. (agosto de 1993). "Programación a prueba de fallos en la optimización del compilador". ACM SIGPLAN Notices . 28 (8): 39–42. doi :10.1145/163114.163118. S2CID  2224606.

Enlaces externos