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".
  • Allocation de registres, solutions
    coalesce all preference edges without fear of creating high degree nodes This is good because a move between two pseudo registers that have been spilled in distinct stack slots is very expensive one load followed by one store let rec coalesce graph coloring match pppick graph fun true with Some x y if G verbose then printf SPILL Coalescing s and s n print vertex graph x print vertex graph y let graph Interference coalesce graph x y in let coloring coalesce graph in Vertex Map add x Vertex Map find y coloring coloring None simplify graph Optimisations La fusion conservative La fonction selection est conservée à l identique Entre les fonctions simplification et selection on trouve maintenant les fonctions coalescing et spilling The algorithm maintains a transformed graph as it runs It is obtained from the original graph by removing and coalescing vertices Each of the functions that follow returns a coloring of the graph that it is passed These functions correspond to the various states of the algorithm simplification coalescing selection simplification removes nodes of low degree It is the algorithm s initial state let rec simplification graph coloring match lowest graph with Some v d when d k We found a node v of low degree Color the rest of the graph then color v This is what I call selection if G verbose then printf Simplifying low vertex s n print vertex graph v selection graph v There are no nodes of low degree Could not simplify further Start coalescing coalescing graph coalescing looks for a preference edge that can be collapsed It is called after simplification so it is known at this point that there are no nodes of low degree and coalescing graph coloring Find a preference edge between two vertices that passes George s criterion match pppick graph georgepp graph with Some a b if G verbose then printf Coalescing s with s n print vertex graph a print vertex graph b Coalesce a with b and color the remaining graph let coloring simplification coalesce graph a b in Assign a the same color as b Vertex Map add a Vertex Map find b coloring coloring None Find a preference edge between a vertex and a hardware register that passes George s criterion match phpick graph georgeph graph with Some a c if G verbose then printf Coalescing s with s n print vertex graph a MIPS print c Coalesce a with c and color the remaining graph let coloring simplification coalesceh graph a c in Assign a the color c Vertex Map add a Color c coloring None Could not coalesce further Start spilling spilling graph spilling begins after simplification and coalescing so it is known at this point that there are no nodes of low degree Thus we are facing a potential spill However we do optimistic coloring we do not spill a vertex right away but proceed normally just as if we were doing simplification So we pick a vertex

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


  • Génération de code assembleur, solutions
    it has been visited before visiting it again would only produce an unreachable IGoto instruction LTL IUnBranch cond r l1 l2 generate LIN IUnBranch cond r l1 visit l2 if not Label Set mem l1 visited then visit fresh l1 LTL IBinBranch cond r1 r2 l1 l2 generate LIN IBinBranch cond r1 r2 l1 visit l2 if not Label Set mem l1 visited then visit fresh l1 LTL IReturn generate LIN IReturn Enlever les labels inutiles let translate entry graph Keep track of the labels that must be explicitly named within the LIN code These are the targets of LIN branch instructions and as a special case the graph s entry point let explicit ref Label Set singleton entry in let mark label explicit Label Set add label explicit in Traverse the control flow graph A simple depth first traversal is implemented here let rec visit l Label l has been visited before so an ILabel l instruction has been issued We must now generate an IGoto instruction that transfers control to this place Because l is the target of a branch instruction we record the fact that it should be explicit if Label Set mem l visited then begin mark l generate LIN IGoto l end else visit fresh l and visit fresh l LTL IUnBranch cond r l1 l2 mark l1 LTL IBinBranch cond r1 r2 l1 l2 mark l1 in visit entry Now get rid of the labels that do not need to be explicit Also reverse the list to reestablish the correct order List filter function LIN ILabel l Label Set mem l explicit true List rev instructions Génération de code assembleur Calcul des déplacements In order to translate IGetStack and ISetStack one must understand the actual layout of stack frames The MIPS stack grows towards low addresses I will speak of the high limit address of the stack frame that is the address of the previous stack frame as the top of the stack frame and of the low limit address of the stack frame as the bottom of the stack frame The top of the stack frame is the initial value of sp when the procedure is entered The bottom of the stack frame is the new value of sp that the procedure installs The difference between the two corresponds to the parameters that are passed on the stack and to the procedure s local stack storage area We refer to this value as the size of the frame Thus the top of the stack frame is at sp locals formals where locals is the size of the local storage area and formals is the size of the formal parameters area both expressed in bytes The parameters are between sp locals and sp locals formals Local storage lies between sp and sp locals A SlotIncoming stack slot is translated into an offset into the frame s parameters area A SlotLocal stack slot is translated into an offset into the frame s local storage area

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

  • Std_signatures.LIST
    map a b a list b list val fold left a b a a b list a val fold right a b b a list b b val iter2 a b unit a list b list unit val map2 a b c a list b list c list val rev map2 a b c a list b list c list val fold left2 a b c a a b list c list a val fold right2 a b c c a list b list c c val for all a bool a list bool val exists a bool a list bool val for all2 a b bool a list b list bool val exists2 a b bool a list b list bool val mem a a list bool val memq a a list bool val find a bool a list a val filter a bool a list a list val find all a bool a list a list val partition a bool a list a list a list val assoc a a b list b val assq a a b list b val mem assoc a a b list bool val mem assq a a b list bool val remove

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

  • Std_signatures.STRING
    concat string string list string val iter char unit string unit val escaped string string val index string char int val rindex string char int val index from string int char int val rindex from string int char int val contains string char bool val contains from string int char bool val rcontains from string int char bool val uppercase string string val lowercase string string val capitalize string string

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

  • Signatures.TAGS.Operators
    sig val t elt t val t elt t val t elt option t val t elt option t end

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

  • Signatures.PATHNAME.Operators
    sig val Signatures PATHNAME t Signatures PATHNAME t Signatures PATHNAME t val Signatures PATHNAME t string Signatures PATHNAME t end

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

  • Signatures.PLUGIN.Command
    N S of spec list A of string P of pathname Px of pathname Sh of string T of tags V of string Quote of spec val atomize string list spec val atomize paths string list spec val execute quiet bool pretend bool t unit val execute many quiet bool pretend bool t list bool list exn option val setup virtual command solver string unit spec unit val search in

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

  • Signatures.PLUGIN.StringSet
    t t val union t t t val inter t t t val diff t t t val compare t t int val equal t t bool val subset t t bool val iter elt unit t unit val fold elt a a t a a val for all elt bool t bool val exists elt bool t bool val filter elt bool t t val partition elt bool t

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