Compilación Tracing Just-in-time (T-JIT)

La compilación Tracing Just-in-time o compilación en tiempo de ejecución por segmentos 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 según el método.

Visión general

La compilación justo a tiempo es una técnica para aumentar la velocidad de ejecución de los 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 por su ámbito 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 seguimiento usan bucles que se ejecutan con frecuencia como su unidad de compilación. Los JIT de seguimiento se basan en la suposición de que los programas pasan la mayor parte de su tiempo en algunos bucles del programa ("bucles calientes") y las iteraciones de bucle subsiguientes a menudo toman rutas 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.

Detalles técnicos

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 denomina traza. Luego, la traza se optimiza y se compila en código de máquina (traza). Cuando este bucle se vuelve a ejecutar, se llama al seguimiento compilado en lugar de la contraparte del programa.

Estos pasos se explican en detalle a continuación:

Fase de perfilado

El objetivo de la creación de perfiles es identificar bucles calientes. Esto se suele hacer contando el número de iteraciones de cada ciclo. Después de que el conteo de un bucle supera un cierto umbral, se considera que el bucle está activo y se ingresa a la fase de seguimiento.

Fase de seguimiento

En la fase de seguimiento, la ejecución del bucle procede con normalidad, 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 a las llamadas a funciones, lo que lleva a que se alineen en el seguimiento. El rastreo continúa hasta que el ciclo llega a su final y vuelve al inicio.

Dado que la traza se registra siguiendo una ruta de ejecución concreta del bucle, las ejecuciones posteriores de esa traza pueden divergir de esa ruta. Para identificar los lugares donde eso puede suceder, se insertan instrucciones especiales de protección en el seguimiento. Un ejemplo de tal lugar son las declaraciones if. El protector es una verificación rápida para determinar si la condición original sigue siendo cierta. Si un guardián falla, se aborta la ejecución del rastreo.

Dado que el rastreo se realiza durante la ejecución, se puede hacer que el rastreo contenga información de tiempo de ejecución (por ejemplo, información de tipo). Esta información se puede usar más tarde en la fase de optimización para aumentar la eficiencia del código.

Fase de optimización y generación de código

Los seguimientos son fáciles de optimizar, ya que representan solo una ruta de ejecución, lo que significa que no existe un flujo de control y no necesita manipulación. Las optimizaciones típicas incluyen la eliminación de subexpresiones constantes, la eliminación de códigos muertos, la asignación de registros, el movimiento de códigos invariantes, el plegado constante y el análisis de escape.

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.

Ejecución

Una vez que la traza se ha compilado en código de máquina, se puede ejecutar en iteraciones posteriores del ciclo. La ejecución de seguimiento continúa hasta que falla una protección.

Historia

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 solo recientemente. La primera mención de una idea similar a la idea actual de rastrear JIT fue en 1970. 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 de seguimiento 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 nativas a medida que se ejecuta en el procesador". Para hacer esto, el flujo de instrucciones nativas 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.

Dynamo se amplió más tarde a DynamoRIO. Un proyecto basado en DynamoRIO fue un marco para la construcción de intérpretes que combina rastreo y evaluación parcial. Se utilizó para "eliminar dinámicamente la sobrecarga del intérprete de las implementaciones del lenguaje".

En 2006, se desarrolló HotpathVM, el primer compilador JIT de rastreo para un lenguaje de alto nivel. Esta VM fue 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 la construcción de asignación única estática (SSA). La motivación para HotpathVM era tener una JVM eficiente para dispositivos móviles con recursos limitados.

Otro ejemplo de un JIT de seguimiento es TraceMonkey, una de las implementaciones de JavaScript de Mozilla para Firefox (2009). TraceMonkey compila seguimientos de bucle 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 lenguaje que se escribieron con la cadena de herramientas de traducción de PyPy, mejorando así el rendimiento de cualquier programa que se ejecute con ese intérprete. Esto es posible rastreando al propio intérprete, en lugar del programa que ejecuta el intérprete.

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 usar para rastrear a través de una implementación de JavaScript.

Ejemplo de un rastro

Considere el siguiente programa de Python que calcula una suma de cuadrados de números enteros sucesivos hasta que esa suma exceda 100000:

def  cuadrado (x): 
    devuelve  x  *  x

i  =  0 
y  =  0 
while  True : 
    y  +=  cuadrado (i) 
    si  y  >  100000: 
        break 
    i  =  i  +  1

Un rastro para este programa podría verse así:

 loopstart (i1,  y1) 
 i2  =  int_mul (i1,  i1) 		# x*x 
 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 squarese inserta en la traza y cómo la instrucción if se convierte en un archivo guard_false.