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