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/releases/release-110.79/ra/ra-core.sml
ViewVC logotype

Annotation of /MLRISC/releases/release-110.79/ra/ra-core.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 744 - (view) (download)
Original Path: sml/trunk/src/MLRISC/ra/ra-core.sml

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

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