Projet du cours de construction de compilateurs: Generator

Description de l'étape

Vous devez écrire un générateur capable d'écrire du code assembleur DLX correspondant à n'importe quel programme acceptés par l'analyseur. Contrairement aux étapes précédentes pour lesquelles nous fournissions une spécification formelle du travail à faire, nous considérerons qu'un consensus naturel existe sur la signification fonctionnelle des différents concepts de Drei. En cas de doute, Gilles est l'implantation de référence.

Le code généré doit être de l'assembleur compatible avec le processeur DLX. Il dispose de 32 registres numérotés 0 – 31.

R0 contient toujours la valeur 0 et n'est pas modifiable,
R1 est utilisé pour stocker le résultat au retour d'un appel de fonction,
R30 est utilisé pour stocker le pointeur de pile SP (stack pointer),
R31 est utilisé par les instructions d'appel (BSR et JSR) pour stocker l'adresse de retour.

Toutes les instructions sont codées au moyen de 32 bits. Certaines parties de ces 32 bits peuvent contenir des constantes, dont il est important de connaître la taille au moment de la production de code. Sur la feuille distribuée au cours et décrivant le jeu d'instruction, ainsi que dans la documentation de l'interface RISC, ces constantes sont identifiées par un nom. La table ci-dessous donne la taille de ces constantes.

Nom	Taille	Utilisation
a, b, c	5 bits	Numéros de registres
ic	16 bits	Entier signé
uc	16 bits	Entier non signé
oc	21 bits	Déplacement signé
lc	26 bits	Adresse non signée

Organisation du travail

Comme pour la partie précédente, nous vous recommandons de travailler par étapes: tout implanter en une seule fois sera difficile. Vous pourriez par exemple utiliser les étapes suivantes.

Les primitives d'entrée-sortie
A l'aide simplement des appels système correspondants: SYS_IO_RD_INT, SYS_IO_RD_CHR, SYS_IO_WR_INT et SYS_IO_WR_CHR (et aussi SYS_IO_FLUSH pour forcer l'affichage), on permet l'entrée et la sortie de valeurs (printInt, readChar, etc.)
Les expressions arithmétiques
Le compilateur peut traiter des programmes constitués d'une simple expression arithmétique, comme (1+2)*3.
Les classes (sans les méthodes) et les objets
Si C est une classe avec les champs f1 = e1, ..., fn = en (y compris les champs hérités), l'expression new C doit créer un objet tel que si l'on sélectionne le champ fi sur cet objet on obtient ei (la valeur d'initialisation du champ). Aussi, e1, ..., en doivent être évalués du premier au dernier, ou l'ordre est défini d'abord par l'ordre d'héritage (super-classe en premier), ensuite par l'ordre d'apparition dans la classe (cette contrainte à été changée le 12 décembre, vous pouvez implanter l'ancienne définition à condition de le mentionner).

Pour cela, il faut tenir compte de la position (offset) d'un champ dans sa classe. Le plus simple est de stocker cette information dans le symbole du champ. La classe FieldSymbol est ainsi étendue d'un champ offset: Int qui encode cette position.

Concrètement, un objet est représenté dans la partie "tas" de la mémoire par une zone contenant un pointeur vers sa table de méthode virtuelle et les valeurs des champs de l'objet, tout mis côte à côte. La valeur d'un objet est l'adresse du début de cette zone mémoire. La génération de code pour une expression new C ne fait donc rien d'autre qu'allouer une zone mémoire, stocker la valeur des expressions e1, ..., en dans cette zone et retourner l'adresse du début de la zone. Un espace doit aussi être prévu pour la table des méthodes virtuelles.

La génération de code pour le nœud de sélection de champ utilise l'information stockée dans le champ offset du symbole contenu dans Name.

Il faut noter que toutes les données que nous manipulons dans le langage (les entiers et les pointeurs vers les objets) peuvent être représentés en mémoire par un mot.

