Compilador optimizador

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

Las optimizaciones de ámbito local utilizan información local a un bloque básico . ^{[ 4 ]} Dado que los bloques básicos no contienen instrucciones de flujo de control, estas optimizaciones requieren un análisis mínimo, lo que reduce el tiempo y los requisitos de almacenamiento. Sin embargo, no se conserva información entre saltos.

Las optimizaciones de alcance global, también conocidas como optimizaciones intraprocedimentales, operan sobre funciones individuales. ^{[ 4 ]} Esto les proporciona más información para trabajar, pero a menudo requiere cálculos costosos. Es necesario asumir el peor escenario posible cuando se realizan llamadas a funciones o se accede a variables globales, ya que se dispone de poca información sobre ellas.

Las optimizaciones de tipo "peephole" se realizan generalmente al final del proceso de compilación, después de que se haya generado el código máquina . Esta optimización examina algunas instrucciones adyacentes (similar a "mirar a través de un agujero" el código) para ver si se pueden reemplazar por una sola instrucción o una secuencia más corta de instrucciones. ^{[ 3 ] : 554} Por ejemplo, una multiplicación de un valor por dos podría ejecutarse de manera más eficiente desplazando el valor a la izquierda o sumándolo a sí mismo (este ejemplo también es una instancia de reducción de fuerza ).

Las optimizaciones interprocedimentales analizan todo el código fuente de un programa. Cuanta más información haya disponible, más efectivas serán las optimizaciones. Esta información se puede utilizar para diversas optimizaciones, como la inserción de funciones en línea , donde una llamada a una función se reemplaza por una copia de su cuerpo.

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 de todas las unidades de traducción, lo que le permite realizar optimizaciones más agresivas, como la inserción en línea entre módulos y la desvirtualización .

La optimización del código máquina implica el uso de un optimizador de código objeto para analizar el programa una vez que se ha enlazado todo el código máquina . Técnicas como la compresión de macros, que ahorra espacio al condensar secuencias de instrucciones comunes, resultan más efectivas cuando se dispone de la imagen completa de la tarea ejecutable para su análisis. ^{[ 5 ]}

La mayoría de los lenguajes de programación de alto nivel comparten construcciones y abstracciones comunes, como estructuras de ramificación (if, switch), bucles (for, while) y encapsulación (estructuras, objetos). Por lo tanto, se pueden usar técnicas de optimización similares en diferentes lenguajes. Sin embargo, ciertas características del lenguaje dificultan algunas optimizaciones. Por ejemplo, los punteros en C y C++ dificultan la optimización de arreglos; véase el análisis de alias . No obstante, lenguajes como PL/I , que también admiten punteros, implementan optimizaciones para arreglos. Por el contrario, algunas características del lenguaje facilitan ciertas optimizaciones. Por ejemplo, en algunos lenguajes, las funciones no pueden tener 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 permiten efectos secundarios, el compilador puede restringir dicha optimización a las funciones que puede determinar que no tienen efectos secundarios.

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. Ejemplos de ello son las instrucciones que realizan varias acciones a la vez, como decrementar un registro y saltar a un salto si no es cero.

El siguiente es un ejemplo de optimización dependiente de la máquina local. Para establecer un registro a 0, la forma obvia es usar la constante '0' en una instrucción que establece un valor de registro a una constante. Una forma menos obvia es realizar una operación XOR con un registro consigo mismo o restarlo de sí mismo. Es responsabilidad del compilador saber qué variante de instrucción usar. En muchas máquinas RISC , ambas instrucciones serían igualmente apropiadas, ya que 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; lo mismo se aplica en IBM System/360 y sucesores para la variante de resta. ^{[ 6 ]} Un problema potencial con esto es que XOR o resta pueden introducir una dependencia de datos con el valor anterior del registro, causando un bloqueo de la tubería , que ocurre cuando el procesador debe retrasar la ejecución de una instrucción porque depende del resultado de una instrucción anterior. Sin embargo, los procesadores suelen tratar la operación XOR de un registro consigo mismo o la resta de un registro de sí mismo como un caso especial que no provoca bloqueos.

