Suave introducción a JIT y compilación dinámica / generación de código.

Question

La base aparentemente simple de la generación de código dinámico dentro de un marco C / C ++ ya se ha tratado en otra pregunta . ¿Hay alguna introducción suave en el tema con ejemplos de código?

Mis ojos están empezando a sangrar mirando a los compiladores JIT de código abierto muy intrincados cuando mis necesidades son mucho más modestas.

¿Existen buenos textos sobre el tema que no supongan un doctorado en informática? Estoy buscando patrones bien gastados, cosas a tener en cuenta, consideraciones de rendimiento, etc. Los recursos electrónicos o basados ??en árboles pueden ser igualmente valiosos. Puede asumir un conocimiento práctico del lenguaje ensamblador (no solo de x86).

Answer 1

Bueno, un patrón que he usado en emuladores es algo como esto:

typedef void (*code_ptr)();
unsigned long instruction_pointer = entry_point;
std::map<unsigned long, code_ptr> code_map;


void execute_block() {
    code_ptr f;
    std::map<unsigned long, void *>::iterator it = code_map.find(instruction_pointer);
    if(it != code_map.end()) {
        f = it->second
    } else {
        f = generate_code_block();
        code_map[instruction_pointer] = f;
    }
    f();
    instruction_pointer = update_instruction_pointer();
}

void execute() {
    while(true) {
        execute_block();
    }
}

Esto es una simplificación, pero la idea está ahí. Básicamente, cada vez que se le pide al motor que ejecute un " bloque básico " (Por lo general, un todo, hasta la siguiente operación de control de flujo o una función completa en la medida de lo posible), lo buscará para ver si ya se ha creado. Si es así, ejecútelo, o créelo, agréguelo y luego ejecútelo.

repetición de enjuague :)

En cuanto a la generación de código, eso se complica un poco, pero la idea es emitir una función " " adecuada " que hace el trabajo de su bloque básico en el contexto de su máquina virtual.

EDITAR: tenga en cuenta que tampoco he demostrado optimizaciones, pero pidió una " introducción suave "

EDIT 2: olvidé mencionar uno de los incrementos de velocidad más productivos que puedes implementar con este patrón. Básicamente, si nunca elimina un bloque de su árbol (puede solucionarlo si lo hace, pero es mucho más sencillo si nunca lo hace), entonces puede " encadenar " bloques juntos para evitar búsquedas. Aquí está el concepto. Cuando regrese de f () y esté a punto de hacer " update_instruction_pointer " ;, si el bloque que acaba de ejecutar finalizó en una llamada, un salto incondicional o no terminó en absoluto en el control de flujo, entonces puede "fixup" " ; su instrucción ret con un jmp directo al siguiente bloque que ejecutará (porque siempre será el mismo) si ya lo ha emitido. Esto lo hace así que está ejecutando más y más a menudo en la máquina virtual y cada vez menos en el " execute_block " función.

Answer 2

No tengo conocimiento de ninguna fuente relacionada específicamente con JIT, pero me imagino que es como un compilador normal, pero es más simple si no estás preocupado por el rendimiento.

La forma más sencilla es comenzar con un intérprete de máquina virtual. Luego, para cada instrucción de VM, genere el código de ensamblaje que el intérprete habría ejecutado.

Para ir más allá de eso, me imagino que usted analizaría los códigos de bytes de la máquina virtual y los convertiría en algún tipo de forma intermedia adecuada (¿tres códigos de dirección? ¿SSA?) y luego optimizaría y generaría el código como en cualquier otro compilador.

Para una máquina virtual basada en pila, puede ser útil hacer un seguimiento de la " actual " la profundidad de la pila a medida que traduce los códigos de bytes en forma intermedia, y trata cada ubicación de la pila como una variable. Por ejemplo, si piensa que la profundidad de pila actual es 4 y ve un " empuje " instrucción, puede generar una asignación a " stack_variable_5 " e incrementar un contador de pila de tiempo de compilación, o algo así. Un " añadir " cuando la profundidad de la pila es 5, se podría generar el código "stack_variable_4 = stack_variable_4 + stack_variable_5 " y disminuir el contador de la pila de tiempo de compilación.

También es posible traducir código basado en pila en árboles de sintaxis. Mantener una pila de tiempo de compilación. Cada " empuje " la instrucción hace que una representación de la cosa que se empuja se almacene en la pila. Los operadores crean nodos de árbol de sintaxis que incluyen sus operandos. Por ejemplo, " X Y + " puede hacer que la pila contenga " var (X) " ;, luego " var (X) var (Y) " y luego el signo más quita ambas referencias var y apaga " más (var (X), var (Y)) " ;.

Answer 3

Consiga una copia del libro de Joel Pobar en Rotor (cuando esté disponible), y profundice en la fuente hasta SSCLI . Cuidado, la locura está dentro :)