Production de code

Le but de ce TD est d'étendre le mini-langage Arith du TD 2 avec des fonctions. On souhaite pouvoir écrire des programmes de la forme suivante : 
  set f(x,y) = let z = x + 4 in x + y + z
  set g(x) = f(x,10) + 3
  print g(4)

Pour vous aider, nous vous fournissons un squelette de compilateur dans lequel certaines parties sont à compléter. Une fois cette archive décompressée avec tar zxvf arithfun.tar.gz, vous obtenez un répertoire arithfun/ contenant les fichiers suivants :

ast.mli la syntaxe abstraite d'Arith (complet)
lexer.mll l'analyseur lexical (complet)
parser.mly l'analyseur syntaxique (complet)
x86_64.ml pour écrire du code X86-64 (complet)
compile.ml la compilation proprement dite (à compléter)
main.ml le programme principal (complet)
Makefile pour automatiser la compilation (complet)
test.exp un fichier de tests, utilisé quand on lance make

Le code fourni compile mais il est incomplet : vous devez compléter le fichier compile.ml.

Question 1. Allocation des variables

Avant de chercher à produire du code X86-64, on va déterminer l'emplacement de chaque variable.

Les variables globales introduites par set sont allouées dans le segment de données, et sont identifiées par leur nom. La table de hachage Compile.genv contient les variables globales qui ont été introduites avec set.

Les variables locales, introduites par let ou arguments de fonction, sont allouées sur la pile. Dans les deux cas, on y fait référence par leur position relative au registre %rbp. Plus précisément, on adopte un schéma de compilation classique : l'appelant passe les arguments sur la pile, puis l'appelé sauvegarde %rbp sur la pile et alloue de la place pour ses variables locales. Ainsi, pour une fonction de la forme set f(x,y) = let z = x+3 in z+y, on aura le tableau d'activation suivant : 

         |   .....   |
         |     x     |   construit par
         |     y     |   l'appelant
  ----------------------------------
         |adr. retour|
  ----------------------------------
 %rbp--> | sauv. %rbp|   construit par
         |     z     |   l'appelé
         |   .....   |
c'est-à-dire, les décalages 24 pour x, 16 pour y et -8 pour z.

Le but de cette question est de reconstruire de nouveaux arbres de syntaxe abstraite dans lesquels les variables locales sont maintenant des entiers représentant ces décalages. Pour cela, vous devez compléter les deux fonctions suivantes dans compile.ml : 

  val alloc_expr: local_env -> int -> Ast.pexpr -> Ast.expr * int
  val alloc_stmt: Ast.pstmt -> Ast.stmt
La fonction alloc_expr reçoit en argument L'entier renvoyé par alloc_expr correspond à la taille totale occupée par les variables locales de l'expression. Notez que les nouveaux arbres de syntaxe abstraite distinguent les variables locales (LVar) et globales (GVar). La fonction alloc_expr doit lever l'exception VarUndef si elle rencontre une variable qui n'a pas été déclarée.

La fonction alloc_stmt renvoie des instructions qui contiennent un argument supplémentaire indiquant l'espace mémoire à réserver sur la pile pour les variables locales des expressions considérées. Notez que le constructeur Fun ne contient plus les paramètres formels de la fonction, car leurs occurrences sont maintenant représentées par des entiers. Par ailleurs, la fonction alloc_stmt remplit la table de hachage Compile.genv avec les variables globales.

Exemple : sur le programme suivant 

set h =
  let x = 4 in
  let y = (let z = 10 * 10 in x + z) in
  x + y
on obtient l'arbre suivant à l'issue de l'analyse syntaxique : 
Ast.PSet ("h",
    Ast.PLetin ("x", Ast.PCst 4,
     Ast.PLetin ("y",
      Ast.PLetin ("z", Ast.PBinop (Ast.Mul, Ast.PCst 10, Ast.PCst 10),
       Ast.PBinop (Ast.Add, Ast.PVar "x", Ast.PVar "z")),
      Ast.PBinop (Ast.Add, Ast.PVar "x", Ast.PVar "y"))))
Les variables sont pour l'instant des chaînes de caractères. À l'issue de l'allocation, en revanche, on aura l'arbre suivant 
Ast.Set ("h",
  Ast.Letin (-8, Ast.Cst 4,
   Ast.Letin (-16,
    Ast.Letin (-16, Ast.Binop (Ast.Mul, Ast.Cst 10, Ast.Cst 10),
     Ast.Binop (Ast.Add, Ast.LVar (-8), Ast.LVar (-16))),
    Ast.Binop (Ast.Add, Ast.LVar (-8), Ast.LVar (-16)))),
  16)
où les variables x, y et z sont maintenant représentées par les entiers -8, -16 et -16 (on note ici que les variables y et z sont allouées au même emplacement) et où le troisième argument de Set, à savoir 16, représente le nombre total d'octets devant être alloués pour les variables de cette instruction.
solution

Question 2. Production de code

Compléter les fonctions compile_expr et compile_stmt pour produire le code X86-64. Un module OCaml X86-64 est fourni pour construire le code X86-64.

Tester avec make, ce qui doit afficher les entiers de 1 à 19, dans cet ordre.

solution
retour à la page du cours