Pour allouer la mémoire, vous devez utiliser l'appel système SYS_GC_ALLOC. Son utilisation implique d'initialiser l'allocateur mémoire. L'initialisation se fait de la façon suivante.
```
// initialise stack pointer
code.emit(SYSCALL, SP, 0, SYS_GET_TOTAL_MEM_SIZE)
// initialise garbage collector:
// the heap starts at address init and its size is 2/3 * (total_mem_size - init) words
emitLoadConstant(r1, heapStart)
code.emit(SUB, r2, SP, r1)
code.emit(DIVIU, r2, r2, 3 * WORD_SIZE)
code.emit(LSHI, r2, r2, 1) // r2 now contains the size of the heap
emitLoadConstant(r3, SP << 27)
code.emit(ADD, r2, r2, r3)
code.emit(SYSCALL, r1, r2, SYS_GC_INIT)
```
Une fois l'initialisation terminée, vous sautez vers le début du programme utilisateur.
Les paramètres et les blocs
Pour gérer les paramètres, il faut gérer la pile. Chaque appel de fonction a le droit d'utiliser un bloc de mémoire, appelé bloc d'activation, alloué sur la pile. L'adresse du début de ce bloc ne change pas au cours d'un appel donné; il est désigné par FP (frame pointer). Normalement, la fin du bloc est aussi connue en comptant le nombre de paramètres de la fonction, et il est trivial de calculer la position d'un paramètre par rapport au FP.
Les boucles et la conditionelle
On ajoute la gestion des branchements if et du while si vous choisissez de faire ce bonus.
Les opérateurs logiques et de comparaisons
Rappelez-vous ici que dans un langage orienté-objet, la comparaison se fait sur l'identité de l'instance (l'adresse) et non la structure de l'objet.
Les méthodes
Cette dernière étape ajoute la gestion des méthodes au compilateur. Cela inclut le calcul de la table des méthodes virtuelles pour chaque classe, la génération de code pour les définition de méthodes et pour les appels de méthodes. Il vous faudra aussi retoucher la génération de code pour la création d'instances new de manière à stocker au début de chaque object un pointeur vers la table des méthodes virtuelles de sa classe.

Les arguments des méthodes doivent être évalués de gauche à droite avant d'être passés à la fonction.

Générateur de code

Dans le cas le plus simple, la seule classe sur laquelle vous aurez à travailler est celle du générateur lui-même. Pour cela, définissez une classe avec au moins l'interface suivante.

class Generator(analyzer: Analyzer) {
  val code: Code
  def gen(tree: Tree): Unit
}

code: Une instance de Code qui contient les instructions assembleurs du programme généré. A l'initialisation, ce programme est vide, après l'appel à gen, il contient le programme assembleur correspondant au programme Drei.
gen: Une méthode qui génère du code assembleur correspondant à l'arbre tree en paramètre. Elle sera toujours appelée avec un tree validé par l'analyseur: on peut donc assumer que les propriétés sur les arbres garanties par l'analyseur sont vraies pour ce paramètre.

Un canevas pour cette classe est à votre disposition.

Autres classes de support

Code.scala

Cet classe utilitaire définit des méthodes pour émettre des instructions DLX, les imprimer dans une fichier, gérer les étiquettes (labels) et la pile des fonctions.

RISC.java

Cet classe contient la définition de diverses constantes liées au processeur DLX, par exemple des constantes pour les instructions et pour les appels système (entrées/sorties, glaneur de cellules, ...).

GeneratorTest.scala

Cet objet permet de tester votre générateur, à condition que l'interface de celui-ci corresponde. A l'exécution

son premier paramètre est le fichier source du programme à analyser,
son second paramètre, optionnel, est le fichier assembleur DLX généré.

Exécuter le code assembleur

Le code que votre interpréteur finira par générer peut être exécuté à l'aide d'un interpréteur RISC/DLX (et d'un débogueur graphique) que nous vous fournissons. Vous les exécuterez de la sorte.

~iclamp/soft/bin/risc-emu
~iclamp/soft/bin/risc-gui

L'option -h vous permettra d'accéder à toutes les options de l'interpréteur.Vous pouvez aussi le télécharger sur votre propre ordinateur.

Ecole polytechnique fédérale de Lausanne

Laboratoire des méthodes de programmation