TD 8 - machine virtuelle à pile

 Login :  Mot de passe :

Nous nous proposons dans ce TD de développer un compilateur, vers une machine à pile, pour un langage While, ainsi que d'implémenter un interpréteur pour ladite machine. Pour ce TD, on vous fournit une bibliothèque qui contient un parseur et un vérificateur de type pour le langage While, ainsi qu'un parseur pour le langage assembleur de la machine virtuelle.

Ce TD se décompose en deux parties. La première partie, qui représente la partie "centrale" de ce TD, consiste en l'implémentation de la machine virtuelle. La seconde partie, qui peut être vue en approfondissement, traite du compilateur pour le langage While.

Installation de la bibliothèque de support

La bibliothèque de support est fournie dans une archive ZIP. Cette dernière contient un ensemble de fichiers sources qu'il faut déplacer à la racine de votre projet. Le module principal est VMLib. Vous l'importerez via l'instruction open Vmlib. L'interface de ce module est documentée dans le fichier vmlib.mli.

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).

    type word = Int64.t
    
    type alucode = ...
    type address = ...
    type opcode  = ...

    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)

    module VMStack : sig
      type stack
    end = struct
      ...
    end
    
    module VMRegister : sig
      (* Enumeration of the registers (by name) *)
      type register = SP | FP | IP | R0
    
      (* Holds the values for the 4 aforementioned registers *)
      (* A register can store exactly of word *)
      type registers
    end = struct
      ...
    end
    
    type vm = ...
  3. Complétez les modules VMStack et VMRegister:

    type vmerror =
      | InvalidAddress
      | DivisionByZero
    
    exception VMError of vmerror
    
    module VMStack : sig
      type stack
    
      (* [create sz] create a new stack of capacity [sz] *)
      val create : int -> stack
    
      (* [capacity st] returns the capacity, in words, of [st]. *)
      val capacity : stack -> int64
    
      (* [get st idx] returns the word located at index [idx] in [st].
         Raise [VMError InvalidAddress] if [idx] is valid *)
      val get : stack -> int64 -> word
    
      (* [set st idx w] sets to [w] the word located at index [idx]
         Raise [VMError InvalidAddress] if [idx] is valid *)
      val set : stack -> int64 -> word -> unit
    end
    
    module VMRegister : sig
      type registers
      type register = SP | FP | IP | R0
    
      (* All registers should default to 0 *)
      val create : unit -> registers
    
       (* Register setter *)
       val set : registers -> register -> word -> unit
    
       (* Register getter *)
       val get : registers -> register -> word
    end
  4. Implémentez un module ALU pour les instructions arithmetico-logiques. Le module Int64 vous fournira toutes les opérations nécessaires:

    module ALU : sig
      val op_add   : word -> word -> word
      val op_sub   : word -> word -> word
      val op_mul   : word -> word -> word
      val op_div   : word -> word -> word
      val op_neg   : word -> word
      val op_lt    : word -> word -> word
      val op_le    : word -> word -> word
      val op_land  : word -> word -> word
      val op_lor   : word -> word -> word
      val op_lnot  : word -> word
    end = struct
      let b2w (b : bool) = if b then 1L else 0L
    
      let op_add = Int64.add
      ...
    end
  5. Écrivez les fonctions principales pour charger et évaluer les opcodes:

    exception VMStop
    
    (* Fetch and return the currently IP-pointed opcode in [vm].
     * This function also increments the IP register so that it
     * points to the next opcode. *)
    let fetch (vm : vm) : opcode = ...
    
    (* Execute on [vm] the opcode [oc]. Raise [VMStop] when of the [vm]
     * wants to halt. *)
    let exec1 (vm : vm) (oc : opcode) : unit = ...
    
    (* Continuously fetch/exec until the [vm] wants to halt *)
    let exec (vm : vm) : unit = ...
  6. À ce stade, il ne vous reste plus qu'à permettre la création d'une machine virtuelle à partir d'un programme:

    val create : opcode array -> vm

    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):

    CALL    0x13
    STOP
    PUSH    0x01
    PUSH    %FP-3
    PUSH    0x00
    ALU     LT
    POP
    JMPZ    0x11
    PUSH    %FP-3
    PUSH    %FP+0
    ALU     MUL
    POP     %FP+0
    PUSH    0x01
    PUSH    %FP-3
    ALU     SUB
    POP     %FP-3
    JMP     0x03
    LOAD    %FP+0
    RET
    PUSH    0x04
    CALL    0x02
    DCD     0x01
    PRT
    RET
  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.

      type 'lbl xopcode = ...
      
      type opcode  = word   xopcode
      type lopcode = string xopcode

      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.

      type srcasm = ...
    3. Écrivez une fonction

      val resolve : srcasm list -> opcode list

      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):

      .entry:
          CALL    main
          STOP
      .fact:
          PUSH    0x01
      .fact_loop:
          PUSH    %FP-3
          PUSH    0x00
          ALU     LT
          POP
          JMPZ    fact_end
          PUSH    %FP-3
          PUSH    %FP+0
          ALU     MUL
          POP     %FP+0
          PUSH    0x01
          PUSH    %FP-3
          ALU     SUB
          POP     %FP-3
          JMP     fact_loop
      .fact_end:
          LOAD    %FP+0
          RET
      .main:
          PUSH    0x04
          CALL    fact
          DCD     0x01
          PRT
      .main_end:
          RET

