La optimización interprocedimental ( IPO ) es un conjunto de técnicas de compilación utilizadas en la programación informática para mejorar el rendimiento de programas que contienen muchas funciones de uso frecuente de longitud pequeña o mediana. La IPO se diferencia de otras optimizaciones de compilación 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 una mejor distribución y localización de la memoria .
La IPO también puede incluir optimizaciones típicas del compilador aplicadas a nivel de todo el programa, por ejemplo, la eliminación de código muerto (DCE), que elimina el código que nunca se ejecuta. La IPO también intenta garantizar un mejor uso de las constantes. Los compiladores modernos ofrecen la 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.
En el caso de los idiomas que se compilan archivo por archivo, una IPO eficaz en las unidades de traducción (archivos de módulo) requiere el conocimiento de los "puntos de entrada" del programa para que se pueda ejecutar una optimización del programa completo ( WPO ). En muchos casos, esto se implementa como un pase de optimización en tiempo de enlace ( LTO ), porque el enlazador puede ver todo el programa.
El objetivo de cualquier optimización para 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 por el otro extremo con un propósito e intentan producir un programa que lo logre, preferiblemente sin dedicarle mucho tiempo a pensar en el proceso.
Por diversas razones, incluida la legibilidad, los programas suelen dividirse en varios procedimientos que se ocupan de unos pocos casos generales. Sin embargo, la generalidad de cada procedimiento puede dar lugar a un desperdicio de esfuerzos en usos específicos. La optimización interprocedimental representa un intento de reducir este desperdicio.
Supongamos que existe 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, más tarde, F(6) nuevamente. Esta segunda evaluación es casi con certeza innecesaria: el resultado podría haberse guardado y consultado 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 involucra referencias a parámetros distintos del argumento explícito 6 que se ha 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 para que se faciliten las invocaciones posteriores para los parámetros relacionados, etc. Perder estos efectos secundarios mediante la no evaluación una segunda vez puede ser aceptable, o puede que no.
En términos más generales, además de la optimización, la segunda razón para usar procedimientos es evitar la duplicación de código que produciría los mismos resultados, o casi los mismos resultados, cada vez que se ejecuta el procedimiento. Por lo tanto, un enfoque general para la optimización sería invertir esto: algunas o todas las invocaciones de un determinado procedimiento se reemplazan por el código respectivo, con los parámetros sustituidos apropiadamente. El compilador intentará entonces optimizar el resultado.
La optimización de todo el programa ( WPO , por sus siglas en inglés) 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, "compilación" , pero este enfoque, si bien es más fácil de escribir y probar y requiere menos recursos durante la compilación en sí, 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 ser ganancias de eficiencia que no cambian la semántica del código objeto emitido.
La optimización en tiempo de enlace ( LTO ) es un tipo de optimización de programa que realiza un compilador a un programa en el momento del enlace . La optimización en 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 la compilación justo a tiempo (JIT) de Java ).
Una vez que todos los archivos se han compilado por separado en archivos de objeto , tradicionalmente, un compilador vincula (fusiona) los archivos de objeto en un solo archivo, el ejecutable . Sin embargo, en LTO tal como lo implementa GNU Compiler Collection (GCC) y LLVM , el compilador puede volcar su representación intermedia (IR), es decir , el bytecode de GIMPLE o el bitcode de LLVM, respectivamente, de modo que todas las diferentes unidades de compilación que conformarán un solo ejecutable se puedan optimizar como un solo módulo cuando finalmente se produzca el enlace. Esto amplía el alcance de las optimizaciones interprocedimentales para abarcar todo el programa (o, más bien, todo lo que es visible en el momento del enlace). Con la optimización en tiempo de enlace, el compilador puede aplicar varias formas de optimización interprocedimental a todo el programa, lo que permite un análisis más profundo, más optimización y, en última instancia, un mejor rendimiento del programa.
En la práctica, LTO no siempre optimiza el programa completo: las funciones de biblioteca , especialmente los objetos compartidos vinculados dinámicamente , se excluyen intencionalmente para evitar la duplicación excesiva y permitir la actualización. El enlace estático naturalmente se presta al concepto de LTO, pero solo funciona con archivos de biblioteca que contienen objetos IR en lugar de archivos de objetos de solo código de máquina. [1] Debido a preocupaciones de rendimiento, ni siquiera la unidad completa siempre se usa directamente: un programa podría dividirse en un LTO de estilo divide y vencerás como 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]
Una forma mucho más limitada de WPO es posible sin LTO, como lo ejemplifica el -fwhole-programswitch de GCC. 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 ninguna otra función en él se use externamente y se pueda optimizar de manera segura. Dado que solo se aplica a un solo módulo, no puede abarcar verdaderamente todo el programa. Se puede combinar con LTO en el sentido de un solo módulo grande, lo que es útil cuando el enlazador no se comunica con GCC sobre qué puntos de entrada o símbolos se están usando 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 de lo contrario a :=- 6 ; Fin de Silly ; {La referencia a b, no a 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 ; Silly ( a , x ) ; escribir ( x ) ; Silly ( x , a ) ; escribir ( x ) ; Silly ( b , b ) ; escribir ( b ) ; Fin del ejemplo ; Si los parámetros a Silly se pasan por valor , las acciones del procedimiento no tienen 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 pueden optimizarse por completo, dejando el valor de a indefinido (lo que no importa) de modo que solo writepermanezcan 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 afecta de hecho a los originales. Esto se hace normalmente pasando la dirección de la máquina de los parámetros al procedimiento de modo que los ajustes del procedimiento se realicen en el área de almacenamiento original. Por lo tanto, en el caso de pasar por referencia, el procedimiento Silly sí tiene un efecto. Supongamos que sus invocaciones se expanden en el lugar, con los parámetros identificados por dirección: el código equivale a
x := 7 ; b := 5 ; si x < 0 entonces a := x + b de lo contrario a :=- 6 ; escribir ( x ) ; {a se cambia.} si a < 0 entonces x := a + b de lo contrario x :=- 6 ; escribir ( x ) ; {Porque los parámetros se intercambian.} si b < 0 entonces b := b + b de lo contrario b :=- 6 ; escribir ( 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 es) y encontrar que los predicados de las declaraciones if son constantes y entonces...
x := 7 ; b := 5 ; a :=- 6 ; write ( 7 ) ; {b no está referenciado, por lo que este uso permanece "puro".} x :=- 1 ; write ( - 1 ) ; {b está referenciado...} b :=- 6 ; write ( - 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 entregan nada al mundo exterior (no aparecen en las declaraciones de salida, ni como entrada para cálculos posteriores (cuyos resultados a su vez conducen a la salida, de lo contrario también son innecesarios)), este código tampoco tiene sentido, por lo que el resultado es
escribir ( 7 ) ; escribir ( - 1 ) ; escribir ( - 6 ) ;Un método variante para pasar parámetros que parecen estar "por referencia" es el método de copia-entrada, copia-salida , en el que el procedimiento funciona sobre 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. Por lo tanto, si los parámetros se pasaran mediante copia-entrada, copia-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 de lo contrario p1 :=- 6 ; {Por lo tanto, p1 ya no puede ser igual a p2.} b := p1 ; b := p2 ; {Copiar. 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 es inmediatamente sobrescrito por el valor de p2 , cuyo valor no ha sido modificado dentro del procedimiento desde su valor original de b , y entonces la tercera declaración se convierte en
escribe ( 5 ) ; {No -6} Es probable que estas diferencias de comportamiento provoquen desconcierto, exacerbado por preguntas sobre el orden en que se copian los parámetros: ¿será de izquierda a derecha al salir y al entrar? Estos detalles probablemente no se expliquen con detalle en el manual del compilador y, si lo hacen, es probable que se pasen por alto por no ser relevantes para la tarea inmediata y se olviden para cuando surja un problema. Si (como es probable) se proporcionan valores temporales a través de un esquema de almacenamiento en pila, entonces es probable que el proceso de copia de retorno se realice en orden inverso al de copia de entrada, lo que en este ejemplo significaría que p1 sería el último valor devuelto a b .
El proceso de expansión de un procedimiento en línea no debe considerarse como una variante del reemplazo textual (como en las expansiones de macros ) porque pueden surgir errores de sintaxis como cuando se modifican parámetros y la invocación particular utiliza constantes como parámetros. Debido a que es importante estar seguro de que ninguna constante suministrada como parámetro cambiará su valor (las constantes se pueden mantener en la memoria al igual que las variables) para evitar que los usos posteriores de esa constante (realizados mediante referencia a su ubicación en la memoria) salgan mal, una técnica común es que el compilador genere código que copie el valor de la constante en una variable temporal cuya dirección se pasa al procedimiento, y si su valor se modifica, no importa; nunca se copia de nuevo a la ubicación de la constante.
Dicho de otro modo, un programa de prueba escrito cuidadosamente puede informar si los parámetros se pasan por valor o por referencia y, si se utilizan, qué tipo de esquema de copia de entrada y de copia de salida se utiliza. Sin embargo, la variación es infinita: los parámetros simples se pueden pasar por copia, mientras que los agregados grandes, como las matrices, se pueden pasar por referencia; las constantes simples, como el cero, se pueden generar mediante códigos de máquina especiales (como Clear o LoadZ), mientras que las constantes más complejas se pueden almacenar en la memoria etiquetadas como de solo lectura y cualquier intento de modificarlas provocaría la terminación inmediata del programa, etc.
Este ejemplo es extremadamente simple, aunque las complicaciones ya son evidentes. Lo más probable es que sea un caso de muchos procedimientos, que tengan una variedad de propiedades deducibles o declaradas por el programador que puedan permitir que las optimizaciones del compilador encuentren alguna ventaja. Cualquier parámetro de un procedimiento puede ser de solo lectura, puede escribirse en él, puede leerse y escribirse en él, o puede ignorarse por completo, lo que da lugar a oportunidades como que las constantes no necesiten protección mediante variables temporales, pero lo que sucede en cualquier invocación dada puede depender de una red compleja 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 de programación permiten (o incluso exigen) afirmaciones sobre el uso de parámetros, y pueden ofrecer además la oportunidad de declarar que los valores de las variables están restringidos a un conjunto determinado (por ejemplo, 6 < x ≤ 28), lo que proporciona más material para el proceso de optimización y también permite realizar 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, en caso afirmativo, 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 merecen una terminación inmediata? Incluso si todo eso se pudiera manejar, ¿qué beneficio podría derivar? ¿Y a qué costo? Las especificaciones completas equivaldrían a una reformulación de la función del programa en otra forma y, además del tiempo que consumiría el compilador para procesarlas, estarían sujetas a errores. En lugar de ello, solo se permiten especificaciones simples con verificación de rango en tiempo de ejecución.
En los casos en que un programa no lee ninguna entrada (como en el ejemplo), se podría imaginar que el análisis del compilador se lleva a cabo de modo que el resultado no sea más que una serie de instrucciones de impresión, o posiblemente algunos bucles que generen dichos valores de manera conveniente. ¿Reconocería entonces un programa para generar números primos y convertiría al método más conocido para hacerlo, o presentaría en cambio una referencia a una biblioteca? ¡Poco probable! En general, surgen consideraciones arbitrariamente complejas (el Entscheidungsproblem ) para impedir esto, y no hay otra opción que ejecutar el código con solo mejoras limitadas.
En el caso de los lenguajes procedimentales como ALGOL , el análisis y la optimización interprocedimentales parecen haber entrado en la práctica comercial a principios de los años 1970. El compilador optimizador PL/I de IBM realizó un análisis interprocedimental para comprender los efectos secundarios tanto de las llamadas a procedimientos como de las excepciones (convertidas, en términos de PL/I, como "con condiciones") [3] y en los artículos de Fran Allen . [4] [5] El trabajo sobre la compilación del lenguaje de programación APL fue necesariamente interprocedimental. [6] [7]
Las técnicas de análisis y optimización interprocedimental fueron objeto de investigación académica en los años 1980 y 1990. Reaparecieron en el mundo de los compiladores comerciales a principios de los años 1990 con los compiladores de Convex Computer Corporation (el "compilador de aplicaciones" para Convex C4) y de Ardent (el compilador para Ardent Titan ). Estos compiladores demostraron que las tecnologías podían hacerse lo suficientemente rápidas como para ser aceptables en un compilador comercial; posteriormente, las técnicas interprocedimentales han aparecido en varios sistemas comerciales y no comerciales.
La colección de compiladores GNU tiene funciones en línea en todos los niveles de optimización. En -O1esto solo se aplica a aquellas llamadas una sola vez ( -finline-functions-once), en -O2esta restricción se relaja ( -finline-functions). De manera predeterminada, este es un comportamiento de un solo archivo, pero con la optimización en 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 de 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 las bibliotecas estáticas , los enlazadores GNU más nuevos tienen una interfaz de "complemento de enlazador" que permite al compilador convertir los archivos de 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 "LTO pesado" que contenga tanto el código de máquina como la IR, pero esto ocupa más espacio. [1]
Dado que tanto GCC como LLVM (clang) pueden producir un IR a partir de una variedad de lenguajes de programación, la IPO en tiempo de enlace puede ocurrir incluso a través de los límites de los lenguajes. Esto se demuestra más comúnmente con C y C++, [9] pero LLVM lo hace posible para Rust y todos los demás compiladores basados en LLVM también. [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 de objeto y las funciones no estáticas nunca pueden eliminarse. El último problema tiene una solución no LTO: el -fwhole-programinterruptor se puede usar para asumir que solo main()es no estático, es decir, visible desde el exterior. [11]
Otra técnica que no es LTO son las "secciones de función" ( -ffunction-sectionsen GCC y Clang). Al colocar cada función en su propia sección en el archivo de objeto, el enlazador puede realizar la eliminación de código muerto sin un IR eliminando secciones no referenciadas (usando la opción del enlazador --gc-sections). [12] Una opción similar está disponible para las variables, pero hace que se produzca un código mucho peor.
Los compiladores Intel C/C++ permiten la IPO de todo el programa. El indicador para habilitar optimizaciones interprocedimentales para un solo archivo es -ip, el indicador para habilitar la optimización interprocedimental en todos los archivos del programa es -ipo. [13] [14]
El compilador MSVC , integrado en Visual Studio, también admite la optimización interprocedimental en todo el programa. [15]
Una interfaz independiente del compilador para permitir optimizaciones interprocedimentales de todo el programa es a través de la INTERPROCEDURAL_OPTIMIZATIONpropiedad en CMake . [16]
Las optimizaciones en tiempo de enlace no requieren la presencia de todo el programa para funcionar. Si el programa no requiere que se exporten símbolos, es posible combinar -flto y -fwhole-program para permitir que los optimizadores interprocedimentales utilicen suposiciones más agresivas que pueden llevar a oportunidades de optimización mejoradas. No es necesario el uso de -fwhole-program cuando el complemento de enlazador está activo (consulte -fuse-linker-plugin).