Un compilador de optimización es un compilador que utiliza varios métodos para obtener un código de programa más óptimo mientras mantiene su funcionalidad. Los objetivos de optimización más comunes son: reducir el tiempo de ejecución del programa, aumentar el rendimiento, compactar el código del programa, ahorrar memoria, minimizar los costos de energía, reducir el número de operaciones de E/S .
La optimización puede ocurrir implícitamente durante la traducción de un programa, pero generalmente se considera un paso separado en el trabajo del compilador. Los enlazadores también pueden realizar parte de las optimizaciones, como eliminar subrutinas no utilizadas o reordenarlas .
La optimización generalmente se implementa a través de una serie de transformaciones de optimización, algoritmos que toman un programa y lo modifican para producir una variante semánticamente equivalente que es más eficiente para algún conjunto de objetivos de optimización. Se ha demostrado que algunos problemas de optimización de código son NP-completos [1] , o incluso indecidibles [2] . No obstante, prácticamente muchos de ellos se resuelven mediante métodos heurísticos, que dan resultados bastante satisfactorios.
Distinguir entre optimización de bajo y alto nivel. La optimización de bajo nivel transforma el programa a nivel de instrucciones elementales, por ejemplo, instrucciones de un procesador de una arquitectura particular . La optimización de alto nivel se lleva a cabo a nivel de elementos estructurales del programa, como módulos, funciones, ramas, ciclos.
Los métodos utilizados en las optimizaciones se pueden clasificar por alcance: pueden afectar tanto a una sola declaración como a un programa completo. Los métodos locales (que afectan a una pequeña parte del programa) son más fáciles de implementar que los métodos globales (que se aplican a todo el programa), pero los métodos globales suelen ser más beneficiosos.
Las optimizaciones de mirilla local consideran varias instrucciones adyacentes (en términos de uno de los gráficos de la representación del programa) (como si "mirara por la mirilla " en el código) para ver si es posible realizar alguna transformación con ellos en términos de optimización meta. En particular, pueden ser reemplazadas por una sola instrucción o una secuencia más corta de instrucciones.
Por ejemplo, duplicar un número se puede hacer de manera más eficiente usando un desplazamiento a la izquierda o sumando el mismo número.
En la optimización local, solo se considera la información de un bloque básico por paso [3] . Dado que no hay transiciones de flujo de control en los bloques básicos , estas optimizaciones requieren poco análisis (ahorran tiempo y reducen los requisitos de memoria), pero también significa que no se almacena información para el siguiente paso.
Las optimizaciones intraprocedurales ( inglés intraprocedural ) son optimizaciones globales que se realizan íntegramente en el marco de una unidad de traducción (por ejemplo, funciones o procedimientos) [4] . Con dicha optimización, se involucra mucha más información que en la local, lo que le permite lograr efectos más significativos, pero esto a menudo requiere cálculos que consumen muchos recursos. Si hay variables globales en la unidad de programa que se está optimizando, la optimización de este tipo puede ser difícil.
Hay un gran número de optimizaciones aplicadas a los bucles. Con una gran cantidad de iteraciones del ciclo, tales optimizaciones son extremadamente efectivas, ya que una parte significativa de la ejecución del programa se ve afectada por una pequeña transformación. Dado que los bucles son una parte importante del tiempo de ejecución de muchos programas, las optimizaciones de bucles existen en casi todos los compiladores y son las más importantes.
Por ejemplo, al identificar invariantes de bucle , a veces es posible eliminar algunas de las operaciones del bucle para no realizar cálculos repetidos redundantes.
Tales tipos de optimizaciones analizan todo el código fuente del programa a la vez. La mayor cantidad de información extraída por estos métodos significa que las optimizaciones pueden ser más eficientes que otros métodos. Dichas optimizaciones pueden usar métodos bastante complejos, por ejemplo, una llamada de función se reemplaza con una copia del cuerpo de la función (en línea o en línea).
Ejemplo Sea alguna función:
int pred ( int x ) { si ( x == 0 ) devolver 0 ; más devuelve x - 1 ; }Antes de incrustarlo, el código se veía así:
int f ( int y ) { volver pred ( y ) + pred ( 0 ) + pred ( y + 1 ); }Después de la optimización:
int f ( int y ) { temperatura interna = 0 ; si ( y == 0 ) temperatura += 0 ; más temp += y - 1 ; /* (una) */ si ( 0 == 0 ) temporal += 0 ; más temp += 0 - 1 ; /* (2) */ si ( y + 1 == 0 ) temperatura += 0 ; otra cosa temp += ( y + 1 ) - 1 ; /* (3) */ temperatura de retorno ; }La incorporación de funciones elimina la sobrecarga asociada con las llamadas a funciones. Además, después de la alineación, es posible aplicar optimizaciones dentro del procedimiento que antes eran imposibles o demasiado difíciles de implementar. Sin embargo, la inserción tiene sus inconvenientes, como casi cualquier optimización: aumenta el tamaño estático del código, lo que puede provocar efectos negativos en partes del equipo que son sensibles a este factor.
Entre los factores que influyen en la optimización, tanto las características informáticas de la máquina de destino (por ejemplo, el número y la velocidad del reloj de los núcleos del procesador, el tamaño de la memoria caché del procesador , el ancho de banda del bus del sistema , la cantidad de RAM) y la arquitectura del destino. procesador (en particular, en diferentes arquitecturas hay disponible un número diferente de registros de propósito general, la canalización computacional se implementa de manera diferente ). Otra clase de factores que afectan la optimización son los escenarios de uso del código de destino, por ejemplo, los objetivos de optimización pueden variar significativamente para el código de depuración y prueba, la ejecución ocasional, el uso continuo, las aplicaciones integradas o independientes.
Entre los principios de optimización utilizados en varios métodos de optimización en compiladores (algunos de ellos pueden contradecirse entre sí o ser inaplicables para diferentes objetivos de optimización):
Las optimizaciones de flujo de datos se basan en el análisis de flujo de datos y, por lo general, consideran el gráfico de flujo de control y el gráfico de flujo de datos conectados entre sí como datos de entrada, así como, a menudo, el árbol de bucles y el etiquetado de bucles del gráfico de flujo de control. Al analizar, en particular, la propagación de la información, en estos gráficos, se revela la posibilidad de optimización en términos de los objetivos deseados, y luego se aplican las optimizaciones.
Eliminar subexpresiones comunes La eliminación de subexpresiones comunes es una optimización del compilador que busca instancias de expresiones idénticas y analiza la posibilidad de reemplazarlas con una única variable que contenga el valor calculado. Convolución de constantes Optimizaciones que reducen los cálculos redundantes reemplazando expresiones constantes y variables con sus valores. Análisis de variables inductivas ( ing. Análisis de variables inductivas ) Consulte la descripción en Optimización de ciclos . Eliminación de registros sin salida Eliminar asignaciones a variables que no se leen posteriormente. La asignación se elimina porque la variable no se ha leído antes del final de la vida útil de la variable o porque una asignación posterior la sobrescribirá.SSA (asignación estática única, asignación estática única) es una forma de representación de gráfico de flujo de datos (DFG) en la que a cada variable se le asigna un valor solo una vez. Esto evita la multiplicación de arcos en el gráfico durante múltiples escrituras y lecturas de una variable y facilita el análisis del gráfico. Para hacer esto, la vista SSA introduce funciones Phi especiales (nodos de gráfico de flujo de datos) en algunos puntos de convergencia en el gráfico de flujo de control. Estos nuevos nodos son las denominadas pseudoasignaciones.
Las definiciones múltiples son posibles no solo por las convergencias del flujo de control ("o"), sino también por la posibilidad de leer algún valor compuesto como un todo, que fue escrito en partes por más de una operación ("y"). En este caso, para mantener la forma SSA, se introducen pseudoasignaciones adicionales dentro de los bloques básicos, que recogen un valor de varios.
Algunas optimizaciones se basan en SSA. Aunque algunos de ellos pueden funcionar sin SSA, son más efectivos cuando SSA está presente.