Le langage While

Types

Le langage While est un langage typé statiquement et possède seulement deux types de base: int pour les entiers machines et bool pour les booléens. Il n'est pas possible d'y définir de types structurés tels les enregistrements.

Expressions

Les expressions du langage sont construites à partir des variables, des constantes entières (en base 10), des valeurs booléennes true et false, ainsi que par application d'opérateurs built-in (telles l'addition ou la négation logique).

Les expressions incluent les appels de procédures (cf. section suivante) sous la syntaxe proc(e1, ..., en)proc est le nom d'une procédure à \(n\) arguments et e1, ..., en sont des expressions qui tiennent lieu d'argument.

Procédures

Il est possible de définir des procédures en While via le mot-clef proc. Une procédure peut prendre des arguments et peut retourner un résultat. Le corps d'une procédure contient une partie de déclaration de variables (avec optionnellement des valeurs d'initialisation), ainsi que le corps de la procédure sous la forme d'une séquence d'instructions:

proc rty name(ty1 arg1, ..., tyn argn) {
  var x1 : tyx1 = e1;
  ...
  var xk : tyxk = ek;
 
  $body;
}

Dans l'exemple ci-dessus, $name est le nom de la procédure et rty est son type de retour (ou void si la procédure ne retourne pas de résultat). Cette procédure prend \(n\) arguments respectivement de type ty1, ..., tyn et qui sont respectivement nommés arg1, ..., argn. Enfin, la procédure déclare \(k\) arguments nommés x1, ..., xk, respectivement de type tyx1, ..., tyxk et respectivement initialisées avec les expressions e1, ..., ek - la partie initialisation étant optionnelle.

Les procédures peuvent être récursives, c'est-à-dire que name peut-faire appel à elle-même dans son corps.

Instructions

Une instruction peut être une affection, une conditionnelle, une boucle while ou une sortie de procédure. Nous donnons leur syntaxe respective ci-dessous, où $block désigne un bloc d'instructions (c'est-à-dire soit une instruction, soit une séquence d'instructions entre accolades):

Instruction Syntaxe
Affectation x = e;
Affectation - retour oublié e;
Conditionnelle if (e) $block else $block
Conditionnelle (sans else) if (e) $block
Boucle while while (e) $block
Sortie de procédure return e;
Sortie de procédure - pas de valeur de retour return ;
Affichage d'une expression (+ NL) print e;

Programme

