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 958 - (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 : george 909 (structure Flowgraph : CONTROL_FLOW_GRAPH
14 : monnier 467 structure Asm : INSTRUCTION_EMITTER
15 : george 933 where I = Flowgraph.I
16 :     and P = Flowgraph.P
17 : monnier 467 structure InsnProps : INSN_PROPERTIES
18 : george 933 where I = Flowgraph.I
19 : leunga 744 structure Spill : RA_SPILL
20 : george 933 where I = Flowgraph.I
21 : monnier 467 ) : RA_FLOWGRAPH =
22 :     struct
23 : george 909 structure CFG = Flowgraph
24 :     structure I = CFG.I
25 :     structure W = CFG.W
26 : monnier 467 structure G = RAGraph
27 :     structure Props = InsnProps
28 :     structure Core = RACore
29 :     structure A = Array
30 :     structure UA = Unsafe.Array (* okay, I'm cheating a bit here *)
31 : leunga 641 structure Spill = Spill
32 : monnier 467
33 :     open G
34 : george 889 structure C = I.C
35 :     structure CB = CellsBasis
36 : monnier 467
37 : monnier 498 fun isOn(flag,mask) = Word.andb(flag,mask) <> 0w0
38 :    
39 : leunga 628 val dump_size = MLRiscControl.getFlag "ra-dump-size"
40 :    
41 : george 909 type flowgraph = CFG.cfg (* flowgraph is a cluster *)
42 : monnier 467
43 :     fun error msg = MLRiscErrorMsg.error("ClusterRA", msg)
44 : leunga 744
45 : monnier 498 val mode = 0w0
46 : monnier 467
47 : george 889 fun uniqCells s = CB.SortedCells.return(CB.SortedCells.uniq s)
48 : monnier 467
49 : george 889 fun chaseCell(c as CB.CELL{col=ref(CB.MACHINE r),...}) = (c,r)
50 :     | chaseCell(CB.CELL{col=ref(CB.ALIASED c), ...}) = chaseCell c
51 :     | chaseCell(c as CB.CELL{col=ref CB.SPILLED, ...}) = (c,~1)
52 :     | chaseCell(c as CB.CELL{col=ref CB.PSEUDO, id, ...}) = (c,id)
53 : leunga 744
54 : george 889 fun colorOf(CB.CELL{col=ref(CB.MACHINE r),...}) = r
55 :     | colorOf(CB.CELL{col=ref(CB.ALIASED c), ...}) = colorOf c
56 :     | colorOf(CB.CELL{col=ref CB.SPILLED, ...}) = ~1
57 :     | colorOf(CB.CELL{col=ref CB.PSEUDO, id, ...}) = id
58 : leunga 744
59 :     fun chase(NODE{color=ref(ALIASED n), ...}) = chase n
60 :     | chase n = n
61 :    
62 : monnier 467 exception NotThere
63 :    
64 : george 909 val Asm.S.STREAM{emit,...} = Asm.makeStream []
65 : monnier 467
66 : george 909 fun dumpFlowgraph(txt, cfg as Graph.GRAPH graph, outstrm) = let
67 :     fun say txt = TextIO.output(outstrm, txt)
68 :     fun dump (nid, CFG.BLOCK{data, labels, insns, ...}) = let
69 :     fun dumpData(CFG.LABEL lab) = say(Label.toString lab ^ "\n")
70 :     | dumpData(CFG.PSEUDO pOp) = say(CFG.P.toString pOp ^ "\n")
71 :     in
72 :     app dumpData (!data);
73 :     app (fn lab => say(Label.toString lab ^ "\n")) (!labels);
74 :     app emit (rev (!insns))
75 :     end
76 :     in app dump (#nodes graph ())
77 :     end
78 :    
79 : george 958 val annotations = CFG.annotations
80 :    
81 : george 909 val dummyBlock = CFG.newBlock(~1, ref 0)
82 :    
83 : monnier 498 fun x + y = Word.toIntX(Word.+(Word.fromInt x, Word.fromInt y))
84 : monnier 467
85 : george 958 val uniq = ListMergeSort.uniqueSort
86 :     (fn ({block=b1,insn=i1},{block=b2,insn=i2}) =>
87 :     case Int.compare(b1,b2) of
88 :     EQUAL => Int.compare(i1,i2)
89 :     | ord => ord)
90 :    
91 : george 909 fun services(cfg as Graph.GRAPH graph) = let
92 :     val CFG.INFO{annotations=clAnns, ...} = #graph_info graph
93 :     val blocks = #nodes graph ()
94 :     fun maxBlockId ((id, CFG.BLOCK _)::rest, curr) =
95 :     if id > curr then maxBlockId(rest, id) else maxBlockId(rest, curr)
96 :     | maxBlockId([], curr) = curr
97 : monnier 467
98 : george 909 val N = maxBlockId(blocks, #capacity graph ())
99 : monnier 467
100 : monnier 498 (*
101 :     * Construct program point
102 :     *)
103 : george 958 fun progPt(blknum, instrId) = {block=blknum, insn=instrId}
104 :     fun blockNum{block,insn} = block
105 :     fun instrNum{block,insn} = insn
106 : monnier 498
107 : george 545 (* blocks indexed by block id *)
108 : george 958 val blockTable = A.array(N, (#new_id graph (), dummyBlock))
109 : monnier 467
110 : george 545 fun fillBlockTable [] = ()
111 : george 909 | fillBlockTable((b as (nid, _))::blocks) =
112 :     (UA.update(blockTable, nid, b); fillBlockTable blocks)
113 : george 545 val _ = fillBlockTable blocks
114 : monnier 467
115 : george 909 val EXIT = (case #exits graph () of [e] => e | _ => error "EXIT")
116 :    
117 : monnier 467 (*
118 : george 545 * Building the interference graph
119 :     *)
120 : leunga 744 fun buildIt (cellkind,
121 : george 545 G as GRAPH{nodes, dedicated, mode, span, copyTmps, ...}) =
122 : monnier 467
123 : george 545 let (* definitions indexed by block id+instruction id *)
124 :     val defsTable = A.array(N, A.array(0, [] : node list))
125 :     val marked = A.array(N, ~1)
126 : leunga 744 val addEdge = Core.addEdge G
127 : leunga 624
128 : leunga 744 (* copies indexed by source
129 :     * This table maps variable v to the program points where
130 :     * v is a source of a copy.
131 :     *)
132 :     val copyTable = IntHashTable.mkTable(N, NotThere)
133 : george 958 : {dst:CB.cell,pt:G.programPoint} list IntHashTable.hash_table
134 : leunga 744 val lookupCopy = IntHashTable.find copyTable
135 :     val lookupCopy = fn r => case lookupCopy r of SOME c => c
136 :     | NONE => []
137 : blume 733 val addCopy = IntHashTable.insert copyTable
138 : leunga 624
139 : george 545 val stamp = ref 0
140 :    
141 :     (* Allocate the arrays *)
142 :     fun alloc [] = ()
143 : george 909 | alloc((id, CFG.BLOCK{insns, ...})::blocks) =
144 :     (UA.update(defsTable, id, A.array(length(!insns)+1, []));
145 :     alloc blocks)
146 : george 545 val _ = alloc blocks
147 :    
148 :     (*
149 :     * Remove pseudo use generated by copy temporaries
150 :     *)
151 :     fun rmPseudoUses [] = ()
152 :     | rmPseudoUses(NODE{uses,...}::ns) = (uses := []; rmPseudoUses ns)
153 :    
154 :     (*
155 : leunga 624 * Initialize the definitions before computing the liveness for v.
156 : george 545 *)
157 : george 909 fun initialize(v, v', useSites) = let
158 :     (* First we remove all definitions for all copies
159 : leunga 624 * with v as source.
160 : george 909 * When we have a copy and while we are processing v
161 : leunga 744 *
162 :     * x <- v
163 :     *
164 :     * x does not really interfere with v at this point,
165 :     * so we remove the definition of x temporarily.
166 : leunga 624 *)
167 :     fun markCopies([], trail) = trail
168 :     | markCopies({pt, dst}::copies, trail) =
169 :     let val b = blockNum pt
170 :     val i = instrNum pt
171 :     val defs = UA.sub(defsTable, b)
172 :     val nodes = UA.sub(defs, i)
173 :     fun revAppend([], nodes) = nodes
174 :     | revAppend(n::ns, nodes) = revAppend(ns, n::nodes)
175 : leunga 744 val dstColor = colorOf dst
176 : leunga 624 fun removeDst([], nodes') = nodes'
177 :     | removeDst((d as NODE{number=r,...})::nodes, nodes')=
178 : leunga 744 if r = dstColor then revAppend(nodes', nodes)
179 : leunga 624 else removeDst(nodes, d::nodes')
180 :     val nodes' = removeDst(nodes, [])
181 :     in UA.update(defs, i, nodes');
182 :     markCopies(copies, (defs, i, nodes)::trail)
183 : george 545 end
184 : leunga 624
185 :     (*
186 : leunga 744 * Then we mark all use sites of v with a fake definition so that
187 :     * the scanning will terminate correctly at these points.
188 : leunga 624 *)
189 :     fun markUseSites([], trail) = trail
190 :     | markUseSites(pt::pts, trail) =
191 :     let val b = blockNum pt
192 :     val i = instrNum pt
193 :     val defs = UA.sub(defsTable, b)
194 :     val nodes = UA.sub(defs, i)
195 :     in UA.update(defs, i, v'::nodes);
196 :     markUseSites(pts, (defs, i, nodes)::trail)
197 : george 545 end
198 : leunga 624
199 :     val copies = lookupCopy v
200 :     val trail = markCopies(copies, [])
201 :     val trail = markUseSites(useSites, trail)
202 :     in trail end
203 : george 545
204 : leunga 624 fun cleanup [] = ()
205 :     | cleanup ((defs, i, nodes)::trail) =
206 :     (UA.update(defs, i, nodes); cleanup trail)
207 : george 545 (*
208 :     * Perform incremental liveness analysis on register v
209 :     * and compute the span
210 :     *)
211 : george 909 fun liveness(v, v' as NODE{uses, ...}, cellV) = let
212 :     val st = !stamp
213 : george 545 val _ = stamp := st + 1
214 :     fun foreachUseSite([], span) = span
215 : george 909 | foreachUseSite(u::uses, span) = let
216 :     val b = blockNum u
217 :     val i = instrNum u
218 :     val block as (_, CFG.BLOCK{freq, ...}) = UA.sub(blockTable, b)
219 :     val span =
220 :     if i = 0 then liveOutAtBlock(block, span) (* live out *)
221 :     else let
222 :     val f = !freq
223 :     val defs = UA.sub(defsTable, b)
224 :     in liveOutAtStmt(block, A.length defs, defs, i+1, f, span+f)
225 :     end
226 :     in foreachUseSite(uses, span)
227 : george 545 end
228 :    
229 : george 909 and visitPred((nid, _), span) =
230 : george 545 let fun foreachPred([], span) = span
231 : george 909 | foreachPred(nid::pred, span) = let
232 :     val span = liveOutAtBlock((nid, #node_info graph nid), span)
233 :     in foreachPred(pred, span)
234 :     end
235 :     in
236 :     foreachPred(#pred graph nid, span)
237 : george 545 end
238 :    
239 : leunga 624 and liveOutAtStmt(block, nDefs, defs, pos, freq, span) =
240 : george 545 (* v is live out *)
241 : leunga 624 if pos < nDefs then
242 : george 545 let fun foreachDef([], true) = span
243 :     | foreachDef([], false) =
244 : leunga 624 liveOutAtStmt(block, nDefs, defs,
245 :     pos+1, freq, span+freq)
246 : george 545 | foreachDef((d as NODE{number=r, ...})::ds, kill) =
247 :     if r = v then foreachDef(ds, true)
248 :     else (addEdge(d, v'); foreachDef(ds, kill))
249 :     in foreachDef(UA.sub(defs, pos), false)
250 :     end
251 :     else visitPred(block, span)
252 :    
253 : george 909 and liveOutAtBlock(block as (nid, CFG.BLOCK{freq, ...}), span) =
254 : george 545 (* v is live out at the current block *)
255 : george 909 if UA.sub(marked, nid) = st then span
256 :     else let
257 :     val defs = UA.sub(defsTable, nid)
258 :     in
259 :     UA.update(marked, nid, st);
260 :     liveOutAtStmt(block, A.length defs, defs, 1, !freq, span)
261 :     end
262 : leunga 624
263 : george 958 val useSites = uniq(!uses)
264 : leunga 624 val trail = initialize(v, v', useSites)
265 : george 545 val span = foreachUseSite (useSites, 0)
266 : leunga 624 val _ = cleanup trail
267 : george 909 in
268 :     span
269 : george 545 end
270 : george 705
271 : george 545 val newNodes = Core.newNodes G
272 : blume 733 val getnode = IntHashTable.lookup nodes
273 : monnier 467 val insnDefUse = Props.defUse cellkind
274 : jhr 900 val getCell = C.getCellsByKind cellkind
275 : monnier 467
276 : george 823 fun isDedicated r = dedicated r
277 : monnier 467
278 : monnier 498 (* Remove all dedicated or spilled registers from the list *)
279 : monnier 467 fun rmvDedicated regs =
280 :     let fun loop([], rs') = rs'
281 :     | loop(r::rs, rs') =
282 : george 889 let fun rmv(r as CB.CELL{col=ref(CB.PSEUDO), id, ...}) =
283 : george 823 if isDedicated(id) then loop(rs, rs') else loop(rs, r::rs')
284 : george 889 | rmv(CB.CELL{col=ref(CB.ALIASED r), ...}) = rmv r
285 :     | rmv(r as CB.CELL{col=ref(CB.MACHINE col), ...}) =
286 : leunga 744 if isDedicated col then loop(rs, rs')
287 :     else loop(rs, r::rs')
288 : george 889 | rmv(CB.CELL{col=ref(CB.SPILLED), ...}) = loop(rs,rs')
289 : leunga 744 in rmv r
290 :     end
291 : monnier 467 in loop(regs, []) end
292 :    
293 :     (*
294 :     * Create parallel move
295 :     *)
296 : leunga 624 fun mkMoves(insn, pt, dst, src, cost, mv, tmps) =
297 : monnier 467 if Props.moveInstr insn then
298 :     let val (dst, tmps) =
299 :     case (Props.moveTmpR insn, dst) of
300 :     (SOME r, _::dst) =>
301 :     (* Add a pseudo use for tmpR *)
302 : leunga 744 (case chase(getnode(colorOf r)) of
303 :     tmp as NODE{uses,defs=ref [d],...} =>
304 : george 958 let fun prev{block,insn}={block=block,insn=insn-1}
305 :     in (uses := [prev d]; (dst, tmp::tmps))
306 :     end
307 : leunga 744 | _ => error "mkMoves"
308 :     )
309 : monnier 467 | (_, dst) => (dst, tmps)
310 :     fun moves([], [], mv) = mv
311 :     | moves(d::ds, s::ss, mv) =
312 : leunga 744 let val (d, cd) = chaseCell d
313 :     val (s, cs) = chaseCell s
314 :     in if isDedicated cd orelse isDedicated cs
315 :     then moves(ds, ss, mv)
316 :     else if cd = cs then moves(ds, ss, mv)
317 :     else
318 :     let val _ =
319 :     addCopy(cs, {dst=d, pt=pt}::lookupCopy cs);
320 :     val dst = chase(getnode cd)
321 :     val src = chase(getnode cs)
322 :     in moves(ds, ss, MV{dst=dst, src=src,
323 :     status=ref WORKLIST,
324 :     hicount=ref 0,
325 :     (* kind=REG_TO_REG, *)
326 :     cost=cost}::mv
327 :     )
328 :     end
329 : monnier 467 end
330 :     | moves _ = error "moves"
331 :     in (moves(dst, src, mv), tmps) end
332 :     else (mv, tmps)
333 :    
334 : george 909
335 :    
336 : monnier 467 (* Add the nodes first *)
337 :     fun mkNodes([], mv, tmps) = (mv, tmps)
338 : george 909 | mkNodes((nid, blk)::blocks, mv, tmps) = let
339 :     val CFG.BLOCK{insns, freq=ref w, annotations, ...} = blk
340 :     val succ = #succ graph nid
341 :     val liveOut = CFG.liveOut blk
342 :     val dtab = A.sub(defsTable, nid)
343 :     fun scan([], pt, i, mv, tmps) = (pt, i, mv, tmps)
344 :     | scan(insn::rest, pt, i, mv, tmps) =
345 :     let val (d, u) = insnDefUse insn
346 :     val defs = rmvDedicated d
347 :     val uses = rmvDedicated u
348 :     val defs = newNodes{cost=w, pt=pt,
349 :     defs=defs, uses=uses}
350 :     val _ = UA.update(dtab, i, defs)
351 :     val (mv, tmps) =
352 :     mkMoves(insn, pt, d, u, w, mv, tmps)
353 : george 958 fun next{block,insn} = {block=block,insn=insn+1}
354 :     in scan(rest,next pt, i+1, mv, tmps)
355 : george 909 end
356 :     val (pt, i, mv, tmps) =
357 :     scan(!insns, progPt(nid,1), 1, mv, tmps)
358 :     in
359 :     (* If the block is escaping, then all liveout
360 :     * registers are considered used here.
361 :     *)
362 :     case succ
363 :     of [id] =>
364 :     if id = EXIT then let
365 :     val liveSet = rmvDedicated(
366 :     uniqCells(getCell(liveOut)))
367 :     in newNodes{cost=w, pt=progPt(nid, 0),
368 : monnier 467 defs=[], uses=liveSet}; ()
369 : george 909 end
370 :     else ()
371 :     | _ => ()
372 :     (*esac*);
373 :     mkNodes(blocks, mv, tmps)
374 : monnier 467 end
375 :    
376 :     (* Add the edges *)
377 :    
378 :     val (moves, tmps) = mkNodes(blocks, [], [])
379 : george 909 in
380 :     IntHashTable.appi
381 : leunga 624 (let val setSpan =
382 :     if isOn(mode,Core.COMPUTE_SPAN) then
383 : leunga 744 let val spanMap = IntHashTable.mkTable
384 :     (IntHashTable.numItems nodes, NotThere)
385 : blume 733 val setSpan = IntHashTable.insert spanMap
386 : leunga 624 val _ = span := SOME spanMap
387 :     in setSpan end
388 :     else fn _ => ()
389 : leunga 744 in fn (v, v' as NODE{cell, color, ...}) =>
390 :     let fun computeLiveness() =
391 :     setSpan(v, liveness(v, v', cell))
392 :     in case !color of
393 :     PSEUDO => computeLiveness()
394 :     | COLORED _ => computeLiveness()
395 :     | MEMREG _ => computeLiveness()
396 :     | _ => ()
397 :     end
398 : leunga 624 end
399 : monnier 498 ) nodes;
400 :     if isOn(Core.SAVE_COPY_TEMPS, mode) then copyTmps := tmps else ();
401 : monnier 467 rmPseudoUses tmps;
402 :     moves
403 : george 909 end (* buildIt *)
404 : monnier 467
405 :     (*
406 :     * Build the interference graph initially.
407 :     *)
408 : george 909 fun build(G, cellkind) = let
409 :     val moves = buildIt(cellkind, G)
410 :     val i2s = Int.toString
411 :     in
412 :     if !dump_size then let
413 :     val GRAPH{nodes, bitMatrix,...} = G
414 :     val insns =
415 :     foldr (fn ((_,CFG.BLOCK{insns,...}),n) => length(!insns) + n) 0 blocks
416 :     in
417 :     TextIO.output
418 :     (!MLRiscControl.debug_stream,
419 :     "RA #blocks="^i2s N ^
420 :     " #insns="^i2s insns ^
421 :     " #nodes="^i2s(IntHashTable.numItems nodes) ^
422 :     " #edges="^i2s(Core.BM.size(!bitMatrix)) ^
423 :     " #moves="^i2s(length moves)^"\n")
424 :     end
425 :     else ();
426 :     moves
427 : leunga 628 end
428 : george 705
429 : monnier 467 (*
430 :     * Rebuild the interference graph;
431 :     * We'll just do it from scratch for now.
432 :     *)
433 :     fun rebuild(cellkind, G) =
434 : leunga 579 (Core.clearNodes G;
435 : leunga 744 buildIt(cellkind, G)
436 : leunga 579 )
437 : monnier 467
438 :     (*
439 :     * Spill a set of nodes and rewrite the flowgraph
440 :     *)
441 : monnier 498 fun spill{copyInstr, spill, spillSrc, spillCopyTmp,
442 : leunga 744 reload, reloadDst, renameSrc, graph,
443 : monnier 467 cellkind, nodes=nodesToSpill} =
444 : leunga 579 let (* Remove the interference graph now *)
445 :     val _ = Core.clearGraph graph
446 :    
447 : monnier 467 (* maps program point to registers to be spilled *)
448 : george 958 val spillSet = G.PPtHashTable.mkTable(32, NotThere)
449 : monnier 467
450 :     (* maps program point to registers to be reloaded *)
451 : george 958 val reloadSet = G.PPtHashTable.mkTable(32, NotThere)
452 : monnier 467
453 :     (* maps program point to registers to be killed *)
454 : george 958 val killSet = G.PPtHashTable.mkTable(32, NotThere)
455 : monnier 467
456 : monnier 498 val spillRewrite = Spill.spillRewrite
457 :     { graph=graph,
458 :     spill=spill,
459 :     spillSrc=spillSrc,
460 :     spillCopyTmp=spillCopyTmp,
461 :     reload=reload,
462 :     reloadDst=reloadDst,
463 :     renameSrc=renameSrc,
464 :     copyInstr=copyInstr,
465 :     cellkind=cellkind,
466 :     spillSet=spillSet,
467 :     reloadSet=reloadSet,
468 :     killSet=killSet
469 :     }
470 :    
471 : monnier 467 (* set of basic blocks that are affected *)
472 : blume 733 val affectedBlocks = IntHashTable.mkTable(32, NotThere)
473 : monnier 467
474 : blume 733 val addAffectedBlocks = IntHashTable.insert affectedBlocks
475 : monnier 467
476 : george 705 fun ins set = let
477 : george 958 val add = G.PPtHashTable.insert set
478 :     val look = G.PPtHashTable.find set
479 : leunga 744 val look = fn r => case look r of SOME s => s | NONE => []
480 : leunga 579 fun enter(r, []) = ()
481 :     | enter(r, pt::pts) =
482 :     (add (pt, r::look pt);
483 :     addAffectedBlocks (blockNum pt, true);
484 :     enter(r, pts)
485 :     )
486 :     in enter
487 : monnier 467 end
488 :    
489 :     val insSpillSet = ins spillSet
490 :     val insReloadSet = ins reloadSet
491 :     val insKillSet =
492 : george 705 let
493 : george 958 val add = G.PPtHashTable.insert killSet
494 :     val look = G.PPtHashTable.find killSet
495 : leunga 744 val look = fn r => case look r of SOME s => s | NONE => []
496 : leunga 579 fun enter(r, []) = ()
497 :     | enter(r, pt::pts) = (add(pt, r::look pt); enter(r, pts))
498 : george 705 in enter
499 :     end
500 : monnier 467
501 : monnier 498 (* Mark all spill/reload locations *)
502 : leunga 744 fun markSpills(G.NODE{color, number, cell, defs, uses, ...}) =
503 : monnier 498 let fun spillIt(defs, uses) =
504 : leunga 744 (insSpillSet(cell, defs);
505 :     insReloadSet(cell, uses);
506 : monnier 498 (* Definitions but no use! *)
507 :     case uses of
508 : leunga 744 [] => insKillSet(cell, defs)
509 : monnier 498 | _ => ()
510 :     )
511 : george 705 val d = !defs
512 :     val u = !uses
513 :     in
514 :     case !color
515 :     of G.SPILLED => spillIt(d,u)
516 :     | G.SPILL_LOC _ => spillIt(d,u)
517 :     | G.MEMREG _ => spillIt(d,u)
518 :     | G.PSEUDO => spillIt(d,u)
519 :     | _ => ()
520 : monnier 498 end
521 : george 705 val _ = app markSpills nodesToSpill
522 : monnier 467
523 :     (* Rewrite all affected blocks *)
524 : george 909 fun rewriteAll (blknum, _) = let
525 :     val (_, CFG.BLOCK{insns as ref instrs, annotations, ...}) =
526 :     A.sub(blockTable, blknum)
527 :     val instrs =
528 :     spillRewrite{pt=progPt(blknum, length instrs),
529 :     instrs=instrs, annotations=annotations}
530 :     in
531 :     insns := instrs
532 :     end
533 : monnier 467
534 :    
535 : george 705 fun mark(G.NODE{color, ...}) =
536 :     (case !color
537 :     of PSEUDO => color := SPILLED
538 :     | SPILLED => ()
539 :     | SPILL_LOC _ => ()
540 :     | ALIASED _ => ()
541 :     | MEMREG _ => ()
542 :     | COLORED _ => error "mark: COLORED"
543 :     | REMOVED => error "mark: REMOVED"
544 :     (*esac*))
545 :     in
546 : blume 733 IntHashTable.appi rewriteAll affectedBlocks;
547 : george 705 app mark nodesToSpill;
548 :     rebuild(cellkind, graph)
549 :     end (* spill *)
550 :     in
551 :     { build = build,
552 :     spill = spill,
553 :     programPoint= fn{block,instr} => progPt(block,instr),
554 :     blockNum = blockNum,
555 :     instrNum = instrNum
556 :     }
557 :     end
558 :     end
559 : monnier 467

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