Compilateur Minijava vers MIPS
La documentation commune aux différentes étapes du projet est regroupée dans la page
Mémento du projet Minijava.
Le compilateur fourni est fonctionnel mais uniquement pour une syntaxe très minimaliste (Hello 42 == ./Exemples/Milestone/Test101.java == milestone 1). Dès que l'on va étendre la syntaxe, le comportement du compilateur est indéfini. Ajouter dans la classe main.Compiler, un appel à la méthode main.Debug.toBeContinued() entre la phase d'analyse syntaxique et les phases suivantes. Cette balise avancera ensuite avec le développement des différentes étapes de la compilation. Comme pour les différentes phases du compilateur, le travail est à réaliser de manière incrémentale en ajoutant au fur et à mesure les différentes règles de la grammaire (milestones 1,...,9) et en validant avec le fichier input.txt à compléter ou adapter.
L'ensemble du compilateur sera réalisé dans un premier temps en ignorant les tableaux d'entiers (milestone 9). L'étape finale du projet ajoutera les tableaux d'entiers dans l'ensemble des phases du compilateur.
Réaliser l'analyse lexicale et syntaxique de Minijava pour les milestones 2 à 7.
Cette étape suppose d'avoir une analyse lexicale et syntaxique opérationnelle pour le langage Minijava. Compléter l'étape précédente en utilisant éventuellement le corrigé.
= Test des Identificateurs : Test2 (klasse), a(field), b(field), Start(method), i(formal), j(formal), k(local), un(method), Test3 (klasse), zero(method),
Le visiteur syntax.PrettyPrint peut donner une idée de squelette, mais le travail demandé ici est beaucoup plus court (20-30 lignes).
Écrire un autre petit visiteur semantic.TestScope qui reconstruit uniquement la structure des accolades {} du fichier d'origine.
Exemple de résultat sur ./Exemples/Milestone/Test105.java :
= Test Scope : Test2{Start{}un{}}Test3{zero{}}
Fusionner les 2 visiteurs précédents dans un seul visiteur semantic.TestFusion. On imprime ainsi l'ensemble des identificateurs à l'intérieur de leur portée respective.
Exemple de résultat sur ./Exemples/Milestone/Test105.java :
= Test Identificateur avec Scope : Test2{a(field), b(field), Start{i(formal), j(formal), k(local), }un{}}Test3{zero{}}
= Table des Symboles (passe1) Scope Root class Object extends null class Test105 extends Object class Test3 extends Test2 class Test2 extends Object Scope Object boolean equals(Object this, Object o) Scope equals_args Object this Object o Scope equals Scope Test105 void main(String[] args) Scope main_args String[] args Scope main Scope Test2 int Start(Test2 this, int i, int j) int un(Test2 this) int a int b Scope Start_args Test2 this int i int j Scope Start int k Scope un_args Test2 this Scope un Scope Test3 int zero(Test3 this) Scope zero_args Test3 this Scope zero
Avant d'utiliser l'héritage des classes Java, il est urgent de valider
l'absence de boucles dans l'héritage.
Cette fonction sémantique est réalisée par la classe semantic.CheckInheritance (algorithmique très basique et peu optimisé !).
Dans la même classe, on va de plus reconstruire la racine de l'arbre des portées pour ajouter l'arbre d'héritage des classes (si c'est un arbre !) comme arbre d'héritage des visibilités des identificateurs. L'héritage Orienté Objet deviendra alors transparent pour la recherche dans la table des symboles. Parcourir rapidement le code et tester le fonctionnement en analysant l'impression de la table de symbole(passe 2)
Écrire la fonction sémantique Identifier allready defined.
Comparer le comportement du compilateur Minijava avec celui de javac dans le cas d'une variable locale de méthode qui redéfinit un argument de la méthode.
Écrire un nouveau visiteur qui vérifie que tous les identificateurs utilisés dans l'AST, sont bien liés à une déclaration dans la table de symbole.
Ignorer pour le moment les identificateurs de méthode, qui ne peuvent être traités que après le contrôle de type : rechercher la méthode pour obj.method() nécessite de connaître le type de obj. N.B. : si l'on prend en compte la liaison dynamique de Java, le test n'est plus après le contrôle de type mais éventuellement à l'exécution !
On peut aussi ignorer l'identificateur de classe de la classe parent dont le contrôle est déjà réalisé de fait dans semantic.CheckInheritance.
Intégrer dans le visiteur Undefined précédent la fonction sémantique qui signale l'ensemble des variables déclarées mais non utilisées. On notera que semanticTree.rootScope.getAllVariables() donne la collection de toutes les variables du programme. Il suffit donc de supprimer au fur et à mesure les variables utilisées pour avoir en fin de la visite les variables Unused.
cf. Mémento Minijava et code fourni...
Le schéma de liaison entre les identificateurs et leurs déclarations réalisé avec la table des symboles consiste à rechercher la déclaration en partant de la portée courante et en remontant l'arbre des portées (cf. lookup*() dans la classe Scope).
Ce schéma fonctionne pour les variables ou pour les méthodes de classe (static) mais ne fonctionne pas directement pour les méthodes d'instance. Pourquoi ?
Si l'on a x.get(); y.get(); dans une même portée, où chercher la déclaration de get() ?
En fait la question est incorrecte. Il y a potentiellement plusieurs déclarations différentes.
solution ?...
Écrire un visiteur qui calcule l'attribut Type de chaque expression dans l'AST Minijava. Le Type est un String avec des valeurs prédéfinies (main.EnumType) pour les types primitifs, ou un nom de classe pour les types Objets. La classe semantic.TypeChecking est fournie comme squelette pour le contrôle de type. Le Type est un attribut synthétisé qui est stocké dans la structure SemanticTree pour la suite de la compilation. L'Attribut Type est nécessaire pour le contrôle de type à suivre mais sera aussi indispensable pour l'allocation mémoire dans la phase de génération de code.
Spoiler : en réalité, on ignorera l'attribut en allouant un mot de quatre octets pour toutes les variables quelque soit le type !
Intégrer dans le Visiteur précédent, le contrôle de type, c'est-à-dire la vérification de l'ensemble des contraintes de typage du langage Minijava. Dans Minijava, il n'y a pas de transtypages pour les types primitifs. Pour les types Object, on a le transtypage naturel lié à l'héritage des classes. Un objet possède le type de tous ces ancêtre. Ce mécanisme est implanté dans le squelette fourni et l'on a aucun besoin de mémoriser ces cas de transtypage pour les phases suivantes de la compilation. On notera l'absence de surcharge des opérateurs, c'est-à-dire la possibilité qu'un opérateur change de sémantique en fonction du type des opérandes. Pour les méthodes, on ignore la liaison dynamique et les possibilités de surcharge, mais on permet la redéfinition (overriding). Tester au fur et au mesure sur des exemples valides ou invalides. En cas de doute, on peut aussi comparer avec le comportement du compilateur javac sur les mêmes exemples.
Terminer et valider les questions "Undefined" et "Unused" de l'étape 2 en intégrant la recherche des méthodes. On ne traite que la liaison statique et l'on ignorera le polymorphisme des méthodes.
Pour simplifier les phases suivantes de la compilation, on réduit en peu le spectre du compilateur en supposant que :
Écrire un traducteur de l'AST vers la Représentation Intermédiaire "code à 3 adresses" (cf. Mémento Minijava section 8). La classe intermediate.Intermediate donne un canevas de départ avec les helpers utiles. Il s'agit d'écrire un visiteur de l'AST avec :
Exemple de résultat :
Une optimisation dans la génération de la forme intermédiaire consiste à évaluer directement les opérations sur des constantes plutôt que de traduire de manière générique pour faire cette évaluation à l'exécution. Modifier le schéma de traduction pour le nœud ExprOpBin sous la forme
Idem pour ExprOpUn.
Pour optimiser l'exécution, mais aussi parce que c'est la sémantique dans le langage java, modifier le schéma de traduction pour l'opérateur booléen "ET" (&&) de manière à ne pas évaluer les 2 opérandes quand cela n'est pas nécessaire. De manière plus générale, la traduction sur les expressions booléennes se fera en utilisant plutôt une forme d'instruction "IF" qu'une forme d'opérateur logique. N.B. : En java, les expressions (n != null) && (n.istrue) ou (n == null) || (n.istrue) sont correctes (pas de NullPointerException) car le deuxième opérande n'est évalué que en fonction de la véracité du premier opérande.
Le schéma de traduction de && devient :
La génération de l'assembleur est réalisée par la classe codegen.CodeGen qui utilisera les classes des packages codegen et codegen.access :
Analyser en détails le contenu de la classe codegen.Allocator. Expliquer en particulier :
Écrire par étapes (milestones) la classe ToMips pour réaliser la compilation du langage Minijava. Enfin le bout du tunnel !!!
Valider le fonctionnement du compilateur sur les exemples du dossier ./Exemples/* et avec un fichier input.txt à construire à cet effet. Pour le test sur différents fichiers, il peut être utile de travailler en ligne de commande :
L'objectif est de compléter la génération de code de l'étape précédente. Afin d'éviter de casser le compilateur qui marche (normalement !), on modifiera les fonctionnalités en créant une nouvelle classe ToMipsPlus qui hérite de la classe ToMips et redéfinira (@Override) uniquement les méthodes visit() que l'on veut améliorer ou étendre.
On adaptera dans CodeGen, l'appel à ToMips ou ToMipsPlus et si besoin on peut modifier certains private de la classe ToMips en protected. Un squelette de classe :
Supprimer la contrainte sur le nombre d'arguments des méthodes. La classe codegen.Allocator implémente déjà la convention d'appel, et définit l'accès aux arguments 4 à N (0($fp),4($fp)..., c'est à dire dans la pile avant la frame de l'appelé). Il faut uniquement modifier les séquences d'appel et de sortie au niveau de l'appelant.
Le schéma simple dans la classe ToMips qui consiste à toujours charger dans les registres $v0 ou $v1 pour faire ensuite des instructions MIPS ne tient pas compte du fait que les variables chargées sont éventuellement déjà dans des registres.
L'objectif de cette question est donc d'éviter d'utiliser les registres $v0 ou $v1 quand les variables de l'instruction IR (arg1,arg2,result) sont déjà dans des registres utilisables directement par les instruction MIPS. On définit le helper suivant :
Le code Reg r0=tmpReg(var,Reg.V0); regLoad(r0,var); produira :
CSC4251-52 (CSC 4536), TELECOM SudParis, P. Hennequin,Last modified: Janvier 2024
Prologue : Prise en main
- Récupérer l'archive Minijava.tar.gz.
- Exécuter la commande Compil-link-lib à la racine du projet (création du lien ./lib -> $LIBCOMP/lib).
- Si besoin revoir le prologue de Exercices CUP et JFlex pour la mise en œuvre de l'IDE.
- Intégrer l'arborescence comme un projet Java dans votre IDE favori.
- Intégrer build.xml dans la "vue Ant" de l'IDE.
- Vérifier que le projet est en mode UTF8 pour votre IDE (pas de problèmes d'accents).
- Lire en détails, la section "1. Structuration des sources" de la documentation Mémento Minijava et regarder les classes fournies.
- Tester la génération (vue ant/generate) et l'exécution du compilateur (classe principale : main.Compiler)
N.B. : L'utilisation de Make ou Ant en ligne de commande reste fonctionnelle mais peut poser des problèmes si l'IDE est actif en même temps. Pour l'exécution en ligne de commande, on peut utiliser la commande Compil-run-minijava qui prend en argument une liste de fichier à compiler à la place du fichier par défaut input.txt. - Analyser rapidement les traces de l'exécution et le code produit input.mips.
- Les questions et la curiosité sont bienvenues.
Analyse lexicale et syntaxique
Préliminaire
Le compilateur fourni est fonctionnel mais uniquement pour une syntaxe très minimaliste (Hello 42 == ./Exemples/Milestone/Test101.java == milestone 1). Dès que l'on va étendre la syntaxe, le comportement du compilateur est indéfini. Ajouter dans la classe main.Compiler, un appel à la méthode main.Debug.toBeContinued() entre la phase d'analyse syntaxique et les phases suivantes. Cette balise avancera ensuite avec le développement des différentes étapes de la compilation. Comme pour les différentes phases du compilateur, le travail est à réaliser de manière incrémentale en ajoutant au fur et à mesure les différentes règles de la grammaire (milestones 1,...,9) et en validant avec le fichier input.txt à compléter ou adapter.
L'ensemble du compilateur sera réalisé dans un premier temps en ignorant les tableaux d'entiers (milestone 9). L'étape finale du projet ajoutera les tableaux d'entiers dans l'ensemble des phases du compilateur.
Le langage Minijava est un sous-ensemble du langage Java. Pour les tests,
il peut donc être utile dans les différentes étapes du projet de comparer
le comportement de votre compilateur Minijava avec celui de javac.
Analyse lexicale et syntaxique
Réaliser l'analyse lexicale et syntaxique de Minijava pour les milestones 2 à 7.
- Lire la documentation du projet Mémento Minijava, sections 2, 3, 4 et 10.
- Écrire les spécifications JFlex et CUP pour réaliser l'analyse du langage Minijava :
- L'identificateur this peut être ignoré en temps que mot-clé dans l'analyse lexicale. Il est traité comme les autres noms de variable dans l'analyse syntaxique. Le rôle particulier de this sera pris en compte au niveau de l'analyse sémantique qui forgera la déclaration implicite de cette variable.
- La gestion des localisations dans le fichier source (méthode AddPosition) est totalement optionnelle.
- Construire l'Arbre de Syntaxe Abstraite en suivant les définitions du package syntax.ast.*.
- Tester et valider l'analyse syntaxique en vérifiant l'impression des AST, et le résultat du visiteur syntax.PrettyPrint. Adapter si besoin la classe main.Debug pour modifier les traces imprimées par le compilateur.
- Utiliser les fichiers de test dans ./Exemples, en particulier : Test[1-3]0[1-7], TestPeano, TestAckermann.
Écrire et tester par étape en suivant les différents milestones :
- milestone 2 : grammaire d'opérateur et priorités, cf. "Calculatrice",
- milestone 3 : Listes simples, cf. "Grammaires de Listes",
- milestone 4 : Listes avec séparateurs, cf. "Grammaires de Listes",
- milestone 5 : Doubles listes, cf. Helpers dans la spécification CUP fournie,
- milestone 6 : Autres expressions,
- milestone 7 : Autres instructions.
Une paire de spécification :
Analyse Sémantique : Table de symboles
Préliminaire
Cette étape suppose d'avoir une analyse lexicale et syntaxique opérationnelle pour le langage Minijava. Compléter l'étape précédente en utilisant éventuellement le corrigé.
N'oublier pas de lire le Mémento Minijava qui contient un ensemble d'informations utiles ou indispensables qui ne sont pas reprises dans cette page : Sections 4 à 7 pour cette étape.
Petite Visite
- Écrire un visiteur semantic/TestIdent qui hérite de syntax.ast.AstVisitorDefault et qui imprime l'ensemble des identificateurs des variables déclarées. Inclure l'appel au visiteur dans semantic/Semantic pour tester.
- Adapter le visiteur pour préciser pour chaque variable, si il s'agit d'un attribut de classe, d'une variable locale ou d'un paramètre formel de méthode.
- (bonus) Compléter le visiteur pour afficher les noms de classes et de méthodes déclarées.
= Test des Identificateurs : Test2 (klasse), a(field), b(field), Start(method), i(formal), j(formal), k(local), un(method), Test3 (klasse), zero(method),
Le visiteur syntax.PrettyPrint peut donner une idée de squelette, mais le travail demandé ici est beaucoup plus court (20-30 lignes).
package semantic;
import syntax.ast.*;
public class TestIdent extends AstVisitorDefault {
public TestIdent(SemanticTree semTree) {
semTree.axiom.accept(this);
}
...
Contre-Visite
Écrire un autre petit visiteur semantic.TestScope qui reconstruit uniquement la structure des accolades {} du fichier d'origine.
Exemple de résultat sur ./Exemples/Milestone/Test105.java :
= Test Scope : Test2{Start{}un{}}Test3{zero{}}
Fusion (bonus)
Fusionner les 2 visiteurs précédents dans un seul visiteur semantic.TestFusion. On imprime ainsi l'ensemble des identificateurs à l'intérieur de leur portée respective.
Exemple de résultat sur ./Exemples/Milestone/Test105.java :
= Test Identificateur avec Scope : Test2{a(field), b(field), Start{i(formal), j(formal), k(local), }un{}}Test3{zero{}}
Bravo, vous avez construit l'arbre des portées (scope) des identificateurs et
vous savez aussi trouver l'ensemble des déclarations. En somme, une table de symboles
presque complète !
Table des Symboles
Outre le Mémento Minijava, Il convient de lire attentivement le contenu des classes du package semantic.symtab
La construction de la Table des symboles pour le compilateur Minijava est
réalisée par la classe semantic.BuildSymTab.
Le squelette fourni est un visiteur qui ne fait rien,
mais contient les helpers utiles pour réaliser le travail.
Analyser les helpers avant de commencer le travail, souvent ils répondent
à la question "où est ce que cela se trouve ?"
On notera que :
- La table des symboles (rootScope) est contenue et initialisée dans la classe semantic.semanticTree.
- La classe Object et sa méthode equals sont déjà intégrées dans la table des symboles avec le code fourni.
- La classe conventionnelle Main de Minijava est aussi intégrée dans le code à titre d'exemple. Les symboles de cette classe (main(), args, className) n'ont en réalité pas d'utilisation dans le langage Minijava.
- Construire l'arbre des portées qui structure la table des symboles (cf. Mémento Minijava, sources, et helpers).
- Calculer l'attribut sémantique hérité currentScope qui associe à chaque nœud de l'AST, la portée où se trouve le nœud. Cet attribut réalise le lien vers les identificateurs visibles depuis ce nœud.
- Stocker l'attribut sémantique currentScope (décoration de l'AST) dans la structure semantic.semanticTree (attribut scopeAttr) pour pouvoir le réutiliser dans la suite de l'analyse sémantique et dans les phases suivantes du compilateur.
- Stocker dans l'arbre des portées, l'ensemble des informations de déclaration d'identificateurs (classe, méthode, variable/attribut). cf. semantic.symtab/Info*.
- Gérer la "variable" this dont la déclaration est implicite dans l'AST :
- Pour chaque méthode, ajouter dans la table des symboles une déclaration explicite de this comme premier paramètre de la méthode.
- Le type de la variable this est le nom de la classe courante !
- Il faut dont calculer l'attribut sémantique hérité currentKlass qui associe à chaque nœud de l'AST, la classe englobante du nœud. Il n'est pas utile de stoker cet attribut dans l'arbre sémantique.
- Réaliser enfin, la fonction sémantique allready defined qui détecte les erreurs de redéfinition d'identificateur au sein d'une même portée. Ce n'est fonctionnellement pas l'endroit pour faire cela, mais c'est très économique de le faire ici (et c'est déjà presque écrit dans le code !).
- Valider le travail en vérifiant l'impression de la table des symboles (passe 1).
= Table des Symboles (passe1) Scope Root class Object extends null class Test105 extends Object class Test3 extends Test2 class Test2 extends Object Scope Object boolean equals(Object this, Object o) Scope equals_args Object this Object o Scope equals Scope Test105 void main(String[] args) Scope main_args String[] args Scope main Scope Test2 int Start(Test2 this, int i, int j) int un(Test2 this) int a int b Scope Start_args Test2 this int i int j Scope Start int k Scope un_args Test2 this Scope un Scope Test3 int zero(Test3 this) Scope zero_args Test3 this Scope zero
Table des symboles et Héritage Orienté Objet
La solution est déjà fournie dans le code !
Dans la même classe, on va de plus reconstruire la racine de l'arbre des portées pour ajouter l'arbre d'héritage des classes (si c'est un arbre !) comme arbre d'héritage des visibilités des identificateurs. L'héritage Orienté Objet deviendra alors transparent pour la recherche dans la table des symboles. Parcourir rapidement le code et tester le fonctionnement en analysant l'impression de la table de symbole(passe 2)
La gestion des erreurs est ici optimiste. c'est à dire
que l'erreur a priori grave est signalée, mais l'on continuera la phase
d'analyse sémantique simplement en ignorant l'héritage Java pour les classes qui n'ont pas Object comme ancêtre.
Allready defined
Écrire la fonction sémantique Identifier allready defined.
Déjà fait en même temps que la construction de la table des
symboles !!!
javac considère comme une erreur de redéfinition, l'écrasement d'un paramètre d'appel par une variable locale. Notre compilateur l'accepte.
Undefined
Écrire un nouveau visiteur qui vérifie que tous les identificateurs utilisés dans l'AST, sont bien liés à une déclaration dans la table de symbole.
Ignorer pour le moment les identificateurs de méthode, qui ne peuvent être traités que après le contrôle de type : rechercher la méthode pour obj.method() nécessite de connaître le type de obj. N.B. : si l'on prend en compte la liaison dynamique de Java, le test n'est plus après le contrôle de type mais éventuellement à l'exécution !
On peut aussi ignorer l'identificateur de classe de la classe parent dont le contrôle est déjà réalisé de fait dans semantic.CheckInheritance.
A venir après le contrôle de type !
Unused
Intégrer dans le visiteur Undefined précédent la fonction sémantique qui signale l'ensemble des variables déclarées mais non utilisées. On notera que semanticTree.rootScope.getAllVariables() donne la collection de toutes les variables du programme. Il suffit donc de supprimer au fur et à mesure les variables utilisées pour avoir en fin de la visite les variables Unused.
A venir après le contrôle de type !
Gestion d'erreurs
cf. Mémento Minijava et code fourni...
Analyse Sémantique : Contrôle de type
En cas de manque d'inspirations, les fichiers Exemples/SemanticError/* sont adaptés pour
les tests de la phase sémantique.
Question de Cours Orienté Objet
Le schéma de liaison entre les identificateurs et leurs déclarations réalisé avec la table des symboles consiste à rechercher la déclaration en partant de la portée courante et en remontant l'arbre des portées (cf. lookup*() dans la classe Scope).
Ce schéma fonctionne pour les variables ou pour les méthodes de classe (static) mais ne fonctionne pas directement pour les méthodes d'instance. Pourquoi ?
Si l'on a x.get(); y.get(); dans une même portée, où chercher la déclaration de get() ?
En fait la question est incorrecte. Il y a potentiellement plusieurs déclarations différentes.
solution ?...
Pour une méthode d'instance, la recherche ne dépend pas de la portée courante mais dépend de la classe concrète du receveur (this). Pour x.get(), la déclaration de get() est à chercher à partir de la portée de la classe concrète de x.
Dans le cas d'une liaison statique (cas pour Minijava), on considère le type déclaré de x qui est connu lors de l'analyse sémantique (contrôle de type). Dans le cas d'une liaison dynamique (Java), on considère le type réel de x (celui de l'instanciation avec new). La liaison dynamique est donc potentiellement réalisée à l'exécution ou dans une phase d'analyse sémantique dynamique (flot d'exécution et coutures d'arbres).
Type top
Écrire un visiteur qui calcule l'attribut Type de chaque expression dans l'AST Minijava. Le Type est un String avec des valeurs prédéfinies (main.EnumType) pour les types primitifs, ou un nom de classe pour les types Objets. La classe semantic.TypeChecking est fournie comme squelette pour le contrôle de type. Le Type est un attribut synthétisé qui est stocké dans la structure SemanticTree pour la suite de la compilation. L'Attribut Type est nécessaire pour le contrôle de type à suivre mais sera aussi indispensable pour l'allocation mémoire dans la phase de génération de code.
Spoiler : en réalité, on ignorera l'attribut en allouant un mot de quatre octets pour toutes les variables quelque soit le type !
La réalisation de cette question peut se faire en parallèle avec la question suivante. Le test et la validation sont en particulier communs aux 2 questions.
cf. question suivante.
Top type
Intégrer dans le Visiteur précédent, le contrôle de type, c'est-à-dire la vérification de l'ensemble des contraintes de typage du langage Minijava. Dans Minijava, il n'y a pas de transtypages pour les types primitifs. Pour les types Object, on a le transtypage naturel lié à l'héritage des classes. Un objet possède le type de tous ces ancêtre. Ce mécanisme est implanté dans le squelette fourni et l'on a aucun besoin de mémoriser ces cas de transtypage pour les phases suivantes de la compilation. On notera l'absence de surcharge des opérateurs, c'est-à-dire la possibilité qu'un opérateur change de sémantique en fonction du type des opérandes. Pour les méthodes, on ignore la liaison dynamique et les possibilités de surcharge, mais on permet la redéfinition (overriding). Tester au fur et au mesure sur des exemples valides ou invalides. En cas de doute, on peut aussi comparer avec le comportement du compilateur javac sur les mêmes exemples.
Bonus
Terminer et valider les questions "Undefined" et "Unused" de l'étape 2 en intégrant la recherche des méthodes. On ne traite que la liaison statique et l'on ignorera le polymorphisme des méthodes.
cf. rendu final.
Génération de la Forme Intermédiaire
Hypothèses pour la génération de code
Pour simplifier les phases suivantes de la compilation, on réduit en peu le spectre du compilateur en supposant que :
- Les méthodes deviennent maintenant globales, c'est à dire que les noms de méthodes sont uniques dans le fichier source. Dans la représentation intermédiaire comme dans le code final MIPS, une méthode correspond à un label avec le nom de la méthode. En cas de duplication, la détection se fera au niveau de l'assemblage avec MARS et un message duplicated label.
- Toutes les "Variables" de Minijava ou de la forme intermédiaire auront une implantation en mémoire identique avec un mot de 32 bits. On simplifie ainsi le calcul des tailles, des alignements...
Traduction AST vers IR
Écrire un traducteur de l'AST vers la Représentation Intermédiaire "code à 3 adresses" (cf. Mémento Minijava section 8). La classe intermediate.Intermediate donne un canevas de départ avec les helpers utiles. Il s'agit d'écrire un visiteur de l'AST avec :
- Calcul (et stockage) d'un Attribut synthétisé Var, qui pour chaque nœud "expression" contient la variable (IRvariable) utilisée par la forme intermédiaire pour stocker le résultat de l'expression. Cette variable est généralement une variable temporaire générée par le traducteur mais peut aussi être une constante ou une variable du programme d'origine.
- Calcul d'un attribut hérité currentMethod qui contient le nom de la méthode courante. Cette information est utilisée uniquement pour associer une portée locale aux variables temporaires IRtempo et permettre une meilleure allocation mémoire à venir.
- Traduction des nœuds de l'AST sous forme de séquences d'instructions IRquadruple. Les exemples de base pour les schémas de traduction sont illustrés dans les diapositives du cours.
- La traduction se fait à la volée au sens où le programme final est la concaténation des traductions de chaque nœud de l'AST en suivant l'ordre de la visite.
Exemple de résultat :
(Bonus) Propagation de constantes
Une optimisation dans la génération de la forme intermédiaire consiste à évaluer directement les opérations sur des constantes plutôt que de traduire de manière générique pour faire cette évaluation à l'exécution. Modifier le schéma de traduction pour le nœud ExprOpBin sous la forme
/* exp1 op exp2 */
traduction(exp1)
traduction(exp2)
si (getVar(exp1) instanceof IRconst)
et (getVar(exp2) instanceof IRconst){
setVar Node, newConst("getValue"(exp1) op "getValue"(exp2))
}
sinon {
setVar node, newTemp()
QAssign op, getVar(exp1), getVar(exp2), getVar(node)
}
cf. rendu final.
(Super Bonus) Optimisation d'expressions booléennes
Pour optimiser l'exécution, mais aussi parce que c'est la sémantique dans le langage java, modifier le schéma de traduction pour l'opérateur booléen "ET" (&&) de manière à ne pas évaluer les 2 opérandes quand cela n'est pas nécessaire. De manière plus générale, la traduction sur les expressions booléennes se fera en utilisant plutôt une forme d'instruction "IF" qu'une forme d'opérateur logique. N.B. : En java, les expressions (n != null) && (n.istrue) ou (n == null) || (n.istrue) sont correctes (pas de NullPointerException) car le deuxième opérande n'est évalué que en fonction de la véracité du premier opérande.
Traductions des opérateurs logiques en opérateur ternaire :
exp1 && exp2 == exp1 ? exp2 : exp1
exp1 || exp2 == exp1 ? exp1 : exp2
! exp1 == exp1 ? false : true
/* exp1 && exp2 */
traduction(exp1)
setVar node newTemp()
QCopy getVar(exp1), getVar(node)
QJumpCond L0, getVar(exp1)
traduction(exp2)
QCopy getVar(exp2), getVar(node)
QLabel L0
cf. rendu final.
Génération de l'assembleur MIPS
Prise en main
La génération de l'assembleur est réalisée par la classe codegen.CodeGen qui utilisera les classes des packages codegen et codegen.access :
- La classe Reg fournit une énumération des registres MIPS pour les autres classes du package.
- La classe MipsWriter est une classe utilitaire pour l'impression dans un fichier des instructions MIPS. On peut l'adapter ou la compléter à la convenance de chacun.
- La classe LinkRuntime réalise l'édition de lien qui se limite à la concaténation du Runtime MIPS.
- La classe ToMips réalise la traduction de la forme intermédiaire vers MIPS. Pour le moment, elle ne gère que le programme hello 42 (Test101).
- La classe Allocator et le package codegen.access construit, à partir de la table des symboles (AST + IR), l'allocation mémoire des variables, des classes, des cadres d'appel... (cf. question suivante).
Allocation mémoire
Analyser en détails le contenu de la classe codegen.Allocator. Expliquer en particulier :
- Les différents types d'accès aux variables de la forme intermédiaire et la mise en œuvre à travers les classes codegen.access.Access*.
- La gestion des variables instances de classe : instanciation et accès aux champs.
- La mise en œuvre de la convention d'appel et le calcul des tailles des cadres d'appel (frame).
- L'allocation des variables locales, temporaires, ou globales.
Quelques remarques importantes :
- Minijava ne contient pas l'accès explicite aux champs d'un objet autrement que sur this. Dans la grammaire, le seul usage du token DOT est l'appel d'une méthode. Les champs d'un objet ne sont accédés que sur la variable this qui est toujours dans le registre $a0.
- La taille d'un objet de classe est définie en prenant la somme des champs de la classe et de ces ancêtres. De même pour le calcul des offsets permettant d'accéder aux champs.
- Les champs d'objet sont accédés sous la forme offset($a0).
- Seul la méthode main() contient des variables globales (temporaires). Elles sont référencées par offset($gp).
- Les variables locales (temporaires ou du programme) sont enregistrées dans le cadre d'appel.
- Les tailles des cadres d'appel (framesize) sont calculées à partir d'une partie fixe (sauvegarde des registres) et incrémentées pour chaque déclaration de variable locale.
- Les variables locales (=presque toutes les variables) sont accédées par offset($fp).
- Seul les paramètres des méthodes utilisent des registres.
Traduction : sélection d'instruction et convention d'appel
Écrire par étapes (milestones) la classe ToMips pour réaliser la compilation du langage Minijava. Enfin le bout du tunnel !!!
- Analyser la structure de la classe ToMips : "Visiteur IR", Helpers, gestion des appels "spéciaux" (_system_*),...
- L'accès aux variables IR (utilisation de codegen.access) est réalisé avec les méthodes regLoad(), regStore().
- Les registres $v0 et $v1 sont librement accessibles pour les calculs temporaires dans le traitement de chaque instruction IR.
- La gestion des paramètres est réalisée avec une liste java.util.ArrayList<IRvariable> params, qui est remplie par les instructions QParam, et utilisée puis réinitialisée dans les instructions QCall et QCallStatic.
- ...
- Étapes :
- Traduction de l'instruction QAssign(+,*).
- Charger les 2 arguments de QAssign dans $v0 et $v1.
- Effectuer l'opération avec résultat dans $v0.
- Enregistrer $v0 dans le résultat de QAssign.
- Traduction de l'instruction QNew.
- Sauvegarder le registre $a0
- Charger dans $a0 la taille de l'objet à instancier (cf. Allocator.classSize())
- Appeler la fonction _new_object du Runtime MIPS
- Enregistrer $v0 (résultat de _new_object) dans le résultat de QNew.
- Restaurer $a0.
- N.B. : On applique ici une convention d'appel simplifiée.
- Construction la convention d'appel :
QLabelMethod et QReturn pour l'appelé,
QCall et QParam pour l'appelant.
-
QLabelMethod :
- Écrire le label de fonction.
- Positionner le cadre d'appel (framepointer) $fp = $sp.
- Allouer le cadre d'appel = avancer la pile de la taille du cadre d'appel Allocator.frameSize().
- Sauvegarder les registres adéquats ($ra,$s0,$s1,...).
-
QReturn :
- Restaurer les registres adéquats.
- Charger dans $v0 la valeur de retour.
- Libérer le cadre d'appel. On notera que $fp contient la valeur de $sp à restaurer !
-
QCall :
- Sauvegarder les registres adéquats ($fp,$a0,$a1,$a2,$a3,$t0,$t1,...).
- Charger les (maximum 4) paramètres dans les registres $a0,$a1,$a2,$a3. Attention : utiliser ici la méthode regLoadSaved pour éviter l'écrasement des paramètres d'appel (exemple de pb. : f(a,b) { f(b,a); } ).
- Effectuer l'appel : jal.
- Enregistrer $v0 comme résultat du QCall.
- Restaurer les registres adéquats.
-
QLabelMethod :
- et le reste : QAssign*, QCopy, QLabel, QJump*,...
Aide-toy, le Ciel t’aidera. — (Jean de la Fontaine, Le Chartier embourbé, dans Fables, livre sixième, 1692-94)
- Traduction de l'instruction QAssign(+,*).
Et un compilateur qui marche ! :
Validation
Valider le fonctionnement du compilateur sur les exemples du dossier ./Exemples/* et avec un fichier input.txt à construire à cet effet. Pour le test sur différents fichiers, il peut être utile de travailler en ligne de commande :
- la cible jar de make ou de ant permet de créer une archive Compiler.jar exécutable du compilateur.
- L'exécution du compilateur se fait alors avec : java -jar Compiler.jar fichier1 fichier2....
- On teste ensuite chaque fichier assembleur produit avec mars fichier.mips.
Amélioration de la génération (Optionnel)
Préambule
L'objectif est de compléter la génération de code de l'étape précédente. Afin d'éviter de casser le compilateur qui marche (normalement !), on modifiera les fonctionnalités en créant une nouvelle classe ToMipsPlus qui hérite de la classe ToMips et redéfinira (@Override) uniquement les méthodes visit() que l'on veut améliorer ou étendre.
On adaptera dans CodeGen, l'appel à ToMips ou ToMipsPlus et si besoin on peut modifier certains private de la classe ToMips en protected. Un squelette de classe :
package codegen;
import intermediate.IR;
import intermediate.ir.*;
public class ToMipsPlus extends ToMips {
public ToMipsPlus(IR ir, Allocator allocator, MipsWriter mw) {
super(ir, allocator, mw);
}
/// VISITs...
Manque d'arguments
Supprimer la contrainte sur le nombre d'arguments des méthodes. La classe codegen.Allocator implémente déjà la convention d'appel, et définit l'accès aux arguments 4 à N (0($fp),4($fp)..., c'est à dire dans la pile avant la frame de l'appelé). Il faut uniquement modifier les séquences d'appel et de sortie au niveau de l'appelant.
- Modifier le traitement de l'instruction QCall pour accepter un nombre quelconque d'arguments dans le langage Minijava.
- Attention de bien empiler (modif de $sp) les arguments supplémentaires avant de créer la frame ; et de dépiler à la fin.
- Vérifier que le compilateur marche encore pour une fonction récursive comme factorielle ou Ackermann.
- Vérifier aussi le fonctionnement sur ./Exemples/Running/Test205.java.
cf. question suivante.
Moins de copie
Le schéma simple dans la classe ToMips qui consiste à toujours charger dans les registres $v0 ou $v1 pour faire ensuite des instructions MIPS ne tient pas compte du fait que les variables chargées sont éventuellement déjà dans des registres.
L'objectif de cette question est donc d'éviter d'utiliser les registres $v0 ou $v1 quand les variables de l'instruction IR (arg1,arg2,result) sont déjà dans des registres utilisables directement par les instruction MIPS. On définit le helper suivant :
private Reg tmpReg(final IRvariable v, final Reg defReg) {
final Reg reg = allocator.access(v).getRegister();
return (reg == null) ? defReg : reg;
}
- exactement le comportement de l'étape 5, si var n'est pas dans un registre (regLoad(Reg.V0,var)),
- une optimisation (aucune instruction) si var est déjà dans un registre.
Et un compilateur plus mieux qui marche encore :
... cf. rendu final...
... cf. rendu final...
On passe aux tableaux
Les étapes précédentes fournissent un compilateur complet mais qui ne traite pas l'ensemble du langage
Minijava. Il s'agit donc dans cette dernière étape, d'intégrer dans l'ensemble des phases du compilateur la gestion des
tableaux d'entiers du langage Minijava. L'énoncé qui suit donne quelques indications mais l'énoncé réel
de cette étape est dans toutes les étapes qui précédent et dans le Mémento Minijava.
Quelques suggestions avant de démarrer :
Un token et cinq règles de grammaire à ajouter dans les spécifications JFlex et CUP.
Quatre nouveaux nœuds à utiliser dans l'AST : syntax.ast.*Array*.
Ne pas oublier de fixer une priorité pour les tokens []. (Bonus : tester aussi le comportement sans cette priorité)
La table de symbole est inchangée à part l'existence d'un type main.EnumType.INT_ARRAY.
Le contrôle de type doit traiter les 4 nouveaux nœuds de l'AST.
Les 4 nouveaux nœuds de l'AST correspondent à 4 nouvelles instructions de la Représentation Intermédiaire.
Exemple de résultat :
Traduire les 4 nouvelles instructions IR dans ToMips*. L'instanciation des tableaux utilisera la fonction _new_object du Runtime MIPS, avec le schéma suivant à implémenter :
Une variable tableau proprement dite est gérée de façon transparente par Allocator pour qui toutes les variables sont des valeurs sur 4 octets, aussi bien pour les types primitifs (entier, booléen), que pour les types références (instance de classe ou tableau).
Exemple de résultat :
Valider le bon fonctionnement du compilateur. Utiliser les Exemples */Test*9.java et le très bel exemple TestBigNum qui calcul 42 comme somme de 3 cubes ! Enfin la vraie révélation du secret de l'univers !!! (ou du metavers !)
Ajouter le contrôle de bornes à l'exécution sur les tableaux. Ajouter aussi le contrôle à l'exécution sur la taille positive dans l'instanciation des tableaux
Ajouter au langage Minijava, les tableaux de booléens.
Préambule
Quelques suggestions avant de démarrer :
- Vérifier que le compilateur de départ est raisonnablement correct (cf. dernière question de l'étape 5).
- Faire un commit/backup/mail_a_1_ami pour ne pas casser le "compilateur qui marche".
- Prévoir éventuellement des tests simples de non-régression (un petit script qui compile N fichiers de tests, et imprime le résultat de l'exécution avec mars).
Analyse lexicale et syntaxique
Un token et cinq règles de grammaire à ajouter dans les spécifications JFlex et CUP.
Quatre nouveaux nœuds à utiliser dans l'AST : syntax.ast.*Array*.
Ne pas oublier de fixer une priorité pour les tokens []. (Bonus : tester aussi le comportement sans cette priorité)
Analyse Sémantique
La table de symbole est inchangée à part l'existence d'un type main.EnumType.INT_ARRAY.
Le contrôle de type doit traiter les 4 nouveaux nœuds de l'AST.
Représentation Intermédiaire
Les 4 nouveaux nœuds de l'AST correspondent à 4 nouvelles instructions de la Représentation Intermédiaire.
Exemple de résultat :
Génération de code MIPS
Traduire les 4 nouvelles instructions IR dans ToMips*. L'instanciation des tableaux utilisera la fonction _new_object du Runtime MIPS, avec le schéma suivant à implémenter :
_new_object avec IN $a0 = 4 * LENGTH + 4, OUT $v0
LENGTH == taille du tableau, à enregistrer à l'offset 0 du tableau
[-- 4 --] [-------------- 4 * LENGTH ---------------------]
+---------+--------+--...---+--------+--...---+-------------+
| LENGTH | [0] | ... | [i] | ... | [LENGTH-1] |
+---------+--------+--...---+--------+--...---+-------------+
^ ^
$v0 $v0 + 4 + 4 * i
Une variable tableau proprement dite est gérée de façon transparente par Allocator pour qui toutes les variables sont des valeurs sur 4 octets, aussi bien pour les types primitifs (entier, booléen), que pour les types références (instance de classe ou tableau).
Exemple de résultat :
Validation
Valider le bon fonctionnement du compilateur. Utiliser les Exemples */Test*9.java et le très bel exemple TestBigNum qui calcul 42 comme somme de 3 cubes ! Enfin la vraie révélation du secret de l'univers !!! (ou du metavers !)
Quand on dépasse les bornes, il n'y a plus de limites ! (Bonus)
Ajouter le contrôle de bornes à l'exécution sur les tableaux. Ajouter aussi le contrôle à l'exécution sur la taille positive dans l'instanciation des tableaux
- Utiliser l'instruction MIPS : sltu $t0, $t1, $t2 (?!?).
- Gérer une sortie en erreur en utilisant la fonction _system_exit(errorCode) du Runtime MIPS (errorCode=666 ou 42 ou...).
Bonus rapide : Tableaux de Booléens
Ajouter au langage Minijava, les tableaux de booléens.
- Ajouter un nom de type dans main.EnumType et une règle dans la spécification CUP.
- Adapter éventuellement le nœud de l'AST ExpArrayNew pour le contrôle de type.
- Compléter le contrôle de type sur les tableaux (entier ou booléen).
- Et cela marche, ou pas !!!
Rendu final
Le travail à rendre est une archive .tar.gz (ou autre) du compilateur complet. En plus des fonctionnalités dont le corrigé est fourni, le compilateur intègre :
- La gestion des tableaux d'entiers.
- Un fichier de test input.txt qui couvre les fonctionnalités du compilateur et qui est valide pour le compilateur.
- Un fichier Readme avec le nom des auteurs, et les commentaires utiles pour le correcteur : on a fait comme il fallait mais ça ne marche pas, on n'a pas fait comme il fallait mais ça marche mieux !, on a mis plein de bonus (ou boni),...
- (Bonus) Étape 2-3 : La fonction sémantique Undefined/Unused pour les variables, les classes et les méthodes.
- (Bonus) Étape 4 : Propagation de constantes.
- (Bonus) Étape 4 : Optimisation d'expression booléenne.
- (Bonus) Étape 6 : Manque d'arguments.
- (Bonus) Étape 6 : Moins de copies.
- (Bonus) Étape 7 : Contrôle de borne de tableau.
- (Bonus) Étape 7 : Tableaux de booléens.
- (Bonus) Tableau d'objets, null, == (opérateur surchargé), division euclidienne (/,%), System.exit(i),....
- Faire le ménage (make clean, ou ant clean) avant de construire l'archive.
- Exclure le dossier lib de l'archive si ce n'est pas un lien symbolique.
- 4 points : Sources d'origine et codes des étapes 1 à 5 (corrigés fournis)
- 3 points : Readme et input.txt
- 9 Points : Tableaux d'entiers
- 1 à 2 points par bonus
- Total : 16 sans bonus, 20 avec 3 boni, 25 avec les 7 bonus,...
Attendez, c'est en train de compiler !
![](../web/TPs/minijava/compiling.png)
CSC4251-52 (CSC 4536), TELECOM SudParis, P. Hennequin,Last modified: Janvier 2024