Un programme est une suite de procédures. Chaque procédure peut faire appel aux procédures qui la précède (ainsi qu'à elle-même).

Exemple

Par exemple, la fonction fact suivante, écrite en While, permet de calculer la factorielle de son argument:

proc int fact(int arg) {
  var res : int = 1;

  while (0 < arg) {
    res = res * arg;
    arg = arg - 1;
  }
  
  return res;
}

Travail demandé

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

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

On vous fourni un parser et analyseur de types pour While. Ainsi, il vous sera possible d'obtenir, à partir d'un fichier source, un arbre de syntaxe typé via le programme OCaml suivant:

let prg = Vmlib.parse_and_tt_file_or_die "filename.wil" in
() (* do something with [prg] *)

Le type de prg est Vmlib.AST.procdef list. De même, le type pour les types, expressions et instructions de While sont respectivement (toujours dans le module Vmlib.AST) type_, expr et instr. Allez voir ces différents types avant de commencer les questions suivantes.

Évaluation des expressions (sans appel de procédures)

Écrire une fonction

module SMap = Map.Make(String)

type cglocals = int SMap.t

val cg_expr : cglocals -> Ast.expr -> srcasm

qui procède à l'assemblage de l'expression donnée en argument. Cette fonction ne prendra pas en charge les appels de procédures (vous échouez si vous voyez le constructeur EProc). En revanche, elle prendra en charge la résolution des variables grâce au premier argument de type cglocals. Ce dernier est une map des identifiants de variable vers des offsets et associe, à une variable, son adresse dans la pile par rapport au registre FP.

Le code assembleur généré poussera le résultat de l'évaluation de l'expression en tête de pile. Il peut modifier le registre R0, mais ne doit pas modifier le registre IP et doit conserver les registres FP.

Par exemple, la compilation de l'expression x (accès à une variable locale) résultera en le code suivant:

LOAD  %FP+$imm(x)
PUSH

$imm(x) est l'offset associé à x dans la map cglocals. Si besoin, les résultats intermédiaires pourront être stockés sur la pile pour une utilisation ultérieure. Par exemple, l'assemblage de e1 + e2 produira:

$ASSEMBLE(e2)
$ASSEMBLE(e1)
ADD

où $ASSEMBLE(ei) est le résultat de l'assemblage de ei.

Pour tester votre assembleur, on vous fournit une API pour parser et typer les expressions (respectivement Vmlib.pexpr_of_string et Vmlib.tt_expr):

val pexpr_of_string : string -> Syntax.pexpr

val tt_expr :
     (Ast.ident * Ast.type_) list
  -> Syntax.pexpr
  -> Ast.expr * (Ast.type_ option)

où le premier argument de tt_expr est la liste des variables locales avec leur type respectif.

Par exemples, vous pourrez tester le programme suivant:

    PUSH 2       ; x -> %FP+0
    PUSH 5       ; y -> %FP+1
    PUSH 34      ; z -> %FP+2
    $ASSEMBLE(x + y * z)
    POP          ; load the evaluation of the expr. into R0
    PRT          ; print R0
    STOP

$ASSEMBLE(...) représente l'assemblage de l'expression donnée en paramètre.

Évaluation des instructions

Nous allons maintenant procédé à l'assemblage des instructions. Écrire une paire de fonctions:

val cg_instr : cglocals -> Ast.instr -> srcasm
val cg_stmt  : cglocals -> Ast.stmt  -> srcasm

qui procède respectivement à l'assemblage d'une instruction et d'un bloc d'instructions. On vous demande de ne pas gérer l'instruction return pour le moment. Le code assembleur généré devra laissé la pile invariante. Il peut modifier le registre R0, mais ne doit pas modifier le registre IP et doit conserver les registres FP & SP.

Afin de gérer le contrôle de flot (conditionnelle / boucle while), vous devrez générer des étiquettes et produire les sauts adéquates. Par exemple, l'assemblage de if (e1) { x = e2; } produire un code assembleur dans les lignes de:

    $ASSEMBLE(e1)
    POP
    JMPZ end_if
    $ASSEMBLE(e2)
    POP
    STORE %FP+$imm(x)
.end_if:

$imm(x) est l'offset associé à x dans la map cglocals, $ASSEMBLE(ei) est le résultat de l'assemblage de l'expression ei et end_if est une étiquette fraîche.

Pour tester votre assembleur, on vous fournit une API pour parser et typer les blocs d'instructions (respectivement Vmlib.pstmt_of_string et Vmlib.tt_stmt):

val pstmt_of_string : string -> Syntax.pstmt

val tt_stmt : (Ast.ident * Ast.type_) list -> Syntax.pstmt -> Ast.stmt

où le premier argument de tt_stmt est, comme pour tt_expr, la liste des variables locales avec leur type respectif.

Par exemples, vous pourrez tester le programme suivant:

    PUSH 2       ; x -> %FP+0
    PUSH 5       ; y -> %FP+1
    PUSH 34      ; z -> %FP+2
    $ASSEMBLE(
      x = x + y * z;
      if (z < 50) { x = x + 1; }
    )
    LOAD %FP+0   ; load x
    PRT          ; print x
    STOP

$ASSEMBLE(...) représente l'assemblage de l'instruction donnée en paramètre.

Évaluation des appels de procédure

Nous allons maintenant procéder à l'assemblage des procédures et de leurs appels. Pour cela, il faut décider de comment les arguments, variables locales, adresse de retour, etc... (ce qu'on appelle bloc d'activation) sont stockés et qui est en charge de construire et de nettoyer les différentes parties de ces blocs d'activation. L'ensemble de ces règles, qui varient d'une architecture et d'un langage à l'autre, est ce qu'on appelle la convention d'appel.

Nous allons maintenant définir la convention d'appel pour le langage While. Le bloc d'activation d'une procédure While est entièrement, comme illustré en vert sur le schéma ci-dessous:

On voit que deux registres participent à la définition du bloc d'activation: SP et FP. Ces deux registres définissent la fenêtre dans laquelle les variables locales de la procédure sont stockées. Il est toujours possible d'ajouter de nouvelles valeurs locales en repoussant ce registre SP, par exemple via l'op-code PUSH qui pousse le contenu de R0 sur la pile.

Cependant, cette fenêtre ne définit pas le bloc d'activation à elle seule: avant FP se trouvent les valeurs $RA (pour return address) et $FP. Ces dernières permettent respectivement de retrouver le pointeur d'exécution (IP) et le pointeur de bloc d'activation (FP) de l'appelant. En effet, ces deux registres ont été effacés lors de l'appel et il nous faudra les retrouver au retour de procédure pour reprendre l'exécution de l'appelant.

Enfin, avant les sauvegardes de FP et IP se situe l'ensemble des arguments de la procédure, dont le nombre dépend de la procédure mais qui est statiquement connu (c'est-à-dire qui est connu lors de la phase d'assemblage).

La convention d'appel est la suivante:

  1. L'appelant pousse sur la pile l'ensemble des arguments de la procédure de droite à gauche - c'est-à-dire que le dernier argument de la procédure sera la premier poussé sur la pile.
  2. Ensuite, il pousse la valeur de FP et IP (dans cet ordre) sur la pile et positionne IP sur l'adresse de code de la procédure. L'ensemble de ces opérations peut être fait via l'op-code CALL
  3. L'appelé commence son exécution et créé de l'espace sur la pile pour ses variables locales. Il a le droit de modifier R0, ne doit pas toucher IP directement et doit préserver FP (c'est-à-dire qu'il doit le restaurer en fait d'exécution de la procédure.
  4. Une fois l'exécution terminée, l'appelé utilise R0 pour retourner stocker son résultat. Il restore alors le bloc d'activation de l'appelant en copiant FP dans SP, puis en retrouvant les anciennes valeurs de FP et IP sur la pile.
  5. Finalement, l'appelant nettoie sa pile en y supprimant les arguments de la procédure appelée.

On retrouve dans le diagramme ci-dessous les différentes phases de la convention d'appel:

On vous demande de modifier l'assemblage des expressions / instructions de manière à ce qu'il supporte les procédures (instruction return et appel de procédures dans les expressions). Enfin, si une procédure porte le nom main qui ne prend pas d'argument, faites en sorte que cette procédure soit appelée par défaut. Vérifiez que le programme suivant fonctionne:

int fact(int i) {
  int r = 1;

  while (0 < i) {
    r = r * i;
    i = i - 1;
  }
  return r;
}

void main() {
  print fact(5);
}