SCM Repository
Annotation of /sml/trunk/src/MLRISC/ra/ra-core.sml
Parent Directory
|
Revision Log
Revision 648 - (view) (download)
1 : | monnier | 427 | (* |
2 : | * | ||
3 : | monnier | 469 | * Overview |
4 : | * ======== | ||
5 : | * This implementation of iterated coalescing differ from the old one in | ||
6 : | * various substantial ways: | ||
7 : | * | ||
8 : | * 1. The move list is prioritized. Higher ranking moves are coalesced first. | ||
9 : | * This tends to favor coalescing of moves that has higher priority. | ||
10 : | * | ||
11 : | * 2. The freeze list is prioritized. Lower ranking nodes are unfrozen | ||
12 : | * first. Since freeze disable moves, this tends to disable moves | ||
13 : | * of low priority. | ||
14 : | * | ||
15 : | * 3. The simplify worklist is not kept explicitly during the | ||
16 : | * simplify/coalesce/freeze phases. Instead, whenever a non-move | ||
17 : | * related node with degree < K is discovered, we call simplify | ||
18 : | * to remove it from the graph immediately. | ||
19 : | * | ||
20 : | * I think this has a few advantages. | ||
21 : | * (a) There is less bookkeeping. | ||
22 : | * (b) Simplify adds coalescable moves to the move list. | ||
23 : | * By doing simplify eagerly, moves are added to the move list | ||
24 : | * faster, allowing higher ranking moves to ``preempt'' low | ||
25 : | * ranking moves. | ||
26 : | * | ||
27 : | * 4. Support for register pairs | ||
28 : | * | ||
29 : | * Important Invariants | ||
30 : | * ==================== | ||
31 : | * 1. Adjacency list | ||
32 : | * a. All nodes on the adjacency list are distinct | ||
33 : | * b. nodes with color ALIASED or REMOVED are NOT consider to be | ||
34 : | * on the adjacency list | ||
35 : | * c. If a node x is COLORED, then we DON'T keep track of | ||
36 : | * its adjacency list | ||
37 : | * d. When a node has been removed, there aren't any moves associated | ||
38 : | * with it. | ||
39 : | * 2. Moves | ||
40 : | * a. Moves marked WORKLIST are on the worklist. | ||
41 : | * b. Moves marked MOVE are NOT on the worklist. | ||
42 : | * c. Moves marked LOST are frozen and are in fact never considered again. | ||
43 : | * d. Moves marked CONSTRAINED cannot be coalesced because the src and dst | ||
44 : | * interfere | ||
45 : | * e. Moves marked COALESCED have been coalesced. | ||
46 : | * f. The movecnt in a node is always the number of nodes | ||
47 : | * currently marked as WORKLIST or MOVE, i.e. the moves that | ||
48 : | * are associated with the node. When this is zero, the node is | ||
49 : | * considered to be non-move related. | ||
50 : | * g. Moves on the move worklist are always distinct. | ||
51 : | * 3. | ||
52 : | * | ||
53 : | * Allen. | ||
54 : | * | ||
55 : | monnier | 427 | *) |
56 : | |||
57 : | structure RACore : RA_CORE = | ||
58 : | struct | ||
59 : | |||
60 : | monnier | 469 | structure G = RAGraph |
61 : | structure A = Array | ||
62 : | structure W = Word | ||
63 : | structure W8A = Word8Array | ||
64 : | structure W8 = Word8 | ||
65 : | monnier | 427 | |
66 : | monnier | 469 | (* For debugging, uncomment Unsafe. *) |
67 : | structure UA = Unsafe.Array | ||
68 : | structure UW8A = Unsafe.Word8Array | ||
69 : | monnier | 427 | |
70 : | monnier | 469 | open G |
71 : | monnier | 427 | |
72 : | monnier | 498 | val debug = false |
73 : | (* val tally = false *) | ||
74 : | |||
75 : | |||
76 : | monnier | 475 | val verbose = MLRiscControl.getFlag "ra-verbose" |
77 : | val ra_spill_coal = MLRiscControl.getCounter "ra-spill-coalescing" | ||
78 : | val ra_spill_prop = MLRiscControl.getCounter "ra-spill-propagation" | ||
79 : | monnier | 469 | |
80 : | monnier | 498 | (* |
81 : | val good_briggs = MLRiscControl.getCounter "good-briggs" | ||
82 : | val bad_briggs = MLRiscControl.getCounter "bad-briggs" | ||
83 : | val good_george = MLRiscControl.getCounter "good-george" | ||
84 : | val bad_george = MLRiscControl.getCounter "bad-george" | ||
85 : | val good_freeze = MLRiscControl.getCounter "good-freeze" | ||
86 : | val bad_freeze = MLRiscControl.getCounter "bad-freeze" | ||
87 : | *) | ||
88 : | |||
89 : | george | 545 | val NO_OPTIMIZATION = 0wx0 |
90 : | val BIASED_SELECTION = 0wx1 | ||
91 : | val DEAD_COPY_ELIM = 0wx2 | ||
92 : | val COMPUTE_SPAN = 0wx4 | ||
93 : | val SAVE_COPY_TEMPS = 0wx8 | ||
94 : | val HAS_PARALLEL_COPIES = 0wx10 | ||
95 : | leunga | 579 | val SPILL_COALESCING = 0wx100 |
96 : | val SPILL_COLORING = 0wx200 | ||
97 : | val SPILL_PROPAGATION = 0wx400 | ||
98 : | val MEMORY_COALESCING = | ||
99 : | SPILL_COALESCING + SPILL_COLORING + SPILL_PROPAGATION | ||
100 : | monnier | 498 | |
101 : | leunga | 579 | |
102 : | monnier | 498 | local |
103 : | |||
104 : | fun isOn(flag,mask) = Word.andb(flag,mask) <> 0w0 | ||
105 : | |||
106 : | monnier | 469 | fun error msg = MLRiscErrorMsg.error("RACore", msg) |
107 : | |||
108 : | (* No overflow checking necessary here *) | ||
109 : | fun x + y = W.toIntX(W.+(W.fromInt x, W.fromInt y)) | ||
110 : | fun x - y = W.toIntX(W.-(W.fromInt x, W.fromInt y)) | ||
111 : | |||
112 : | monnier | 475 | fun concat([], b) = b |
113 : | | concat(x::a, b) = concat(a, x::b) | ||
114 : | |||
115 : | monnier | 498 | in |
116 : | |||
117 : | monnier | 469 | (* |
118 : | * Bit Matrix routines | ||
119 : | monnier | 427 | *) |
120 : | monnier | 469 | structure BM = |
121 : | struct | ||
122 : | fun hashFun(i, j, shift, size) = | ||
123 : | monnier | 498 | let val i = W.fromInt i |
124 : | val j = W.fromInt j | ||
125 : | val h = W.+(W.<<(i, shift), W.+(i, j)) | ||
126 : | val mask = W.-(W.fromInt size, 0w1) | ||
127 : | in W.toIntX(W.andb(h, mask)) end | ||
128 : | monnier | 427 | |
129 : | monnier | 469 | val empty = BM{table=SMALL(ref(A.array(0, [])), 0w0), elems=ref 0, edges=0} |
130 : | monnier | 427 | |
131 : | monnier | 469 | (* |
132 : | val indices = A.array(1024,0) | ||
133 : | monnier | 427 | |
134 : | monnier | 469 | fun init(i,j) = |
135 : | if i < 1024 then | ||
136 : | (A.update(indices, i, j); init(i+1, i+j+1)) | ||
137 : | else () | ||
138 : | |||
139 : | val _ = init(0, 0) | ||
140 : | *) | ||
141 : | leunga | 628 | fun size (BM{elems, ...}) = !elems |
142 : | monnier | 469 | |
143 : | fun edges(BM{table=SMALL(ref table, _), ...}) = A.length table | ||
144 : | | edges(BM{table=LARGE(ref table, _), ...}) = A.length table | ||
145 : | (*| edges(BM{table=BITMATRIX _, edges, ...}) = edges *) | ||
146 : | |||
147 : | fun member(BM{table=SMALL(table, shift), ...}) = | ||
148 : | monnier | 498 | (fn (i, j) => |
149 : | monnier | 469 | let val (i,j) = if i < j then (i, j) else (j, i) |
150 : | val k = W.+(W.<<(W.fromInt i, 0w15), W.fromInt j) | ||
151 : | fun find [] = false | ||
152 : | | find(k'::b) = k = k' orelse find b | ||
153 : | val tab = !table | ||
154 : | in find(UA.sub(tab, hashFun(i, j, shift, A.length tab))) end | ||
155 : | ) | ||
156 : | | member(BM{table=LARGE(table, shift), ...}) = | ||
157 : | monnier | 498 | (fn (i, j) => |
158 : | monnier | 469 | let val (i,j) = if i < j then (i, j) else (j, i) |
159 : | fun find NIL = false | ||
160 : | | find(B(i',j',b)) = i = i' andalso j = j' orelse find b | ||
161 : | val tab = !table | ||
162 : | in find(UA.sub(tab, hashFun(i, j, shift, A.length tab))) end | ||
163 : | ) | ||
164 : | monnier | 498 | (* |
165 : | monnier | 469 | | member(BM{table=BITMATRIX table, ...}) = |
166 : | monnier | 498 | (fn (i, j) => |
167 : | monnier | 469 | let val (i,j) = if i > j then (i, j) else (j, i) |
168 : | val bit = W.fromInt(UA.sub(indices, i) + j) | ||
169 : | val index = W.toIntX(W.>>(bit, 0w3)) | ||
170 : | val mask = W.<<(0w1, W.andb(bit, 0w7)) | ||
171 : | in W.andb(W.fromInt(W8.toInt(UW8A.sub(table, index))), mask) <> 0w0 | ||
172 : | end | ||
173 : | ) | ||
174 : | monnier | 498 | *) |
175 : | monnier | 469 | |
176 : | fun add (BM{table=SMALL(table, shift), elems, ...}) = | ||
177 : | let fun insert(i, j) = | ||
178 : | let val (i,j) = if i < j then (i, j) else (j, i) | ||
179 : | val tab = !table | ||
180 : | val len = A.length tab | ||
181 : | in if !elems < len then | ||
182 : | let val index = hashFun(i, j, shift, len) | ||
183 : | val k = W.+(W.<<(W.fromInt i, 0w15), W.fromInt j) | ||
184 : | fun find [] = false | ||
185 : | | find(k'::b) = k = k' orelse find b | ||
186 : | val b = UA.sub(tab, index) | ||
187 : | in if find b then false | ||
188 : | else (UA.update(tab, index, k::b); | ||
189 : | elems := !elems + 1; true) | ||
190 : | end | ||
191 : | else (* grow table *) | ||
192 : | let val oldTable = tab | ||
193 : | val oldSize = A.length oldTable | ||
194 : | val newSize = oldSize + oldSize | ||
195 : | val newTable = A.array(newSize,[]) | ||
196 : | fun enter n = | ||
197 : | if n < oldSize then | ||
198 : | let fun loop([],a,b) = | ||
199 : | (UA.update(newTable, n, a); | ||
200 : | UA.update(newTable, n + oldSize, b); | ||
201 : | enter(n+1)) | ||
202 : | | loop(k::l,a,b) = | ||
203 : | let val i = W.toIntX(W.>>(k, 0w15)) | ||
204 : | val j = W.toIntX(W.-(k,W.<<(W.fromInt i, 0w15))) | ||
205 : | in if hashFun(i, j, shift, newSize) = n | ||
206 : | then loop(l, k::a, b) | ||
207 : | else loop(l, a, k::b) | ||
208 : | end | ||
209 : | in loop(UA.sub(oldTable, n), [], []) end | ||
210 : | else () | ||
211 : | in table := newTable; | ||
212 : | enter 0; | ||
213 : | insert(i, j) | ||
214 : | end | ||
215 : | end | ||
216 : | in insert | ||
217 : | end | ||
218 : | | add (BM{table=LARGE(table, shift), elems, ...}) = | ||
219 : | let fun insert(i, j) = | ||
220 : | let val (i,j) = if i < j then (i, j) else (j, i) | ||
221 : | val tab = !table | ||
222 : | val len = A.length tab | ||
223 : | in if !elems < len then | ||
224 : | george | 545 | let val index = hashFun(i, j, shift, len) |
225 : | monnier | 469 | fun find NIL = false |
226 : | | find(B(i',j',b)) = i = i' andalso j = j' orelse find b | ||
227 : | val b = UA.sub(tab, index) | ||
228 : | in if find b then false | ||
229 : | else (UA.update(tab, index, B(i,j,b)); | ||
230 : | elems := !elems + 1; true) | ||
231 : | end | ||
232 : | else (* grow table *) | ||
233 : | let val oldTable = tab | ||
234 : | val oldSize = A.length oldTable | ||
235 : | val newSize = oldSize + oldSize | ||
236 : | val newTable = A.array(newSize,NIL) | ||
237 : | fun enter n = | ||
238 : | if n < oldSize then | ||
239 : | let fun loop(NIL,a,b) = | ||
240 : | (UA.update(newTable, n, a); | ||
241 : | UA.update(newTable, n + oldSize, b); | ||
242 : | enter(n+1)) | ||
243 : | | loop(B(i,j,l),a,b) = | ||
244 : | if hashFun(i, j, shift, newSize) = n | ||
245 : | then loop(l, B(i,j,a), b) | ||
246 : | else loop(l, a, B(i,j,b)) | ||
247 : | in loop(UA.sub(oldTable, n), NIL, NIL) end | ||
248 : | else () | ||
249 : | in table := newTable; | ||
250 : | enter 0; | ||
251 : | insert(i, j) | ||
252 : | end | ||
253 : | end | ||
254 : | in insert | ||
255 : | end | ||
256 : | monnier | 498 | (* |
257 : | monnier | 469 | | add(BM{table=BITMATRIX table, ...}) = |
258 : | (fn (i, j) => | ||
259 : | let val (i,j) = if i > j then (i, j) else (j, i) | ||
260 : | val bit = W.fromInt(UA.sub(indices, i) + j) | ||
261 : | val index = W.toIntX(W.>>(bit, 0w3)) | ||
262 : | val mask = W.<<(0w1, W.andb(bit, 0w7)) | ||
263 : | val value = W.fromInt(W8.toInt(UW8A.sub(table, index))) | ||
264 : | in if W.andb(value, mask) <> 0w0 then false | ||
265 : | else (UW8A.update(table, index, | ||
266 : | W8.fromInt(W.toIntX(W.orb(value, mask)))); true) | ||
267 : | end | ||
268 : | ) | ||
269 : | monnier | 498 | *) |
270 : | monnier | 469 | |
271 : | fun delete (BM{table=SMALL(table, shift), elems, ...}) = | ||
272 : | (fn (i,j) => | ||
273 : | let val k = W.+(W.<<(W.fromInt i, 0w15), W.fromInt j) | ||
274 : | fun find [] = [] | ||
275 : | | find(k'::b) = | ||
276 : | if k = k' then (elems := !elems - 1; b) else find b | ||
277 : | val tab = !table | ||
278 : | val index = hashFun(i, j, shift, A.length tab) | ||
279 : | val n = !elems | ||
280 : | in UA.update(tab, index, find(UA.sub(tab, index))); | ||
281 : | !elems <> n | ||
282 : | end | ||
283 : | ) | ||
284 : | | delete (BM{table=LARGE(table, shift), elems, ...}) = | ||
285 : | (fn (i,j) => | ||
286 : | let fun find NIL = NIL | ||
287 : | | find(B(i', j', b)) = | ||
288 : | if i = i' andalso j = j' then (elems := !elems - 1; b) | ||
289 : | else B(i', j', find b) | ||
290 : | val tab = !table | ||
291 : | val index = hashFun(i, j, shift, A.length tab) | ||
292 : | val n = !elems | ||
293 : | in UA.update(tab, index, find(UA.sub(tab, index))); | ||
294 : | !elems <> n | ||
295 : | end | ||
296 : | ) | ||
297 : | (* | ||
298 : | | delete(BM{table=BITMATRIX table, ...}) = | ||
299 : | (fn (i, j) => | ||
300 : | let val (i,j) = if i > j then (i, j) else (j, i) | ||
301 : | val bit = W.fromInt(UA.sub(indices, i) + j) | ||
302 : | val index = W.toIntX(W.>>(bit, 0w3)) | ||
303 : | val mask = W.-(W.<<(0w1, W.andb(bit, 0w7)), 0w1) | ||
304 : | val value = W.fromInt(W8.toInt(UW8A.sub(table, index))) | ||
305 : | in if W.andb(value, mask) = 0w0 then false | ||
306 : | else (UW8A.update(table, index, | ||
307 : | W8.fromInt(W.toIntX(W.andb(value,W.notb mask)))); | ||
308 : | true) | ||
309 : | end | ||
310 : | ) | ||
311 : | *) | ||
312 : | end | ||
313 : | |||
314 : | |||
315 : | (* | ||
316 : | * Priority Queue. Let's hope the compiler will inline it for performance | ||
317 : | *) | ||
318 : | functor PriQueue(type elem val less : elem * elem -> bool) = | ||
319 : | struct | ||
320 : | |||
321 : | |||
322 : | (* A leftist tree is a binary tree with priority ordering | ||
323 : | * with the invariant that the left branch is always the taller one | ||
324 : | *) | ||
325 : | type elem = elem | ||
326 : | monnier | 498 | datatype pri_queue = TREE of elem * int * pri_queue * pri_queue | EMPTY |
327 : | monnier | 469 | |
328 : | fun merge'(EMPTY, EMPTY) = (EMPTY, 0) | ||
329 : | | merge'(EMPTY, a as TREE(_, d, _, _)) = (a, d) | ||
330 : | | merge'(a as TREE(_, d, _, _), EMPTY) = (a, d) | ||
331 : | | merge'(a as TREE(x, d, l, r), b as TREE(y, d', l', r')) = | ||
332 : | let val (root, l, r1, r2) = | ||
333 : | if less(x, y) then (x, l, r, b) else (y, l', r', a) | ||
334 : | val (r, d_r) = merge'(r1, r2) | ||
335 : | monnier | 498 | val d_l = case l of EMPTY => 0 | TREE(_, d, _, _) => d |
336 : | val (l, r, d_t) = if d_l >= d_r then (l, r, d_l+1) else (r, l, d_r+1) | ||
337 : | monnier | 469 | in (TREE(root, d_t, l, r), d_t) end |
338 : | |||
339 : | monnier | 498 | fun merge(a, b) = #1(merge'(a, b)) |
340 : | monnier | 469 | |
341 : | fun add (x, EMPTY) = TREE(x, 1, EMPTY, EMPTY) | ||
342 : | | add (x, b as TREE(y, d', l', r')) = | ||
343 : | if less(x,y) then TREE(x, d'+1, b, EMPTY) | ||
344 : | else #1(merge'(TREE(x, 1, EMPTY, EMPTY), b)) | ||
345 : | end | ||
346 : | |||
347 : | structure FZ = PriQueue | ||
348 : | (type elem=node | ||
349 : | leunga | 579 | fun less(NODE{movecost=ref p1,...}, NODE{movecost=ref p2,...}) = p1 <= p2 |
350 : | monnier | 469 | ) |
351 : | structure MV = PriQueue | ||
352 : | (type elem=G.move | ||
353 : | leunga | 579 | fun less(MV{cost=p1,...}, MV{cost=p2,...}) = p1 >= p2 |
354 : | monnier | 469 | ) |
355 : | monnier | 498 | |
356 : | monnier | 469 | type move_queue = MV.pri_queue |
357 : | type freeze_queue = FZ.pri_queue | ||
358 : | |||
359 : | |||
360 : | (* | ||
361 : | * Utility functions | ||
362 : | *) | ||
363 : | monnier | 427 | fun chase(NODE{color=ref(ALIASED r), ...}) = chase r |
364 : | | chase x = x | ||
365 : | |||
366 : | monnier | 469 | fun colorOf(G.GRAPH{showReg,...}) (NODE{number, color, pri,...}) = |
367 : | showReg number^ | ||
368 : | (case !color of | ||
369 : | monnier | 498 | PSEUDO => "" |
370 : | | REMOVED => "r" | ||
371 : | | ALIASED _ => "a" | ||
372 : | | COLORED c => "["^showReg c^"]" | ||
373 : | | SPILLED ~1 => "s" | ||
374 : | | SPILLED c => (if c >= 0 then "m" else "s")^ | ||
375 : | (if c >= 0 andalso number = c then "" | ||
376 : | else "{"^Int.toString c^"}") | ||
377 : | monnier | 469 | ) |
378 : | |||
379 : | fun show G (node as NODE{pri,...}) = | ||
380 : | colorOf G node^(if !verbose then "("^Int.toString(!pri)^")" else "") | ||
381 : | |||
382 : | (* | ||
383 : | * Dump the interference graph | ||
384 : | *) | ||
385 : | fun dumpGraph(G as G.GRAPH{nodes, showReg, K,...}) stream = | ||
386 : | let fun pr s = TextIO.output(stream, s) | ||
387 : | val show = show G | ||
388 : | val colorOf = colorOf G | ||
389 : | monnier | 498 | fun prMove(MV{src, dst, status=ref(WORKLIST | BRIGGS_MOVE | GEORGE_MOVE), |
390 : | cost,...}) = | ||
391 : | monnier | 469 | pr(colorOf(chase dst)^" <- "^colorOf(chase src)^ |
392 : | "("^Int.toString(cost)^") ") | ||
393 : | | prMove _ = () | ||
394 : | monnier | 498 | |
395 : | fun prAdj(n,n' as NODE{adj, degree, uses, defs, | ||
396 : | color, pri, movecnt, movelist, ...}) = | ||
397 : | (pr(show n'); | ||
398 : | if !verbose then pr(" deg="^Int.toString(!degree)) else (); | ||
399 : | (case !color of | ||
400 : | ALIASED n => (pr " => "; pr(show n); pr "\n") | ||
401 : | | _ => | ||
402 : | (pr(" <-->"); | ||
403 : | app (fn n => (pr " "; pr(show n))) (!adj); pr "\n"; | ||
404 : | if !verbose andalso !movecnt > 0 then | ||
405 : | (pr("\tmoves "^Int.toString(!movecnt)^": "); | ||
406 : | app prMove (!movelist); | ||
407 : | pr "\n" | ||
408 : | ) | ||
409 : | george | 545 | else () |
410 : | monnier | 498 | ) |
411 : | ) | ||
412 : | ) | ||
413 : | monnier | 469 | |
414 : | in pr("=========== K="^Int.toString K^" ===========\n"); | ||
415 : | app prAdj (ListMergeSort.sort (fn ((x, _),(y, _)) => x > y) | ||
416 : | (Intmap.intMapToList nodes)) | ||
417 : | monnier | 427 | end |
418 : | |||
419 : | monnier | 469 | |
420 : | (* | ||
421 : | * Function to create new nodes. | ||
422 : | * Note: it is up to the caller to remove all dedicated registers. | ||
423 : | *) | ||
424 : | fun newNodes(G.GRAPH{nodes, firstPseudoR, ...}) = | ||
425 : | let val getnode = Intmap.map nodes | ||
426 : | val addnode = Intmap.add nodes | ||
427 : | |||
428 : | fun defUse{defs, uses, pt, cost} = | ||
429 : | let fun def reg = | ||
430 : | let val node as NODE{pri, defs,...} = getnode reg | ||
431 : | in pri := !pri + cost;(* increment the priority by the cost *) | ||
432 : | defs := pt :: !defs; | ||
433 : | node | ||
434 : | end | ||
435 : | handle _ => | ||
436 : | let val col = if reg < firstPseudoR then COLORED(reg) else PSEUDO | ||
437 : | val node = | ||
438 : | NODE{number=reg, color=ref col, degree=ref 0, | ||
439 : | adj=ref [], movecnt=ref 0, movelist = ref [], | ||
440 : | movecost=ref 0, (* pair=false, *) pri=ref cost, | ||
441 : | defs=ref [pt], uses=ref []} | ||
442 : | in addnode(reg, node); node | ||
443 : | end | ||
444 : | fun use reg = | ||
445 : | let val node as NODE{pri, uses,...} = getnode reg | ||
446 : | in pri := !pri + cost; (* increment the priority by the cost *) | ||
447 : | uses := pt :: !uses | ||
448 : | end | ||
449 : | handle _ => | ||
450 : | let val col = if reg < firstPseudoR then COLORED(reg) else PSEUDO | ||
451 : | val node = | ||
452 : | NODE{number=reg, color=ref col, degree=ref 0, | ||
453 : | adj=ref [], movecnt=ref 0, movelist = ref [], | ||
454 : | movecost=ref 0, (* pair=false, *) | ||
455 : | pri=ref cost, defs=ref [], uses=ref[pt] | ||
456 : | } | ||
457 : | in addnode(reg, node) | ||
458 : | end | ||
459 : | fun defAll([],ds) = ds | defAll(r::rs,ds) = defAll(rs,def r::ds) | ||
460 : | fun useAll [] = () | useAll(r::rs) = (use r; useAll rs) | ||
461 : | val defs = defAll(defs,[]) | ||
462 : | val _ = useAll uses | ||
463 : | in defs | ||
464 : | end | ||
465 : | in defUse | ||
466 : | monnier | 427 | end |
467 : | |||
468 : | |||
469 : | monnier | 469 | (* |
470 : | * Add an edge (x, y) to the interference graph. | ||
471 : | * Nop if the edge already exists. | ||
472 : | * Note: adjacency lists of colored nodes are not stored | ||
473 : | * within the interference graph to save space. | ||
474 : | monnier | 498 | * Now we allow spilled node to be added to the edge; these do not |
475 : | * count toward the degree. | ||
476 : | monnier | 469 | *) |
477 : | fun addEdge(GRAPH{bitMatrix,...}) = | ||
478 : | let val addBitMatrix = BM.add(!bitMatrix) | ||
479 : | monnier | 498 | in fn (x as NODE{number=xn, color=colx, adj=adjx, degree=degx, ...}, |
480 : | y as NODE{number=yn, color=coly, adj=adjy, degree=degy, ...}) => | ||
481 : | monnier | 427 | if xn = yn then () |
482 : | monnier | 469 | else if addBitMatrix(xn, yn) then |
483 : | monnier | 498 | (case (!colx, !coly) of |
484 : | (PSEUDO, PSEUDO) => (adjx := y :: !adjx; degx := !degx + 1; | ||
485 : | adjy := x :: !adjy; degy := !degy + 1) | ||
486 : | | (PSEUDO, COLORED _) => (adjx := y :: !adjx; degx := !degx + 1) | ||
487 : | | (PSEUDO, SPILLED _) => (adjx := y :: !adjx; adjy := x :: !adjy) | ||
488 : | | (COLORED _, PSEUDO) => (adjy := x :: !adjy; degy := !degy + 1) | ||
489 : | | (COLORED _, COLORED _) => () | ||
490 : | | (COLORED _, SPILLED _) => () | ||
491 : | | (SPILLED _, PSEUDO) => (adjx := y :: !adjx; adjy := x :: !adjy) | ||
492 : | | (SPILLED _, COLORED _) => () | ||
493 : | | (SPILLED _, SPILLED _) => () | ||
494 : | | _ => error "addEdge" | ||
495 : | ) | ||
496 : | else () (* edge already there *) | ||
497 : | monnier | 427 | end |
498 : | |||
499 : | (* | ||
500 : | monnier | 469 | * Remove an edge from the bitmatrix |
501 : | monnier | 427 | *) |
502 : | monnier | 469 | fun removeEdge(GRAPH{bitMatrix,...}) = |
503 : | let val rmvBitMatrix = BM.delete(!bitMatrix) | ||
504 : | fun filter(c,[], adj') = adj' | ||
505 : | | filter(c,(n as NODE{color,...})::adj, adj') = | ||
506 : | filter(c, adj, if c = color then adj' else n::adj') | ||
507 : | fun rmv(NODE{color, adj, degree, (* pair=p1, *)...}, | ||
508 : | s as NODE{(* pair=p2, *) color=c2,...}) = | ||
509 : | (case !color of | ||
510 : | PSEUDO => (adj := filter(c2,!adj,[]); | ||
511 : | (* check for pair <-> pair interference *) | ||
512 : | (* if p1 andalso p2 then degree := !degree - 2 | ||
513 : | else *) degree := !degree - 1 | ||
514 : | ) | ||
515 : | | COLORED _ => () (* not stored *) | ||
516 : | | ALIASED _ => error "removeEdge: ALIASED" | ||
517 : | | REMOVED => error "removeEdge: REMOVED" | ||
518 : | | SPILLED _ => error "removeEdge: SPILLED" | ||
519 : | ) | ||
520 : | in fn (x as NODE{number=xn, ...}, y as NODE{number=yn, ...}) => | ||
521 : | if xn = yn then () | ||
522 : | else if rmvBitMatrix(if xn < yn then (xn, yn) else (yn, xn)) then | ||
523 : | (rmv(x, y); rmv(y, x)) | ||
524 : | else () | ||
525 : | monnier | 427 | end |
526 : | |||
527 : | (* | ||
528 : | monnier | 469 | * Initialize a list of worklists |
529 : | monnier | 427 | *) |
530 : | monnier | 469 | fun initWorkLists |
531 : | monnier | 498 | (GRAPH{nodes, K, bitMatrix, regmap, pseudoCount, blockedCount, |
532 : | firstPseudoR, deadCopies, memMoves, mode, ...}) {moves} = | ||
533 : | leunga | 585 | let |
534 : | (* Remove duplicates from the moves *) | ||
535 : | (* | ||
536 : | local | ||
537 : | fun idOf(mv as MV{src=NODE{number=x, ...}, | ||
538 : | dst=NODE{number=y, ...}, ...}) = | ||
539 : | if x < y then (x,y,mv) else (y,x,mv) | ||
540 : | fun order((a,b,mv1), (c,d,mv2)) = a < c orelse a = c andalso b < d | ||
541 : | fun elimDup((a,b,mv)::mvs, mvs') = elimDup'(a,b,mv,mvs,mvs') | ||
542 : | | elimDup([], mvs') = mvs' | ||
543 : | and elimDup'(a,b,mv,[],mvs') = mv::mvs' | ||
544 : | | elimDup'(a:int,b:int,mv1 as MV{cost=c1,status,src,dst,hicount,...}, | ||
545 : | (c,d,mv2 as MV{cost=c2,...})::rest,mvs') = | ||
546 : | if a=c andalso b=d then | ||
547 : | elimDup'(a,b,MV{cost=c1+c2,status=status, | ||
548 : | src=src,dst=dst,hicount=hicount}, | ||
549 : | rest, mvs') | ||
550 : | else | ||
551 : | elimDup'(c,d,mv2,rest,mv1::mvs') | ||
552 : | val moves = ListMergeSort.sort order (map idOf moves) | ||
553 : | in | ||
554 : | val moves = elimDup(moves, []) | ||
555 : | end | ||
556 : | *) | ||
557 : | |||
558 : | |||
559 : | (* Filter moves that already have an interference | ||
560 : | monnier | 469 | * Also initialize the movelist and movecnt fields at this time. |
561 : | *) | ||
562 : | val member = BM.member(!bitMatrix) | ||
563 : | monnier | 427 | |
564 : | monnier | 469 | fun setInfo(NODE{color=ref PSEUDO, movecost, movecnt, movelist,...}, |
565 : | mv, cost) = | ||
566 : | (movelist := mv :: !movelist; | ||
567 : | movecnt := !movecnt + 1; | ||
568 : | movecost := !movecost + cost | ||
569 : | ) | ||
570 : | | setInfo _ = () | ||
571 : | monnier | 427 | |
572 : | monnier | 498 | fun filter([], mvs', mem) = (mvs', mem) |
573 : | | filter((mv as MV{src as NODE{number=x, color=ref colSrc,...}, | ||
574 : | dst as NODE{number=y, color=ref colDst,...}, | ||
575 : | cost, ...})::mvs, | ||
576 : | mvs', mem) = | ||
577 : | (case (colSrc, colDst) of | ||
578 : | (COLORED _, COLORED _) => filter(mvs, mvs', mem) | ||
579 : | | (SPILLED _, SPILLED _) => filter(mvs, mvs', mem) | ||
580 : | | (SPILLED _, _) => filter(mvs, mvs', mv::mem) | ||
581 : | | (_, SPILLED _) => filter(mvs, mvs', mv::mem) | ||
582 : | | _ => | ||
583 : | if member(x, y) (* moves that interfere *) | ||
584 : | then filter(mvs, mvs', mem) | ||
585 : | monnier | 469 | else (setInfo(src, mv, cost); |
586 : | setInfo(dst, mv, cost); | ||
587 : | monnier | 498 | filter(mvs, MV.add(mv, mvs'), mem) |
588 : | monnier | 469 | ) |
589 : | monnier | 498 | ) |
590 : | monnier | 427 | |
591 : | monnier | 498 | fun filter'([], mvs', mem, dead) = (mvs', mem, dead) |
592 : | | filter'((mv as | ||
593 : | MV{src as NODE{number=x, color as ref colSrc, | ||
594 : | pri, adj, uses,...}, | ||
595 : | dst as NODE{number=y, color=ref colDst, | ||
596 : | defs=dstDefs, uses=dstUses,...}, | ||
597 : | cost, ...})::mvs, | ||
598 : | mvs', mem, dead) = | ||
599 : | (case (colSrc, colDst, dstDefs, dstUses) of | ||
600 : | (COLORED _, COLORED _, _, _) => filter'(mvs, mvs', mem, dead) | ||
601 : | | (SPILLED _, SPILLED _, _, _) => filter'(mvs, mvs', mem, dead) | ||
602 : | | (SPILLED _, _, _, _) => filter'(mvs, mvs', mv::mem, dead) | ||
603 : | | (_, SPILLED _, _, _) => filter'(mvs, mvs', mv::mem, dead) | ||
604 : | | (_, PSEUDO, ref [pt], ref []) => | ||
605 : | monnier | 469 | (* eliminate dead copy *) |
606 : | monnier | 498 | let fun decDegree [] = () |
607 : | | decDegree(NODE{color=ref PSEUDO, degree, ...}::adj) = | ||
608 : | (degree := !degree - 1; decDegree adj) | ||
609 : | | decDegree(_::adj) = decDegree adj | ||
610 : | fun elimUses([], _, uses, pri, cost) = (uses, pri) | ||
611 : | | elimUses(pt::pts, pt' : int, uses, pri, cost) = | ||
612 : | if pt = pt' then elimUses(pts, pt', uses, pri-cost, cost) | ||
613 : | else elimUses(pts, pt', pt::uses, pri, cost) | ||
614 : | val (uses', pri') = elimUses(!uses, pt, [], !pri, cost); | ||
615 : | monnier | 469 | in pri := pri'; |
616 : | uses := uses'; | ||
617 : | color := ALIASED src; | ||
618 : | decDegree(!adj); | ||
619 : | monnier | 498 | filter'(mvs, mvs', mem, y::dead) |
620 : | monnier | 427 | end |
621 : | monnier | 498 | | _ => (* normal moves *) |
622 : | if member(x, y) (* moves that interfere *) | ||
623 : | then filter'(mvs, mvs', mem, dead) | ||
624 : | monnier | 469 | else (setInfo(src, mv, cost); |
625 : | setInfo(dst, mv, cost); | ||
626 : | monnier | 498 | filter'(mvs, MV.add(mv, mvs'), mem, dead) |
627 : | monnier | 469 | ) |
628 : | monnier | 498 | ) |
629 : | |||
630 : | monnier | 469 | (* |
631 : | * Scan all nodes in the graph and check which worklist they should | ||
632 : | * go into. | ||
633 : | *) | ||
634 : | monnier | 498 | fun collect([], simp, fz, moves, spill, pseudos, blocked) = |
635 : | (pseudoCount := pseudos; | ||
636 : | blockedCount := blocked; | ||
637 : | monnier | 469 | {simplifyWkl = simp, |
638 : | moveWkl = moves, | ||
639 : | freezeWkl = fz, | ||
640 : | spillWkl = spill | ||
641 : | } | ||
642 : | monnier | 498 | ) |
643 : | | collect(node::rest, simp, fz, moves, spill, pseudos, blocked) = | ||
644 : | monnier | 469 | (case node of |
645 : | NODE{color=ref PSEUDO, movecnt, degree, ...} => | ||
646 : | if !degree >= K then | ||
647 : | monnier | 498 | collect(rest, simp, fz, moves, node::spill, |
648 : | pseudos+1, blocked) | ||
649 : | monnier | 469 | else if !movecnt > 0 then |
650 : | monnier | 498 | collect(rest, simp, FZ.add(node, fz), |
651 : | moves, spill, pseudos+1, blocked+1) | ||
652 : | monnier | 469 | else |
653 : | monnier | 498 | collect(rest, node::simp, fz, moves, spill, |
654 : | pseudos+1, blocked) | ||
655 : | | _ => collect(rest, simp, fz, moves, spill, pseudos, blocked) | ||
656 : | monnier | 469 | ) |
657 : | monnier | 427 | |
658 : | monnier | 469 | (* First build the move priqueue *) |
659 : | monnier | 498 | val (mvs, mem) = |
660 : | if isOn(mode, DEAD_COPY_ELIM) then | ||
661 : | let val (mvs, mem, dead) = filter'(moves, MV.EMPTY, [], []) | ||
662 : | in deadCopies := dead; (mvs, mem) | ||
663 : | monnier | 469 | end |
664 : | monnier | 498 | else filter(moves, MV.EMPTY, []) |
665 : | monnier | 469 | |
666 : | leunga | 624 | in memMoves := mem; (* memory moves *) |
667 : | monnier | 498 | collect(Intmap.values nodes, [], FZ.EMPTY, mvs, [], 0, 0) |
668 : | monnier | 469 | end |
669 : | |||
670 : | (* | ||
671 : | * Return a regmap that reflects the current interference graph. | ||
672 : | * Spilled registers are given the special value ~1 | ||
673 : | *) | ||
674 : | fun regmap(G.GRAPH{nodes,...}) = | ||
675 : | let val getnode = Intmap.map nodes | ||
676 : | fun num(NODE{color=ref(COLORED r),...}) = r | ||
677 : | | num(NODE{color=ref(ALIASED n),...}) = num n | ||
678 : | monnier | 498 | | num(NODE{color=ref(SPILLED s),...}) = if s >= 0 then s else ~1 |
679 : | monnier | 469 | | num(NODE{number, color=ref PSEUDO,...}) = number |
680 : | | num _ = error "regmap" | ||
681 : | fun lookup r = num(getnode r) handle _ => r (* XXX *) | ||
682 : | in lookup | ||
683 : | end | ||
684 : | |||
685 : | (* | ||
686 : | * Return a regmap that reflects the current interference graph, | ||
687 : | * during spilling. | ||
688 : | *) | ||
689 : | fun spillRegmap(G.GRAPH{nodes,...}) = | ||
690 : | let val getnode = Intmap.map nodes | ||
691 : | fun num(NODE{color=ref(COLORED r),...}) = r | ||
692 : | | num(NODE{color=ref(ALIASED n),...}) = num n | ||
693 : | | num(NODE{color=ref(SPILLED _),number,...}) = number | ||
694 : | | num(NODE{number, color=ref PSEUDO,...}) = number | ||
695 : | | num _ = error "spillRegmap" | ||
696 : | fun lookup r = num(getnode r) handle _ => r (* XXX *) | ||
697 : | in lookup | ||
698 : | end | ||
699 : | |||
700 : | (* | ||
701 : | * Return a regmap that returns the current spill location | ||
702 : | * during spilling. | ||
703 : | *) | ||
704 : | fun spillLoc(G.GRAPH{nodes,...}) = | ||
705 : | let val getnode = Intmap.map nodes | ||
706 : | fun num(NODE{color=ref(ALIASED n), ...}) = num n | ||
707 : | | num(NODE{color=ref(SPILLED ~1), number, ...}) = number | ||
708 : | | num(NODE{color=ref(SPILLED c), ...}) = c | ||
709 : | | num(NODE{number, ...}) = number | ||
710 : | fun lookup r = num(getnode r) handle _ => r (* XXX *) | ||
711 : | in lookup | ||
712 : | end | ||
713 : | |||
714 : | (* | ||
715 : | * Core phases: | ||
716 : | * Simplify, coalesce, freeze. | ||
717 : | * | ||
718 : | * NOTE: When a node's color is REMOVED or ALIASED, | ||
719 : | * it is not considered to be part of the adjacency list | ||
720 : | * | ||
721 : | * 1. The move list has no duplicate | ||
722 : | * 2. The freeze list may have duplicates | ||
723 : | *) | ||
724 : | fun iteratedCoalescingPhases | ||
725 : | leunga | 579 | (G as GRAPH{K, bitMatrix, spillFlag, trail, stamp, mode, |
726 : | monnier | 498 | pseudoCount, blockedCount, ...}) = |
727 : | monnier | 469 | let val member = BM.member(!bitMatrix) |
728 : | monnier | 427 | val addEdge = addEdge G |
729 : | monnier | 469 | val show = show G |
730 : | leunga | 579 | val memoryCoalescingOn = isOn(mode, MEMORY_COALESCING) |
731 : | monnier | 427 | |
732 : | leunga | 579 | val blocked = blockedCount |
733 : | |||
734 : | monnier | 469 | (* |
735 : | * SIMPLIFY node: | ||
736 : | * precondition: node must be part of the interference graph (PSEUDO) | ||
737 : | *) | ||
738 : | monnier | 498 | fun simplify(node as NODE{color, number, adj, degree, (*pair,*)...}, |
739 : | mv, fz, stack) = | ||
740 : | monnier | 469 | let val _ = if debug then print("Simplifying "^show node^"\n") else () |
741 : | fun forallAdj([], mv, fz, stack) = (mv, fz, stack) | ||
742 : | monnier | 498 | | forallAdj((n as NODE{color=ref PSEUDO, degree as ref d,...})::adj, |
743 : | mv, fz, stack) = | ||
744 : | if d = K then | ||
745 : | let val (mv, fz, stack) = lowDegree(n, mv, fz, stack) | ||
746 : | in forallAdj(adj, mv, fz, stack) end | ||
747 : | else (degree := d - 1; forallAdj(adj, mv, fz, stack)) | ||
748 : | | forallAdj(_::adj, mv, fz, stack) = forallAdj(adj, mv, fz, stack) | ||
749 : | monnier | 469 | in color := REMOVED; |
750 : | monnier | 498 | pseudoCount := !pseudoCount - 1; |
751 : | monnier | 469 | forallAdj(!adj, mv, fz, node::stack) (* push onto stack *) |
752 : | end (* simplify *) | ||
753 : | |||
754 : | monnier | 498 | and simplifyAll([], mv, fz, stack) = (mv, fz, stack) |
755 : | | simplifyAll(node::simp, mv, fz, stack) = | ||
756 : | let val (mv, fz, stack) = simplify(node, mv, fz, stack) | ||
757 : | in simplifyAll(simp, mv, fz, stack) end | ||
758 : | |||
759 : | monnier | 469 | (* |
760 : | * Decrement the degree of a pseudo node. | ||
761 : | * precondition: node must be part of the interference graph | ||
762 : | * If the degree of the node is now K-1. | ||
763 : | * Then if (a) the node is move related, freeze it. | ||
764 : | * (b) the node is non-move related, simplify it | ||
765 : | * | ||
766 : | * node -- the node to decrement degree | ||
767 : | * mv -- queue of move candidates to be coalesced | ||
768 : | * fz -- queue of freeze candidates | ||
769 : | * stack -- stack of removed nodes | ||
770 : | *) | ||
771 : | monnier | 498 | and lowDegree(node as NODE{degree as ref d, movecnt, adj, color,...}, |
772 : | (* false, *) mv, fz, stack) = | ||
773 : | (* normal edge *) | ||
774 : | monnier | 469 | (if debug then |
775 : | print("DecDegree "^show node^" d="^Int.toString(d-1)^"\n") else (); | ||
776 : | monnier | 498 | degree := K - 1; |
777 : | (* node is now low degree!!! *) | ||
778 : | let val mv = enableMoves(!adj, mv) | ||
779 : | in if !movecnt > 0 then (* move related *) | ||
780 : | (blocked := !blocked + 1; (mv, FZ.add(node, fz), stack)) | ||
781 : | else (* non-move related, simplify now! *) | ||
782 : | simplify(node, mv, fz, stack) | ||
783 : | end | ||
784 : | monnier | 469 | ) |
785 : | (* | ||
786 : | | decDegree(node as NODE{degree as ref d, movecnt, adj, color,...}, | ||
787 : | true, mv, fz, stack) = (* register pair edge *) | ||
788 : | (degree := d - 2; | ||
789 : | if d >= K andalso !degree < K then | ||
790 : | (* node is now low degree!!! *) | ||
791 : | let val mv = enableMoves(node :: !adj, mv) | ||
792 : | in if !movecnt > 0 then (* move related *) | ||
793 : | monnier | 498 | (blocked := !blocked + 1; (mv, FZ.add(node, fz), stack)) |
794 : | monnier | 469 | else (* non-move related, simplify now! *) |
795 : | simplify(node, mv, fz, stack) | ||
796 : | end | ||
797 : | else | ||
798 : | (mv, fz, stack) | ||
799 : | ) | ||
800 : | *) | ||
801 : | |||
802 : | (* | ||
803 : | * Enable moves: | ||
804 : | * given: a list of nodes (some of which are not in the graph) | ||
805 : | * do: all moves associated with these nodes are inserted | ||
806 : | * into the move worklist | ||
807 : | *) | ||
808 : | and enableMoves([], mv) = mv | ||
809 : | | enableMoves(n::ns, mv) = | ||
810 : | let (* add valid moves onto the worklist. | ||
811 : | * there are no duplicates on the move worklist! | ||
812 : | monnier | 427 | *) |
813 : | monnier | 498 | fun addMv([], ns, mv) = enableMoves(ns, mv) |
814 : | | addMv((m as MV{status, hicount as ref hi, ...})::rest, | ||
815 : | ns, mv) = | ||
816 : | monnier | 469 | (case !status of |
817 : | monnier | 498 | (BRIGGS_MOVE | GEORGE_MOVE) => |
818 : | (* decrements hi, when hi <= 0 enable move *) | ||
819 : | if hi <= 1 then | ||
820 : | (status := WORKLIST; addMv(rest, ns, MV.add(m, mv))) | ||
821 : | else | ||
822 : | (hicount := hi-1; addMv(rest, ns, mv)) | ||
823 : | | _ => addMv(rest, ns, mv) | ||
824 : | monnier | 469 | ) |
825 : | in (* make sure the nodes are actually in the graph *) | ||
826 : | case n of | ||
827 : | NODE{movelist, color=ref PSEUDO, movecnt,...} => | ||
828 : | if !movecnt > 0 then (* is it move related? *) | ||
829 : | monnier | 498 | addMv(!movelist, ns, mv) |
830 : | monnier | 469 | else |
831 : | enableMoves(ns, mv) | ||
832 : | | _ => enableMoves(ns, mv) | ||
833 : | end (* enableMoves *) | ||
834 : | |||
835 : | (* | ||
836 : | * Brigg's conservative coalescing test: | ||
837 : | * given: an unconstrained move (x, y) | ||
838 : | * return: true or false | ||
839 : | *) | ||
840 : | monnier | 498 | fun conservative(hicount, |
841 : | x as NODE{degree=ref dx, adj=xadj, (* pair=px, *) ...}, | ||
842 : | monnier | 469 | y as NODE{degree=ref dy, adj=yadj, (* pair=py, *) ...}) = |
843 : | dx + dy < K orelse | ||
844 : | let (* | ||
845 : | monnier | 498 | * hi -- is the number of nodes with deg > K (without duplicates) |
846 : | * n -- the number of nodes that have deg = K but not neighbors | ||
847 : | * of both x and y | ||
848 : | monnier | 469 | * We use the movecnt as a flag indicating whether |
849 : | * a node has been visited. A negative count is used to mark | ||
850 : | * a visited node. | ||
851 : | monnier | 427 | *) |
852 : | monnier | 498 | fun undo([], extraHi) = |
853 : | extraHi <= 0 orelse (hicount := extraHi; false) | ||
854 : | | undo(movecnt::tr, extraHi) = | ||
855 : | (movecnt := ~1 - !movecnt; undo(tr, extraHi)) | ||
856 : | fun loop([], [], hi, n, tr) = undo(tr, (hi + n) - K + 1) | ||
857 : | | loop([], yadj, hi, n, tr) = loop(yadj, [], hi, n, tr) | ||
858 : | monnier | 469 | | loop(NODE{color, movecnt as ref m, degree=ref deg, ...}::vs, |
859 : | monnier | 498 | yadj, hi, n, tr) = |
860 : | (case !color of | ||
861 : | COLORED _ => | ||
862 : | if m < 0 then | ||
863 : | (* node has been visited before *) | ||
864 : | loop(vs, yadj, hi, n, tr) | ||
865 : | else | ||
866 : | (movecnt := ~1 - m; (* mark as visited *) | ||
867 : | loop(vs, yadj, hi+1, n, movecnt::tr)) | ||
868 : | | PSEUDO => | ||
869 : | if deg < K then loop(vs, yadj, hi, n, tr) | ||
870 : | else if m >= 0 then | ||
871 : | (* node has never been visited before *) | ||
872 : | (movecnt := ~1 - m; (* mark as visited *) | ||
873 : | if deg = K | ||
874 : | then loop(vs, yadj, hi, n+1, movecnt::tr) | ||
875 : | else loop(vs, yadj, hi+1, n, movecnt::tr) | ||
876 : | ) | ||
877 : | else | ||
878 : | (* node has been visited before *) | ||
879 : | if deg = K then loop(vs, yadj, hi, n-1, tr) | ||
880 : | else loop(vs, yadj, hi, n, tr) | ||
881 : | | _ => loop(vs, yadj, hi, n, tr) (* REMOVED/ALIASED *) | ||
882 : | ) | ||
883 : | in loop(!xadj, !yadj, 0, 0, []) end | ||
884 : | monnier | 469 | |
885 : | (* | ||
886 : | * Heuristic used to determine whether a pseudo and machine register | ||
887 : | * can be coalesced. | ||
888 : | * Precondition: | ||
889 : | * The two nodes are assumed not to interfere. | ||
890 : | *) | ||
891 : | monnier | 498 | fun safe(hicount, reg, NODE{adj, ...}) = |
892 : | let fun loop([], hi) = hi = 0 orelse (hicount := hi; false) | ||
893 : | | loop(n::adj, hi) = | ||
894 : | monnier | 469 | (case n of |
895 : | monnier | 498 | (* Note: Actively we only have to consider pseudo nodes and not |
896 : | * nodes that are removed, since removed nodes either have | ||
897 : | * deg < K or else optimistic spilling must be in effect! | ||
898 : | *) | ||
899 : | NODE{degree,number,color=ref(PSEUDO | REMOVED), ...} => | ||
900 : | if !degree < K orelse member(reg, number) then loop(adj, hi) | ||
901 : | else loop(adj, hi+1) | ||
902 : | | _ => loop(adj, hi) | ||
903 : | monnier | 469 | ) |
904 : | monnier | 498 | in loop(!adj, 0) end |
905 : | monnier | 469 | |
906 : | (* | ||
907 : | * Decrement the active move count of a node. | ||
908 : | * When the move count reaches 0 and the degree < K | ||
909 : | * simplify the node immediately. | ||
910 : | * Precondition: node must be a node in the interference graph | ||
911 : | * The node can become a non-move related node. | ||
912 : | *) | ||
913 : | fun decMoveCnt | ||
914 : | (node as NODE{movecnt, color=ref PSEUDO, degree, movecost,...}, | ||
915 : | cnt, cost, mv, fz, stack) = | ||
916 : | let val newCnt = !movecnt - cnt | ||
917 : | in movecnt := newCnt; | ||
918 : | movecost := !movecost - cost; | ||
919 : | if newCnt = 0 andalso !degree < K (* low degree and movecnt = 0 *) | ||
920 : | monnier | 498 | then (blocked := !blocked - 1; simplify(node, mv, fz, stack)) |
921 : | monnier | 469 | else (mv, fz, stack) |
922 : | end | ||
923 : | | decMoveCnt(_, _, _, mv, fz, stack) = (mv, fz, stack) | ||
924 : | |||
925 : | (* | ||
926 : | * Combine two nodes u and v into one. | ||
927 : | * v is replaced by u | ||
928 : | * u is the new combined node | ||
929 : | * Precondition: u <> v and u and v must be unconstrained | ||
930 : | * | ||
931 : | * u, v -- two nodes to be merged, must be distinct! | ||
932 : | monnier | 498 | * coloingv -- is u a colored node? |
933 : | monnier | 469 | * mvcost -- the cost of the move that has been eliminated |
934 : | * mv -- the queue of moves | ||
935 : | * fz -- the queue of freeze candidates | ||
936 : | * stack -- stack of removed nodes | ||
937 : | *) | ||
938 : | monnier | 498 | fun combine(u, v, coloringv, mvcost, mv, fz, stack) = |
939 : | monnier | 469 | let val NODE{color=vcol, pri=pv, movecnt=cntv, movelist=movev, adj=adjv, |
940 : | monnier | 498 | defs=defsv, uses=usesv, degree=degv, ...} = v |
941 : | monnier | 469 | val NODE{color=ucol, pri=pu, movecnt=cntu, movelist=moveu, adj=adju, |
942 : | monnier | 498 | defs=defsu, uses=usesu, degree=degu, ...} = u |
943 : | |||
944 : | monnier | 469 | (* merge movelists together, taking the opportunity |
945 : | * to prune the lists | ||
946 : | *) | ||
947 : | fun mergeMoveList([], mv) = mv | ||
948 : | leunga | 585 | | mergeMoveList((m as MV{status,hicount,src,dst,...})::rest, mv) = |
949 : | monnier | 469 | (case !status of |
950 : | monnier | 498 | BRIGGS_MOVE => |
951 : | (* if we are changing a copy from v <-> w to uv <-> w | ||
952 : | * makes sure we reset its trigger count, so that it | ||
953 : | * will be tested next. | ||
954 : | *) | ||
955 : | leunga | 585 | (if coloringv then |
956 : | (status := GEORGE_MOVE; | ||
957 : | hicount := 0; | ||
958 : | if debug then | ||
959 : | print ("New george "^show src^"<->"^show dst^"\n") | ||
960 : | else () | ||
961 : | ) | ||
962 : | monnier | 498 | else (); |
963 : | mergeMoveList(rest, m::mv) | ||
964 : | ) | ||
965 : | | GEORGE_MOVE => | ||
966 : | (* if u is colored and v is not, then the move v <-> w | ||
967 : | * becomes uv <-> w where w is colored. This can always | ||
968 : | * be discarded. | ||
969 : | *) | ||
970 : | (if coloringv then mergeMoveList(rest, mv) | ||
971 : | else mergeMoveList(rest, m::mv) | ||
972 : | ) | ||
973 : | | WORKLIST => mergeMoveList(rest, m::mv) | ||
974 : | monnier | 469 | | _ => mergeMoveList(rest, mv) |
975 : | ) | ||
976 : | |||
977 : | (* Form combined node; add the adjacency list of v to u *) | ||
978 : | fun union([], mv, fz, stack) = (mv, fz, stack) | ||
979 : | monnier | 498 | | union((t as NODE{color, (* pair=pt, *)degree, ...})::adj, |
980 : | mv, fz, stack) = | ||
981 : | monnier | 469 | (case !color of |
982 : | monnier | 498 | (COLORED _ | SPILLED _) => |
983 : | (addEdge(t, u); union(adj, mv, fz, stack)) | ||
984 : | monnier | 469 | | PSEUDO => |
985 : | (addEdge(t, u); | ||
986 : | monnier | 498 | let val d = !degree |
987 : | in if d = K then | ||
988 : | let val (mv, fz, stack) = lowDegree(t, mv, fz, stack) | ||
989 : | in union(adj, mv, fz, stack) end | ||
990 : | else (degree := d - 1; union(adj, mv, fz, stack)) | ||
991 : | end | ||
992 : | monnier | 469 | ) |
993 : | | _ => union(adj, mv, fz, stack) | ||
994 : | ) | ||
995 : | monnier | 498 | |
996 : | monnier | 469 | in vcol := ALIASED u; |
997 : | (* combine the priority of both: | ||
998 : | * note that since the mvcost has been counted twice | ||
999 : | * in the original priority, we substract it twice | ||
1000 : | * from the new priority. | ||
1001 : | *) | ||
1002 : | monnier | 498 | pu := !pu + !pv - mvcost - mvcost; |
1003 : | monnier | 469 | (* combine the def/use pts of both nodes. |
1004 : | * Strictly speaking, the def/use points of the move | ||
1005 : | * should also be removed. But since we never spill | ||
1006 : | * a coalesced node and only spilling makes use of these | ||
1007 : | monnier | 475 | * def/use points, we are safe for now. |
1008 : | * | ||
1009 : | * New comment: with spill propagation, it is necessary | ||
1010 : | * to keep track of the spilled program points. | ||
1011 : | monnier | 469 | *) |
1012 : | leunga | 579 | if memoryCoalescingOn then |
1013 : | (defsu := concat(!defsu, !defsv); | ||
1014 : | usesu := concat(!usesu, !usesv) | ||
1015 : | ) | ||
1016 : | else (); | ||
1017 : | monnier | 469 | case !ucol of |
1018 : | PSEUDO => | ||
1019 : | monnier | 498 | (if !cntv > 0 then |
1020 : | (if !cntu > 0 then blocked := !blocked - 1 else (); | ||
1021 : | moveu := mergeMoveList(!movev, !moveu) | ||
1022 : | ) | ||
1023 : | else (); | ||
1024 : | monnier | 469 | movev := []; (* XXX kill the list to free space *) |
1025 : | cntu := !cntu + !cntv | ||
1026 : | ) | ||
1027 : | | _ => () | ||
1028 : | ; | ||
1029 : | cntv := 0; | ||
1030 : | |||
1031 : | monnier | 498 | let val removingHi = !degv >= K andalso (!degu >= K orelse coloringv) |
1032 : | monnier | 469 | (* Update the move count of the combined node *) |
1033 : | monnier | 498 | val (mv, fz, stack) = union(!adjv, mv, fz, stack) |
1034 : | val (mv, fz, stack) = | ||
1035 : | decMoveCnt(u, 2, mvcost + mvcost, mv, fz, stack) | ||
1036 : | (* If either v or u are high degree then at least one high degree | ||
1037 : | * node is removed from the neighbors of uv after coalescing | ||
1038 : | *) | ||
1039 : | val mv = if removingHi then enableMoves(!adju, mv) else mv | ||
1040 : | in coalesce(mv, fz, stack) | ||
1041 : | monnier | 469 | end |
1042 : | end | ||
1043 : | |||
1044 : | (* | ||
1045 : | * COALESCE: | ||
1046 : | * Repeat coalescing and simplification until mv is empty. | ||
1047 : | *) | ||
1048 : | monnier | 498 | and coalesce(MV.EMPTY, fz, stack) = (fz, stack) |
1049 : | | coalesce(MV.TREE(MV{src, dst, status, hicount, cost, ...}, _, l, r), | ||
1050 : | fz, stack) = | ||
1051 : | let (* val _ = coalesce_count := !coalesce_count + 1 *) | ||
1052 : | val u = chase src | ||
1053 : | monnier | 469 | val v as NODE{color=ref vcol, ...} = chase dst |
1054 : | (* make u the colored one *) | ||
1055 : | val (u as NODE{number=u', color=ref ucol, ...}, | ||
1056 : | v as NODE{number=v', color=ref vcol, ...}) = | ||
1057 : | case vcol of | ||
1058 : | COLORED _ => (v, u) | ||
1059 : | | _ => (u, v) | ||
1060 : | val _ = if debug then print ("Coalescing "^show u^"<->"^show v | ||
1061 : | ^" ("^Int.toString cost^")") else () | ||
1062 : | val mv = MV.merge(l, r) | ||
1063 : | monnier | 498 | fun coalesceIt(status, v) = |
1064 : | (status := COALESCED; | ||
1065 : | if !spillFlag then trail := UNDO(v, status, !trail) else () | ||
1066 : | ) | ||
1067 : | monnier | 469 | in if u' = v' then (* trivial move *) |
1068 : | monnier | 498 | let val _ = if debug then print(" Trivial\n") else () |
1069 : | val _ = coalesceIt(status, v) | ||
1070 : | in coalesce(decMoveCnt(u, 2, cost+cost, mv, fz, stack)) | ||
1071 : | end | ||
1072 : | monnier | 469 | else |
1073 : | (case vcol of | ||
1074 : | COLORED _ => | ||
1075 : | (* two colored nodes cannot be coalesced *) | ||
1076 : | monnier | 498 | (status := CONSTRAINED; |
1077 : | if debug then print(" Both Colored\n") else (); | ||
1078 : | coalesce(mv, fz, stack)) | ||
1079 : | monnier | 469 | | _ => |
1080 : | monnier | 498 | if member(u', v') then |
1081 : | monnier | 469 | (* u and v interfere *) |
1082 : | monnier | 498 | let val _ = status := CONSTRAINED |
1083 : | val _ = if debug then print(" Interfere\n") else (); | ||
1084 : | val (mv, fz, stack) = | ||
1085 : | decMoveCnt(u, 1, cost, mv, fz, stack) | ||
1086 : | in coalesce(decMoveCnt(v, 1, cost, mv, fz, stack)) end | ||
1087 : | monnier | 469 | else |
1088 : | case ucol of | ||
1089 : | COLORED _ => (* u is colored, v is not *) | ||
1090 : | monnier | 498 | if safe(hicount, u', v) then |
1091 : | (if debug then print(" Safe\n") else (); | ||
1092 : | (*if tally then good_george := !good_george+1 else ();*) | ||
1093 : | coalesceIt(status, v); | ||
1094 : | combine(u, v, true, cost, mv, fz, stack) | ||
1095 : | ) | ||
1096 : | monnier | 469 | else |
1097 : | monnier | 498 | ((* remove it from the move list *) |
1098 : | status := GEORGE_MOVE; | ||
1099 : | (*if tally then bad_george := !bad_george + 1 else ();*) | ||
1100 : | monnier | 469 | if debug then print(" Unsafe\n") else (); |
1101 : | monnier | 498 | coalesce(mv, fz, stack) |
1102 : | monnier | 469 | ) |
1103 : | | _ => (* u, v are not colored *) | ||
1104 : | monnier | 498 | if conservative(hicount, u, v) then |
1105 : | (if debug then print(" OK\n") else (); | ||
1106 : | (*if tally then good_briggs := !good_briggs+1 else ();*) | ||
1107 : | coalesceIt(status, v); | ||
1108 : | combine(u, v, false, cost, mv, fz, stack) | ||
1109 : | ) | ||
1110 : | monnier | 469 | else (* conservative test failed *) |
1111 : | monnier | 498 | ((* remove it from the move list *) |
1112 : | status := BRIGGS_MOVE; | ||
1113 : | (*if tally then bad_briggs := !bad_briggs + 1 else ();*) | ||
1114 : | monnier | 469 | if debug then print(" Non-conservative\n") else (); |
1115 : | monnier | 498 | coalesce(mv, fz, stack) |
1116 : | monnier | 469 | ) |
1117 : | ) | ||
1118 : | end | ||
1119 : | |||
1120 : | (* mark a node n as frozen: | ||
1121 : | * Go thru all the moves (n, m), decrement the move count of m | ||
1122 : | * precondition: degree must be < K | ||
1123 : | * movecnt must be > 0 | ||
1124 : | * node -- the node to be frozen | ||
1125 : | * fz -- a queue of freeze candidates | ||
1126 : | * stack -- stack of removed nodes | ||
1127 : | *) | ||
1128 : | monnier | 498 | fun markAsFrozen( |
1129 : | node as NODE{number=me, degree, | ||
1130 : | adj, movelist, movecnt as ref mc,...}, | ||
1131 : | fz, stack) = | ||
1132 : | monnier | 469 | let val _ = if debug then print("Mark as frozen "^Int.toString me^"\n") |
1133 : | else () | ||
1134 : | (* eliminate all moves, return a list of nodes that | ||
1135 : | * can be simplified | ||
1136 : | *) | ||
1137 : | fun elimMoves([], simp) = simp | ||
1138 : | | elimMoves(MV{status, src, dst, ...}::mvs, simp) = | ||
1139 : | case !status of | ||
1140 : | WORKLIST => error "elimMoves" | ||
1141 : | monnier | 498 | | (BRIGGS_MOVE | GEORGE_MOVE) => (* mark move as lost *) |
1142 : | monnier | 469 | let val _ = status := LOST |
1143 : | val src as NODE{number=s,...} = chase src | ||
1144 : | monnier | 498 | val you = if s = me then chase dst else src |
1145 : | monnier | 469 | in case you of |
1146 : | NODE{color=ref(COLORED _),...} => | ||
1147 : | elimMoves(mvs, simp) | ||
1148 : | | NODE{movecnt as ref c, degree, ...} => (* pseudo *) | ||
1149 : | (movecnt := c - 1; | ||
1150 : | if c = 1 andalso !degree < K then | ||
1151 : | leunga | 579 | (blocked := !blocked - 1; |
1152 : | elimMoves(mvs, you::simp)) | ||
1153 : | monnier | 469 | else |
1154 : | elimMoves(mvs, simp) | ||
1155 : | ) | ||
1156 : | end | ||
1157 : | | _ => elimMoves(mvs, simp) | ||
1158 : | |||
1159 : | monnier | 498 | (* Note: |
1160 : | * We are removing a high degree node, so try to enable all moves | ||
1161 : | * associated with its neighbors. | ||
1162 : | *) | ||
1163 : | |||
1164 : | val mv = if !degree >= K then enableMoves(!adj, MV.EMPTY) | ||
1165 : | else MV.EMPTY | ||
1166 : | |||
1167 : | in if mc = 0 | ||
1168 : | then simplify(node, mv, fz, stack) | ||
1169 : | else | ||
1170 : | (movecnt := 0; | ||
1171 : | simplifyAll(node::elimMoves(!movelist, []), mv, fz, stack) | ||
1172 : | ) | ||
1173 : | monnier | 427 | end |
1174 : | |||
1175 : | monnier | 469 | (* |
1176 : | * FREEZE: | ||
1177 : | * Repeat picking | ||
1178 : | * a node with degree < K from the freeze list and freeze it. | ||
1179 : | * fz -- queue of freezable nodes | ||
1180 : | * stack -- stack of removed nodes | ||
1181 : | * undo -- trail of coalesced moves after potential spill | ||
1182 : | monnier | 427 | *) |
1183 : | monnier | 498 | fun freeze(fz, stack) = |
1184 : | let fun loop(FZ.EMPTY, FZ.EMPTY, stack) = stack | ||
1185 : | | loop(FZ.EMPTY, newFz, _) = error "no freeze candidate" | ||
1186 : | | loop(FZ.TREE(node, _, l, r), newFz, stack) = | ||
1187 : | monnier | 469 | let val fz = FZ.merge(l, r) |
1188 : | in case node of | ||
1189 : | (* This node has not been simplified | ||
1190 : | * This must be a move-related node. | ||
1191 : | *) | ||
1192 : | monnier | 498 | NODE{color=ref PSEUDO, degree, ...} => |
1193 : | if !degree >= K (* can't be frozen yet? *) | ||
1194 : | then | ||
1195 : | ((*if tally then bad_freeze := !bad_freeze+1 else ();*) | ||
1196 : | leunga | 648 | loop(fz, FZ.add(node,newFz), stack)) |
1197 : | monnier | 469 | else (* freeze node *) |
1198 : | monnier | 498 | let val _ = |
1199 : | if debug then print("Freezing "^show node^"\n") | ||
1200 : | else () | ||
1201 : | (*val _ = | ||
1202 : | if tally then good_freeze := !good_freeze + 1 | ||
1203 : | else ()*) | ||
1204 : | leunga | 579 | val _ = blocked := !blocked - 1; |
1205 : | monnier | 469 | val (mv, fz, stack) = markAsFrozen(node, fz, stack) |
1206 : | monnier | 498 | val (fz, stack) = coalesce(mv, fz, stack) |
1207 : | in if !blocked = 0 | ||
1208 : | then ((* print "[no freezing again]"; *) stack) | ||
1209 : | else ((* print("[freezing again "^ | ||
1210 : | Int.toString(!blocked)^"]"); *) | ||
1211 : | loop(FZ.merge(fz, newFz), FZ.EMPTY, stack)) | ||
1212 : | monnier | 469 | end |
1213 : | monnier | 498 | | _ => |
1214 : | ((*if tally then bad_freeze := !bad_freeze + 1 else ();*) | ||
1215 : | loop(fz, newFz, stack)) | ||
1216 : | monnier | 469 | end |
1217 : | monnier | 498 | in if !blocked = 0 then ((* print "[no freezing]"; *) stack) |
1218 : | else ((* print("[freezing "^Int.toString(!blocked)^"]"); *) | ||
1219 : | loop(fz, FZ.EMPTY, stack)) | ||
1220 : | monnier | 427 | end |
1221 : | monnier | 469 | |
1222 : | monnier | 498 | (* |
1223 : | * Sort simplify worklist in increasing degree. | ||
1224 : | * Matula and Beck suggests that we should always remove the | ||
1225 : | * node with the lowest degree first. This is an approximation of | ||
1226 : | * the idea. | ||
1227 : | *) | ||
1228 : | monnier | 469 | (* |
1229 : | monnier | 498 | val buckets = A.array(K, []) : G.node list A.array |
1230 : | fun sortByDegree nodes = | ||
1231 : | let fun insert [] = () | ||
1232 : | | insert((n as NODE{degree=ref deg, ...})::rest) = | ||
1233 : | (UA.update(buckets, deg, n::UA.sub(buckets, deg)); insert rest) | ||
1234 : | fun collect(~1, L) = L | ||
1235 : | | collect(deg, L) = collect(deg-1, concat(UA.sub(buckets, deg), L)) | ||
1236 : | in insert nodes; | ||
1237 : | collect(K-1, []) | ||
1238 : | end | ||
1239 : | *) | ||
1240 : | |||
1241 : | (* | ||
1242 : | monnier | 469 | * Iterate over simplify, coalesce, freeze |
1243 : | *) | ||
1244 : | fun iterate{simplifyWkl, moveWkl, freezeWkl, stack} = | ||
1245 : | let (* simplify everything *) | ||
1246 : | monnier | 498 | val (mv, fz, stack) = |
1247 : | simplifyAll((* sortByDegree *) simplifyWkl, | ||
1248 : | moveWkl, freezeWkl, stack) | ||
1249 : | val (fz, stack) = coalesce(mv, fz, stack) | ||
1250 : | val stack = freeze(fz, stack) | ||
1251 : | in {stack=stack} | ||
1252 : | monnier | 469 | end |
1253 : | in {markAsFrozen=markAsFrozen, iterate=iterate} | ||
1254 : | monnier | 427 | end |
1255 : | |||
1256 : | monnier | 469 | (* |
1257 : | * The main entry point for the iterated coalescing algorithm | ||
1258 : | *) | ||
1259 : | fun iteratedCoalescing G = | ||
1260 : | let val {iterate,...} = iteratedCoalescingPhases G | ||
1261 : | in iterate end | ||
1262 : | monnier | 427 | |
1263 : | monnier | 469 | |
1264 : | (* | ||
1265 : | * Potential Spill: | ||
1266 : | * Find some node on the spill list and just optimistically | ||
1267 : | * remove it from the graph. | ||
1268 : | *) | ||
1269 : | fun potentialSpillNode (G as G.GRAPH{spillFlag,...}) = | ||
1270 : | let val {markAsFrozen,...} = iteratedCoalescingPhases G | ||
1271 : | george | 545 | val spilled = SPILLED ~1 |
1272 : | in fn {node, cost, stack} => | ||
1273 : | monnier | 469 | let val _ = spillFlag := true (* potential spill found *) |
1274 : | monnier | 498 | val (mv, fz, stack) = markAsFrozen(node, FZ.EMPTY, stack) |
1275 : | george | 545 | in if cost < 0.0 then |
1276 : | let val NODE{color, ...} = node in color := spilled end | ||
1277 : | else (); | ||
1278 : | {moveWkl=mv, freezeWkl=fz, stack=stack} | ||
1279 : | monnier | 469 | end |
1280 : | end | ||
1281 : | |||
1282 : | |||
1283 : | |||
1284 : | (* | ||
1285 : | * SELECT: | ||
1286 : | * Using optimistic spilling | ||
1287 : | *) | ||
1288 : | fun select(G as GRAPH{getreg, getpair, trail, firstPseudoR, stamp, | ||
1289 : | monnier | 498 | spillFlag, proh, mode, ...}) {stack} = |
1290 : | monnier | 469 | let fun undoCoalesced END = () |
1291 : | | undoCoalesced(UNDO(NODE{number, color, ...}, status, trail)) = | ||
1292 : | monnier | 498 | (status := BRIGGS_MOVE; |
1293 : | monnier | 469 | if number < firstPseudoR then () else color := PSEUDO; |
1294 : | undoCoalesced trail | ||
1295 : | ) | ||
1296 : | val show = show G | ||
1297 : | |||
1298 : | (* Fast coloring, assume no spilling can occur *) | ||
1299 : | fun fastcoloring([], stamp) = ([], stamp) | ||
1300 : | | fastcoloring((node as NODE{color, (* pair, *) adj, ...})::stack, | ||
1301 : | stamp) = | ||
1302 : | let (* set up the proh array *) | ||
1303 : | monnier | 427 | fun neighbors [] = () |
1304 : | monnier | 469 | | neighbors(r::rs) = |
1305 : | let fun mark(NODE{color=ref(COLORED c), ...}) = | ||
1306 : | (UA.update(proh, c, stamp); neighbors rs) | ||
1307 : | | mark(NODE{color=ref(ALIASED n), ...}) = mark n | ||
1308 : | | mark _ = neighbors rs | ||
1309 : | in mark r end | ||
1310 : | monnier | 427 | val _ = neighbors(!adj) |
1311 : | monnier | 469 | in color := COLORED(getreg{pref=[], proh=proh, stamp=stamp}); |
1312 : | fastcoloring(stack, stamp+1) | ||
1313 : | end | ||
1314 : | |||
1315 : | (* Briggs' optimistic spilling heuristic *) | ||
1316 : | fun optimistic([], spills, stamp) = (spills, stamp) | ||
1317 : | george | 545 | | optimistic((node as NODE{color=ref(SPILLED _), ...})::stack, |
1318 : | spills, stamp) = | ||
1319 : | optimistic(stack, node::spills, stamp) | ||
1320 : | monnier | 469 | | optimistic((node as NODE{color, (* pair, *) adj, ...})::stack, |
1321 : | spills, stamp) = | ||
1322 : | let (* set up the proh array *) | ||
1323 : | fun neighbors [] = () | ||
1324 : | | neighbors(r::rs) = | ||
1325 : | let fun mark(NODE{color=ref(COLORED c), ...}) = | ||
1326 : | (UA.update(proh, c, stamp); neighbors rs) | ||
1327 : | | mark(NODE{color=ref(ALIASED n), ...}) = mark n | ||
1328 : | | mark _ = neighbors rs | ||
1329 : | in mark r end | ||
1330 : | val _ = neighbors(!adj) | ||
1331 : | monnier | 427 | val spills = |
1332 : | monnier | 469 | let val col = getreg{pref=[], proh=proh, stamp=stamp} |
1333 : | in color := COLORED col; spills | ||
1334 : | monnier | 427 | end handle _ => node::spills |
1335 : | monnier | 469 | in optimistic(stack, spills, stamp+1) end |
1336 : | |||
1337 : | (* Briggs' optimistic spilling heuristic, with biased coloring *) | ||
1338 : | fun biasedColoring([], spills, stamp) = (spills, stamp) | ||
1339 : | george | 545 | | biasedColoring((node as NODE{color=ref(SPILLED _), ...})::stack, |
1340 : | spills, stamp) = | ||
1341 : | biasedColoring(stack, node::spills, stamp) | ||
1342 : | monnier | 469 | | biasedColoring( |
1343 : | (node as NODE{number, color, adj, | ||
1344 : | (* pair, *) movecnt, movelist,...})::stack, | ||
1345 : | spills, stamp) = | ||
1346 : | let (* set up the proh array *) | ||
1347 : | fun neighbors [] = () | ||
1348 : | | neighbors(r::rs) = | ||
1349 : | (case chase r of | ||
1350 : | NODE{color=ref(COLORED c), ...} => | ||
1351 : | (UA.update(proh, c, stamp); neighbors rs) | ||
1352 : | | _ => neighbors rs | ||
1353 : | ) | ||
1354 : | (* | ||
1355 : | * Look at lost moves and see if it is possible to | ||
1356 : | * color the move with the same color | ||
1357 : | *) | ||
1358 : | fun getPref([], pref) = pref | ||
1359 : | monnier | 498 | | getPref(MV{status=ref(LOST | BRIGGS_MOVE | GEORGE_MOVE), |
1360 : | src, dst, ...}::mvs, pref) = | ||
1361 : | monnier | 469 | let val src as NODE{number=s,...} = chase src |
1362 : | monnier | 498 | val other = if s = number then chase dst else src |
1363 : | monnier | 469 | in case other of |
1364 : | NODE{color=ref(COLORED c),...} => getPref(mvs, c::pref) | ||
1365 : | | _ => getPref(mvs, pref) | ||
1366 : | end | ||
1367 : | | getPref(_::mvs, pref) = getPref(mvs, pref) | ||
1368 : | |||
1369 : | val _ = neighbors(!adj) | ||
1370 : | val pref = getPref(!movelist,[]) | ||
1371 : | val spills = | ||
1372 : | let val col = getreg{pref=[], proh=proh, stamp=stamp} | ||
1373 : | in color := COLORED col; spills | ||
1374 : | end handle _ => node::spills | ||
1375 : | in biasedColoring(stack, spills, stamp+1) end | ||
1376 : | monnier | 498 | val (spills, st) = if isOn(mode, BIASED_SELECTION) |
1377 : | monnier | 469 | then biasedColoring(stack, [], !stamp) |
1378 : | else if !spillFlag then | ||
1379 : | optimistic(stack, [], !stamp) | ||
1380 : | else | ||
1381 : | fastcoloring(stack, !stamp) | ||
1382 : | in stamp := st; | ||
1383 : | case spills of | ||
1384 : | [] => {spills=[]} | ||
1385 : | | spills => | ||
1386 : | leunga | 579 | let fun undo [] = () |
1387 : | | undo(NODE{color,...}::nodes) = (color := PSEUDO; undo nodes) | ||
1388 : | in undo stack; | ||
1389 : | undoCoalesced (!trail); | ||
1390 : | trail := END; | ||
1391 : | {spills=spills} | ||
1392 : | end | ||
1393 : | monnier | 469 | end |
1394 : | |||
1395 : | (* | ||
1396 : | monnier | 498 | * Incorporate memory<->register moves into the interference graph |
1397 : | *) | ||
1398 : | fun initMemMoves(GRAPH{memMoves, ...}) = | ||
1399 : | let fun move(NODE{movelist, movecost, ...}, mv, cost) = | ||
1400 : | (movelist := mv :: !movelist; | ||
1401 : | movecost := cost + !movecost | ||
1402 : | ) | ||
1403 : | |||
1404 : | fun setMove(dst, src, mv, cost) = | ||
1405 : | (move(dst, mv, cost); move(src, mv, cost)) | ||
1406 : | |||
1407 : | fun init [] = () | ||
1408 : | | init((mv as MV{dst, src, cost, ...})::mvs) = | ||
1409 : | let val dst as NODE{color=dstCol, ...} = chase dst | ||
1410 : | val src as NODE{color=srcCol, ...} = chase src | ||
1411 : | in case (!dstCol, !srcCol) of | ||
1412 : | (SPILLED x, SPILLED y) => setMove(dst, src, mv, cost) | ||
1413 : | | (SPILLED _, PSEUDO) => setMove(dst, src, mv, cost) | ||
1414 : | | (PSEUDO, SPILLED _) => setMove(dst, src, mv, cost) | ||
1415 : | | (SPILLED _, COLORED _) => () (* skip *) | ||
1416 : | | (COLORED _, SPILLED _) => () (* skip *) | ||
1417 : | | _ => error "initMemMoves" ; | ||
1418 : | init mvs | ||
1419 : | end | ||
1420 : | val moves = !memMoves | ||
1421 : | in memMoves := []; | ||
1422 : | init moves | ||
1423 : | end | ||
1424 : | |||
1425 : | george | 545 | |
1426 : | monnier | 498 | (* |
1427 : | george | 545 | * Compute savings due to memory<->register moves |
1428 : | *) | ||
1429 : | fun moveSavings(GRAPH{memMoves=ref [], ...}) = (fn node => 0) | ||
1430 : | | moveSavings(GRAPH{memMoves, bitMatrix, ...}) = | ||
1431 : | let exception Savings | ||
1432 : | val savingsMap = Intmap.new(32, Savings) | ||
1433 : | : {pinned:int,cost:int} Intmap.intmap | ||
1434 : | val savings = Intmap.mapWithDefault(savingsMap, {pinned= ~1, cost=0}) | ||
1435 : | val addSavings = Intmap.add savingsMap | ||
1436 : | val member = BM.member(!bitMatrix) | ||
1437 : | fun incSavings(u, v, c) = | ||
1438 : | let val {pinned, cost} = savings u | ||
1439 : | in if pinned <> ~1 andalso v <> pinned orelse member(u, v) | ||
1440 : | then () | ||
1441 : | else addSavings(u, {pinned=v, cost=cost + c + c}) | ||
1442 : | end | ||
1443 : | leunga | 579 | fun computeSavings [] = () |
1444 : | | computeSavings(MV{dst, src, cost, ...}::mvs) = | ||
1445 : | let val src as NODE{number=u, color=cu, ...} = chase src | ||
1446 : | val dst as NODE{number=v, color=cv, ...} = chase dst | ||
1447 : | in case (!cu, !cv) of | ||
1448 : | (SPILLED _, PSEUDO) => incSavings(v, u, cost) | ||
1449 : | | (PSEUDO, SPILLED _) => incSavings(u, v, cost) | ||
1450 : | | _ => (); | ||
1451 : | computeSavings mvs | ||
1452 : | end | ||
1453 : | in computeSavings (!memMoves); | ||
1454 : | george | 545 | fn node => #cost(savings node) |
1455 : | end | ||
1456 : | |||
1457 : | (* | ||
1458 : | monnier | 469 | * Update the regmap, after finishing register allocation. |
1459 : | * All nodes must have been colored. | ||
1460 : | *) | ||
1461 : | fun finishRA(GRAPH{regmap, nodes, deadCopies, ...}) = | ||
1462 : | let val enter = Intmap.add regmap | ||
1463 : | fun set(r, NODE{color=ref(COLORED c),...}) = enter(r, c) | ||
1464 : | | set(r, NODE{color=ref(ALIASED n),...}) = set(r, n) | ||
1465 : | monnier | 498 | | set(r, NODE{color=ref(SPILLED s),...}) = |
1466 : | enter(r,if s >= 0 then s else ~1) (* XXX *) | ||
1467 : | | set(r, _) = error("finishRA "^Int.toString r) | ||
1468 : | monnier | 469 | in Intmap.app set nodes; |
1469 : | case !deadCopies of | ||
1470 : | [] => () | ||
1471 : | | dead => app (fn r => enter(r, ~1)) dead | ||
1472 : | end | ||
1473 : | monnier | 427 | |
1474 : | monnier | 469 | (* |
1475 : | * Update the regmap, after copy propagation | ||
1476 : | *) | ||
1477 : | fun finishCP(GRAPH{regmap, nodes,...}) = | ||
1478 : | let val enter = Intmap.add regmap | ||
1479 : | in Intmap.app | ||
1480 : | (fn (r, node as NODE{color as ref(ALIASED _),...}) => | ||
1481 : | (case chase node of | ||
1482 : | NODE{color=ref(COLORED c),...} => enter(r, c) | ||
1483 : | | NODE{color=ref PSEUDO, number,...} => enter(r, number) | ||
1484 : | | NODE{color=ref REMOVED, number,...} => enter(r, number) | ||
1485 : | | _ => error "finishCP" | ||
1486 : | ) | ||
1487 : | | _ => () | ||
1488 : | ) nodes | ||
1489 : | end | ||
1490 : | |||
1491 : | (* | ||
1492 : | * Clear the interference graph, but keep the nodes | ||
1493 : | *) | ||
1494 : | monnier | 498 | fun clearGraph(GRAPH{bitMatrix, maxRegs, trail, spillFlag, |
1495 : | george | 545 | deadCopies, memMoves, copyTmps, ...}) = |
1496 : | monnier | 469 | let val edges = BM.edges(!bitMatrix) |
1497 : | in trail := END; | ||
1498 : | spillFlag := false; | ||
1499 : | deadCopies := []; | ||
1500 : | monnier | 498 | memMoves := []; |
1501 : | george | 545 | copyTmps := []; |
1502 : | bitMatrix := BM.empty; | ||
1503 : | monnier | 469 | bitMatrix := G.newBitMatrix{edges=edges, maxRegs=maxRegs()} |
1504 : | end | ||
1505 : | |||
1506 : | fun clearNodes(GRAPH{nodes,...}) = | ||
1507 : | let fun init(_, NODE{pri, degree, adj, movecnt, movelist, | ||
1508 : | movecost, defs, uses, ...}) = | ||
1509 : | (pri := 0; degree := 0; adj := []; movecnt := 0; movelist := []; | ||
1510 : | defs := []; uses := []; movecost := 0) | ||
1511 : | in Intmap.app init nodes | ||
1512 : | end | ||
1513 : | |||
1514 : | monnier | 498 | end (* local *) |
1515 : | |||
1516 : | monnier | 469 | end |
root@smlnj-gforge.cs.uchicago.edu | ViewVC Help |
Powered by ViewVC 1.0.0 |