TD 8 - compilation d’un langage While

Nous nous proposons dans ce TD de développer un compilateur, vers une machine à pile, pour un langage While. La machine cible sera la VM développée lors du TD6.

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.

Vous pouvez, au choix, utiliser votre implémentation de la VM ou bien utiliser celle donnée en correction.

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. Cette archive vient également avec la correction de la VM (module Asmvm).

La machine virtuelle

La description de la machine virtuelle peut-être retrouvée dans le sujet du TD 6.

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

rty name(ty1 arg1, ..., tyn argn) {
  tyx1 x1 = e1;
  ...
  tyxk xk = 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):

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:

int fact(int arg) {
  int res = 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:

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.

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

Écrire une fonction

open Asmvm
open Asmvm.VM
open Asmvm.HiAsm

open Vmlib
open Vmlib.Ast

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

où $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

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

2. É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:

où $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

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

3. É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);
}