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 /sml/trunk/src/MLRISC/ra/cluster-ra.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/ra/cluster-ra.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 545 - (view) (download)

1 : monnier 467 (*
2 :     * This module provides services for the new RA when using the cluster
3 :     * representation.
4 : monnier 475 * The algorithm is adapted from
5 :     * Algorithm 19.17 from Appel, Modern Compiler Implementation in ML,
6 :     * Calculation of live ranges in SSA form. We don't directly use SSA
7 :     * here but the principles are the same.
8 : monnier 467 *
9 :     * -- Allen
10 :     *)
11 :    
12 :     functor ClusterRA
13 :     (structure Flowgraph : FLOWGRAPH
14 :     structure Asm : INSTRUCTION_EMITTER
15 :     structure InsnProps : INSN_PROPERTIES
16 : monnier 498 sharing Flowgraph.I = InsnProps.I = Asm.I
17 : monnier 467 sharing Asm.P = Flowgraph.P
18 :     ) : RA_FLOWGRAPH =
19 :     struct
20 :     structure F = Flowgraph
21 :     structure I = F.I
22 :     structure W = F.W
23 :     structure C = I.C
24 :     structure G = RAGraph
25 :     structure Props = InsnProps
26 :     structure Core = RACore
27 :     structure A = Array
28 :     structure UA = Unsafe.Array (* okay, I'm cheating a bit here *)
29 : monnier 498 structure Spill = RASpill(structure InsnProps = InsnProps
30 :     structure Asm = Asm
31 :     )
32 : monnier 467
33 : george 545 structure PrintCluster = PrintCluster
34 : monnier 467 (structure Flowgraph = F
35 :     structure Asm = Asm
36 :     )
37 :    
38 :     open G
39 :    
40 : monnier 498 fun isOn(flag,mask) = Word.andb(flag,mask) <> 0w0
41 :    
42 : monnier 467 type flowgraph = F.cluster (* flowgraph is a cluster *)
43 :    
44 :     fun error msg = MLRiscErrorMsg.error("ClusterRA", msg)
45 : monnier 498
46 :     val mode = 0w0
47 : monnier 467
48 : monnier 498 (*
49 :     local
50 :     val redundant_spills_on = MLRiscControl.getFlag "count-redundant-spills"
51 :     val red_reloads = MLRiscControl.getCounter "redundant-reloads"
52 :     in fun countSpillsReloads nodesToSpill =
53 :     if !redundant_spills_on then
54 :     app (fn G.NODE{color=ref(G.ALIASED _), ...} => ()
55 :     | G.NODE{number, defs=ref defs, uses=ref uses, pri, ...} =>
56 :     let datatype defUse = DEF | USE
57 :     val defsUses =
58 :     ListMergeSort.sort (fn ((a,_), (b,_)) => a < b)
59 :     (map (fn pt => (pt,DEF)) defs @
60 :     map (fn pt => (pt,USE)) uses)
61 :     fun scan((a,b)::(rest as (c,d)::_)) =
62 :     (if (a=c+1 orelse a=c+2)
63 :     andalso blockNum a = blockNum c then
64 :     (case (b,d) of
65 :     (DEF, USE) => red_reloads := !red_reloads + 1
66 :     | (USE, USE) => red_reloads := !red_reloads + 1
67 :     | _ => ()
68 :     )
69 :     else ();
70 :     scan rest
71 :     )
72 :     | scan _ = ()
73 :     in scan defsUses
74 :     end
75 :     ) nodesToSpill
76 :     else ()
77 :     end
78 :     *)
79 :    
80 : monnier 467 fun regmap(F.CLUSTER{regmap, ...}) = regmap
81 :    
82 :     fun dumpFlowgraph(msg, cluster, stream) =
83 :     PrintCluster.printCluster stream
84 :     ("------------------ "^msg^" ------------------") cluster
85 :    
86 :     exception NotThere
87 :    
88 : monnier 498 (*
89 : monnier 467 val Asm.S.STREAM{emit, ...} = Asm.makeStream []
90 : monnier 498 *)
91 : monnier 467
92 :     val dummyLabel = F.LABEL(Label.Label{id= ~1, addr=ref ~1, name=""})
93 :    
94 : monnier 498 fun x + y = Word.toIntX(Word.+(Word.fromInt x, Word.fromInt y))
95 : monnier 467
96 :     fun length l =
97 :     let fun loop([],n) = n
98 : monnier 498 | loop(_::l,n) = loop(l,n+1)
99 : monnier 467 in loop(l,0) end
100 :    
101 :     fun services(cluster as F.CLUSTER{regmap, blocks, blkCounter, ...}) =
102 :     let (* Create a graph based view of cluster *)
103 :     val N = !blkCounter
104 :    
105 : monnier 498 fun computeShift(0w0, max) = 0w31-max
106 :     | computeShift(N, max) = computeShift(Word.>>(N, 0w1), Word.+(max,0w1))
107 :     val shift = computeShift(Word.>>(Word.fromInt N, 0w15), 0w15)
108 :     val mask = Word.<<(0w1, shift) - 0w1
109 :    
110 :     (*
111 :     * Construct program point
112 :     *)
113 :     fun progPt(blknum, instrId) =
114 :     Word.toIntX(Word.+(Word.<<(Word.fromInt blknum, shift),
115 :     Word.fromInt instrId))
116 :     fun blockNum pt = Word.toIntX(Word.>>(Word.fromInt pt, shift))
117 :     fun instrNum pt = Word.toIntX(Word.andb(Word.fromInt pt, mask))
118 :    
119 : george 545 (* blocks indexed by block id *)
120 : monnier 467 val blockTable = A.array(N, dummyLabel)
121 :    
122 : george 545 fun fillBlockTable [] = ()
123 :     | fillBlockTable((b as F.BBLOCK{blknum, ...})::blocks) =
124 :     (UA.update(blockTable, blknum, b); fillBlockTable blocks)
125 :     | fillBlockTable(_::blocks) = fillBlockTable blocks
126 :     val _ = fillBlockTable blocks
127 : monnier 467
128 :     (*
129 : george 545 * Building the interference graph
130 :     *)
131 :     fun buildIt (cellkind, regmap,
132 :     G as GRAPH{nodes, dedicated, mode, span, copyTmps, ...}) =
133 : monnier 467
134 : george 545 let (* definitions indexed by block id+instruction id *)
135 :     val defsTable = A.array(N, A.array(0, [] : node list))
136 :     val marked = A.array(N, ~1)
137 :    
138 :     val stamp = ref 0
139 :    
140 :     (* Allocate the arrays *)
141 :     fun alloc [] = ()
142 :     | alloc((b as F.BBLOCK{blknum, insns, ...})::blocks) =
143 :     let val n = length(!insns)
144 :     val m = n+1
145 :     in UA.update(defsTable, blknum, A.array(m, []));
146 :     alloc blocks
147 :     end
148 :     | alloc(_::blocks) = alloc blocks
149 :     val _ = alloc blocks
150 :    
151 :     (*
152 :     * Remove pseudo use generated by copy temporaries
153 :     *)
154 :     fun rmPseudoUses [] = ()
155 :     | rmPseudoUses(NODE{uses,...}::ns) = (uses := []; rmPseudoUses ns)
156 :    
157 :     (*
158 :     * Mark the use site as definitions so that the traversal would
159 :     * end properly.
160 :     *)
161 :     fun markUseSites(v,[]) = ()
162 :     | markUseSites(v,u::uses) =
163 : monnier 498 let val b = blockNum u
164 :     val i = instrNum u
165 :     val defs = UA.sub(defsTable, b)
166 : george 545 in UA.update(defs, i, v::UA.sub(defs, i));
167 :     markUseSites(v, uses)
168 : monnier 498 end
169 : george 545
170 :     (*
171 :     * Unmark fake def sites
172 :     *)
173 :     fun unmarkUseSites [] = ()
174 :     | unmarkUseSites(u::uses) =
175 : monnier 498 let val b = blockNum u
176 :     val i = instrNum u
177 :     val defs = UA.sub(defsTable, b)
178 :     val _::instrs = UA.sub(defs, i)
179 : george 545 in UA.update(defs, i, instrs);
180 :     unmarkUseSites uses
181 : monnier 467 end
182 : george 545
183 :     (*
184 :     * Perform incremental liveness analysis on register v
185 :     *)
186 :     fun liveness(v, v' as NODE{uses, ...}, addEdge) =
187 :     let val st = !stamp
188 :     val _ = stamp := st + 1
189 :     fun foreachUseSite([]) = ()
190 :     | foreachUseSite(u::uses) =
191 :     let val b = blockNum u
192 :     val i = instrNum u
193 :     val block = UA.sub(blockTable, b)
194 :     in if i = 0 then
195 :     liveOutAtBlock(block) (* live out *)
196 :     else
197 :     liveOutAtStmt(block, UA.sub(defsTable, b), i+1);
198 :     foreachUseSite(uses)
199 :     end
200 :    
201 :     and visitPred(block) =
202 :     let fun foreachPred([]) = ()
203 :     | foreachPred((b, _)::pred) =
204 :     (liveOutAtBlock(b); foreachPred(pred))
205 :     in case block of
206 :     F.BBLOCK{pred, ...} => foreachPred(!pred)
207 :     | _ => error "visitPred"
208 :     end
209 :    
210 :     and liveOutAtStmt(block, defs, pos) =
211 :     (* v is live out *)
212 :     if pos < A.length defs then
213 :     let fun foreachDef([], true) = ()
214 :     | foreachDef([], false) =
215 :     liveOutAtStmt(block, defs, pos+1)
216 :     | foreachDef((d as NODE{number=r, ...})::ds, kill) =
217 :     if r = v then foreachDef(ds, true)
218 :     else if r < 256 andalso v < 256
219 :     then foreachDef(ds, kill)
220 :     else (addEdge(d,v'); foreachDef(ds, kill))
221 :     in foreachDef(UA.sub(defs, pos), false)
222 :     end
223 :     else visitPred(block)
224 :    
225 :     and liveOutAtBlock(block as F.BBLOCK{blknum, ...}) =
226 :     (* v is live out at the current block *)
227 :     if UA.sub(marked, blknum) = st then ()
228 : monnier 467 else
229 : george 545 (UA.update(marked, blknum, st);
230 :     liveOutAtStmt(block, UA.sub(defsTable, blknum), 1)
231 :     )
232 :     | liveOutAtBlock _ = ()
233 :    
234 :     val useSites = SortedList.uniq(!uses)
235 :     in markUseSites(v', useSites);
236 :     foreachUseSite(useSites);
237 :     unmarkUseSites useSites
238 :     end
239 :    
240 :     (*
241 :     * Perform incremental liveness analysis on register v
242 :     * and compute the span
243 :     *)
244 :     fun liveness2(v, v' as NODE{uses, ...}, addEdge, setSpan) =
245 :     let val st = !stamp
246 :     val _ = stamp := st + 1
247 :     fun foreachUseSite([], span) = span
248 :     | foreachUseSite(u::uses, span) =
249 :     let val b = blockNum u
250 :     val i = instrNum u
251 :     in case UA.sub(blockTable, b) of
252 :     block as F.BBLOCK{freq, ...} =>
253 :     let val span =
254 :     if i = 0 then
255 :     liveOutAtBlock(block, span) (* live out *)
256 :     else
257 :     let val f = !freq
258 :     in liveOutAtStmt(block, UA.sub(defsTable, b),
259 :     i+1, f, span+f)
260 :     end;
261 :     in foreachUseSite(uses, span)
262 :     end
263 :     | _ => error "liveness2"
264 :     end
265 :    
266 :     and visitPred(block, span) =
267 :     let fun foreachPred([], span) = span
268 :     | foreachPred((b, _)::pred, span) =
269 :     let val span = liveOutAtBlock(b, span)
270 :     in foreachPred(pred, span) end
271 :     in case block of
272 :     F.BBLOCK{pred, ...} => foreachPred(!pred, span)
273 :     | _ => error "visitPred"
274 :     end
275 :    
276 :     and liveOutAtStmt(block, defs, pos, freq, span) =
277 :     (* v is live out *)
278 :     if pos < A.length defs then
279 :     let fun foreachDef([], true) = span
280 :     | foreachDef([], false) =
281 :     liveOutAtStmt(block, defs, pos+1, freq, span+freq)
282 :     | foreachDef((d as NODE{number=r, ...})::ds, kill) =
283 :     if r = v then foreachDef(ds, true)
284 :     else (addEdge(d, v'); foreachDef(ds, kill))
285 :     in foreachDef(UA.sub(defs, pos), false)
286 :     end
287 :     else visitPred(block, span)
288 :    
289 :     and liveOutAtBlock(block as F.BBLOCK{blknum, freq, ...}, span) =
290 :     (* v is live out at the current block *)
291 :     if UA.sub(marked, blknum) = st then span
292 :     else
293 :     (UA.update(marked, blknum, st);
294 :     liveOutAtStmt(block, UA.sub(defsTable, blknum),
295 :     1, !freq, span)
296 :     )
297 :     | liveOutAtBlock(_, span) = span
298 :    
299 :     val useSites = SortedList.uniq(!uses)
300 :     val _ = markUseSites(v', useSites)
301 :     val span = foreachUseSite (useSites, 0)
302 :     val _ = unmarkUseSites useSites
303 :     in setSpan(v, span)
304 :     end
305 :    
306 :     val newNodes = Core.newNodes G
307 : monnier 467 val getnode = Intmap.map nodes
308 :     val insnDefUse = Props.defUse cellkind
309 :     val getCell = C.getCell cellkind
310 :    
311 :     fun isDedicated r =
312 :     r < 0 orelse
313 :     r < A.length dedicated andalso UA.sub(dedicated, r)
314 :    
315 : monnier 498 (* Remove all dedicated or spilled registers from the list *)
316 : monnier 467 fun rmvDedicated regs =
317 :     let fun loop([], rs') = rs'
318 :     | loop(r::rs, rs') =
319 :     let val r = regmap r
320 :     in loop(rs, if isDedicated r then rs' else r::rs') end
321 :     in loop(regs, []) end
322 :    
323 :     (*
324 :     * Create parallel move
325 :     *)
326 :     fun mkMoves(insn, dst, src, cost, mv, tmps) =
327 :     if Props.moveInstr insn then
328 :     let val (dst, tmps) =
329 :     case (Props.moveTmpR insn, dst) of
330 :     (SOME r, _::dst) =>
331 :     (* Add a pseudo use for tmpR *)
332 : monnier 498 let fun chase(NODE{color=ref(ALIASED n), ...}) =
333 :     chase n
334 :     | chase n = n
335 : george 545 in case chase(getnode r) of
336 :     tmp as NODE{uses,defs=ref [d],...} =>
337 :     (uses := [d-1]; (dst, tmp::tmps))
338 :     | _ => error "mkMoves"
339 :     end
340 : monnier 467 | (_, dst) => (dst, tmps)
341 :     fun moves([], [], mv) = mv
342 :     | moves(d::ds, s::ss, mv) =
343 :     if isDedicated d orelse isDedicated s
344 :     then moves(ds, ss, mv)
345 :     else
346 : monnier 498 let fun chases(NODE{color=ref(ALIASED src), ...}, dst) =
347 :     chases(src, dst)
348 :     | chases(src, dst) = chases'(src, dst)
349 :     and chases'(src, NODE{color=ref(ALIASED dst), ...}) =
350 :     chases'(src, dst)
351 :     | chases'(src, dst) = (src, dst)
352 :     val (src as NODE{number=s, ...},
353 :     dst as NODE{number=d, ...}) =
354 :     chases(getnode s, getnode d)
355 : monnier 467 in if d = s then moves(ds, ss, mv)
356 :     else moves(ds, ss, MV{dst=dst, src=src,
357 :     status=ref WORKLIST,
358 : monnier 498 hicount=ref 0,
359 : monnier 467 (* kind=REG_TO_REG, *)
360 :     cost=cost}::mv)
361 :     end
362 :     | moves _ = error "moves"
363 :     in (moves(dst, src, mv), tmps) end
364 :     else (mv, tmps)
365 :    
366 :     (* Add the nodes first *)
367 :     fun mkNodes([], mv, tmps) = (mv, tmps)
368 :     | mkNodes(F.BBLOCK{blknum, insns, succ, freq=ref w,
369 :     liveOut, ...}::blks, mv, tmps)=
370 :     let val dtab = A.sub(defsTable, blknum)
371 :     fun scan([], pt, i, mv, tmps) = (pt, i, mv, tmps)
372 :     | scan(insns as insn::rest, pt, i, mv, tmps) =
373 :     let val (d, u) = insnDefUse insn
374 :     val defs = rmvDedicated d
375 :     val uses = rmvDedicated u
376 :     val defs = newNodes{cost=w, pt=pt,
377 :     defs=defs, uses=uses}
378 :     val _ = UA.update(dtab, i, defs)
379 :     val (mv, tmps) = mkMoves(insn, d, u, w, mv, tmps)
380 : monnier 498 in scan(rest, pt+1, i+1, mv, tmps)
381 : monnier 467 end
382 :     val (pt, i, mv, tmps) =
383 :     scan(!insns, progPt(blknum,1), 1, mv, tmps)
384 :     val _ = if pt >= progPt(blknum+1, 0) then
385 : monnier 498 error("mkNodes: too many instructions")
386 : monnier 467 else ()
387 : george 545 (* fun fill i =
388 : monnier 467 if i < A.length dtab then
389 : monnier 498 (UA.update(dtab, i, []); fill(i+1))
390 : george 545 else () *)
391 :     in (* fill i; *)
392 : monnier 467 (* If the block is escaping, then all liveout
393 :     * registers are considered used here.
394 :     *)
395 :     case !succ of
396 :     [(F.EXIT _, _)] =>
397 :     let val liveSet = rmvDedicated(getCell(!liveOut))
398 :     in newNodes{cost=w, pt=progPt(blknum, 0),
399 :     defs=[], uses=liveSet}; ()
400 :     end
401 :     | _ => ()
402 :     ;
403 :     mkNodes(blks, mv, tmps)
404 :     end
405 :     | mkNodes(_::blks, mv, tmps) = mkNodes(blks, mv, tmps)
406 :    
407 :     (* Add the edges *)
408 :    
409 :     val (moves, tmps) = mkNodes(blocks, [], [])
410 : monnier 498 val addEdge = Core.addEdge G
411 :     in Intmap.app
412 :     (if isOn(mode,Core.COMPUTE_SPAN) then
413 : george 545 let val spanMap = Intmap.new(Intmap.elems nodes, NotThere)
414 :     val setSpan = Intmap.add spanMap
415 :     val _ = span := SOME spanMap
416 : monnier 498 in fn (v, v' as NODE{color=ref(PSEUDO | COLORED _), ...}) =>
417 :     liveness2(v, v', addEdge, setSpan)
418 :     | (v, v' as NODE{color=ref(SPILLED c), ...}) =>
419 :     if c >= 0 then liveness2(v, v', addEdge, setSpan) else ()
420 :     | _ => ()
421 :     end
422 :     else
423 :     (fn (v, v' as NODE{color=ref(PSEUDO | COLORED _), ...}) =>
424 :     liveness(v, v', addEdge)
425 :     | (v, v' as NODE{color=ref(SPILLED c), ...}) =>
426 :     if c >= 0 then liveness(v, v', addEdge) else ()
427 :     | _ => ()
428 :     )
429 :     ) nodes;
430 :     if isOn(Core.SAVE_COPY_TEMPS, mode) then copyTmps := tmps else ();
431 : monnier 467 rmPseudoUses tmps;
432 :     moves
433 :     end
434 :    
435 :     (*
436 :     * Build the interference graph initially.
437 :     *)
438 :     fun build(G, cellkind) = buildIt(cellkind, C.lookup regmap, G)
439 :    
440 :     (*
441 :     * Grow a table
442 :     *)
443 : george 545 (*
444 : monnier 467 fun grow(b, n) =
445 :     let (* val m = Word.toIntX(Word.>>(Word.fromInt(n+8),0w3)) *)
446 :     val m = n+1
447 : monnier 498 in (* if A.length(A.sub(marked, b)) < m then
448 : monnier 467 UA.update(marked, b, A.array(m, ~1))
449 : monnier 498 else (); *)
450 : monnier 467 if A.length(A.sub(defsTable, b)) < m then
451 :     UA.update(defsTable, b, A.array(m, []))
452 :     else ()
453 :     end
454 : george 545 *)
455 : monnier 467
456 :     (*
457 :     * Rebuild the interference graph;
458 :     * We'll just do it from scratch for now.
459 :     *)
460 :     fun rebuild(cellkind, G) =
461 :     (Core.clearGraph G; Core.clearNodes G;
462 :     buildIt(cellkind, Core.regmap G, G))
463 :    
464 :     val regs = foldr(fn (r, "") => Int.toString r
465 :     | (r, l) => Int.toString r^","^l) ""
466 :    
467 :     (*
468 :     * Spill a set of nodes and rewrite the flowgraph
469 :     *)
470 : monnier 498 fun spill{copyInstr, spill, spillSrc, spillCopyTmp,
471 :     reload, reloadDst, renameSrc, graph as G.GRAPH{regmap, ...},
472 : monnier 467 cellkind, nodes=nodesToSpill} =
473 :     let
474 :     (* maps program point to registers to be spilled *)
475 :     val spillSet = Intmap.new(32, NotThere) : C.cell list Intmap.intmap
476 :    
477 :     (* maps program point to registers to be reloaded *)
478 :     val reloadSet = Intmap.new(32, NotThere) : C.cell list Intmap.intmap
479 :    
480 :     (* maps program point to registers to be killed *)
481 :     val killSet = Intmap.new(32, NotThere) : C.cell list Intmap.intmap
482 :    
483 : monnier 498 val spillRewrite = Spill.spillRewrite
484 :     { graph=graph,
485 :     spill=spill,
486 :     spillSrc=spillSrc,
487 :     spillCopyTmp=spillCopyTmp,
488 :     reload=reload,
489 :     reloadDst=reloadDst,
490 :     renameSrc=renameSrc,
491 :     copyInstr=copyInstr,
492 :     cellkind=cellkind,
493 :     spillSet=spillSet,
494 :     reloadSet=reloadSet,
495 :     killSet=killSet
496 :     }
497 :    
498 : monnier 467 (* set of basic blocks that are affected *)
499 :     val affectedBlocks = Intmap.new(32, NotThere) : bool Intmap.intmap
500 :    
501 :     val addAffectedBlocks = Intmap.add affectedBlocks
502 :    
503 :     fun ins set =
504 :     let val add = Intmap.add set
505 :     val look = Intmap.mapWithDefault(set, [])
506 : monnier 498 in fn r => fn x =>
507 : monnier 467 (add (x, r::look x);
508 :     addAffectedBlocks (blockNum x, true)
509 :     )
510 :     end
511 :    
512 :     val insSpillSet = ins spillSet
513 :     val insReloadSet = ins reloadSet
514 :     val insKillSet =
515 :     let val add = Intmap.add killSet
516 :     val look = Intmap.mapWithDefault(killSet, [])
517 : monnier 498 in fn r => fn x => add (x, r::look x) end
518 : monnier 467
519 : monnier 498 (* Mark all spill/reload locations *)
520 :     val markSpills = app
521 :     (fn G.NODE{color, number, defs=ref defs, uses=ref uses, ...} =>
522 :     let fun spillIt(defs, uses) =
523 :     (app (insSpillSet number) defs;
524 :     app (insReloadSet number) uses;
525 :     (* Definitions but no use! *)
526 :     case uses of
527 :     [] => app (insKillSet number) defs
528 :     | _ => ()
529 :     )
530 :     in case !color of
531 :     G.SPILLED c => spillIt(defs, uses)
532 :     | G.PSEUDO => spillIt(defs, uses)
533 :     | _ => ()
534 :     end
535 :     )
536 :     val _ = markSpills nodesToSpill
537 : monnier 467
538 : monnier 498 (* Print all spill/reload locations *)
539 :     (* val _ = countSpillsReloads nodesToSpill *)
540 :     (*
541 :     val _ =
542 :     if !(MLRiscControl.getFlag "dump-spills") then
543 :     app
544 : monnier 475 (fn G.NODE{color=ref(G.ALIASED _), ...} => ()
545 : monnier 498 | G.NODE{number, defs=ref defs, uses=ref uses, pri, ...} =>
546 :     let fun pr pt = let val b = blockNum pt
547 :     val p = instrNum pt
548 :     in Int.toString b^"."^Int.toString p end
549 :     fun prs pts = foldr (fn (pt,"") => pr pt
550 :     | (pt,l) => pr pt^", "^l) "" pts
551 :     in case
552 :     (if List.exists
553 :     (fn def => List.exists (fn use => use=def-1) uses)
554 :     defs then (print "DEF-USE "; true) else false,
555 :     if List.exists
556 :     (fn use => List.exists (fn use2 => use=use2-1) uses)
557 :     uses then (print " USE-USE "; true) else false) of
558 :     (false,false) => ()
559 :     | _ =>
560 :     (print("Spilling ["^Int.toString(!pri)^
561 :     "] r"^Int.toString number);
562 :     print(" defs="^prs(SortedList.uniq defs));
563 :     print(" uses="^prs(SortedList.uniq uses));
564 :     print "\n")
565 :     end
566 : monnier 475 ) nodesToSpill
567 : monnier 498 else ()
568 :     *)
569 : monnier 467
570 :     (* Rewrite all affected blocks *)
571 :     fun rewriteAll (blknum, _) =
572 : george 545 case A.sub(blockTable, blknum) of
573 :     F.BBLOCK{annotations, insns as ref instrs, ...} =>
574 :     let val instrs =
575 :     spillRewrite{pt=progPt(blknum, length instrs),
576 :     instrs=instrs,
577 :     annotations=annotations}
578 :     in insns := instrs
579 :     (* grow(blknum, length instrs) *)
580 :     end
581 :     | _ => error "rewriteAll"
582 : monnier 467
583 :     in Intmap.app rewriteAll affectedBlocks;
584 : monnier 498 let val spilledMarker = SPILLED ~2
585 :     in app (fn G.NODE{number, color as ref(SPILLED c), ...} =>
586 :     if number <> c then color := spilledMarker else ()
587 :     | G.NODE{color as ref PSEUDO, ...} =>
588 :     color := spilledMarker
589 :     | _ => ()
590 :     ) nodesToSpill
591 :     end;
592 : monnier 467 rebuild(cellkind, graph)
593 :     end
594 :    
595 : monnier 498 in {build=build, spill=spill,
596 :     programPoint=fn{block,instr} => progPt(block,instr),
597 :     blockNum=blockNum,
598 :     instrNum=instrNum
599 :     }
600 : monnier 467 end
601 :    
602 :     end

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