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

SCM Repository

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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 958 - (view) (download) (as text)
Original Path: sml/trunk/src/MLRISC/ra/ra-graph.sig

1 : monnier 469 (*
2 :     * This is the new interference graph used by the new register allocator.
3 :     *
4 :     * -- Allen
5 :     *)
6 : monnier 427
7 :     signature RA_GRAPH =
8 :     sig
9 :    
10 : leunga 744 structure C : CELLS_BASIS
11 :    
12 : monnier 427 (*
13 :     * The following are the data structures used in the register allocator.
14 :     *)
15 :    
16 : monnier 469 (* A new bit matrix datatype.
17 :     * We use the small representation whenever possible to save space.
18 :     *)
19 :     datatype bitMatrix = BM of {table:hashTable,
20 :     elems:int ref,
21 :     edges:int}
22 :     and hashTable = SMALL of word list Array.array ref * word
23 :     | LARGE of bucket Array.array ref * word
24 :     (* | BITMATRIX of Word8Array.array *)
25 :     and bucket = NIL | B of int * int * bucket
26 : monnier 427
27 :     exception Nodes
28 :    
29 : monnier 469 type priority = int
30 :     type cost = int
31 :    
32 :     (*
33 :     * The following represent a program point in the program.
34 :     *
35 :     * The last instruction in the block is numbered 1, i.e. the instruction
36 :     * numbering is in reverse. The number 0 is reserved for "live-out".
37 :     *
38 :     *)
39 : george 958 type programPoint = {block:int, insn:int}
40 : monnier 469
41 : leunga 744 (* 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 : monnier 498 type mode = word
57 :    
58 : monnier 427 datatype interferenceGraph =
59 : monnier 469 GRAPH of
60 :     { bitMatrix : bitMatrix ref,
61 : blume 733 nodes : node IntHashTable.hash_table,
62 : monnier 469 K : int,
63 :     firstPseudoR : int,
64 : george 823 dedicated : int -> bool,
65 : monnier 469 getreg : {pref:int list, stamp:int, proh:int Array.array} -> int,
66 :     getpair : {pref:int list, stamp:int, proh:int Array.array} -> int,
67 :     proh : int Array.array,
68 :     stamp : int ref,
69 : monnier 427
70 : monnier 469 (* Info to undo a spill when an optimistic spill has occurred *)
71 :     spillFlag : bool ref,
72 : monnier 427
73 : leunga 744 spilledRegs : bool IntHashTable.hash_table,
74 :     (*registers that have been spilled*)
75 : monnier 469 trail : trailInfo ref,
76 :    
77 :     (* how to pretty print a register *)
78 : leunga 744 showReg : C.cell -> string,
79 : monnier 469
80 :     (* how many registers there are? *)
81 :     numRegs : int,
82 :     maxRegs : unit -> int,
83 :    
84 :     (* dead copies *)
85 : leunga 744 deadCopies : C.cell list ref,
86 : monnier 498 copyTmps : node list ref,
87 :     memMoves : move list ref,
88 :     memRegs : node list ref,
89 : monnier 469
90 :     (* spill locations *)
91 : monnier 498 spillLoc : int ref,
92 :    
93 :     (* span indexed by node id *)
94 : blume 733 span : int IntHashTable.hash_table option ref,
95 : monnier 498
96 :     (* mode *)
97 :     mode : mode,
98 :    
99 :     pseudoCount : int ref,
100 :     blockedCount : int ref
101 : monnier 469 }
102 :    
103 : monnier 498 and moveStatus = BRIGGS_MOVE (* not yet coalesceable *)
104 :     | GEORGE_MOVE (* not yet coalesceable *)
105 :     | COALESCED (* coalesced *)
106 :     | CONSTRAINED (* src and target intefere *)
107 :     | LOST (* frozen moves *)
108 :     | WORKLIST (* on the move worklist *)
109 : monnier 469
110 : monnier 427 and move =
111 : monnier 469 MV of {src : node, (* source register of move *)
112 :     dst : node, (* destination register of move *)
113 :     (*kind : moveKind, *) (* kind of move *)
114 :     cost : cost, (* cost *)
115 : monnier 498 status : moveStatus ref, (* coalesced? *)
116 :     hicount: int ref (* neighbors of high degree *)
117 : monnier 427 }
118 :    
119 : monnier 469 and moveKind = REG_TO_REG (* register to register *)
120 :     | EVEN_TO_REG (* even register in pair to register *)
121 :     | ODD_TO_REG (* odd register in pair to register *)
122 :     | PAIR_TO_PAIR (* register pair to register pair *)
123 :     | REG_TO_EVEN (* register to even register in pair *)
124 :     | REG_TO_ODD (* register to odd register in pair *)
125 : monnier 427
126 : george 705 and nodeStatus =
127 : monnier 469 PSEUDO (* pseudo register *)
128 :     | REMOVED (* removed from the interference graph *)
129 :     | ALIASED of node (* coalesced *)
130 :     | COLORED of int (* colored *)
131 : leunga 744 | MEMREG of int * C.cell(* register implemented in memory *)
132 : george 705 | SPILLED (* spilled *)
133 :     | SPILL_LOC of int (* spilled at logical location *)
134 : monnier 469
135 : monnier 498 (* Note on SPILLED:
136 :     * SPILLED ~1 means that the spill location is still undetermined
137 :     * SPILLED c, c >= 0 means that c is a fixed "memory register"
138 :     * SPILLED c, c < ~1 means that c is a logical spill location
139 :     * assigned by the register allocator
140 :     *)
141 :    
142 : monnier 427 and node =
143 : leunga 744 NODE of { number : int, (* node number *)
144 :     cell: C.cell,
145 : monnier 427 movecnt: int ref, (* #moves this node is involved in *)
146 :     movelist: move list ref, (* moves associated with this node *)
147 :     degree : int ref, (* current degree *)
148 :     color : nodeStatus ref, (* status *)
149 : monnier 469 adj : node list ref, (* adjacency list *)
150 :     pri : priority ref, (* priority *)
151 :     movecost : cost ref, (* move cost *)
152 :     (* pair : bool, *) (* register pair? *)
153 :     defs : programPoint list ref,
154 :     uses : programPoint list ref
155 : monnier 427 }
156 :    
157 : monnier 469 and trailInfo = END | UNDO of node * moveStatus ref * trailInfo
158 : monnier 427
159 : monnier 469 (* Create a new bitMatrix *)
160 :     val newBitMatrix : {edges : int, maxRegs : int} -> bitMatrix
161 : monnier 427
162 : monnier 469 (* Create a new interference graph *)
163 : blume 733 val newGraph : { nodes : node IntHashTable.hash_table,
164 : monnier 427 numRegs : int,
165 : monnier 469 maxRegs : unit -> int,
166 : monnier 427 K : int,
167 :     firstPseudoR : int,
168 : george 823 dedicated : int -> bool,
169 : leunga 744 showReg : C.cell -> string,
170 : monnier 427 getreg :
171 : monnier 469 {pref:int list,stamp:int,proh:int Array.array} -> int,
172 :     getpair :
173 :     {pref:int list,stamp:int,proh:int Array.array} -> int,
174 : monnier 498 proh : int Array.array,
175 :     mode : mode,
176 :     spillLoc : int ref,
177 : leunga 744 memRegs : C.cell list
178 : monnier 469 } -> interferenceGraph
179 : monnier 427
180 :     end

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