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

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