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 499 - (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 :     structure PrintCluster = PrintClusterFn
34 :     (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 :     (* blocks indexed by block id *)
120 : monnier 467 val blockTable = A.array(N, dummyLabel)
121 :    
122 :     (* definitions indexed by block id+instruction id *)
123 :     val defsTable = A.array(N, A.array(0, [])) : node list A.array A.array
124 : monnier 498 val marked = A.array(N, ~1)
125 : monnier 467
126 :     val stamp = ref 0
127 :    
128 :     (* Build the initial interference graph *)
129 :     fun init [] = ()
130 :     | init((b as F.BBLOCK{blknum, insns, ...})::blocks) =
131 :     let val n = length(!insns)
132 :     (* val m = Word.toIntX(Word.>>(Word.fromInt(n+8),0w3)) *)
133 :     val m = n+1
134 :     in UA.update(blockTable, blknum, b);
135 :     UA.update(defsTable, blknum, A.array(m, []));
136 :     init blocks
137 :     end
138 :     | init(_::blocks) = init blocks
139 :     val _ = init blocks
140 :    
141 :     (*
142 : monnier 498 * Remove pseudo use generated by copy temporaries
143 : monnier 467 *)
144 : monnier 498 fun rmPseudoUses [] = ()
145 :     | rmPseudoUses(NODE{uses,...}::ns) = (uses := []; rmPseudoUses ns)
146 : monnier 467
147 : monnier 498 (*
148 :     val marker = NODE{pri=ref 0,adj=ref [],degree=ref 0,movecnt=ref 0,
149 :     color=ref PSEUDO, defs=ref [], uses=ref [],
150 :     movecost=ref 0,movelist=ref [], number= ~1}
151 :     *)
152 : monnier 467
153 :     (*
154 : monnier 498 * Remove duplicates on use sites
155 : monnier 467 *)
156 : monnier 498 (*
157 :     fun uniq [] = []
158 :     | uniq (l as [_]) = l
159 :     | uniq (l as [x,y]) = if x = y then [x] else l
160 :     | uniq uses =
161 :     let fun mark([], uses') = uses'
162 :     | mark(u::uses, uses') =
163 :     let val b = blockNum u
164 :     val i = instrNum u
165 :     val defs = UA.sub(defsTable, b)
166 :     in case A.sub(defs, i) of
167 :     NODE{number= ~1, ...}::_ => mark(uses, uses')
168 :     | instrs => (UA.update(defs, i, marker::instrs);
169 :     mark(uses, u::uses'))
170 :     end
171 :     val useSites = mark(uses, [])
172 :     fun unmark [] = ()
173 :     | unmark(u::uses) =
174 :     let val b = blockNum u
175 :     val i = instrNum u
176 :     val defs = UA.sub(defsTable, b)
177 :     val _::instrs = UA.sub(defs, i)
178 :     in UA.update(defs, i, instrs); unmark uses end
179 :     in unmark useSites;
180 :     useSites
181 :     end
182 :     *)
183 : monnier 467
184 :     (*
185 : monnier 498 * Mark the use site as definitions so that the traversal would
186 :     * end properly.
187 :     *)
188 :     fun markUseSites(v,[]) = ()
189 :     | markUseSites(v,u::uses) =
190 :     let val b = blockNum u
191 :     val i = instrNum u
192 :     val defs = UA.sub(defsTable, b)
193 :     in UA.update(defs, i, v::UA.sub(defs, i));
194 :     markUseSites(v, uses)
195 :     end
196 :    
197 :     (*
198 :     * Unmark fake def sites
199 :     *)
200 :     fun unmarkUseSites [] = ()
201 :     | unmarkUseSites(u::uses) =
202 :     let val b = blockNum u
203 :     val i = instrNum u
204 :     val defs = UA.sub(defsTable, b)
205 :     val _::instrs = UA.sub(defs, i)
206 :     in UA.update(defs, i, instrs);
207 :     unmarkUseSites uses
208 :     end
209 :    
210 :     (*
211 : monnier 467 * Perform incremental liveness analysis on register v
212 :     *)
213 :     fun liveness(v, v' as NODE{uses, ...}, addEdge) =
214 :     let val st = !stamp
215 :     val _ = stamp := st + 1
216 : monnier 498 fun foreachUseSite([]) = ()
217 : monnier 467 | foreachUseSite(u::uses) =
218 :     let val b = blockNum u
219 :     val i = instrNum u
220 :     val block = UA.sub(blockTable, b)
221 :     in if i = 0 then
222 :     liveOutAtBlock(block) (* live out *)
223 :     else
224 : monnier 498 liveOutAtStmt(block, UA.sub(defsTable, b), i+1);
225 :     foreachUseSite(uses)
226 : monnier 467 end
227 :    
228 : monnier 498 and visitPred(block) =
229 : monnier 467 let fun foreachPred([]) = ()
230 :     | foreachPred((b, _)::pred) =
231 : monnier 498 (liveOutAtBlock(b); foreachPred(pred))
232 : monnier 467 val F.BBLOCK{pred, ...} = block
233 :     in foreachPred(!pred) end
234 :    
235 : monnier 498 and liveOutAtStmt(block, defs, pos) =
236 : monnier 467 (* v is live out *)
237 :     if pos < A.length defs then
238 : monnier 498 let fun foreachDef([], true) = ()
239 :     | foreachDef([], false) =
240 :     liveOutAtStmt(block, defs, pos+1)
241 : monnier 467 | foreachDef((d as NODE{number=r, ...})::ds, kill) =
242 :     if r = v then foreachDef(ds, true)
243 : monnier 498 else if r < 256 andalso v < 256 then foreachDef(ds, kill)
244 :     else (addEdge(d,v'); foreachDef(ds, kill))
245 :     in foreachDef(UA.sub(defs, pos), false)
246 : monnier 467 end
247 : monnier 498 else visitPred(block)
248 : monnier 467
249 :     and liveOutAtBlock(block as F.BBLOCK{blknum, ...}) =
250 :     (* v is live out at the current block *)
251 : monnier 498 if UA.sub(marked, blknum) = st then ()
252 :     else
253 :     (UA.update(marked, blknum, st);
254 :     liveOutAtStmt(block, UA.sub(defsTable, blknum), 1)
255 :     )
256 :     | liveOutAtBlock _ = ()
257 :    
258 :     val useSites = SortedList.uniq(!uses)
259 :     in markUseSites(v', useSites);
260 :     foreachUseSite(useSites);
261 :     unmarkUseSites useSites
262 :     end
263 :    
264 :     (*
265 :     * Perform incremental liveness analysis on register v
266 :     * and compute the span
267 :     *)
268 :     fun liveness2(v, v' as NODE{uses, ...}, addEdge, setSpan) =
269 :     let val st = !stamp
270 :     val _ = stamp := st + 1
271 :     fun foreachUseSite([], span) = span
272 :     | foreachUseSite(u::uses, span) =
273 :     let val b = blockNum u
274 :     val i = instrNum u
275 :     val block as F.BBLOCK{freq, ...} = UA.sub(blockTable, b)
276 :     val span =
277 :     if i = 0 then
278 :     liveOutAtBlock(block, span) (* live out *)
279 : monnier 467 else
280 : monnier 498 let val f = !freq
281 :     in liveOutAtStmt(block, UA.sub(defsTable, b),
282 :     i+1, f, span+f)
283 :     end;
284 :     in foreachUseSite(uses, span)
285 : monnier 467 end
286 :    
287 : monnier 498 and visitPred(block, span) =
288 :     let fun foreachPred([], span) = span
289 :     | foreachPred((b, _)::pred, span) =
290 :     let val span = liveOutAtBlock(b, span)
291 :     in foreachPred(pred, span) end
292 :     val F.BBLOCK{pred, ...} = block
293 :     in foreachPred(!pred, span) end
294 :    
295 :     and liveOutAtStmt(block, defs, pos, freq, span) =
296 :     (* v is live out *)
297 :     if pos < A.length defs then
298 :     let fun foreachDef([], true) = span
299 :     | foreachDef([], false) =
300 :     liveOutAtStmt(block, defs, pos+1, freq, span+freq)
301 :     | foreachDef((d as NODE{number=r, ...})::ds, kill) =
302 :     if r = v then foreachDef(ds, true)
303 :     else (addEdge(d, v'); foreachDef(ds, kill))
304 :     in foreachDef(UA.sub(defs, pos), false)
305 :     end
306 :     else visitPred(block, span)
307 :    
308 :     and liveOutAtBlock(block as F.BBLOCK{blknum, freq, ...}, span) =
309 :     (* v is live out at the current block *)
310 :     if UA.sub(marked, blknum) = st then span
311 :     else
312 :     (UA.update(marked, blknum, st);
313 :     liveOutAtStmt(block, UA.sub(defsTable, blknum),
314 :     1, !freq, span)
315 :     )
316 :     | liveOutAtBlock(_, span) = span
317 :    
318 :     val useSites = SortedList.uniq(!uses)
319 :     val _ = markUseSites(v', useSites)
320 :     val span = foreachUseSite (useSites, 0)
321 :     (*val _ = print("Span(r"^Int.toString v^")="^Int.toString span^"\n")*)
322 :     val _ = unmarkUseSites useSites
323 :     in setSpan(v, span)
324 : monnier 467 end
325 :    
326 :     (*
327 :     * Building the interference graph
328 :     *)
329 : monnier 498 fun buildIt (cellkind, regmap,
330 :     G as GRAPH{nodes, dedicated, mode, span, copyTmps, ...}) =
331 : monnier 467 let val newNodes = Core.newNodes G
332 :     val getnode = Intmap.map nodes
333 :     val insnDefUse = Props.defUse cellkind
334 :     val getCell = C.getCell cellkind
335 :    
336 :     fun isDedicated r =
337 :     r < 0 orelse
338 :     r < A.length dedicated andalso UA.sub(dedicated, r)
339 :    
340 : monnier 498 (* Remove all dedicated or spilled registers from the list *)
341 : monnier 467 fun rmvDedicated regs =
342 :     let fun loop([], rs') = rs'
343 :     | loop(r::rs, rs') =
344 :     let val r = regmap r
345 :     in loop(rs, if isDedicated r then rs' else r::rs') end
346 :     in loop(regs, []) end
347 :    
348 :     (*
349 :     * Create parallel move
350 :     *)
351 :     fun mkMoves(insn, dst, src, cost, mv, tmps) =
352 :     if Props.moveInstr insn then
353 :     let val (dst, tmps) =
354 :     case (Props.moveTmpR insn, dst) of
355 :     (SOME r, _::dst) =>
356 :     (* Add a pseudo use for tmpR *)
357 : monnier 498 let fun chase(NODE{color=ref(ALIASED n), ...}) =
358 :     chase n
359 :     | chase n = n
360 :     val tmp as NODE{uses,defs=ref [d],...} =
361 : monnier 467 chase(getnode r)
362 : monnier 498 in uses := [d-1]; (dst, tmp::tmps) end
363 : monnier 467 | (_, dst) => (dst, tmps)
364 :     fun moves([], [], mv) = mv
365 :     | moves(d::ds, s::ss, mv) =
366 :     if isDedicated d orelse isDedicated s
367 :     then moves(ds, ss, mv)
368 :     else
369 : monnier 498 let fun chases(NODE{color=ref(ALIASED src), ...}, dst) =
370 :     chases(src, dst)
371 :     | chases(src, dst) = chases'(src, dst)
372 :     and chases'(src, NODE{color=ref(ALIASED dst), ...}) =
373 :     chases'(src, dst)
374 :     | chases'(src, dst) = (src, dst)
375 :     val (src as NODE{number=s, ...},
376 :     dst as NODE{number=d, ...}) =
377 :     chases(getnode s, getnode d)
378 : monnier 467 in if d = s then moves(ds, ss, mv)
379 :     else moves(ds, ss, MV{dst=dst, src=src,
380 :     status=ref WORKLIST,
381 : monnier 498 hicount=ref 0,
382 : monnier 467 (* kind=REG_TO_REG, *)
383 :     cost=cost}::mv)
384 :     end
385 :     | moves _ = error "moves"
386 :     in (moves(dst, src, mv), tmps) end
387 :     else (mv, tmps)
388 :    
389 :     (* Add the nodes first *)
390 :     fun mkNodes([], mv, tmps) = (mv, tmps)
391 :     | mkNodes(F.BBLOCK{blknum, insns, succ, freq=ref w,
392 :     liveOut, ...}::blks, mv, tmps)=
393 :     let val dtab = A.sub(defsTable, blknum)
394 :     fun scan([], pt, i, mv, tmps) = (pt, i, mv, tmps)
395 :     | scan(insns as insn::rest, pt, i, mv, tmps) =
396 :     let val (d, u) = insnDefUse insn
397 :     val defs = rmvDedicated d
398 :     val uses = rmvDedicated u
399 :     val defs = newNodes{cost=w, pt=pt,
400 :     defs=defs, uses=uses}
401 :     val _ = UA.update(dtab, i, defs)
402 :     val (mv, tmps) = mkMoves(insn, d, u, w, mv, tmps)
403 : monnier 498 in scan(rest, pt+1, i+1, mv, tmps)
404 : monnier 467 end
405 :     val (pt, i, mv, tmps) =
406 :     scan(!insns, progPt(blknum,1), 1, mv, tmps)
407 :     val _ = if pt >= progPt(blknum+1, 0) then
408 : monnier 498 error("mkNodes: too many instructions")
409 : monnier 467 else ()
410 :     fun fill i =
411 :     if i < A.length dtab then
412 : monnier 498 (UA.update(dtab, i, []); fill(i+1))
413 : monnier 467 else ()
414 :     in fill i;
415 :     (* If the block is escaping, then all liveout
416 :     * registers are considered used here.
417 :     *)
418 :     case !succ of
419 :     [(F.EXIT _, _)] =>
420 :     let val liveSet = rmvDedicated(getCell(!liveOut))
421 :     in newNodes{cost=w, pt=progPt(blknum, 0),
422 :     defs=[], uses=liveSet}; ()
423 :     end
424 :     | _ => ()
425 :     ;
426 :     mkNodes(blks, mv, tmps)
427 :     end
428 :     | mkNodes(_::blks, mv, tmps) = mkNodes(blks, mv, tmps)
429 :    
430 :     (* Add the edges *)
431 :    
432 :     val (moves, tmps) = mkNodes(blocks, [], [])
433 : monnier 498 val addEdge = Core.addEdge G
434 :     in Intmap.app
435 :     (if isOn(mode,Core.COMPUTE_SPAN) then
436 :     let val setSpan = Intmap.add span
437 :     in fn (v, v' as NODE{color=ref(PSEUDO | COLORED _), ...}) =>
438 :     liveness2(v, v', addEdge, setSpan)
439 :     | (v, v' as NODE{color=ref(SPILLED c), ...}) =>
440 :     if c >= 0 then liveness2(v, v', addEdge, setSpan) else ()
441 :     | _ => ()
442 :     end
443 :     else
444 :     (fn (v, v' as NODE{color=ref(PSEUDO | COLORED _), ...}) =>
445 :     liveness(v, v', addEdge)
446 :     | (v, v' as NODE{color=ref(SPILLED c), ...}) =>
447 :     if c >= 0 then liveness(v, v', addEdge) else ()
448 :     | _ => ()
449 :     )
450 :     ) nodes;
451 :     if isOn(Core.SAVE_COPY_TEMPS, mode) then copyTmps := tmps else ();
452 : monnier 467 rmPseudoUses tmps;
453 :     moves
454 :     end
455 :    
456 :     (*
457 :     * Build the interference graph initially.
458 :     *)
459 :     fun build(G, cellkind) = buildIt(cellkind, C.lookup regmap, G)
460 :    
461 :     (*
462 :     * Grow a table
463 :     *)
464 :     fun grow(b, n) =
465 :     let (* val m = Word.toIntX(Word.>>(Word.fromInt(n+8),0w3)) *)
466 :     val m = n+1
467 : monnier 498 in (* if A.length(A.sub(marked, b)) < m then
468 : monnier 467 UA.update(marked, b, A.array(m, ~1))
469 : monnier 498 else (); *)
470 : monnier 467 if A.length(A.sub(defsTable, b)) < m then
471 :     UA.update(defsTable, b, A.array(m, []))
472 :     else ()
473 :     end
474 :    
475 :     (*
476 :     * Rebuild the interference graph;
477 :     * We'll just do it from scratch for now.
478 :     *)
479 :     fun rebuild(cellkind, G) =
480 :     (Core.clearGraph G; Core.clearNodes G;
481 :     buildIt(cellkind, Core.regmap G, G))
482 :    
483 :     val regs = foldr(fn (r, "") => Int.toString r
484 :     | (r, l) => Int.toString r^","^l) ""
485 :    
486 :     (*
487 :     * Spill a set of nodes and rewrite the flowgraph
488 :     *)
489 : monnier 498 fun spill{copyInstr, spill, spillSrc, spillCopyTmp,
490 :     reload, reloadDst, renameSrc, graph as G.GRAPH{regmap, ...},
491 : monnier 467 cellkind, nodes=nodesToSpill} =
492 :     let
493 :     (* maps program point to registers to be spilled *)
494 :     val spillSet = Intmap.new(32, NotThere) : C.cell list Intmap.intmap
495 :    
496 :     (* maps program point to registers to be reloaded *)
497 :     val reloadSet = Intmap.new(32, NotThere) : C.cell list Intmap.intmap
498 :    
499 :     (* maps program point to registers to be killed *)
500 :     val killSet = Intmap.new(32, NotThere) : C.cell list Intmap.intmap
501 :    
502 : monnier 498 val spillRewrite = Spill.spillRewrite
503 :     { graph=graph,
504 :     spill=spill,
505 :     spillSrc=spillSrc,
506 :     spillCopyTmp=spillCopyTmp,
507 :     reload=reload,
508 :     reloadDst=reloadDst,
509 :     renameSrc=renameSrc,
510 :     copyInstr=copyInstr,
511 :     cellkind=cellkind,
512 :     spillSet=spillSet,
513 :     reloadSet=reloadSet,
514 :     killSet=killSet
515 :     }
516 :    
517 : monnier 467 (* set of basic blocks that are affected *)
518 :     val affectedBlocks = Intmap.new(32, NotThere) : bool Intmap.intmap
519 :    
520 :     val addAffectedBlocks = Intmap.add affectedBlocks
521 :    
522 :     fun ins set =
523 :     let val add = Intmap.add set
524 :     val look = Intmap.mapWithDefault(set, [])
525 : monnier 498 in fn r => fn x =>
526 : monnier 467 (add (x, r::look x);
527 :     addAffectedBlocks (blockNum x, true)
528 :     )
529 :     end
530 :    
531 :     val insSpillSet = ins spillSet
532 :     val insReloadSet = ins reloadSet
533 :     val insKillSet =
534 :     let val add = Intmap.add killSet
535 :     val look = Intmap.mapWithDefault(killSet, [])
536 : monnier 498 in fn r => fn x => add (x, r::look x) end
537 : monnier 467
538 : monnier 498 (* Mark all spill/reload locations *)
539 :     val markSpills = app
540 :     (fn G.NODE{color, number, defs=ref defs, uses=ref uses, ...} =>
541 :     let fun spillIt(defs, uses) =
542 :     (app (insSpillSet number) defs;
543 :     app (insReloadSet number) uses;
544 :     (* Definitions but no use! *)
545 :     case uses of
546 :     [] => app (insKillSet number) defs
547 :     | _ => ()
548 :     )
549 :     in case !color of
550 :     G.SPILLED c => spillIt(defs, uses)
551 :     | G.PSEUDO => spillIt(defs, uses)
552 :     | _ => ()
553 :     end
554 :     )
555 :     val _ = markSpills nodesToSpill
556 : monnier 467
557 : monnier 498 (* Print all spill/reload locations *)
558 :     (* val _ = countSpillsReloads nodesToSpill *)
559 :     (*
560 :     val _ =
561 :     if !(MLRiscControl.getFlag "dump-spills") then
562 :     app
563 : monnier 475 (fn G.NODE{color=ref(G.ALIASED _), ...} => ()
564 : monnier 498 | G.NODE{number, defs=ref defs, uses=ref uses, pri, ...} =>
565 :     let fun pr pt = let val b = blockNum pt
566 :     val p = instrNum pt
567 :     in Int.toString b^"."^Int.toString p end
568 :     fun prs pts = foldr (fn (pt,"") => pr pt
569 :     | (pt,l) => pr pt^", "^l) "" pts
570 :     in case
571 :     (if List.exists
572 :     (fn def => List.exists (fn use => use=def-1) uses)
573 :     defs then (print "DEF-USE "; true) else false,
574 :     if List.exists
575 :     (fn use => List.exists (fn use2 => use=use2-1) uses)
576 :     uses then (print " USE-USE "; true) else false) of
577 :     (false,false) => ()
578 :     | _ =>
579 :     (print("Spilling ["^Int.toString(!pri)^
580 :     "] r"^Int.toString number);
581 :     print(" defs="^prs(SortedList.uniq defs));
582 :     print(" uses="^prs(SortedList.uniq uses));
583 :     print "\n")
584 :     end
585 : monnier 475 ) nodesToSpill
586 : monnier 498 else ()
587 :     *)
588 : monnier 467
589 :     (* Rewrite all affected blocks *)
590 :     fun rewriteAll (blknum, _) =
591 : monnier 498 let val F.BBLOCK{annotations, insns as ref instrs, ...} =
592 : monnier 467 A.sub(blockTable, blknum)
593 : monnier 498 val instrs = spillRewrite{pt=progPt(blknum, length instrs),
594 :     instrs=instrs,
595 :     annotations=annotations}
596 : monnier 467 in insns := instrs;
597 :     grow(blknum, length instrs)
598 :     end
599 :    
600 :     in Intmap.app rewriteAll affectedBlocks;
601 : monnier 498 let val spilledMarker = SPILLED ~2
602 :     in app (fn G.NODE{number, color as ref(SPILLED c), ...} =>
603 :     if number <> c then color := spilledMarker else ()
604 :     | G.NODE{color as ref PSEUDO, ...} =>
605 :     color := spilledMarker
606 :     | _ => ()
607 :     ) nodesToSpill
608 :     end;
609 : monnier 467 rebuild(cellkind, graph)
610 :     end
611 :    
612 : monnier 498 in {build=build, spill=spill,
613 :     programPoint=fn{block,instr} => progPt(block,instr),
614 :     blockNum=blockNum,
615 :     instrNum=instrNum
616 :     }
617 : monnier 467 end
618 :    
619 :     end

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