Introduction douce à JIT et compilation dynamique / génération de code

Question

La autre question traite déjà de la base, d'une simplicité trompeuse, de la génération de code dynamique au sein d'un environnement C / C ++. Y at-il des introductions douces dans le sujet avec des exemples de code?

Mes yeux commencent à saigner en regardant des compilateurs JIT open source extrêmement complexes alors que mes besoins sont beaucoup plus modestes.

Existe-t-il de bons textes sur le sujet qui ne supposent pas un doctorat en informatique? Je recherche des motifs usés, des éléments à surveiller, des considérations de performance, etc. Les ressources électroniques ou basées sur des arbres peuvent être tout aussi utiles. Vous pouvez assumer une connaissance pratique du langage d'assemblage (pas uniquement x86).

Answer 1

Eh bien, un motif que j'ai utilisé dans les émulateurs ressemble à ceci:

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();
    }
}

Ceci est une simplification, mais l’idée est là. Fondamentalement, chaque fois que le moteur est invité à exécuter un "bloc de base" (généralement tout à fait possible jusqu'à la prochaine opération de contrôle de flux ou toute la fonction), il le recherchera pour voir s'il a déjà été créé. Si tel est le cas, exécutez-le, sinon créez-le, ajoutez-le, puis exécutez-le.

rinçage répété:)

En ce qui concerne la génération de code, cela se complique un peu, mais l’idée est d’émettre une "fonction" appropriée. qui fait le travail de votre bloc de base dans le contexte de votre VM.

EDIT: notez que je n’ai pas non plus présenté d’optimisation, mais vous avez demandé une "introduction douce"

.

EDIT 2: J'ai oublié de mentionner l'un des accélérateurs les plus productifs que vous puissiez implémenter avec ce modèle. Fondamentalement, si vous ne supprimez jamais un bloc de votre arbre (vous pouvez le contourner si vous le faites, mais c'est beaucoup plus simple si vous ne le faites jamais), vous pouvez alors "chaîner" bloque ensemble pour éviter les recherches. Voici le concept. Chaque fois que vous revenez de f () et que vous êtes sur le point de faire le "update_instruction_pointer", si le bloc que vous venez d'exécuter s'est terminé en appel, en saut inconditionnel ou ne s'est pas terminé en contrôle de flux, vous pouvez alors "réparer". ; son instruction ret avec un jmp direct au bloc suivant qu’elle exécutera (car ce sera toujours le même) si vous l’avez déjà émise. Cela signifie que vous exécutez de plus en plus souvent dans la machine virtuelle et de moins en moins dans la commande & execute; execute_block " fonction.

Answer 2

Je ne connais aucune source spécifiquement liée aux JIT, mais j'imagine que c'est un peu comme un compilateur normal, mais plus simple si vous n'êtes pas inquiet pour la performance.

La méthode la plus simple consiste à utiliser un interpréteur de machine virtuelle. Ensuite, pour chaque instruction de machine virtuelle, générez le code d'assemblage que l'interpréteur aurait exécuté.

Pour aller au-delà, j'imagine que vous devez analyser les codes d'octets de la machine virtuelle, les convertir en une sorte de forme intermédiaire appropriée (code d'adresse à trois? SSA?), puis optimiser et générer du code comme dans tout autre compilateur.

Pour une machine virtuelle basée sur une pile, il peut être utile de garder une trace du "courant". profondeur de la pile lorsque vous traduisez les codes d’octets en une forme intermédiaire et traitez chaque emplacement de la pile comme une variable. Par exemple, si vous pensez que la profondeur actuelle de la pile est de 4 et que vous voyez un "push" instruction, vous pouvez générer une affectation à " stack_variable_5 " et incrémenter un compteur de pile de compilation, ou quelque chose comme ça. Un " ajouter " lorsque la profondeur de la pile est égale à 5, le code peut être généré: "pile_variable_4 = pile_variable_4 + pile_variable_5" et décrémenter le compteur de pile de temps de compilation.

Il est également possible de traduire le code basé sur la pile en arbres de syntaxe. Maintenir une pile au moment de la compilation. Chaque " push " L’instruction fait en sorte que la représentation de la chose poussée soit stockée dans la pile. Les opérateurs créent des nœuds d'arborescence de syntaxe qui incluent leurs opérandes. Par exemple, " X Y + " peut provoquer que la pile contienne "var (X)", puis "var (X) var (Y)" puis le plus fait apparaître les deux références var et pousse "plus (var (X), var (Y))".

Answer 3

Procurez-vous un exemplaire du livre de Joel Pobar sur Rotor (lorsqu'il est disponible) et explorez la source jusqu'au SSCLI . Attention, la folie est en dedans:)