La optimización interprocedural ( IPO ) es una colección de técnicas de compilación utilizadas en programación informática para mejorar el rendimiento de programas que contienen muchas funciones de uso frecuente y de longitud pequeña o mediana. IPO se diferencia de otras optimizaciones del compilador al analizar el programa completo en lugar de una sola función o bloque de código.
IPO busca reducir o eliminar cálculos duplicados y el uso ineficiente de la memoria y simplificar secuencias iterativas como los bucles. Si se produce una llamada a otra rutina dentro de un bucle, el análisis de IPO puede determinar que es mejor incorporar esa rutina. Además, IPO puede reordenar las rutinas para mejorar la ubicación y el diseño de la memoria .
IPO también puede incluir optimizaciones típicas del compilador aplicadas a nivel de todo el programa, por ejemplo, eliminación de código muerto (DCE), que elimina el código que nunca se ejecuta. IPO también intenta garantizar un mejor uso de las constantes. Los compiladores modernos ofrecen IPO como una opción en tiempo de compilación. El proceso de IPO real puede ocurrir en cualquier paso entre el código fuente legible por humanos y la producción de un programa binario ejecutable terminado.
Para los lenguajes que se compilan archivo por archivo, una IPO efectiva en todas las unidades de traducción (archivos de módulo) requiere conocimiento de los "puntos de entrada" del programa para que se pueda ejecutar una optimización completa del programa ( WPO ). En muchos casos, esto se implementa como un paso de optimización del tiempo de enlace ( LTO ), porque todo el programa es visible para el enlazador.
El objetivo de cualquier optimización de la velocidad es que el programa se ejecute lo más rápido posible; el problema es que no es posible que un compilador analice correctamente un programa y determine qué hará , y mucho menos qué pretendía el programador que hiciera. Por el contrario, los programadores humanos comienzan en el otro extremo con un propósito e intentan producir un programa que lo logre, preferiblemente sin pensar mucho en el proceso.
Por diversas razones, incluida la legibilidad, los programas frecuentemente se dividen en una serie de procedimientos que manejan algunos casos generales. Sin embargo, la generalidad de cada procedimiento puede resultar en un desperdicio de esfuerzos en usos específicos. La optimización interprocedimiento representa un intento de reducir este desperdicio.
Supongamos que hay un procedimiento que evalúa F(x), y que F es una función pura , y el código solicita el resultado de F(6) y luego, F(6) nuevamente. Es casi seguro que esta segunda evaluación es innecesaria: el resultado podría haberse guardado y consultarlo más tarde. Esta simple optimización se frustra en el momento en que la implementación de F(x) se vuelve impura; es decir, su ejecución implica referencias a parámetros distintos al argumento explícito 6 que ha sido cambiado entre las invocaciones, o efectos secundarios como imprimir algún mensaje en un registro, contar el número de evaluaciones, acumular el tiempo de CPU consumido, preparar tablas internas. de modo que se faciliten las invocaciones posteriores de parámetros relacionados, etc. Perder estos efectos secundarios por no evaluación por segunda vez puede ser aceptable o no.
De manera más general, además de la optimización, la segunda razón para utilizar procedimientos es evitar la duplicación de código que produciría los mismos resultados, o casi los mismos resultados, cada vez que se realiza el procedimiento. Por lo tanto, un enfoque general de optimización sería revertir esto: algunas o todas las invocaciones de un determinado procedimiento se reemplazan por el código respectivo, con los parámetros adecuadamente sustituidos. Luego, el compilador intentará optimizar el resultado.
La optimización completa del programa ( WPO ) es la optimización del compilador de un programa utilizando información sobre todos los módulos del programa. Normalmente, las optimizaciones se realizan por módulo, "compilando" ; pero este enfoque, si bien es más fácil de escribir y probar y requiere menos recursos durante la compilación misma, no permite tener certeza sobre la seguridad de una serie de optimizaciones como la inserción agresiva y, por lo tanto, no puede realizarlas incluso si realmente resultaran serlo. ganancias de eficiencia que no cambian la semántica del código objeto emitido.
La optimización del tiempo de enlace ( LTO ) es un tipo de optimización de programa realizada por un compilador a un programa en el momento del enlace . La optimización del tiempo de enlace es relevante en lenguajes de programación que compilan programas archivo por archivo y luego vinculan esos archivos entre sí (como C y Fortran ), en lugar de hacerlo todos a la vez (como el sistema justo a tiempo de Java ). compilación (JIT)).
Una vez que todos los archivos se han compilado por separado en archivos objeto , tradicionalmente, un compilador vincula (fusiona) los archivos objeto en un solo archivo, el ejecutable . Sin embargo, en LTO implementado por GNU Compiler Collection (GCC) y LLVM , el compilador puede volcar su representación intermedia (IR), es decir, código de bytes GIMPLE o código de bits LLVM, respectivamente, de modo que todas las diferentes unidades de compilación que irán a crear un único ejecutable se puede optimizar como un solo módulo cuando finalmente se realice el enlace. Esto amplía el alcance de las optimizaciones interprocedimientos para abarcar todo el programa (o, más bien, todo lo que es visible en el momento del enlace). Con la optimización del tiempo de enlace, el compilador puede aplicar varias formas de optimización interprocedimiento a todo el programa, lo que permite un análisis más profundo, una mayor optimización y, en última instancia, un mejor rendimiento del programa.
En la práctica, LTO no siempre optimiza todo el programa: las funciones de la biblioteca , especialmente los objetos compartidos vinculados dinámicamente , se mantienen intencionalmente fuera para evitar una duplicación excesiva y permitir la actualización. Los enlaces estáticos naturalmente se prestan al concepto de LTO, pero solo funcionan con archivos de biblioteca que contienen objetos IR en lugar de archivos de objetos de código de máquina únicamente. [1] Debido a problemas de rendimiento, ni siquiera siempre se utiliza directamente toda la unidad; un programa podría dividirse en un LTO estilo divide y vencerás, como el WHOPR de GCC. [2] Y, por supuesto, cuando el programa que se está construyendo es en sí mismo una biblioteca, la optimización mantendría todos los símbolos disponibles externamente (exportados), sin esforzarse demasiado en eliminarlos como parte de DCE. [1]
Todavía es posible una forma mucho más limitada de WPO sin LTO, como lo ejemplifica el cambio de GCC -fwhole-program. Este modo hace que GCC asuma que el módulo que se está compilando contiene el punto de entrada de todo el programa, de modo que todas las demás funciones que contiene no se utilizan externamente y se pueden optimizar de forma segura. Dado que sólo se aplica a un único módulo, no puede abarcar realmente todo el programa. Se puede combinar con LTO en el sentido de un módulo grande, lo cual es útil cuando el vinculador no se comunica con GCC sobre qué puntos de entrada o símbolos se están utilizando externamente. [1]
Ejemplo de programa ; entero b ; {Una variable "global" para el procedimiento Silly.} Procedimiento Silly ( a , x ) si x < 0 entonces a := x + b else a :=- 6 ; Fin tonto ; {La referencia a b, que no es un parámetro, hace que Silly sea "impuro" en general.} entero a , x ; {Estas variables son visibles para Silly solo si hay parámetros.} x := 7 ; b := 5 ; Tonto ( a , x ) ; escribe ( x ) ; Tonto ( x , a ) ; escribe ( x ) ; Tonto ( b , b ) ; escriba ( b ) ; Fin del ejemplo ; Si los parámetros a Silly se pasan por valor , las acciones del procedimiento no tienen ningún efecto sobre las variables originales y, dado que Silly no hace nada en su entorno (leer de un archivo, escribir en un archivo, modificar variables globales como b , etc. .) su código más todas las invocaciones se pueden optimizar por completo, dejando el valor de a indefinido (lo cual no importa) para que solo writequeden las declaraciones, simplemente imprimiendo valores constantes.
Si, en cambio, los parámetros se pasan por referencia , entonces la acción sobre ellos dentro de Silly sí afecta a los originales. Esto generalmente se hace pasando la dirección de la máquina de los parámetros al procedimiento para que los ajustes del procedimiento estén en el área de almacenamiento original. Así, en el caso de pasar por referencia, el procedimiento Silly sí tiene efecto. Supongamos que sus invocaciones se expanden en el lugar, con parámetros identificados por dirección: el código equivale a
x := 7 ; b := 5 ; si x < 0 entonces a := x + b si no a :=- 6 ; escribe ( x ) ; {a se cambia.} si a < 0 entonces x := a + b else x :=- 6 ; escribe ( x ) ; {Porque los parámetros se intercambian.} si b < 0 entonces b := b + b else b :=- 6 ; escriba ( b ) ; {Dos versiones de la variable b en Silly, más el uso global.} El compilador podría entonces, en este ejemplo bastante pequeño, seguir las constantes a lo largo de la lógica (tal como está) y encontrar que los predicados de las declaraciones if son constantes y así...
x := 7 ; b := 5 ; un :=- 6 ; escribir ( 7 ) ; {no se hace referencia a b, por lo que este uso sigue siendo "puro".} x :=- 1 ; escribir ( -1 ) ; {b está referenciado...} b :=- 6 ; escribir ( -6 ) ; {b se modifica a través de su manifestación de parámetros.} Y dado que las asignaciones a a , b y x no aportan nada al mundo exterior (no aparecen en declaraciones de salida, ni como entrada para cálculos posteriores (cuyos resultados a su vez conducen a salida, de lo contrario también son innecesarios)), hay Tampoco tiene sentido este código, por lo que el resultado es
escribir ( 7 ) ; escribir ( -1 ) ; escribir ( -6 ) ;Un método variante para pasar parámetros que parecen ser "por referencia" es la copia de entrada y salida, mediante la cual el procedimiento funciona en una copia local de los parámetros cuyos valores se copian de nuevo a los originales al salir del procedimiento. Si el procedimiento tiene acceso al mismo parámetro pero de diferentes maneras como en invocaciones como Silly(a,a) o Silly(a,b) , pueden surgir discrepancias. Entonces, si los parámetros se pasaran mediante copia de entrada y salida en orden de izquierda a derecha, entonces Silly(b,b) se expandiría a
p1 := b ; p2 := b ; {Copiar. Las variables locales p1 y p2 son iguales.} si p2 < 0 entonces p1 := p2 + b else p1 :=- 6 ; {Por lo tanto, p1 ya no puede ser igual a p2.} b := p1 ; b := p2 ; {Copiar afuera. En orden de izquierda a derecha, se sobrescribe el valor de p1.} Y en este caso copiar el valor de p1 (que ha sido cambiado) a b no tiene sentido, porque inmediatamente se sobrescribe con el valor de p2 , cuyo valor no ha sido modificado dentro del procedimiento desde su valor original de b , y así la tercera declaración se convierte
escribir ( 5 ) ; {No -6} Es probable que tales diferencias en el comportamiento causen perplejidad, exacerbada por preguntas sobre el orden en que se copian los parámetros: ¿será de izquierda a derecha tanto en la salida como en la entrada? Estos detalles probablemente no se explican cuidadosamente en el manual del compilador y, si lo están, probablemente se pasarán por alto por no ser relevantes para la tarea inmediata y se olvidarán durante mucho tiempo cuando surja el problema. Si (como es probable) los valores temporales se proporcionan a través de un esquema de almacenamiento de pila, entonces es probable que el proceso de copia se realice en el orden inverso al de copia, lo que en este ejemplo significaría que p1 sería el último valor devuelto a b en su lugar.
El proceso de expandir un procedimiento en línea no debe considerarse como una variante de reemplazo textual (como en las expansiones de macros ) porque pueden surgir errores de sintaxis cuando se modifican parámetros y la invocación particular usa constantes como parámetros. Debido a que es importante estar seguro de que no se cambiará el valor de ninguna constante suministrada como parámetro (las constantes se pueden mantener en la memoria al igual que las variables) para que los usos posteriores de esa constante (realizados mediante referencia a su ubicación de memoria) no salgan mal, Una técnica común es que el compilador genere código copiando el valor de la constante en una variable temporal cuya dirección se pasa al procedimiento, y si se modifica su valor, no importa; nunca se vuelve a copiar a la ubicación de la constante.
Dicho de otra manera, un programa de prueba cuidadosamente escrito puede informar si los parámetros se pasan por valor o por referencia y, si se utilizan, qué tipo de esquema de entrada y salida de copia. Sin embargo, la variación es infinita: los parámetros simples se pueden pasar mediante copia, mientras que los agregados grandes, como matrices, se pueden pasar por referencia; constantes simples como cero pueden generarse mediante códigos de máquina especiales (como Clear o LoadZ), mientras que constantes más complejas pueden almacenarse en la memoria etiquetadas como de solo lectura y cualquier intento de modificarlas resulta en la terminación inmediata del programa, etc.
Este ejemplo es extremadamente simple, aunque las complicaciones ya son evidentes. Lo más probable es que se trate de muchos procedimientos, con una variedad de propiedades deducibles o declaradas por el programador que pueden permitir que las optimizaciones del compilador encuentren alguna ventaja. Cualquier parámetro de un procedimiento puede ser de sólo lectura, escribirse, leerse y escribirse, o ignorarse por completo, dando lugar a oportunidades como que las constantes no necesiten protección mediante variables temporales, pero lo que sucede en cualquier invocación dada bien puede depender de una compleja red de consideraciones. Otros procedimientos, especialmente los procedimientos similares a funciones, tendrán ciertos comportamientos que en invocaciones específicas pueden permitir que se evite algo de trabajo: por ejemplo, la función Gamma , si se invoca con un parámetro entero, podría convertirse en un cálculo que involucre factoriales enteros.
Algunos lenguajes informáticos permiten (o incluso requieren) afirmaciones sobre el uso de parámetros y podrían ofrecer además la oportunidad de declarar que las variables tienen sus valores restringidos a algún conjunto (por ejemplo, 6 < x ≤ 28), proporcionando así más recursos para la proceso de optimización y también proporcionar comprobaciones útiles de la coherencia del código fuente para detectar errores. Pero esto nunca es suficiente: sólo a algunas variables se les pueden dar restricciones simples, mientras que otras requerirían especificaciones complejas: ¿cómo se podría especificar que la variable P debe ser un número primo y, de ser así, se incluye o no el valor 1? Las complicaciones son inmediatas: ¿cuáles son los rangos válidos para un día del mes D dado que M es un número de mes? ¿Y todas las violaciones son dignas de terminación inmediata? Incluso si todo eso pudiera manejarse, ¿qué beneficio podría derivarse? ¿Y a qué costo? Las especificaciones completas equivaldrían a una reformulación de la función del programa en otra forma y, aparte del tiempo que consumiría el compilador procesándolas, estarían sujetas a errores. En cambio, solo se permiten especificaciones simples con verificación de rango de tiempo de ejecución.
En los casos en los que un programa no lee ninguna entrada (como en el ejemplo), uno podría imaginar que el análisis del compilador se lleva adelante de modo que el resultado no sea más que una serie de declaraciones impresas, o posiblemente algunos bucles que generen dichos valores de manera conveniente. ¿Reconocería entonces un programa para generar números primos y lo convertiría al método más conocido para hacerlo, o presentaría en su lugar una referencia a una biblioteca? ¡Improbable! En general, surgen consideraciones arbitrariamente complejas (el Entscheidungsproblem ) para impedir esto, y no hay otra opción que ejecutar el código sólo con mejoras limitadas.
Para lenguajes procedimentales como ALGOL , el análisis y la optimización interprocedurales parecen haber entrado en la práctica comercial a principios de los años 1970. El compilador de optimización PL/I de IBM realizó un análisis interprocedural para comprender los efectos secundarios tanto de las llamadas a procedimientos como de las excepciones (enunciadas, en términos de PL/I, como "en condiciones") [3] y en artículos de Fran Allen . [4] [5] El trabajo de compilación del lenguaje de programación APL fue necesariamente interprocedimiento. [6] [7]
Las técnicas de análisis y optimización interprocedurales fueron objeto de investigación académica en las décadas de 1980 y 1990. Reaparecieron en el mundo de los compiladores comerciales a principios de la década de 1990 con compiladores de Convex Computer Corporation (el "compilador de aplicaciones" para Convex C4) y de Ardent (el compilador de Ardent Titan ). Estos compiladores demostraron que las tecnologías podían hacerse lo suficientemente rápidas para ser aceptables en un compilador comercial; Posteriormente, han aparecido técnicas interprocesales en varios sistemas comerciales y no comerciales.
La colección de compiladores GNU tiene funciones integradas en todos los niveles de optimización. Esto -O1solo se aplica a aquellos que solo se llaman una vez ( -finline-functions-once), -O2esta restricción se relaja ( -finline-functions). De forma predeterminada, este es un comportamiento de un solo archivo, pero con la optimización del tiempo de enlace -fltose convierte en un programa completo. [1] La interfaz de línea de comandos de Clang es similar a la de GCC, con la excepción de que no hay ninguna -fwhole-programopción. [8]
Los archivos objeto producidos por LTO contienen una representación intermedia (IR) específica del compilador que se interpreta en el momento del enlace. Para asegurarse de que esto funcione bien con bibliotecas estáticas , los enlazadores GNU más nuevos tienen una interfaz de "complemento de enlace" que permite al compilador convertir los archivos objeto en un formato de código de máquina cuando sea necesario. Este complemento también ayuda a impulsar el proceso LTO en general. Alternativamente, se puede producir un objeto "fat LTO" que contenga tanto el código de máquina como el IR, pero esto requiere más espacio. [1]
Dado que tanto GCC como LLVM (clang) pueden producir un IR desde una variedad de lenguajes de programación, la IPO en tiempo de enlace puede ocurrir incluso a través de los límites del idioma. Esto se demuestra más comúnmente con C y C++, [9] pero LLVM también lo hace posible para Rust y todos los demás compiladores basados en LLVM. [10]
GCC y Clang realizan IPO de forma predeterminada en el nivel de optimización 2. Sin embargo, el grado de optimización es limitado cuando LTO está deshabilitado, ya que IPO solo puede ocurrir dentro de un archivo objeto y las funciones no estáticas nunca pueden eliminarse. Este último problema tiene una solución no LTO: el -fwhole-programinterruptor se puede utilizar para suponer que sólo main()es no estático, es decir, visible desde el exterior. [11]
Otra técnica que no es LTO son las "secciones de funciones" ( -ffunction-sectionsen GCC y Clang). Al colocar cada función en su propia sección en el archivo objeto, el vinculador puede realizar la eliminación de código inactivo sin un IR eliminando secciones sin referencia (usando la opción del vinculador --gc-sections). [12] Hay una opción similar disponible para las variables, pero provoca que se produzca un código mucho peor.
Los compiladores Intel C/C++ permiten la IPO de todo el programa. La bandera para habilitar las optimizaciones interprocedimientos para un solo archivo es -ip, la bandera para habilitar la optimización interprocedimientos en todos los archivos del programa es -ipo. [13] [14]
El compilador MSVC , integrado en Visual Studio, también admite la optimización interprocedural de todo el programa. [15]
Una interfaz independiente del compilador para permitir optimizaciones interprocedimientos de todo el programa se realiza a través de la INTERPROCEDURAL_OPTIMIZATIONpropiedad en CMake . [dieciséis]
Las optimizaciones del tiempo de enlace no requieren la presencia de todo el programa para funcionar. Si el programa no requiere que se exporte ningún símbolo, es posible combinar -flto y -fwhole-program para permitir que los optimizadores interprocedimientos utilicen suposiciones más agresivas que pueden conducir a mejores oportunidades de optimización. El uso de -fwhole-program no es necesario cuando el complemento del vinculador está activo (consulte -fuse-linker-plugin).