Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Diff of /MLRISC/trunk/ra/ra-graph.sig
ViewVC logotype

Diff of /MLRISC/trunk/ra/ra-graph.sig

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 545, Thu Feb 24 13:56:44 2000 UTC revision 1009, Wed Jan 9 19:44:22 2002 UTC
# Line 7  Line 7 
7  signature RA_GRAPH =  signature RA_GRAPH =
8  sig  sig
9    
10       structure C : CELLS_BASIS
11    
12    (*    (*
13     * The following are the data structures used in the register allocator.     * The following are the data structures used in the register allocator.
14     *)     *)
# Line 34  Line 36 
36     * numbering is in reverse.  The number 0 is reserved for "live-out".     * numbering is in reverse.  The number 0 is reserved for "live-out".
37     *     *
38     *)     *)
39    type programPoint = int    type programPoint = {block:int, insn:int}
40    
41      (* Hash table indexed by program point *)
42      structure PPtHashTable : MONO_HASH_TABLE
43          where type Key.hash_key = programPoint
44    
45      type frame_offset = int
46      type logical_spill_id = int
47    
48      datatype spillLoc =
49         FRAME   of logical_spill_id  (* spill to a new frame location *)
50       | MEM_REG of C.cell            (* spill to a memory register *)
51    
52      (* Hash table indexed by spill location *)
53      structure SpillLocHashTable : MONO_HASH_TABLE
54          where type Key.hash_key = spillLoc
55    
56    type mode = word    type mode = word
57    
58    datatype interferenceGraph =    datatype interferenceGraph =
59       GRAPH of       GRAPH of
60       { bitMatrix    : bitMatrix ref,       { bitMatrix    : bitMatrix ref,
61         nodes        : node Intmap.intmap,         nodes        : node IntHashTable.hash_table,
        regmap       : int Intmap.intmap,  
62         K            : int,         K            : int,
63         firstPseudoR : int,         firstPseudoR : int,
64         dedicated    : bool Array.array,         dedicated    : int -> bool,
65         getreg       : {pref:int list, stamp:int, proh:int Array.array} -> int,         getreg       : {pref:int list, stamp:int, proh:int Array.array} -> int,
66         getpair      : {pref:int list, stamp:int, proh:int Array.array} -> int,         getpair      : {pref:int list, stamp:int, proh:int Array.array} -> int,
67         proh         : int Array.array,         proh         : int Array.array,
# Line 54  Line 70 
70         (* Info to undo a spill when an optimistic spill has occurred *)         (* Info to undo a spill when an optimistic spill has occurred *)
71         spillFlag    : bool ref,         spillFlag    : bool ref,
72    
73         spilledRegs  : bool Intmap.intmap, (*registers that have been spilled*)         spilledRegs  : bool IntHashTable.hash_table,
74                               (*registers that have been spilled*)
75         trail        : trailInfo ref,         trail        : trailInfo ref,
76    
77         (* how to pretty print a register *)         (* how to pretty print a register *)
78         showReg      : int -> string,         showReg      : C.cell -> string,
79    
80         (* how many registers there are? *)         (* how many registers there are? *)
81         numRegs      : int,         numRegs      : int,
82         maxRegs      : unit -> int,         maxRegs      : unit -> int,
83    
84         (* dead copies *)         (* dead copies *)
85         deadCopies   : int list ref,         deadCopies   : C.cell list ref,
86         copyTmps     : node list ref,         copyTmps     : node list ref,
87         memMoves     : move list ref,         memMoves     : move list ref,
88         memRegs      : node list ref,         memRegs      : node list ref,
# Line 74  Line 91 
91         spillLoc     : int ref,         spillLoc     : int ref,
92    
93         (* span indexed by node id *)         (* span indexed by node id *)
94         span         : int Intmap.intmap option ref,         span         : int IntHashTable.hash_table option ref,
95    
96         (* mode *)         (* mode *)
97         mode         : mode,         mode         : mode,
# Line 93  Line 110 
110    and move =    and move =
111      MV of {src    : node,               (* source register of move *)      MV of {src    : node,               (* source register of move *)
112             dst    : node,               (* destination register of move *)             dst    : node,               (* destination register of move *)
113             (*kind   : moveKind, *)      (* kind of move *)  (*           kind   : moveKind,           (* kind of move *) *)
114             cost   : cost,               (* cost *)             cost   : cost,               (* cost *)
115             status : moveStatus ref,     (* coalesced? *)             status : moveStatus ref,     (* coalesced? *)
116             hicount: int ref             (* neighbors of high degree *)             hicount: int ref             (* neighbors of high degree *)
# Line 105  Line 122 
122                 | PAIR_TO_PAIR    (* register pair to register pair *)                 | PAIR_TO_PAIR    (* register pair to register pair *)
123                 | REG_TO_EVEN     (* register to even register in pair *)                 | REG_TO_EVEN     (* register to even register in pair *)
124                 | REG_TO_ODD      (* register to odd register in pair *)                 | REG_TO_ODD      (* register to odd register in pair *)
125    (*  and moveKind = REGmvk                (* register-register move *)
126                   | MEMREGmvk       (* move involving memReg  *)
127    
128    *)
129    
130    and nodeStatus =    and nodeStatus =
131          PSEUDO                (* pseudo register *)          PSEUDO                (* pseudo register *)
132        | REMOVED               (* removed from the interference graph *)        | REMOVED               (* removed from the interference graph *)
133        | ALIASED of node       (* coalesced *)        | ALIASED of node       (* coalesced *)
134        | COLORED of int        (* colored *)        | COLORED of int        (* colored *)
135        | SPILLED of int        (* spilled *)        | MEMREG of int * C.cell(* register implemented in memory *)
136          | SPILLED               (* spilled *)
137          | SPILL_LOC of int      (* spilled at logical location *)
138    
139         (* Note on SPILLED:         (* Note on SPILLED:
140          *  SPILLED ~1 means that the spill location is still undetermined          *  SPILLED ~1 means that the spill location is still undetermined
# Line 122  Line 145 
145    
146    and node =    and node =
147      NODE of { number : int,             (* node number *)      NODE of { number : int,             (* node number *)
148                  cell:    C.cell,
149                movecnt: int ref,         (* #moves this node is involved in *)                movecnt: int ref,         (* #moves this node is involved in *)
150                movelist: move list ref,  (* moves associated with this node *)                movelist: move list ref,  (* moves associated with this node *)
151                degree : int ref,         (* current degree *)                degree : int ref,         (* current degree *)
# Line 140  Line 164 
164    val newBitMatrix : {edges : int, maxRegs : int} -> bitMatrix    val newBitMatrix : {edges : int, maxRegs : int} -> bitMatrix
165    
166    (* Create a new interference graph *)    (* Create a new interference graph *)
167    val newGraph : { nodes        : node Intmap.intmap,    val newGraph : { nodes        : node IntHashTable.hash_table,
                    regmap       : int Intmap.intmap,  
168                     numRegs      : int,                     numRegs      : int,
169                     maxRegs      : unit -> int,                     maxRegs      : unit -> int,
170                     K            : int,                     K            : int,
171                     firstPseudoR : int,                     firstPseudoR : int,
172                     dedicated    : bool Array.array,                     dedicated    : int -> bool,
173                     showReg      : int -> string,                     showReg      : C.cell -> string,
174                     getreg       :                     getreg       :
175                       {pref:int list,stamp:int,proh:int Array.array} -> int,                       {pref:int list,stamp:int,proh:int Array.array} -> int,
176                     getpair      :                     getpair      :
# Line 155  Line 178 
178                     proh         : int Array.array,                     proh         : int Array.array,
179                     mode         : mode,                     mode         : mode,
180                     spillLoc     : int ref,                     spillLoc     : int ref,
181                     firstMemReg  : int,                     memRegs      : C.cell list
                    numMemRegs   : int  
182                   } -> interferenceGraph                   } -> interferenceGraph
183    
184  end  end

Legend:
Removed from v.545  
changed lines
  Added in v.1009

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0