El seguimiento de la compilación justo a tiempo es una técnica utilizada por las máquinas virtuales para optimizar la ejecución de un programa en tiempo de ejecución . Esto se hace registrando una secuencia lineal de operaciones ejecutadas con frecuencia, compilándolas en código de máquina nativo y ejecutándolas. Esto se opone a los compiladores tradicionales justo a tiempo (JIT) que funcionan por método.
La compilación justo a tiempo es una técnica para aumentar la velocidad de ejecución de programas mediante la compilación de partes de un programa en código de máquina en tiempo de ejecución. Una forma de categorizar diferentes compiladores JIT es según su alcance de compilación. Mientras que los compiladores JIT basados en métodos traducen un método a la vez a código de máquina, los JIT de rastreo utilizan bucles ejecutados con frecuencia como unidad de compilación. Los JIT de seguimiento se basan en el supuesto de que los programas pasan la mayor parte de su tiempo en algunos bucles del programa ("bucles calientes") y que las iteraciones de bucles posteriores suelen tomar caminos similares. Las máquinas virtuales que tienen un JIT de seguimiento suelen ser entornos de ejecución de modo mixto, lo que significa que tienen un intérprete o un compilador de métodos además del JIT de seguimiento.
Un compilador JIT de seguimiento pasa por varias fases en tiempo de ejecución. En primer lugar, se recopila información de perfiles para los bucles. Una vez que se ha identificado un bucle activo, se ingresa a una fase de seguimiento especial , que registra todas las operaciones ejecutadas de ese bucle. Esta secuencia de operaciones se llama seguimiento. Luego, el seguimiento se optimiza y se compila en código de máquina (rastreo). Cuando este bucle se ejecuta nuevamente, se llama al seguimiento compilado en lugar de a la contraparte del programa.
Estos pasos se explican en detalle a continuación:
El objetivo de la elaboración de perfiles es identificar bucles activos. Esto suele hacerse contando el número de iteraciones de cada bucle. Después de que el recuento de un bucle supera un cierto umbral, se considera que el bucle está activo y se ingresa en la fase de rastreo.
En la fase de seguimiento, la ejecución del bucle se desarrolla normalmente, pero además cada operación ejecutada se registra en un seguimiento. Las operaciones registradas normalmente se almacenan en un árbol de seguimiento , a menudo en una representación intermedia (IR). El seguimiento sigue las llamadas a funciones, lo que hace que se incluyan en el seguimiento. El rastreo continúa hasta que el bucle llega a su final y vuelve al inicio.
Dado que el seguimiento se registra siguiendo una ruta de ejecución concreta del bucle, las ejecuciones posteriores de ese seguimiento pueden divergir de esa ruta. Para identificar los lugares donde esto puede suceder, se insertan instrucciones de guardia especiales en el rastro. Un ejemplo de un lugar así son las declaraciones if. El guardia realiza una verificación rápida para determinar si la condición original sigue siendo cierta. Si falla una guarda, se aborta la ejecución del rastreo.
Dado que el seguimiento se realiza durante la ejecución, se puede hacer que el seguimiento contenga información de tiempo de ejecución (por ejemplo, información de tipo ). Esta información se puede utilizar posteriormente en la fase de optimización para aumentar la eficiencia del código.
Las trazas son fáciles de optimizar, ya que representan sólo una ruta de ejecución, lo que significa que no existe ningún flujo de control y no necesita manipulación. Las optimizaciones típicas incluyen eliminación de subexpresiones constantes , eliminación de códigos inactivos , asignación de registros , movimiento de códigos invariantes , plegado constante y análisis de escape . [1]
Después de la optimización, la traza se convierte en código de máquina. De manera similar a la optimización, esto es fácil debido a la naturaleza lineal de las trazas.
Una vez que el seguimiento se ha compilado en código de máquina, se puede ejecutar en iteraciones posteriores del bucle. La ejecución del seguimiento continúa hasta que falla una guardia.
Mientras que la idea de los JIT se remonta a la década de 1960, los JIT de rastreo se han utilizado con más frecuencia sólo recientemente. La primera mención de una idea similar a la idea actual de rastrear JIT fue en 1970. [2] Se observó que el código compilado podría derivarse de un intérprete en tiempo de ejecución simplemente almacenando las acciones realizadas durante la interpretación.
La primera implementación del rastreo es Dynamo, "un sistema de optimización dinámica de software que es capaz de mejorar de forma transparente el rendimiento de un flujo de instrucciones nativo a medida que se ejecuta en el procesador". [3] Para hacer esto, el flujo de instrucciones nativo se interpreta hasta que se encuentra una secuencia de instrucciones "activa". Para esta secuencia se genera, almacena en caché y ejecuta una versión optimizada.
Posteriormente, Dynamo se amplió a DynamoRIO . Un proyecto basado en DynamoRIO fue un marco para la construcción de intérpretes que combina el rastreo y la evaluación parcial. Se utilizó para "eliminar dinámicamente la sobrecarga del intérprete de las implementaciones del lenguaje". [4]
En 2006, se desarrolló HotpathVM, el primer compilador JIT de seguimiento para un lenguaje de alto nivel [ cita necesaria ] . [5] Esta máquina virtual era capaz de identificar dinámicamente instrucciones de código de bytes ejecutadas con frecuencia, que se rastrean y luego se compilan en código de máquina mediante una construcción de asignación única estática (SSA). La motivación para HotpathVM fue tener una JVM eficiente para dispositivos móviles con recursos limitados.
Otro ejemplo de JIT de seguimiento es TraceMonkey , una de las implementaciones de JavaScript de Mozilla para Firefox (2009). [6] TraceMonkey compila seguimientos de bucles ejecutados con frecuencia en el lenguaje dinámico JavaScript en tiempo de ejecución y especializa el código generado para los tipos dinámicos reales que ocurren en cada ruta.
Otro proyecto que utiliza JIT de seguimiento es PyPy . Permite el uso de JIT de seguimiento para implementaciones de lenguajes que se escribieron con la cadena de herramientas de traducción de PyPy, mejorando así el rendimiento de cualquier programa que se ejecute utilizando ese intérprete. Esto es posible rastreando al propio intérprete, en lugar del programa que ejecuta el intérprete. [7]
Microsoft también ha explorado el seguimiento de JIT en el proyecto SPUR para su lenguaje intermedio común (CIL). SPUR es un rastreador genérico para CIL, que también se puede utilizar para rastrear a través de una implementación de JavaScript. [8]
Considere el siguiente programa Python que calcula una suma de cuadrados de números enteros sucesivos hasta que esa suma exceda 100000:
def cuadrado ( x ): devolver x * xi = 0 y = 0 mientras que Verdadero : y += cuadrado ( i ) si y > 100000 : romper i = i + 1Un seguimiento de este programa podría verse así:
inicio de bucle ( i1 , y1 ) i2 = int_mul ( i1 , i1 ) # i*i y2 = int_add ( y1 , i2 ) # y += i*i b1 = int_gt ( y2 , 100000 ) guard_false ( b1 ) i3 = int_add ( i1) , 1 ) # i = i+1 salto ( i3 , y2 )Observe cómo la llamada a la función squareestá integrada en el seguimiento y cómo la declaración if se convierte en un archivo guard_false.
