|
Tous les ajouts du 24 janvier sont en rouge.
Introduction
Le but de cette partie est de produire le code machine
correspondant au programme analysé, en fonction des règles sémantiques
du langage. Toutes les étapes précédentes avaient pour seul but de
s'assurer que le programme était correct par rapport aux règles du
langage, et de transformer le programme textuel en une forme
facilement manipulable : l'arbre abstrait. Une fois ce travail
préparatoire effectué, le compilateur peut commencer son « vrai »
travail, la production de code cible.
La production de code nous occupera jusqu'à la fin du semestre.
Nous séparerons cette partie en plusieurs étapes, que nous vous
conseillons d'effectuer dans l'ordre donné, mais vous êtes bien
entendu libres de vous organiser comme bon vous semble.
Étapes à réaliser
L'idée générale de la production de code est relativement
simple : il s'agit de parcourir l'arbre abstrait représentant le
programme et de produire, pour chaque nœud, le code qui lui
correspond. La production de code s'organise donc autour d'un
visiteur.
L'implémentation des différents cas du visiteur peut être faite
par étapes. Celles-ci sont décrites ci-dessous. La description de
chaque étape commence par l'énumération des productions de la
grammaire abstraite qui doivent être implémentées au cours de
l'étape.
Étape 1
T = UnitType
| IntType
| ListType T
| FunType { T } T.
Les déclartions de types ne produisent pas de code et les méthodes
caseUnitType, ..., caseFunType ne devraient
jamais être appelées. Ces méthodes peuvent donc simplement rester
vide.
Étape 2
E = Operation O E [ E ]
| UnitLit
| IntLit int
| ...
O = Eq | Add
| Ne | Sub
| Lt | Mul
| Le | Div
| Gt | Mod
| Ge
| ...
Le but de la deuxième étape est de produire du code pour les
expressions arithmétiques. À la fin de cette étape, le compilateur
devrait être capable de compiler des programmes constitués d'une
simple expression arithmétique, comme 1+2*3.
Au cours de cette étape, on produit également le code pour la
valeur () (le nœud UnitLit). Cette valeur
est simplement représentée par l'entier 0.
Étape 3
E = If E E E
| ...
Le but de la trosième étape est d'ajouter la gestion des
expressions conditionnelles au compilateur. Pour ce faire, commencez
par ajouter les items conditionnels, comme cela a été vu au cours,
puis utilisez-les pour compiler les expressions conditionnelles.
Étape 4
E = Operation O E [ E ]
| NilLit
| ...
O = Cons
| Head
| Tail
| IsEmpty
| ...
Le but de la quatrième étape est d'ajouter la gestion des listes au
compilateur.
La représentation que nous allons utiliser pour les listes est
basée sur des paires, comme en Lisp. Une liste n'est donc rien d'autre
qu'une paire dont le premier élément contient la tête de la liste, et
le second sa queue. La queue peut être la liste vide [],
que l'on représente par la constante 0.
En mémoire, on représente les paires par une zone contenant les
deux éléments de la paire côte à côte. On manipule ces zones au moyen
de pointeurs qui pointent vers leur début. L'opérateur ::
ne fait donc rien d'autre que d'allouer une telle zone, puis il y
place la tête et la queue de la liste, avant de retourner un pointeur
vers la zone. L'opérateur head extrait pour sa part la
première valeur d'une telle zone, tail extrait la
seconde, et isEmpty vérifie si le pointeur qu'elle reçoit
est nul. Bien entendu, head et tail doivent
signaler une erreur s'ils sont appliqués à la liste vide, au moyen de
l'appel système SYS_EXIT.
Il faut noter que toutes les données que nous utilisons dans le
langage (les booléens, les entiers, les pointeurs de fonction et les
[pointeurs vers les] listes) peuvent être représentés en mémoire par
un mot. Cela implique que toutes les paires ont la même
taille en mémoire, et que les opérateurs ::,
head, tail et isEmpty
fonctionnent donc de manière uniforme quel que soit le type du contenu
de la liste sur laquelle ils agissent.
La figure ci-dessous montre comment la liste
1::2::3::4::[] peut être représentée en mémoire. Les
flèches représentent des pointeurs.
![Représentation mémoire de [1,2,3,4]](list.gif)
Pour allouer la mémoire, vous devez utiliser l'appel système
SYS_GC_ALLOC. Son utilisation implique d'initialiser
l'allocateur mémoire. Cela est fait au début de la méthode
caseProgram de la classe Generator.
Étape 5
S = VarDecl ident T E
| ...
E = Assign ident E
| Ident ident
| Block { S } E
| ...
Le but de la cinquième étape est d'ajouter la gestion des blocs,
des variables locales et des affectations.
Pour cela, il vous faut gèrer la pile. Comme vous l'avez vu au cours,
chaque appel de fonction a le droit d'utiliser un bloc de mémoire
alloué sur la pile. L'addresse 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 de la pile
(stack size).
Lors de la génération de code, vous devez calculer pour chaque
instruction quelle est la taille de la pile. Pour cela, la classe Code fournit les méthodes
incStackSize, decStackSize et
getStackSize qui permettent d'augmenter, de diminuer et
de lire la taille de la pile. Chaque fois que vous émettez une
instruction qui modifie le registre SP, donc la taille de
la pile, vous devez aussi appeler incStackSize ou
decStackSize.
Le nœud VarDecl déclare une nouvelle variable
qui est placée au sommet de la pile (par une opération
PUSH). Afin que les nœuds Assign et
Ident puissent accéder à cette variable, il faut qu'ils
sachent où elle se trouve sur la pile. Pour cela, on utilise le champ
offset de la classe Symbol (c'est un nouveau champ que
vous devez ajouter vous-même). Ce champ contient la position de la
variable sur la pile par rapport à FP. Il doit être
initialisé par le nœud VarDecl.
Pour générer le code du nœud Assign, on utilise
le symbole qui a été stocké dans le nœud lors de l'analyse des
types. Le champ offset de ce nœud désigne la
position sur la pile à laquelle la valeur doit être
stockée. Toutefois, cette position est définie par rapport à
FP alors que pour l'instruction STW à
emmettre on a besoin de la position par rapport à
SP. Pour calculer cette position par rapport à
SP, il faut utiliser la taille de la pile retournée par
la méthode getStackSize et le fait qu'à tout moment
SP=FP-code.getStackSize().
La génération de code des nœuds Ident retourne
simplement un StackItem dont l'offset correspond à celui
du symbole stocké dans le nœud.
La génération de code des nœuds Block doit bien
sûr gnérer le code des instructions et de l'expression qu'ils
contienent. En plus de cela, ils doivent libérer la mémoire allouée
par d'éventuels nœuds VarDecl qu'ils
contiennent.
Étape 6
S = While E E
| Exec E
| ...
Le but de la sixième étape est d'ajouter la gestion des boucles
while et des expressions utilisées en tant
qu'instruction. La génération de code pour les
nœuds Exec revient simplement à générer le code de son
expression. Le seul point auquel il faut faire attention est qu'il
faut libérer tous les registres qui ont été alloués lors de cette
génération. Ces registres, s'il y en a, sont tous reférencés par
l'item retourné par l'appel à generate et peuvent donc
être libérés en appelant la méthode freeRegisters sur cet
item.
Pour générer le code des nœuds While, il faut générer
le code de son expression et de son corps selon le schéma
suivant :
start: ... // code de la condition
B?? R? exit // sortie de la boulce
... // code du corps
BEQ R0 start // retour au début de la boucle
exit : ... // suite du programme
Lors de la génération du code du corps de la boucle, il faut, comme
pour les nœuds Exec, prendre garde à bien libérer
tous les registres alloués.
Étape 7
P = Program { D } E.
D = FunDecl ident { F } T E.
F = Formal ident T.
E = FunCall E { E }
| ...
Le but de la septième et dernière étape est d'ajouter la gestion
des fonctions au compilateur.
La gestion des fonctions inclut les fonctions prédéfinies
printInt, printChar, readInt et
readChar. Ces fonctions peuvent être traitées de manière
tout à fait standard si on prend soin de produire leur code avant de
produire le reste du code.
N'oubliez pas que, en misc, on peut manipuler les fonctions comme
n'importe quelle autre donnée, via les pointeurs de fonction.
Tests
Notez que les fichiers d'exemple de code misc disponibles sur la
page du cours ne contiennent ni boucles, ni affectations. N'oubliez
donc pas de tester ces constructions. De plus, pour tester votre
générateur, ne vous contentez pas de faire de petits programmes
testant chacun une seule construction du langage misc ou un seul type
de nœud. En effet, de nombreux problèmes n'apparaisent que
lorsqu'on utilise en même temps différents concepts. Faites donc
également quelques tests avec des programmes qui utilisent plusieurs
concepts en même temps. Ecrivez, par exemple, une fonction qui prend
en argument une liste de fonctions, parcourt cette liste au moyen
d'une boucle while et appelle chacune des fonctions
contenues dans la liste.
Fichiers fournis
Pour cette étape, nous vous fournissons les fichiers
suivants :
-
Code.java contient les
méthodes pour produire les instructions assembleur.
Item.java contient la
classe Item et ses sous-classes, dont la plupart
sont à compléter au fur et à mesure. Generator.java
contient le visiteur de génération de code. Il s'agit du
principal fichier à compléter. GeneratorTest.java
contient le programme de test. Main.java contient le
programme principal (la seule différence avec GeneratorTest.java est que
ce programme génère un fichier avec l'extension
.risc lorsque aucun fichier objet n'est spécifié).
RISC.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, ...). Les
commentaires importants qui figurent dans ce fichier sont aussi
disponibles sous forme HTML.
Projet en Scala
Les fichiers pour le projet en Scala :
Code.scala,
Item.scala,
Generator.scala,
GeneratorTest.scala,
RISC.java (attention il est
différent de celui pour le projet en Java).
Exécution des programmes
Pour tester les programmes produits par votre compilateur, nous
mettons à votre disposition un interpréteur et un débogueur graphique
simple. Ces outils prennent un certain nombre d'options, dont vous
pouvez obtenir la liste en les lançant avec l'option
-h.
L'interpréteur se lance en tapant
~iclamp/soft/bin/risc-emu, tandis que le débogueur se
lance en tapant ~iclamp/soft/bin/risc-gui.
Architecture du processeur utilisé
L'architecture utilisée a brièvement été présentée au cours. Les
éléments importants sont rappelés ici.
Le processeur comporte 32 registres, numérotés de 0 à 31. Quelques
registres ont un usage particulier :
R0 contient toujours la valeur 0 et n'est pas
modifiable, R31 est utilisé par les instructions d'appel
(BSR et JSR) pour stocker l'adresse de
retour, R30 est utilisé pour stocker le pointeur de pile
SP (stack pointer), R29 est utilisé pour stocker le résultat au retour
d'un appel de fonction.
À noter que le pointeur de pile doit être initialisé au début
du programme. Cela est fait au début de la méthode
caseProgram de la classe Generator.
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 |
|
