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-java.tar.gz

Une fois cette archive décompressée (par exemple avec tar zxvf rtl-java.tar.gz), vous obtenez un répertoire mini_c/ contenant plusieurs fichiers Java :

Ops.java Opérations x86-64 utilisées pendant la sélection d'instructions
Label.java Étiquettes
Register.java Registres (physiques et pseudo-registres)
RTL.java Langage RTL (Register Transfer Language)
RTLinterp.java Interprète de code RTL (pour tester)

Ces classes sont complètes et documentées ici. On prendra le temps de bien comprendre le code fourni.

Travail demandé

Dans une nouvelle classe ToRTL, écrire une méthode
  RTLfile translate(File f)
qui traduit l'arbre de syntaxe abstraite issu du typage en code RTL, c'est-à-dire en une valeur du type RTLfile. On pourra écrire cette classe comme un visiteur de la classe abstraite issue du typage, c'est-à-dire
  class ToRTL extends EmptyVisitor { ... }

On pourra récupérer ce nouveau Main.java qui ajoute au compilateur une option --interp-rtl pour exécuter le code RTL (avec la classe RTLinterp fournie). Par ailleurs, ce nouveau programme principal affiche le code RTL (avec la méthode print de la classe RTLfile 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 variable globale :
  RTLgraph graph; // graphe en cours de construction
La méthode add de la classe RTLgraph ajoute une nouvelle instruction dans le graphe, à une étiquette fraîche qui est renvoyée.

Pour traduire une expression, il faut se donner

Pour traduire une instruction, il faut se donner

Traduire chaque fonction mini-C vers le type RTLfun des fonctions RTL. Il suffit de créer un pseudo-registre pour le résultat et une étiquette pour la sortie, puis de traduire le corps de la fonction mini-C avec ces paramètres.

Traduire enfin un programme mini-C vers le type RTLfile, 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 le traitement des opérations arithmétiques (à l'exception de && et ||).

Les nouvelles instructions RTL à utiliser sont : Rmunop, Rmbinop.

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 y, x;
  y = 40;
  x = 2;
  return y + x;
}

4. Instructions

Ajouter 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 méthode qui, étant données une expression et deux étiquettes truel et falsel, traduit l'expression 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 : Rmubranch, Rmbbranch, Rgoto.

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 : Rcall.

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 : Rload, Rstore.

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