archive-fr.com » FR » N » NICOLASPOUILLARD.FR

Total: 307

Choose link from "Titles, links and description words view":

Or switch to "Titles and links view".
  • Analyse syntaxique
    document head head body body tail tail on utilisera si possible la librairie standard de menhir qui définit les règles paramétriques les plus courantes Elles sont détaillées dans le manuel de menhir figure 3 voici leur équivalent sous forme d expressions régulières Règle de menhir option X preceded opening X delimited opening X closing list X nonempty list X separated list sep X separated nonempty list sep X Expression régulière X opening X opening X closing X X X sep X X sep X on peut déclarer qu un non terminal est inline ce qui a le même effet qu expanser toutes les productions de ce non terminal dans toutes les productions qui l incluent C est recommandé pour les opérateurs arithmétiques en particulier de façon à avoir une grammaire plus lisible en factorisant les opérateurs tout en gardant les règles de priorité des opérateurs définies avec left right ou nonassoc Compilation et exécution La compilation s effectue encore une fois à l aide du Makefile make menhir ocamlc ocamlc opt infer v base parser tokens mly parser mly File tokens mly line 7 characters 30 33 Warning the token AND is unused ocamlopt opt o compilo integer cmx misc cmx Comme la semaine dernière vous pouvez tester votre parseur en lui faisant parser du Pseudo Pascal puis l imprimer sur l entrée standard compilo dpp test zero p Vous pouvez vérifier que le compilateur complet fait lui le travail attendu cd wget URL ci dessus tar xvzf petit tar gz cd petit make petit compilo dpp test zero p program var x integer begin x 0 end Conflits En cas de conflit vous devez aller regarder le fichier parser conflicts qui exprime les conflits en terme de grammaire Le fichier parser automaton contient l automate sous jacent avec les conflits exprimés en terme d état comme c est le cas en général avec les générateurs d analyseurs syntaxiques du style de yacc On vous suggère notamment d utiliser autant que possible les règles paramétriques définies dans la librairie standard de menhir d utiliser de préférences les priorités des terminaux pour résoudre les conflits shift reduce Non terminaux et productions Les productions concernant les expressions et les instructions sont à compléter Les grammaires des types des conditions des blocs des procédures des fonctions et des programmes vous sont donnés On vous conseil d avancer progressivement et de tester régulièrement votre parseur Laissez vous guider par les tests dans le répertoire test en commençant par trivial 2 3 p Le cas de readln Le traitement de readln est un peut spécial en Pseudo Pascal en effet comme en pascal on écrit readln x où x est une variable ou readln a i où a et i sont des expressions Car contrairement à Pascal Pseudo Pascal ne peut passer les paramètres par références À vous de trouver une astuce pour traiter les deux cas d utilisation cités précédemment Actions sémantiques Les actions sémantiques construisent l arbre de syntaxe abstraite du programme reconnu

    Original URL path: http://nicolaspouillard.fr/td-compil/TD3/index.html (2015-10-11)
    Open archived version from archive


  • Sélection d'instructions
    renvoie un couple formé de un environnement global de type genv qui associe à chaque nom de variable globale un offset un entier qui représente la taille totale de mémoire à réserver pour les variables globales Vous pouvez utiliser la fonction StringMap fold appliquée aux variables globales p PP globals du programme p Voir la solution Ensuite il faut traduire les lectures et écritures de variables globales en fonction de cette nouvelle représentation Il s agit donc de traiter les cas suivants pour la lecture le motif PP EGetVar v dans translate expression pour l écriture le motif PP ISetVar v e dans translate instruction On peut vérifier sur un exemple simple qui utilise une variable globale que ça marche compilo iupp test echo p 98 98 Voir la solution Accès à la mémoire dynamique Il faut traduire les lectures écritures de tableaux en accès élémentaires à la mémoire utilisant les opérations load et store On vous demande d implémenter les fonctions suivantes en utilisant la fonction Upp2upp mkbinop let w2b e UPP expression UPP expression let element address base UPP expression index UPP expression UPP expression let mkload addr UPP expression UPP expression let mkstore addr UPP expression value UPP expression UPP instruction w2b prend en argument une expression donnant un nombre de mots et renvoie une expression donnant le nombre d octets correspondant element address prend en argument deux expressions donnant l adresse de base d un tableau et un indice dans ce tableau et renvoie l adresse de l élément correspondant les fonctions mkload et mkstore traduisent les accès en lecture et en écriture à la mémoire dynamique Dans le cas d une adresse sous forme de UOpAddi vous pouvez profiter du mode d adressage des opérations load et store qui attendent en deuxième argument un décalage constant par rapport à l adresse donnée en premier argument Voir la solution Utilisez les fonctions précédemment implémentées pour traduire les lectures écritures de tableaux le motif PP EArrayGet earray eindex de translate expression le motif PP IArraySet earray eindex evalue de translate instruction Voir la solution Il ne reste plus qu à traduire l allocation de tableau en un appel à la fonction primitive Alloc en traduisant également la taille du tableau en octets Cela revient à traiter le motif PP EArrayAlloc e de translate expression Voir la solution Comme vous avez maintenant un traducteur complet même si pas optimal de PP vers UPP vous pouvez vérifier à tout moment la correction de vos modifications avec make upp qui doit rendre OK pour tous les tests Opérations arithmétiques On s intéresse maintenant à la façon dont les opérations binaires sont traduites dans upp2upp ml en particulier les opérations les plus courantes addition soustraction et multiplication qui doivent être les plus efficaces possibles La traduction courante manque assez d imagination il va falloir l améliorer let mkadd e1 e2 EBinOp OpAdd e1 e2 let mksub e1 e2 EBinOp OpSub e1 e2 let rec mkmul e1 e2 EBinOp OpMul e1 e2

    Original URL path: http://nicolaspouillard.fr/td-compil/TD4/index.html (2015-10-11)
    Open archived version from archive

  • Expressions et registres
    dans la fonction translate instruction Relisez le code pour comprendre le fonctionnement à rebours de ces fonctions de transformation on part du label de l instruction suivante et on renvoie le label de l instruction nouvellement créée Détail important remarquez l utilisation de la fonction allocate pour créer un nouveau pseudo registre Pour vous échauffer traitez le cas d une constante dans translate expression Cela permet d interpréter correctement le code RTL d un programme trivial qui appelle writeln compilo irtl test trivial p 10 Voir la solution Un langage inexpressif sans expressions 0 On va compléter progressivement la fonction translate expression Il faudra utiliser les sous fonctions suivantes let lookup var name string Register t let allocate Register t let generate instr RTL instruction Label t lookup associe à un nom de variable locale le pseudo registre représentant cette variable allocate renvoie un nouveau pseudo registre generate associe à une instruction un nouveau label Variables globales et appels de fonctions Le cas le plus simple est celui de la lecture d une variable globale pour lequel presque rien ne change Idem pour un appel de fonction avec l utilisation de translate call Voir la solution Variables locales Le cas de la lecture d une variable locale est à peine plus compliqué Il n y a pas d opérateur de copie d un registre dans un autre il faut trouver une traduction équivalente en utilisant les opérations MIPS Note Essayez d utiliser l opérateur UOpAddi avec des arguments bien choisis Vous complèterez aussi le cas de l écriture d une variable locale dans translate instruction Voir la solution Opérations unaires binaires Les opérations unaires UPP EUnOp et binaires UPP EBinOp produisent des valeurs intermédiaires qui doivent être sauvées dans des pseudo registres Attention à l ordre des instructions générées La lecture dans un tableau UPP Load se traite de manière similaire Voir la solution Un langage inconditionnel sans conditions 0 En première approche On cherche maintenant à compléter le code de translate condition On remplace les conditions par des instructions de branchement conditionnel On se contente pour l instant de tester la non nullité de la condition fonction mkunbranch On finit par les opérateurs logiques UPP CNot UPP CAnd et UPP COr en n oubliant pas le caractère paresseux des deux derniers Pour pouvoir tester vos traductions vous aurez aussi besoin de traiter le cas du if dans translate instruction Note Une seule expression Pseudo Pascal peut avoir des effets de bord laquelle Est ce vrai dans d autres langages que vous connaissez C Java OCaml Voir la solution En y réfléchissant mieux Considérez le test test gcdfunc p qui contient de nombreuses conditions et imprimez votre traduction compilo drtl test gcdfunc p Que pensez vous de la traduction des conditions Pourrait on l améliorer en tenant compte des tests autorisés par MIPS dans les branchements consultez les types MIPSOps uncon et MIPSOps bincon pour le détail des tests en RTL En effet MIPS autorise certains tests binaires comme condition

    Original URL path: http://nicolaspouillard.fr/td-compil/TD5/index.html (2015-10-11)
    Open archived version from archive

  • Traduction des appels
    nécessaires pour satisfaire la signature du module rtl2ertlI mli Cela devrait permettre de compiler le compilateur sans erreurs Note Pour l instant le corps d une fonction peut se contenter de lancer une exception Voir la solution Fonctions auxiliaires Vous aurez besoin dans la suite d implémenter tout ou partie des fonctions suivantes au renommage près Vous pouvez choisir de les implémenter d abord ou de passer tout de suite à la section suivante Pseudo registres et registres matériels Le language ERTL fournit deux instructions pour passer d un pseudo registre à un registre matériel et inversement IGetHwReg et ISetHwReg Vous pouvez avoir besoin d implémenter les fonctions suivantes let sethwreg desthwr sourcer MIPS register Register t l Label t Label t let sethwregs moves MIPS register Register t list l Label t Label t let osethwreg desthwr osourcer MIPS register Register t option l Label t Label t let gethwreg destr sourcehwr Register t MIPS register l Label t Label t let gethwregs moves Register t MIPS register list l Label t Label t let ogethwreg odestr sourcehwr Register t option MIPS register l Label t Label t sethwreg crée une instruction de copie du contenu d un pseudo registre sourcer vers un registre matériel desthwr avec l le label de l instruction suivante et renvoie le label correspondant à cette instruction sethwregs fait la même chose que sethwreg pour une liste de paires de registres osethwreg ne fait rien si osourcer vaut None et applique sethwreg sinon gethwreg est la fonction symétrique de sethwreg gethwregs fait la même chose que gethwreg pour une liste de paires de registres ogethwreg ne fait rien si odestr vaut None et applique gethwreg sinon Voir la solution Pseudo registres et emplacements de pile Le language ERTL fournit deux instructions pour passer d un pseudo registre à un emplacement de pile et inversement IGetStack et ISetStack Les emplacements de pile sont distingués suivant qu il s agit pour la fonction d emplacements de pile entrants ou sont stockés certains de ses paramètres ERTL SlotIncoming ou d emplacements de pile sortants ou sont stockés certains paramètres des fonctions qu elle même appelle ERTL SlotOutgoing Les emplacements sont représentés par un décalage entier depuis le début de la zone correspondante ce qui amène naturellement à écrire les fonctions suivantes let offsets rs Register t list Register t int32 list let setstackslots sourcers Register t list l Label t Label t let getstackslots destrs Register t list l Label t Label t offsets associe à chaque registre passé en paramètre un décalage en byte correspondant à l emplacement qui lui sera alloué le premier registre de la liste étant stocké à l emplacement de décalage 0 setstackslots crée pour chaque pseudo registre passé en paramètre une instruction de copie du contenu du pseudo registre dans un emplacement de pile sortant et renvoie le label représentant la séquence de ces instructions avec l le label de l instruction suivante getstackslots crée pour chaque pseudo registre passé en

    Original URL path: http://nicolaspouillard.fr/td-compil/TD6/index.html (2015-10-11)
    Open archived version from archive

  • Analyse de durée de vie
    propagation arrière le paramètre input correspond aux registres vivants après l instruction et instruction semantics doit retourner les registres vivants avant l instruction Voir la solution Vous pouvez tester votre programme en affichant les registres vivants à chaque point du programme ERTL avec la commande compilo dertl dlive programme Ou pour réduire le nombre de registres physiques compilo dertl dlive few programme Optimisation du code mort Regardez en particulier ce qui se passe pour le pseudo registre contenant la valeur de la variable x de la fonction dead dans l exemple test dead p Il fait bien partie des registres vivants alors que comme le nom de l exemple l indique il devrait être mort puisque la valeur de x n est pas utilisée Que faire pour ne pas considérer ces registres comme vivants Une optimisation immédiate consiste à ne pas effectuer une écriture dans un pseudo registre si celui ci n est pas vivant après l instruction et si l élimination de l instruction ne modifie pas l exécution du programme Complétez la fonction eliminable pour qu elle renvoie Some l avec l le label de l instruction suivante quand on peut éliminer l instruction pour la raison évoquée ci dessus et None sinon Note Elle pourrait renvoyer un booléen pour l application qui nous intéresse on choisit ce type pour une utilisation ultérieure Utilisez la pour améliorer la détection des variables vivantes dans instruction semantics Voir la solution Relancez le calcul des registres vivants sur test dead p le pseudo registre correspondant à x a disparu Calcul des interférences Un graphe d interférence a pour sommets les registres pseudo ou physiques de la fonction et relie par ses arêtes les registres pouvant être vivants en même temps à un point du programme Vous allez le construire en utilisant la spécification donnée dans interference mli Il s agit de compléter le code de build ml On utilise ici liveafter soit l ensemble des registres vivants après chaque instruction c est à dire au moment d écrire un registre Le graphe d interférence graph n a initialement aucune arête Une première version Complétez le graphe d interférence en y ajoutant une arête pour tout couple de registres dont un est écrit par une instruction et l autre est vivant à ce point du programme Vous pouvez utiliser la fonction mki let mki g graph defregs Register Set t MIPS RegisterSet t liveregs Register Set t MIPS RegisterSet t graph qui ajoute au graphe g les arêtes entre les paires de registres prises dans defregs et liveregs en prenant soin d éviter de faire interférer un registre avec lui même ou deux registres physiques ensemble Voir la solution Vous pouvez visualiser le graphe d interférence produit en utilisant les commandes compilo dgraph nom de fonction programme circo Tps fichier eps kghostview fichier eps Le cas des move Regardez ce qui se passe dans un cas simple avec l exemple test trivial p Est ce que toutes les interférences affichées sont indispensables

    Original URL path: http://nicolaspouillard.fr/td-compil/TD7/index.html (2015-10-11)
    Open archived version from archive

  • Allocation de registres
    fonctions suivantes où la fonction simplification correspond à colorier dans l algorithme et la fonction selection correspond à allouer let forbidden colors graph Interference graph coloring coloring v Register t ColorSet t let simplification graph Interference graph coloring let selection graph Interference graph v Vertex t coloring Voir la solution En 16 millions de couleurs Vous allez compléter le code de spill ml Lors de l allocation d emplacements de pile on peut considérer que le nombre d emplacements possibles est infini Les variables avec de nombreuses interférences ne posent pas de problème ici Cela nous amène à optimiser l allocation d emplacements de pile pour tenir compte des préférences entre variables On applique donc un coloriage avec fusion sur un ensemble de couleurs infini fusionner graph s il existe une arête de préférence u v du graphe alors fusionner graph u et v ont fusionné sinon colorier graph colorier graph choisir une variable v avec le degré minimum colorier graph v déterminer les couleurs impossibles pour v choisir une couleur c pour v Vous aurez besoin des fonctions ipp remove lowest pppick et coalesce du module Interference Attention à la fonction coalesce qui rend un graphe où ne reste qu un seul des 2 noeuds qui lui sont passés en argument le deuxième Cela impose de colorier également le premier après coup On vous demande d implémenter les fonctions suivantes où la fonction simplify correspond à colorier dans l algorithme et la fonction coalesce correspond à fusionner let forbidden slots graph Interference graph coloring coloring v Register t Int32Set t let simplify graph Interference graph coloring let coalesce graph Interference graph coloring Voir la solution Vous avez implémenté complètement l allocation de registres Vous pouvez désormais tester votre programme avec make ltl Du coloriage à l art pictural De nombreuses optimisations existent pour l allocation de registres on va en implémenter quelques unes On ne s intéresse ici qu à l allocation de registres physiques du module Coloring La fusion conservative On voudrait pouvoir allouer les variables reliées par une arête de préférence au même registre physique Comme on n a pas ici un nombre de couleurs infini il faut procéder plus finement que lors de l allocation d emplacements de pile On applique donc un coloriage avec fusion conservative sur un ensemble de couleurs fini colorier graph s il existe une variable v de degré inférieur à k alors allouer graph v sinon fusionner graph allouer graph v colorier graph v déterminer les couleurs possibles pour v si aucune couleur possible alors allouer v sur la pile sinon choisir une couleur c pour v fusionner graph s il existe une arête de préférence u v du graphe qui passe le test de George alors colorier graph u et v ont fusionné sinon empiler graph empiler graph choisir une variable v de degré maximum allouer graph v Vous aurez besoin des fonctions pppick coalesce coalesceh et highest du module Interference Les fonctions qui implémentent le test de George sont

    Original URL path: http://nicolaspouillard.fr/td-compil/TD8/index.html (2015-10-11)
    Open archived version from archive

  • Génération de code assembleur
    traversal let visit l Label t unit visit fresh l is called when l has not been visited before let visit fresh l Label t unit Voir la solution Vous pouvez tester votre code avec la commande make lin et visualiser le code produit avec compilo ilin dlin programme Le code généré contient de nombreux labels instructions LIN ILabel inutiles tous ceux qui ne sont pas la destination d une instruction LIN IGoto Améliorez l implémentation précédente pour enregistrer à la volée les labels qui sont effectivement destination d un goto et utilisez cette information pour enlever après le parcours du code les labels inutiles dans instructions Voir la solution En fait la solution implémentée dans ltl2lin ml est un peu meilleure Elle repose sur l utilisation d une passe dans branch ml qui élimine les instructions LTL IGoto avant de traduire le code en LIN Génération de code assembleur Il s agit de compléter lin2asm ml Le sous ensemble de l assembleur MIPS destination de cette traduction est présenté dans ASM mli Les deux problèmes posés par cette traduction sont les suivants le registre sp doit être incrémenté décrémenté à chaque appel de fonction les offsets utilisés pour accéder aux paramètres entrants sortants et aux variables locales doivent être traduits en offsets par rapport à sp La figure suivante récapitule la convention MIPS lors d un appel de f à g pour les arguments qui ne sont pas passés par registres physiques Voici ensuite une figure détaillée de l agencement des trames de pile Cela nécessite d implémenter les variables et fonctions suivantes locals proc is the size of the proc s local stack area let locals proc LIN procedure int32 formals proc is the size of the proc s incoming stack area let formals proc LIN procedure int32

    Original URL path: http://nicolaspouillard.fr/td-compil/TD9/index.html (2015-10-11)
    Open archived version from archive

  • Signatures.OrderedTypePrintable
    sig type t val compare Signatures OrderedTypePrintable t Signatures OrderedTypePrintable t int val print Format formatter Signatures OrderedTypePrintable t unit end

    Original URL path: http://nicolaspouillard.fr/ocamlbuild/html/type_Signatures.OrderedTypePrintable.html (2015-10-11)
    Open archived version from archive