INF 441 / TD 6

Pierre-Yves Strub

TD 6 - machine virtuelle à pile

 Login :  Mot de passe :

Nous nous proposons dans ce TD de développer un interpréteur pour une machine à pile. Pour ce TD, nous vous fournissons une bibliothèque un parseur pour le langage assembleur de la machine virtuelle et nous concentrerons sur l’écriture de l’interpréteur.

Par la suite, lors d’une future session, nous écrirons un compilateur pour un langage While qui génèrera du code pour ladite machine virtuelle.

La machine virtuelle

La machine virtuelle que nous allons implémenter à les caractéristiques suivantes:

Op-codes

On donne dans cette section les types d’adressage possibles, ainsi que la liste des op-codes et la liste des instructions arithmetico-logiques.

Constantes machines

Certaines opérations peuvent manipuler des valeurs constantes directement.

On utilise la méta-variable $imm pour les constantes machines.

Adresse de pile

On rappelle que la pile de la machine est constitutée de cellules pouvant contenir chacun un mot et dont la première est à l’index 0. Il n’est pas possible de référencer une cellule directement par son index absolu mais relativement, via un offset, au registre SP ou FP. La syntaxe d’une telle adresse est %r+$imm (resp. %r-$imm) où r est SP ou FP et $imm est une constante. Une telle adresse référence la cellule dont l’index est égal au contenu du registre r auquel on a rajouté (resp. retranché) $imm.

Par convention, on appelle tête de pile la cellule dont l’index est %SP-1.

On utilise la méta-variable $address pour les adresses de pile.

Adresse d’instruction

La machine virtuelle possède un espace dédié au stockage du code à exécuter. Nous rappelons que ce dernier est stocké sous forme logique - une instruction occupe exactement une case mémoire. Les cases mémoires sont numérotées à partir de 0 et le code est toujours chargé à l’adresse 0.

Une adresse d’instruction est simplement une constante indique l’index de la case mémoire de l’instruction dans la mémoire dédiée.

On utilise la méta-variable $label pour les adresses d’instruction.

Liste des op-codes

La machine virtuelle possède 12 instructions, dont on donne le détail ci-dessous (Note: la résolution des adresses doit être faite avant le début de l’exécution de l’instruction. Par exemple, POP %SP-2 résoud %SP-2 avant de commencer à modifier la valeur de SP):

Nom Argument
PRT Affiche le contenu de R0 sur la sortie standard
DCD $imm Retire $imm éléments de la pile
POP Retire la tête de pile et charge son contenu dans R0
POP $address Retire la tête de pile et stocke son contenu à l’address $address
PUSH Pousse sur la pile le contenu de R0
PUSH $imm Pousse sur la pile la valeur $imm
PUSH $address Lit la pile à l’adresse $address et pousse le résultat sur la pile
LOAD $imm Charge la constante $imm dans R0
LOAD $address Lit la pile à l’adresse $address et stocke le résultat dans R0
STORE $address Lit le contenu de R0 et stocke le résultat dans la pile à l’adresse $address
JMP $label Déplace le pointeur d’instruction à l’adresse $label
JMPZ $label Si le contenu de R0 est nul, déplace le pointeur d’instruction à l’adresse $label
ALU $alucode Exécute l’opération arithmético-logique $alucode et pousse le résultat sur la pile
CALL $label Appel de procédure (cf. ci-dessous)
RET Retour de procédure (cf. ci-dessous)
STOP Arrêt de la VM

Les instructions RET et CALL seront utilisées pour l’appel de procédures. On donnera les détails de convention d’appel dans la seconde partie de ce projet. Pour le moment, vous avez seulement besoin de savoir que:

Liste des opérations arithmetico-logiques

La machine virtuelle donne accès à un ensemble d’opération arithmetico-logique, dont on donne le détail ci dessous. Les instructions arithmétiques sont toutes signées. Les instructions logiques considère le mot constant 0 comme la valeur de vérité fausse, et toute autre constante comme la valeur de vérité vraie. Les arguments des opérations sont lus sur la pile (de gauche à droite du haut de la pile vers sa base) pour les opérateurs prenant plusieurs arguments.

Nom Opération Nom Opération
ADD Addition entière signée SUB Soustraction entière signée
MUL Multiplication entière signée DIV Division entière signée
LT Comparaison signée stricte LE Comparaison signée large
AND Et logique OR Ou logique
NOT Négation logique NEG Négation entière signée

Travail demandé

À la fin de cette partie, vous devrez déposer votre assembleur:

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

On vous demande d’implémenter un évaluateur pour la machine virtuelle présentée ci-dessus. Ainsi,

  1. Définissez les structures de donnée nécessaires à la représentation des opcodes (incluant les constantes, les différents modes d’adressage et les codes de l’ALU).

    On rappelle que les mots machines sont de taille 64-bits. Le module OCaml Int64 (doc) contient un tel type. Il est possible de créer des valeurs litérales de type int64 via la syntaxe xxxL, par exemple 10L ou 0x1aL en hexadécimal.

  2. Écrivez une structure de donnée pour représenter l’état de la machine, à savoir, l’état de ses registres et de sa pile. Structurez autant que possible votre code, c’est-à-dire faites un module dédié pour la gestion de la pile (VMStack) et un pour la gestion de l’ensemble des registres (VMRegister). Ces structures seront par la suite utilisée de manière impérative, on vous demande d’éviter de faire des structures fonctionnelles pour ce TD. Notamment, la pile sera de taille fixe, qui sera donnée à l’initialisation, et devra permettre les accès aléatoires en lecture/écriture. (Vous pouvez regarder la question suivante pour avoir une idée des fonctionnalités demandées)

  3. Complétez les modules VMStack et VMRegister:

  4. Implémentez un module ALU pour les instructions arithmetico-logiques. Le module Int64 vous fournira toutes les opérations nécessaires:

  5. Écrivez les fonctions principales pour charger et évaluer les opcodes:

  6. À ce stade, il ne vous reste plus qu’à permettre la création d’une machine virtuelle à partir d’un programme:

    et de la tester sur le code suivant qui calcule la factorielle de 4 (en traduisant le programme à la main vers une liste d’opcode en OCaml):

  7. Il n’est pas toujours aisé de faire le calcul des adresses de code à la main pour les sauts, et surtout de le maintenir, l’ajout d’une instruction décalant toutes les adresses de 1. Pour palier ce problème, nous allons introduire des adresses logiques (ou étiquettes) qui seront ensuite résolues vers des adresses de code.

    1. Définir un type xopcode, similaire au type opcode ci-dessus, mais qui est paramétrique en le type des adresses de code. En redéfinissant opcode comme alias de type pour word xopcode, votre interpréteur devrait fonctionner sans modification.

      L’alias de type lopcode représente quant à lui un opcode où les adresses de code sont des étiquettes (string).

    2. Définissez un type srcasm dont les valeurs sont soit un lopcode (OPCode oc), soit une étiquette (Label lbl). Ce dernier permettra de marquer des endroits du code grâce à une étiquette et d’y faire référence par la suite dans les instruction JMP & JMPZ.

    3. Écrivez une fonction

      qui assemble un programme sous la forme d’une liste de srcasm en résolvant toutes les adresses logiques.

    4. Testez votre programme sur le code suivant (les entrées de la forme .label: indique où pointe, dans le code, l’étiquette label):