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 2126 - (view) (download) (as text)

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

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