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".
  • Assembleur MIPS, solutions
    printf tli s d n registers target i X printf tmove s a0 n registers target Binexp op e1 e2 do compile target e1 do compile target 1 e2 printf t s s s s n memo of op op registers target registers target registers target 1 let compile expression e do compile 0 e L allocation des registres est faite à l aide du paramètre target de la fonction do compile Cet entier target est l indice dans le tableau registers du premier registre disponible étant entendu que ceux d indices inférieurs sont indisponibles Il n est pas tout à fait immédiat que cette fonction est correcte Considérons les appels récursifs do compile target e1 do compile target 1 e2 Le résultat du calcul de e 1 est présent dans le registre d indice target Ce registre ne doit donc pas être modifié par le code qui calcule e 2 C est bien le cas puisque comme on le prouverait facilement le code produit par un appel do compile i ne modifie que des registres d indice supérieur ou égal à i On remarquera également qu aucun registre n est perdu au sens où tous les registres considérés comme indisponibles servent effectivement à garder un résultat utile pour la suite Bonne utilisation du jeu d instructions Voici une solution possible let registers a0 v0 a1 a2 t0 type arg I of int R of int let parg chan function I i fprintf chan d i R r fprintf chan s registers r let to reg t a match a with I i printf tli s d n registers t i t t 1 R r r t let rec do compile target e match e with Int i I i target X R 0 target Binexp Plus Times as

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


  • Un interprète Pseudo-Pascal, solutions
    qui associe à chaque nom de variable locale une valeur mutable La fonction lookup cherche d abord dans l environnement local env une liaison pour le nom de variable qui lui est passé en paramètre Si cette recherche échoue elle cherche alors cette liaison dans l environnement global genv let lookup genv environment env environment x string value ref try StringMap find x env with Not found try StringMap find x genv with Not found assert false On utilise la fonction de librairie Map find expliquée dans le manuel Objective Caml L explication permet de savoir que Map find lève l exception Not found lorsqu il n y a pas de paire x dans la table et de se servir de ce fait Variables globales La fonction interpret prend la forme suivante let interpret p let genv StringMap map allocate p globals in interpret instruction p defs genv StringMap empty p main où allocate est une fonction qui crée une valeur mutable ou ref en OCaml qu elle initialise à une valeur par défaut Pour les entiers et les booléens cette valeur par défaut est tout simplement 0 ou false pour les tableaux cela implique d ajouter un nouveau type de valeur VNil pour les tableaux pas encore alloués type value VBool of bool VInt of int32 VArray of value array VNil let default function TypBool VBool false TypInt VInt 0l TypArray VNil let allocate typ ref default typ La lecture d une variable nécessite de modifier interpret expression pour lui ajouter le cas suivant EGetVar x lookup genv env x L écriture d une variable nécessite de modifier interpret instruction pour lui ajouter le cas suivant ISetVar x e lookup genv env x interpret expression defs genv env e Fonctions et tableaux Appels de fonctions Le code de fabrication du nouvel environnement local est commun aux procédures et aux fonctions Il s agit de redéfinir l environnement env étendu par les nouvelles liaisons des variables locales à leur valeur par défaut et des noms des arguments paramètres dits formels à la valeur de l argument correspondant paramètres dits effectifs let env List fold right2 fun formal actual env StringMap add formal ref actual env proc formals actuals StringMap empty in let env StringMap addm StringMap map allocate proc locals env in On utilise ici une fonction d itération qui implémente une boucle de manière fonctionnelle la fonction de librairie List fold right2 Dans le cas des fonctions on augmente l environnement d appel d une liaison entre le nom de la fonction et une valeur par défaut correspondant au type de retour attendu Cette liaison est celle de la variable résultat de la fonction Rappelons en effet qu en Pascal on procède ainsi function fact x integer integer begin fact end Ainsi pour finir de construire l environnement d appel d une fonction La fonction Option fold est implémentée dans le fichier option ml Ensuite il reste à évaluer le corps de la fonction dans l environnement si chèrement

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

  • Analyse syntaxique, solutions
    par exemple x t i Il semble clair que l on veut x t i C est à dire que l opérateur est en quelque sorte le plus prioritaire de tous Enfin on règle le problème du dangling else en rendant plus prioritaire le shift qui a la priorité du else que le reduce qui a la priorité du then Les déclarations des priorités sont left AND OR nonassoc LT LE GT GE EQ NE left MINUS PLUS left TIMES SLASH nonassoc unary minus NOT nonassoc LBRACKET nonassoc THEN nonassoc ELSE On a donc du moins prioritaire au plus prioritaire d abord les opérateurs logiques qui sont d égale priorité ensuite les opérateurs de comparaison qui sont non associatifs de sorte que x y z déclenche une erreur puis l addition et la soustraction qui sont associatifs à gauche de sorte que les arbres penchent à gauche puis la multiplication et la division puis le moins unaire et la négation logique opérateurs unaires l indexation dans un tableau vient en dernier enfin dans l ordre on a then puis else Vous pouvez vous demander comment reformuler la grammaire pour régler ces conflits en l absence de telles règles de priorité

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

  • Syntaxe de Pseudo-Pascal
    puis vient le nom du type Ces listes de déclarations sont séparées par des point virgules Plusieurs listes de variables peuvent ainsi être déclarées aucune de ces listes ne pouvant être vide Le tout se termine par un point virgule Par exemple var r array of integer i j integer La liste des arguments utilisée dans la définition d une procédure ou d une fonction suit les mêmes règles à l exception de l utilisation de var au début et du point virgule à la fin Un bloc d instructions est une liste d instructions f séparées par des points virgules entre les mots clés begin et end Une instruction peut être de différentes sortes une affectation de variable consiste en un nom de variable suivi de puis d une expression une affectation dans un tableau consiste en une expression qui donne le tableau suivi d une expression entre crochets qui donne l index suivi de puis d une expression un appel de procédure consiste en un nom de procédure suivi d une liste d expressions f séparées par des virgules entre parenthèses une conditionnelle à une seule alternative commence par le mot clé if suivi d une condition du mot clé then et d une instruction ou un bloc d instructions une conditionnelle à deux alternatives commence comme la conditionnelle à une alternative suivie du mot clé else et d une instruction ou un bloc d instructions une boucle commence par le mot clé while suivi d une condition du mot clé do et d une instruction ou un bloc d instructions Une expression peut aussi être de différentes sortes une constante de type booléen ou entier une lecture de variable consiste en le nom de cette variable une opération unaire consiste en un opérateur unaire suivi d une

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

  • Sélection d'instructions, solutions
    the global variables StringMap fold fun global PP typ genv next StringMap add global next genv next MIPS word p PP globals StringMap empty 0l Accès aux variables globales Comme précédemment Variable access in translate expression Distinguish globals and locals PP EGetVar v if StringSet mem v env then This is a local variable UPP EGetVar v else This is a global variable Translate to a global variable access instruction UPP EGetGlobal StringMap find v genv Variable update in translate instruction Distinguish globals and locals PP ISetVar v e if StringSet mem v env then This is a local variable UPP ISetVar v translate expression genv env e else This is a global variable Translate to a global variable update instruction UPP ISetGlobal StringMap find v genv translate expression genv env e Mémoire dynamique Fonctions utiles Translating a word count into a byte count This involves multiplying by the word size let w2b e Upp2upp mkbinop OpMul UPP EConst MIPS word e Convert a pair of an array base address and element index into an element address This involves adding the base address to the index converted to a byte offset let element address base index Upp2upp mkbinop OpAdd base w2b index Memory loads and stores let mkload function An explicit offset is available Make it part of the load instruction UPP EUnOp UOpAddi i e UPP ELoad e i Default case e UPP ELoad e 0l let mkstore e1 e2 match e1 with An explicit offset is available Make it part of the store instruction UPP EUnOp UOpAddi i1 e1 UPP IStore e1 i1 e2 Default case UPP IStore e1 0l e2 Accès à la mémoire dynamique Array read in translate expression We compute the element s address and access it PP EArrayGet earray eindex mkload element address translate

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

  • Expressions et registres, solutions
    conditional branch UPP CExpression e mkunbranch e UConGtz truel falsel Boolean negation This is implemented without generating any code simply by exchanging the two destination labels UPP CNot c translate condition c falsel truel Boolean conjunction The semantics of the conjunction operator is non strict that is the second condition is not evaluated at all if the first condition evaluates to false UPP CAnd c1 c2 translate condition c1 translate condition c2 truel falsel falsel Boolean disjunction The semantics of the disjunction operator is non strict that is the second condition is not evaluated at all if the first condition evaluates to true UPP COr c1 c2 translate condition c1 truel translate condition c2 truel falsel Et dans translate instruction Conditional Observe how the destination label destl is duplicated so that both branches of the if construct meet again after their execution is over UPP IIf c i1 i2 translate condition c translate instruction i1 destl translate instruction i2 destl Optimisations Voici le code de translate condition avec toutes les optimisations demandées Translating conditions translate condition c truel falsel generates new RTL instructions whose effect is to evaluate the condition c and to transfer control to one of the labels truel and falsel depending on the condition s value It returns the entry label of the newly generated instructions let rec translate condition c UPP condition truel Label t falsel Label t Label t match c with The general compilation scheme for Boolean expressions which follows evaluates the expression into a temporary register then performs a conditional branch depending on whether the register is 0 or 1 Yet some special cases of Boolean expressions can be translated more efficiently That is if the expression is an application of a comparison operator and if it can be mapped into a branch condition consult the types RTL uncon and RTL bincon then we do not need a temporary register we can issue a conditional branch instruction that directly tests the desired condition First here are the cases where we can generate a unary conditional branch instruction UPP CExpression UPP EBinOp OpGe e UPP EConst 0l UPP CExpression UPP EBinOp OpLe UPP EConst 0l e mkunbranch e UConGez truel falsel UPP CExpression UPP EBinOp OpGt e UPP EConst 0l UPP CExpression UPP EBinOp OpLt UPP EConst 0l e mkunbranch e UConGtz truel falsel UPP CExpression UPP EBinOp OpLe e UPP EConst 0l UPP CExpression UPP EBinOp OpGe UPP EConst 0l e mkunbranch e UConLez truel falsel UPP CExpression UPP EBinOp OpLt e UPP EConst 0l UPP CExpression UPP EBinOp OpGt UPP EConst 0l e mkunbranch e UConLtz truel falsel Next here are the cases where we can generate a binary conditional branch instruction UPP CExpression UPP EBinOp OpEq e1 e2 mkbinbranch e1 e2 ConEq truel falsel UPP CExpression UPP EBinOp OpNe e1 e2 mkbinbranch e1 e2 ConNe truel falsel Last here is the general case for Boolean expressions The expression e can evaluate only to true or false which we have represented as

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

  • Traduction des appels, solutions
    l generate ERTL ISetHwReg desthwr sourcer l let sethwregs moves l List fold right sethwreg moves l let osethwreg desthwr osourcer l match osourcer with None l Some sourcer sethwreg desthwr sourcer l let gethwreg destr sourcehwr l generate ERTL IGetHwReg destr sourcehwr l let gethwregs moves l List fold right gethwreg moves l let ogethwreg odestr sourcehwr l match odestr with None l Some destr gethwreg destr sourcehwr l Pseudo registres et emplacements de pile Les fonctions setstackslots et getstackslots sont strictement symétriques ce qui est normal puisque les emplacements sortants de l appelant correspondent aux emplacements entrants de l appelé donc l écriture et la lecture doivent se faire dans le même ordre si on veut que les arguments au site d appel et les paramètres formels de la fonction appelée correspondent Define functions that generate instructions for moving data between stack slots and pseudo registers These are used in order to access the formal parameters stored in the stack s incoming area and when calling a function to write its actual parameters into the stack s outgoing area offsets rs turns the list of pseudo registers rs into a list of pairs of a pseudo register and a stack offset It is here that the offsets at which parameters are stored on the stack is decided This function is used both in setstackslots for storing actual parameters and in getstackslots for fetching formal parameters this ensures consistency between caller and callee let offsets rs let ros List fold right fun r offset ros offset MIPS word r offset ros rs 0l in ros let setstackslots sourcers l List fold right fun sourcer offset l generate ERTL ISetStack ERTL SlotOutgoing offset sourcer l offsets sourcers l let getstackslots destrs l List fold right fun destr offset l generate ERTL IGetStack destr ERTL SlotIncoming offset l offsets destrs l Traduction des appels On suit la convention d appel en utilisant des fonctions auxiliaires de copie dans des registres matériels sethwregs ou dans des emplacements de pile setstackslots ainsi qu une fonction qui récupère optionnellement la valeur d un registre matériel ogethwreg translate call odestr callee actuals l translates the RTL instruction ICall odestr callee actuals l into an ERTL instruction or sequence of instructions that transfers control to l Before the call we copy the actual parameters into their designated position as dictated by the calling convention The first few parameters are passed in registers the rest on the stack For function calls only after the call we copy the result from its designated position to its desired location The IGoto instruction is a convenient way of turning a label into an instruction let translate call odestr callee actuals l ERTL IGoto sethwregs Misc combine MIPS parameters actuals setstackslots Misc subtract actuals MIPS parameters generate ERTL ICall callee Misc length actuals ogethwreg odestr MIPS result l Traduction du prologue et de l épilogue On commencer par générer une liste de couples nouveau pseudo registre registre matériel à sauvegarder Each

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

  • Analyse de durée de vie, solutions
    by the instruction or 2 it is live after the instruction and not defined by the instruction let instruction semantics i instruction invalue L t L t L join used i L diff invalue defined i Optimisation du code inutile La détection des instructions inutiles est la suivante An instruction is considered pure if it has no side effect that is if its only effect is to write a value to its destination pseudo register or hardware register A pure instruction whose destination is dead after the instruction will be eliminated during the translation of ERTL to LTL This is done by replacing the instruction with an IGoto instruction eliminable liveafter i returns Some l where l is i s single successor if instruction i is eliminable Otherwise it returns None The parameter liveafter is the set of variables that are live after the instruction let eliminable pliveafter hliveafter L t i instruction match i with IGetHwReg r l IGetStack r l IGetGlobal r l IConst r l IUnOp r l IBinOp r l ILoad r l if Register Set mem r pliveafter then None else Some l ISetHwReg hwr l if MIPS RegisterSet mem hwr hliveafter then None else Some l IReturn INewFrame IDeleteFrame ISetStack ISetGlobal ICall IStore IGoto IUnBranch IBinBranch None Ce qui donne comme nouvelle sémantique des instructions This is the abstract semantics of instructions It defines the out value of an instruction in terms of its in value That is since liveness analysis is a backward analysis it defines the pseudo registers that are live before the instruction in terms of those that are live after the instruction The standard definition is a pseudo register is considered live before the instruction if either 1 it is used by the instruction or 2 it is live after the instruction and not defined by the instruction As an exception to this rule if the instruction is eliminable then a pseudo register is considered live before the instruction if and only if it is live after the instruction This anticipates on the instruction s elimination This exception means that the source pseudo registers of a pure instruction need not be considered live if the instruction s result is unused This allows a sequence of pure instructions whose end result is dead to be considered entirely dead It is a simple but not entirely trivial exercise to check that this transfer function is monotone let instruction semantics i instruction invalue L t L t match eliminable invalue i with None L join L diff invalue defined i used i Some invalue Calcul des interférences Une première version Le code découle de la définition des interférences Create interference edges The general rule is every pseudo register or hardware register that is defined written by an instruction interferes with every pseudo register or hardware register other than itself that is live immediately after the instruction executes let graph Label Map fold fun label i graph let defined Liveness defined i in let

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