Projet de compilation: generator

Les groupes qui, lors du test de l'étape generator du projet, peuvent démontrer la capacité de leur compilateur à traiter la coercition et le test dynamique des types ou type cast/check recevront un bonus de 10 points sur leur projet.

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. Notre compilateur Drei vers Scala peut aider à clarifier les éléments douteux.

Le code généré doit être de l'assembleur compatible avec le processeur DLX dont les instructions sont décrites dans ce document. 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, ..., fn (y compris les champs hérités), l'expression new C(e1, ...., en) doit créer un objet tel que si l'on sélectionne le champ fi sur cet objet on obtient la valeur de l'expression ei. Aussi, e1, ..., en doivent être évalués de gauche à droite.

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(e1, ..., en) 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 blocs et les variables locales
Cette étape ajoute la gestion des blocs, des variables locales et des affectations. Pour cela, 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). La fin du bloc est variable; elle est repérée par le registre SP (stack pointer). La différence entre SP et FP est appelée la taille du bloc d'activation (frame size).

Lors de la génération de code, vous devez calculer pour chaque instruction quelle est la taille du bloc d'activation. Pour cela, la classe Code fournit les méthodes incFrameSize, decFrameSize et getFrameSize.

La déclaration d'une variable la place au sommet de la pile. Afin de générer le code pour modifier et lire cette variable, il faut toujours savoir où elle se trouve sur la pile. Pour cela, on ajoute un champ offset au symbole de variable. Ce champ contient la position de la variable sur la pile par rapport à FP. Il doit être initialisé pendant la génération du code de la déclaration de variable.

La génération de code des blocs doit bien sûr générer le code des énoncés et de l'expression finale qu'ils contiennent. En plus de cela, ils doivent libérer la mémoire allouée sur la pile par les éventuelles déclarations de variables qu'ils contiennent.
Les boucles et la conditionelle
On ajoute la gestion des branchements while et if.
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 (java) 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