INF564 - TD 6 - Production de code RTL

Le but de ce TD est de réaliser la production de code intermédiaire RTL pour le langage mini-C.

Code fourni

Archive à télécharger : rtl-ocaml.tar.gz

Une fois cette archive décompressée (par exemple avec tar zxvf rtl-ocaml.tar.gz), vous obtenez un répertoire mini-c/ contenant plusieurs modules OCaml :

Pp Utilitaires d'impression
Ops Opérations x86-64 utilisées pendant la sélection d'instructions
Label Étiquettes
Register Registres
Rtltree Register Transfer Language (RTL)
Rtlinterp Interprète de code RTL (pour tester)

Ces modules sont complets. Cliquer sur le nom du module pour accéder à sa documentation. On prendra le temps de bien comprendre le code fourni.

Travail demandé

Dans un nouveau fichier rtl.ml, écrire une fonction program traduisant l'arbre de syntaxe abstraite issu du typage en code RTL, c'est-à-dire renvoyant une valeur du type Rtltree.file.

On pourra récupérer ce nouveau minic.ml qui ajoute au compilateur une option --interp-rtl pour exécuter le code RTL (avec la fonction Rtlinterp.program fournie). Par ailleurs, ce nouveau programme principal affiche le code RTL (avec la fonction Rtltree.print_file fournie) dès lors que l'option --debug est passée.

On suggère très fortement de procéder construction par construction, en testant systématiquement à chaque fois.

1. Programme minimal

On commence avec Le graphe de flot de contrôle en cours de construction pourra être stocké dans une référence globale :
  let graph = ref Label.M.empty
Il est utile d'introduire une fonction pour ajouter une nouvelle instruction dans le graphe, à une étiquette fraîche qui est renvoyée :
  let generate i =
    let l = Label.fresh () in
    graph := Label.M.add l i !graph;
    l

Pour les expressions, écrire une fonction de la forme

  let rec expr e destr destl = ...
e est l'expression à traduire, destr le registre de destination de la valeur de cette expression et destl l'étiquette où il faut transférer ensuite le contrôle.

Pour les instructions, écrire une fonction de la forme

  let rec stmt s destl retr exitl = ...
s est l'instruction à traduire et destl l'étiquette où il faut transférer ensuite le contrôle. Lorsque l'instruction est return, la valeur renvoyée doit être mise dans le registre retr et le contrôle doit être passé à l'étiquette exitl.

Écrire une fonction deffun qui traduit une fonction mini-C vers le type Rtltree.deffun des fonctions RTL. Il suffit de créer un pseudo-registre pour le résultat et une étiquette pour la sortie, avant d'appeler la fonction précédente sur le corps de la fonction mini-C.

Écrire enfin une fonction qui traduit un programme mini-C vers le type Rtltree.file, en traduisant chacune des fonctions.

Tester avec le programme :

int main() {
  return 42;
}
On doit obtenir quelque chose comme :
=== RTL ==================================================
#1 main()
  entry : L2
  exit  : L1
  locals:
  L2: mov $42 #1  --> L1

2. Arithmétiques

Ajouter à la fonction expr le traitement des opérations arithmétiques (à l'exception de && et ||).

Les nouvelles instructions RTL à utiliser sont : Emunop, Embinop.

Tester avec des programmes comme

int main() {
  return 40 - (-2);
}

3. Variables

Ajouter le traitement des variables locales (mais pas les paramètres de fonction pour l'instant). Chaque variable est associée à un pseudo-registre frais. (L'allocation de registres déterminera plus tard son emplacement physique.) On pourra introduire une table donnant pour chaque variable locale le pseudo-registre qui lui est associé.

Tester avec des programmes comme

int main() {
  int x, y;
  y = 40;
  x = 2;
  return y + x;
}

4. Instructions

Ajouter à la fonction stmt le traitement des instructions manquantes, c'est-à-dire l'instruction vide (;), l'évaluation d'une expression (e;), la conditionnelle (if) et la boucle (while).

Pour traduire les instructions if et while, il peut être utile d'introduire une fonction

  let rec condition e truel false = ...
qui traduit une expression e en RTL et transfert le contrôle à l'étiquette truel si sa valeur est non nulle et à l'étiquette falsel sinon.

Ajouter également le traitement des constructions && et ||, en respectant leur évaluation paresseuse.

Les nouvelles instructions RTL à utiliser sont : Emubranch, Embbranch, Egoto.

Tester avec des programmes comme

int main() {
  if (1 <= 2)
    return 3;
  else
    return 4;
}

5. Appel de fonction

Ajouter le traitement des paramètres formels et de l'appel de fonction. À chaque paramètre formel est associé un pseudo-registre frais. On y accède comme pour une variable locale (déjà fait plus haut). Pour un appel, les paramètres effectifs sont passés dans autant de pseudo-registres. Remarque : il n'est pas nécessaire de faire un traitement particulier pour les fonctions putchar et sbrk.

Les nouvelles instructions RTL à utiliser sont : Ecall.

Tester avec des programmes comme

int fact(int n) {
  if (n <= 1) return 1;
  return n * fact(n-1);
}
int main() {
  return fact(42);
}

6. Structures

Ajouter enfin le traitement des structures, c'est-à-dire l'accès à un champ (e->x) et l'affectation d'un champ (e1->x = e2). Remarque : Il n'y a rien à faire pour une déclaration de structure.

Les nouvelles instructions RTL à utiliser sont : Eload, Estore.

Tester avec des programmes comme

struct S { int a; int b; };
int main() {
  struct S *p;
  p = sbrk(sizeof(struct S));
  p->a = 40;
  p->b = 2;
  return p->a + p->b;
}

7. Tests

On réutilise les mêmes tests que pour le typage (tests-v1.tar.gz) mais avec cette fois l'option -i du script run, de la manière suivante :
> ./run -i  "mon/chemin/vers/mini-c --interp-rtl"
Test de mon/chemin/vers/mini-c --interp-rtl

Interprétation
Execution normale
-----------------
...........................................................
Execution conduisant à un échec
-------------------------------
...
Compilation:
Compilation : 62/62 : 100%
Comportement du code : 62/62 : 100%

retour à la page du cours