1 |
(* |
(* |
2 |
* Graph data structure used by the modular register allocator. |
* This is the new interference graph used by the new register allocator. |
3 |
* |
* |
4 |
* -- Allen |
* -- Allen |
5 |
*) |
*) |
7 |
structure RAGraph : RA_GRAPH = |
structure RAGraph : RA_GRAPH = |
8 |
struct |
struct |
9 |
|
|
10 |
structure BM = TriangularBitMatrix |
(* A new bit matrix datatype. |
11 |
|
* We use the small representation whenever possible to save space. |
12 |
|
*) |
13 |
|
datatype bitMatrix = BM of {table:hashTable, |
14 |
|
elems:int ref, |
15 |
|
edges:int} |
16 |
|
and hashTable = SMALL of word list Array.array ref * word |
17 |
|
| LARGE of bucket Array.array ref * word |
18 |
|
(* | BITMATRIX of Word8Array.array *) |
19 |
|
and bucket = NIL | B of int * int * bucket |
20 |
|
|
21 |
|
type priority = int |
22 |
|
|
23 |
|
type programPoint = int |
24 |
|
|
25 |
|
type cost = int |
26 |
|
|
27 |
datatype interferenceGraph = |
datatype interferenceGraph = |
28 |
GRAPH of { bitMatrix : BM.bitMatrix, |
GRAPH of { bitMatrix : bitMatrix ref, |
29 |
nodes : node Intmap.intmap, |
nodes : node Intmap.intmap, |
30 |
regmap : int Intmap.intmap, |
regmap : int Intmap.intmap, |
31 |
K : int, |
K : int, |
32 |
firstPseudoR : int, |
firstPseudoR : int, |
33 |
|
dedicated : bool Array.array, |
34 |
getreg : |
getreg : |
35 |
{pref:int list,stamp:int,proh:int Array.array} -> int, |
{pref:int list,stamp:int,proh:int Array.array} -> int, |
36 |
|
getpair : |
37 |
|
{pref:int list, stamp:int, proh:int Array.array} -> int, |
38 |
proh : int Array.array, |
proh : int Array.array, |
39 |
stamp : int ref, |
stamp : int ref, |
40 |
|
|
41 |
(* Info to undo a spill when an optimistic spill has occurred *) |
(* Info to undo a spill when an optimistic spill has occurred *) |
42 |
spillFlag : bool ref, |
spillFlag : bool ref, |
43 |
undoInfo : (node * moveStatus ref) list ref |
spilledRegs : bool Intmap.intmap, |
44 |
|
trail : trailInfo ref, |
45 |
|
|
46 |
|
showReg : int -> string, |
47 |
|
numRegs : int, |
48 |
|
maxRegs : unit -> int, |
49 |
|
|
50 |
|
deadCopies : int list ref, |
51 |
|
spillLoc : int ref |
52 |
} |
} |
53 |
|
|
54 |
and moveStatus = MOVE | COALESCED | CONSTRAINED | LOST | WORKLIST |
and moveStatus = MOVE | COALESCED | CONSTRAINED | LOST | WORKLIST |
56 |
and move = |
and move = |
57 |
MV of {src : node, (* source register of move *) |
MV of {src : node, (* source register of move *) |
58 |
dst : node, (* destination register of move *) |
dst : node, (* destination register of move *) |
59 |
|
(* kind: moveKind, *) (* what kind of move *) |
60 |
|
cost : cost, (* cost *) |
61 |
status : moveStatus ref (* coalesced? *) |
status : moveStatus ref (* coalesced? *) |
62 |
} |
} |
63 |
|
|
64 |
and nodeStatus = REMOVED | PSEUDO | ALIASED of node | COLORED of int |
and moveKind = REG_TO_REG (* register to register *) |
65 |
|
| EVEN_TO_REG (* even register in pair to register *) |
66 |
|
| ODD_TO_REG (* odd register in pair to register *) |
67 |
|
| PAIR_TO_PAIR (* register pair to register pair *) |
68 |
|
| REG_TO_EVEN (* register to even register in pair *) |
69 |
|
| REG_TO_ODD (* register to odd register in pair *) |
70 |
|
|
71 |
|
and nodeStatus = |
72 |
|
PSEUDO (* pseudo register *) |
73 |
|
| REMOVED (* removed from the interference graph *) |
74 |
|
| ALIASED of node (* coalesced *) |
75 |
|
| COLORED of int (* colored *) |
76 |
|
| SPILLED of int (* spilled *) |
77 |
|
| ALIASED_SPILL of node (* aliased spill node *) |
78 |
|
|
79 |
and node = |
and node = |
80 |
NODE of { number : int, (* node number *) |
NODE of { number : int, (* node number *) |
82 |
movelist: move list ref, (* moves associated with this node *) |
movelist: move list ref, (* moves associated with this node *) |
83 |
degree : int ref, (* current degree *) |
degree : int ref, (* current degree *) |
84 |
color : nodeStatus ref, (* status *) |
color : nodeStatus ref, (* status *) |
85 |
adj : node list ref (* adjacency list *) |
adj : node list ref, (* adjacency list *) |
86 |
} |
pri : priority ref, (* priority *) |
87 |
(* |
movecost : cost ref, (* move cost *) |
88 |
* The valid transitions for a node are: |
(* pair : bool, *) (* register pair? *) |
89 |
* PSEUDO -> REMOVED % during simplify |
defs : programPoint list ref, |
90 |
* PSEUDO -> ALIASED(n) % during coalescing |
uses : programPoint list ref |
|
* REMOVED -> COLORED(r) % assigning a color |
|
|
* |
|
|
* ... all others are illegal. |
|
|
*) |
|
|
|
|
|
type 'a worklist = 'a list |
|
|
type nodelist = node worklist |
|
|
type movelist = move worklist |
|
|
|
|
|
type ('sim,'move,'freeze,'spill,'stack) lists = |
|
|
{simplifyWkl: 'sim, (* nodes that can be simplified *) |
|
|
moveWkl : 'move, (* moves to be considered for coalescing *) |
|
|
freezeWkl : 'freeze, (* all n, s.t. degree(n)<K and moveRelated(n) *) |
|
|
spillWkl : 'spill, (* all n, s.t. degree(n)>=K *) |
|
|
stack : 'stack (* nodes removed from the graph *) |
|
91 |
} |
} |
92 |
|
|
93 |
type worklists = (nodelist,movelist,nodelist,nodelist,nodelist) lists |
and trailInfo = END | UNDO of node * moveStatus ref * trailInfo |
94 |
|
|
95 |
exception Nodes |
exception Nodes |
96 |
|
|
97 |
|
fun error msg = MLRiscErrorMsg.error("RAGraph", msg) |
98 |
|
|
99 |
|
val stampCounter = ref 0 |
100 |
|
|
101 |
|
(* Create a new bitMatrix *) |
102 |
|
fun roundSize size = |
103 |
|
let fun f(x, shift) = |
104 |
|
if x >= size then (x, Word.>>(shift, 0w1)) |
105 |
|
else f(x+x, shift+0w1) |
106 |
|
in f(64, 0w6) end |
107 |
|
|
108 |
|
val max = Word.<<(0w1,Word.>>(Word.fromInt Word.wordSize,0w1)) |
109 |
|
val _ = if max < Word.<<(0w1,0w15) |
110 |
|
then error "word size too small" else () |
111 |
|
|
112 |
|
fun newBitMatrix{edges, maxRegs} = |
113 |
|
let val table = |
114 |
|
(* if maxRegs < 1024 then |
115 |
|
let val denseBytes = (maxRegs * (maxRegs + 1) + 15) div 16 |
116 |
|
in BITMATRIX(Word8Array.array(denseBytes,0w0)) |
117 |
|
end |
118 |
|
else *) |
119 |
|
let val (tableSize, shift) = roundSize edges |
120 |
|
in if Word.fromInt maxRegs < max then |
121 |
|
SMALL(ref(Array.array(tableSize,[])),shift) |
122 |
|
else |
123 |
|
LARGE(ref(Array.array(tableSize,NIL)),shift) |
124 |
|
end |
125 |
|
in BM{table=table, elems=ref 0, edges=edges} |
126 |
|
end |
127 |
|
|
128 |
(* Create a new interference graph *) |
(* Create a new interference graph *) |
129 |
fun newGraph{nodes,regmap,K,firstPseudoR,getreg,numRegs} = |
fun newGraph{nodes,regmap,K,firstPseudoR,dedicated, |
130 |
|
getreg,getpair,showReg,maxRegs,numRegs,proh} = |
131 |
let (* lower triangular bitmatrix primitives *) |
let (* lower triangular bitmatrix primitives *) |
132 |
(* NOTE: The average ratio of E/N is about 16 *) |
(* NOTE: The average ratio of E/N is about 16 *) |
133 |
val bitMatrix = BM.new numRegs |
val bitMatrix = newBitMatrix{edges=numRegs * 16,maxRegs=maxRegs()} |
134 |
in GRAPH{ bitMatrix = bitMatrix, |
in if !stampCounter > 10000000 then stampCounter := 0 else (); |
135 |
|
GRAPH{ bitMatrix = ref bitMatrix, |
136 |
nodes = nodes, |
nodes = nodes, |
137 |
regmap = regmap, |
regmap = regmap, |
138 |
K = K, |
K = K, |
139 |
firstPseudoR = firstPseudoR, |
firstPseudoR = firstPseudoR, |
140 |
|
dedicated = dedicated, |
141 |
getreg = getreg, |
getreg = getreg, |
142 |
proh = Array.array(firstPseudoR,~1), |
getpair = getpair, |
143 |
stamp = ref 0, |
proh = proh, |
144 |
|
stamp = stampCounter, |
145 |
spillFlag = ref false, |
spillFlag = ref false, |
146 |
undoInfo = ref [] |
spilledRegs = Intmap.new(2,Nodes), |
147 |
|
trail = ref END, |
148 |
|
showReg = Int.toString, |
149 |
|
numRegs = numRegs, |
150 |
|
maxRegs = maxRegs, |
151 |
|
deadCopies = ref [], |
152 |
|
spillLoc = ref ~2 |
153 |
} |
} |
154 |
end |
end |
155 |
|
|
156 |
end |
end |
|
|
|