La optimización de bucles actúa sobre las instrucciones que componen un bucle, como un bucle for ; por ejemplo, el movimiento de código invariante de bucle . Las optimizaciones de bucles pueden tener un impacto significativo porque muchos programas pasan un gran porcentaje de su tiempo dentro de bucles. ^{[ 3 ] : 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 , se puede actualizar adecuadamente cada vez que se modifica la variable del bucle. Esto supone una reducción de la robustez y también puede permitir que las definiciones de la variable de índice se conviertan en código muerto . ^{[ 3 ] : 596–598} Esta información también es útil para la eliminación de comprobaciones de límites y el análisis de dependencias , entre otras cosas.j := 4*i + 1

Fisión de bucle o distribución de bucle

La división de bucles intenta fragmentar un bucle en varios bucles sobre el mismo rango de índices, de modo que cada nuevo bucle solo toma una parte del cuerpo del bucle original. Esto puede mejorar la localidad de referencia tanto a los datos a los que se accede dentro del bucle como al código dentro del mismo.

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 iterarían el mismo número de veces, independientemente de si ese número se conoce en tiempo de compilación, sus cuerpos se pueden combinar siempre que no hagan referencia a los datos del otro.

Inversión de bucle

Esta técnica transforma un bucle while estándar en un bucle do/while (también conocido como repeat/until ) envuelto en una condición if , reduciendo a la mitad el número de saltos en los casos en que se ejecuta el bucle. Si bien esto duplica la comprobación de la condición (aumentando el tamaño del código), resulta más eficiente, ya que los saltos suelen provocar un bloqueo en 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 condición if .

Intercambio en bucle

Estas optimizaciones intercambian bucles internos por bucles externos. Cuando las variables del bucle indexan un array, dicha transformación puede mejorar la localidad de referencia, dependiendo de la estructura del array.

Movimiento de código invariante de bucle

Si una cantidad se calcula dentro de un bucle en 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. ^{[ 3 ] : 596} Esto es particularmente importante con las expresiones de cálculo de direcciones generadas por bucles sobre arreglos. 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 del bucle.

Optimización de bucles anidados

Algunos algoritmos de uso generalizado, como la multiplicación de matrices, presentan un comportamiento de caché muy deficiente y accesos excesivos a la memoria. La optimización de bucles anidados aumenta el número de aciertos de caché al operar sobre bloques pequeños y mediante el intercambio de bucles.

Inversión del 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, por lo tanto, permitir otras optimizaciones. Además, en algunas arquitecturas, la inversión de bucle contribuye a un código más pequeño, ya que cuando se decrementa 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. Esta 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 inversión de bucle ahorra la cantidad de bytes necesarios para almacenar el parámetro. Adicionalmente, si el número de comparación excede el tamaño de palabra de la plataforma, en el orden de bucle estándar, se necesitarían ejecutar múltiples instrucciones para evaluar la comparación, lo cual 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 comprueba la condición del bucle y la cantidad de saltos; las comprobaciones y los saltos pueden perjudicar el rendimiento al afectar la canalización de instrucciones. Una optimización de "menos saltos". El desenrollado completo de un bucle elimina toda la sobrecarga, pero requiere que se conozca el número de iteraciones en tiempo de compilación.

División de bucles

La división de bucles intenta simplificar un bucle o eliminar dependencias dividiéndolo en múltiples bucles con el mismo cuerpo, pero que iteran sobre diferentes porciones contiguas del rango de índices. Un caso especial útil es el pelado de bucles , que puede simplificar un bucle con una primera iteración problemática al realizar dicha iteración por separado antes de entrar en el bucle.

Desactivación del bucle

La operación de desconexión traslada una condición del interior de un bucle al exterior del mismo duplicando el cuerpo del bucle dentro de cada una de las cláusulas if y else de la condición.

Pipeline de software

El bucle se reestructura de tal manera que el trabajo realizado en una iteración se divide en varias partes y se ejecuta a lo largo de varias iteraciones. En un bucle ajustado, esta técnica oculta la latencia entre la carga y el uso de los valores.

Paralelización automática

Un bucle se convierte en código multihilo 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.

Las optimizaciones de almacenamiento predictivas permiten que las operaciones de almacenamiento se realicen antes de lo que se permitiría en el contexto de hilos y bloqueos. El proceso necesita saber de antemano qué valor almacenará la asignación que debería haber seguido. El propósito de esta flexibilizació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 correctamente sincronizados. ^{[ 9 ]}

Las optimizaciones del flujo de datos , basadas en el análisis del flujo de datos , dependen principalmente de cómo ciertas propiedades de los datos se propagan mediante las aristas de control en el grafo de flujo de control . Algunas de estas incluyen:

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á y, por lo tanto, solo calculan su valor una vez. ^{[ 3 ] : 592–594}

Plegado y propagación constantes

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. ^{[ 10 ]} 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 , resulta difícil realizar optimizaciones, ya que cualquier variable podría haber sido modificada al asignarle una ubicación de memoria. Al especificar qué punteros pueden ser alias de qué variables, se pueden ignorar los punteros no relacionados.

eliminación de tiendas muertas

Eliminación de las 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.

Estas optimizaciones deben realizarse tras transformar el programa a un formato especial denominado formato de asignación única estática (SSA) , en el que cada variable se asigna en un único lugar. Si bien algunas funcionan sin SSA, resultan más efectivas con este formato. Muchas optimizaciones descritas en otras secciones también se benefician sin necesidad de realizar cambios especiales, como la asignación de registros.

Numeración de valor global

GVN elimina la redundancia mediante la construcción de un grafo de valores del programa y la posterior determinación de qué valores se calculan con expresiones equivalentes. GVN puede identificar cierta redundancia que la eliminación de subexpresiones convencional no detecta, y viceversa.

Propagación de constantes condicionales dispersas

Combina la propagación de constantes, el plegado de constantes y la 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 porciones del grafo de flujo de control que esto hace inaccesibles.

Asignación de registro

Las variables más utilizadas deben almacenarse en los registros del procesador para un acceso más rápido. Para determinar qué variables colocar en los registros, se crea un grafo de interferencia. Cada variable es un vértice y, cuando dos variables se utilizan simultáneamente (tienen un rango de vida que se interseca), se crea una arista entre ellas. Este grafo se colorea, por ejemplo, utilizando el algoritmo de Chaitin con el mismo número de colores que de registros. Si la coloración falla, una variable se "desborda" a 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 múltiples modos de direccionamiento , ofrecen varias formas diferentes de realizar una operación específica, utilizando secuencias de instrucciones completamente distintas. La función del selector de instrucciones es elegir de forma óptima qué instrucciones implementar para cada operador en la representación intermedia de bajo nivel . Por ejemplo, en muchos procesadores de la familia 68000 y la arquitectura x86, se pueden utilizar 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 operaciones aritméticas con menor almacenamiento.

Programación de la instrucción

La planificación de instrucciones es una optimización importante para los procesadores modernos con arquitectura segmentada, ya que evita bloqueos o interrupciones en la segmentación agrupando las instrucciones sin dependencias, al tiempo que se preserva la semántica original.

Rematerialización

La rematerialización recalcula un valor en lugar de cargarlo desde la memoria, eliminando así el acceso a la misma. Esto se realiza simultáneamente con la asignación de registros para evitar desbordamientos.

factorización de código

Si varias secuencias de código son idénticas, o pueden parametrizarse o reordenarse para que sean idénticas, pueden reemplazarse con llamadas a una subrutina compartida. Esto a menudo permite compartir código para la configuración de la subrutina y, en ocasiones, para la recursión de cola. ^{[ 13 ]}

Trampolines

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

Reordenamiento de cálculos

Basándose en la programación lineal entera , los compiladores de reestructuración mejoran la localidad de los datos y exponen un mayor paralelismo mediante la reordenación de los cálculos. Los compiladores optimizadores de espacio pueden reordenar el código para alargar secuencias que se pueden factorizar en subrutinas.

Aunque muchas de estas características también se aplican a los lenguajes no funcionales, tienen su origen en lenguajes funcionales como Lisp y ML , o son particularmente importantes en ellos .

Optimización de llamadas de cola

Una llamada a 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 mediante un proceso denominado eliminación de recursión de cola u optimización de llamadas de cola.

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

En los lenguajes 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

Los cálculos que producen el mismo resultado independientemente de la entrada dinámica en tiempo de ejecución pueden evaluarse en tiempo de compilación.

Eliminación de la comprobación de límites

Muchos lenguajes, como Java , imponen la comprobación de límites en todos los accesos a matrices. Esto supone un grave cuello de botella en el rendimiento de ciertas aplicaciones, como el código científico. La eliminación de la comprobación de límites permite al compilador eliminarla de forma segura 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 ramas (depende de la máquina)

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

Reordenamiento de bloques de código

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

eliminación de código muerto

Elimina las instrucciones que no afectan al comportamiento del programa, por ejemplo, las definiciones que no tienen utilidad, denominadas 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, puede escribirse una sola vez fuera de la sentencia condicional. Del mismo modo, si ciertos tipos de expresiones (por ejemplo, la asignación de una constante a una variable) aparecen dentro de un bucle, pueden sacarse de él, ya que su efecto será el mismo independientemente de si se ejecutan varias veces o solo una. Esto se conoce como eliminación total de redundancia. Una optimización similar, pero más potente, es la eliminación parcial de redundancia (PRE).

Expansión en línea o expansión macro

Cuando un código invoca un procedimiento , es posible insertar directamente el cuerpo del procedimiento dentro del código que lo llama, en lugar de transferirle el control. Esto ahorra la sobrecarga asociada a las llamadas a procedimientos, además de brindar la oportunidad de realizar diversas optimizaciones específicas para cada parámetro, pero tiene un costo en términos 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 un gran número de llamadas a procedimientos pequeños. Esta es una optimización de "menos saltos". Las sentencias de los lenguajes de programación imperativos también son un ejemplo de dicha optimización. Si bien las sentencias podrían implementarse con llamadas a funciones, casi siempre se implementan con inserción de código en línea.

enhebrado de salto

En esta optimización, se fusionan los saltos condicionales consecutivos que dependen total o parcialmente de la misma condición.

Por ejemplo:

if ( cond ) { foo (); } if ( cond ) { bar (); }// se convierte en: if ( cond ) { foo (); bar (); }

y:

if ( cond ) { foo (); } if ( ! cond ) { bar (); }// se convierte en: if ( cond ) { foo (); } else { bar (); }

Macrocompresión

Una optimización de espacio que reconoce secuencias de código comunes, 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. ^{[ 5 ]} Esto se realiza de manera más efectiva como una optimización de código 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 interpretado 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 , ^{[ 5 ]} 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 expresiones para minimizar los recursos necesarios para la evaluación de expresiones.

Reordenamiento de prueba

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

La optimización interprocedimental opera sobre todo el programa, abarcando procedimientos y archivos. Colabora estrechamente con sus contrapartes intraprocedimentales, mediante la cooperación de una parte local y una parte global. Las optimizaciones interprocedimentales típicas incluyen la inserción de código en línea, la eliminación de código muerto, la propagación de constantes y la reordenación de procedimientos. Como es habitual, el compilador debe realizar un análisis interprocedimental antes de sus optimizaciones. Estos análisis incluyen el análisis de alias, el análisis de acceso a matrices y la construcción de un grafo 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 compilador de código abierto GCC fue criticado por la falta de análisis y optimizaciones interprocedimentales potentes, aunque esto 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 por defecto. Los usuarios deben usar opciones del compilador explícitamente para indicarle que habilite el análisis interprocedimental y otras optimizaciones costosas.