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 1053 - (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 984 (structure Asm : INSTRUCTION_EMITTER
14 :     structure Flowgraph : CONTROL_FLOW_GRAPH
15 :     where I = Asm.I
16 :     and P = Asm.S.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 : george 984 fun sayPseudo p = (say(CFG.P.toString p); say "\n")
69 :     val labToString = CFG.P.Client.AsmPseudoOps.defineLabel
70 :     fun dump (nid, CFG.BLOCK{labels, align, insns, ...}) =
71 :     (case !align of NONE => () | SOME p => sayPseudo p;
72 :     app (fn lab => say(labToString lab ^ "\n")) (!labels);
73 :     app emit (rev (!insns)))
74 :     val CFG.INFO{data, ...} = #graph_info graph
75 :     in
76 :     app dump (#nodes graph ());
77 :     app sayPseudo (rev(!data))
78 :    
79 : george 909 end
80 :    
81 : george 958 val annotations = CFG.annotations
82 :    
83 : george 909 val dummyBlock = CFG.newBlock(~1, ref 0)
84 :    
85 : monnier 498 fun x + y = Word.toIntX(Word.+(Word.fromInt x, Word.fromInt y))
86 : monnier 467
87 : george 958 val uniq = ListMergeSort.uniqueSort
88 :     (fn ({block=b1,insn=i1},{block=b2,insn=i2}) =>
89 :     case Int.compare(b1,b2) of
90 :     EQUAL => Int.compare(i1,i2)
91 :     | ord => ord)
92 :    
93 : george 909 fun services(cfg as Graph.GRAPH graph) = let
94 :     val CFG.INFO{annotations=clAnns, ...} = #graph_info graph
95 :     val blocks = #nodes graph ()
96 :     fun maxBlockId ((id, CFG.BLOCK _)::rest, curr) =
97 :     if id > curr then maxBlockId(rest, id) else maxBlockId(rest, curr)
98 :     | maxBlockId([], curr) = curr
99 : monnier 467
100 : george 909 val N = maxBlockId(blocks, #capacity graph ())
101 : monnier 467
102 : monnier 498 (*
103 :     * Construct program point
104 :     *)
105 : george 958 fun progPt(blknum, instrId) = {block=blknum, insn=instrId}
106 :     fun blockNum{block,insn} = block
107 :     fun instrNum{block,insn} = insn
108 : monnier 498
109 : george 545 (* blocks indexed by block id *)
110 : george 958 val blockTable = A.array(N, (#new_id graph (), dummyBlock))
111 : monnier 467
112 : george 1053 (* fill block table *)
113 :     val _ = List.app (fn b as (nid, _) => Array.update(blockTable, nid, b)) 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 :     (* Add the nodes first *)
335 :     fun mkNodes([], mv, tmps) = (mv, tmps)
336 : george 909 | mkNodes((nid, blk)::blocks, mv, tmps) = let
337 :     val CFG.BLOCK{insns, freq=ref w, annotations, ...} = blk
338 :     val succ = #succ graph nid
339 :     val liveOut = CFG.liveOut blk
340 :     val dtab = A.sub(defsTable, nid)
341 :     fun scan([], pt, i, mv, tmps) = (pt, i, mv, tmps)
342 :     | scan(insn::rest, pt, i, mv, tmps) =
343 :     let val (d, u) = insnDefUse insn
344 :     val defs = rmvDedicated d
345 :     val uses = rmvDedicated u
346 :     val defs = newNodes{cost=w, pt=pt,
347 :     defs=defs, uses=uses}
348 :     val _ = UA.update(dtab, i, defs)
349 :     val (mv, tmps) =
350 :     mkMoves(insn, pt, d, u, w, mv, tmps)
351 : george 958 fun next{block,insn} = {block=block,insn=insn+1}
352 :     in scan(rest,next pt, i+1, mv, tmps)
353 : george 909 end
354 :     val (pt, i, mv, tmps) =
355 :     scan(!insns, progPt(nid,1), 1, mv, tmps)
356 :     in
357 :     (* If the block is escaping, then all liveout
358 :     * registers are considered used here.
359 :     *)
360 :     case succ
361 :     of [id] =>
362 :     if id = EXIT then let
363 :     val liveSet = rmvDedicated(
364 :     uniqCells(getCell(liveOut)))
365 :     in newNodes{cost=w, pt=progPt(nid, 0),
366 : monnier 467 defs=[], uses=liveSet}; ()
367 : george 909 end
368 :     else ()
369 :     | _ => ()
370 :     (*esac*);
371 :     mkNodes(blocks, mv, tmps)
372 : monnier 467 end
373 :    
374 :     (* Add the edges *)
375 :    
376 :     val (moves, tmps) = mkNodes(blocks, [], [])
377 : george 909 in
378 :     IntHashTable.appi
379 : leunga 624 (let val setSpan =
380 :     if isOn(mode,Core.COMPUTE_SPAN) then
381 : leunga 744 let val spanMap = IntHashTable.mkTable
382 :     (IntHashTable.numItems nodes, NotThere)
383 : blume 733 val setSpan = IntHashTable.insert spanMap
384 : leunga 624 val _ = span := SOME spanMap
385 :     in setSpan end
386 :     else fn _ => ()
387 : leunga 744 in fn (v, v' as NODE{cell, color, ...}) =>
388 :     let fun computeLiveness() =
389 :     setSpan(v, liveness(v, v', cell))
390 :     in case !color of
391 :     PSEUDO => computeLiveness()
392 :     | COLORED _ => computeLiveness()
393 :     | MEMREG _ => computeLiveness()
394 :     | _ => ()
395 :     end
396 : leunga 624 end
397 : monnier 498 ) nodes;
398 :     if isOn(Core.SAVE_COPY_TEMPS, mode) then copyTmps := tmps else ();
399 : monnier 467 rmPseudoUses tmps;
400 :     moves
401 : george 909 end (* buildIt *)
402 : monnier 467
403 :     (*
404 :     * Build the interference graph initially.
405 :     *)
406 : george 909 fun build(G, cellkind) = let
407 :     val moves = buildIt(cellkind, G)
408 :     val i2s = Int.toString
409 :     in
410 :     if !dump_size then let
411 :     val GRAPH{nodes, bitMatrix,...} = G
412 :     val insns =
413 :     foldr (fn ((_,CFG.BLOCK{insns,...}),n) => length(!insns) + n) 0 blocks
414 :     in
415 :     TextIO.output
416 :     (!MLRiscControl.debug_stream,
417 :     "RA #blocks="^i2s N ^
418 :     " #insns="^i2s insns ^
419 :     " #nodes="^i2s(IntHashTable.numItems nodes) ^
420 :     " #edges="^i2s(Core.BM.size(!bitMatrix)) ^
421 :     " #moves="^i2s(length moves)^"\n")
422 :     end
423 :     else ();
424 :     moves
425 : leunga 628 end
426 : george 705
427 : monnier 467 (*
428 :     * Rebuild the interference graph;
429 :     * We'll just do it from scratch for now.
430 :     *)
431 :     fun rebuild(cellkind, G) =
432 : leunga 579 (Core.clearNodes G;
433 : leunga 744 buildIt(cellkind, G)
434 : leunga 579 )
435 : monnier 467
436 :     (*
437 :     * Spill a set of nodes and rewrite the flowgraph
438 :     *)
439 : monnier 498 fun spill{copyInstr, spill, spillSrc, spillCopyTmp,
440 : leunga 744 reload, reloadDst, renameSrc, graph,
441 : monnier 467 cellkind, nodes=nodesToSpill} =
442 : leunga 579 let (* Remove the interference graph now *)
443 :     val _ = Core.clearGraph graph
444 :    
445 : monnier 467 (* maps program point to registers to be spilled *)
446 : george 958 val spillSet = G.PPtHashTable.mkTable(32, NotThere)
447 : monnier 467
448 :     (* maps program point to registers to be reloaded *)
449 : george 958 val reloadSet = G.PPtHashTable.mkTable(32, NotThere)
450 : monnier 467
451 :     (* maps program point to registers to be killed *)
452 : george 958 val killSet = G.PPtHashTable.mkTable(32, NotThere)
453 : monnier 467
454 : monnier 498 val spillRewrite = Spill.spillRewrite
455 :     { graph=graph,
456 :     spill=spill,
457 :     spillSrc=spillSrc,
458 :     spillCopyTmp=spillCopyTmp,
459 :     reload=reload,
460 :     reloadDst=reloadDst,
461 :     renameSrc=renameSrc,
462 :     copyInstr=copyInstr,
463 :     cellkind=cellkind,
464 :     spillSet=spillSet,
465 :     reloadSet=reloadSet,
466 :     killSet=killSet
467 :     }
468 :    
469 : monnier 467 (* set of basic blocks that are affected *)
470 : blume 733 val affectedBlocks = IntHashTable.mkTable(32, NotThere)
471 : monnier 467
472 : blume 733 val addAffectedBlocks = IntHashTable.insert affectedBlocks
473 : monnier 467
474 : george 705 fun ins set = let
475 : george 958 val add = G.PPtHashTable.insert set
476 :     val look = G.PPtHashTable.find set
477 : leunga 744 val look = fn r => case look r of SOME s => s | NONE => []
478 : leunga 579 fun enter(r, []) = ()
479 :     | enter(r, pt::pts) =
480 :     (add (pt, r::look pt);
481 :     addAffectedBlocks (blockNum pt, true);
482 :     enter(r, pts)
483 :     )
484 :     in enter
485 : monnier 467 end
486 :    
487 :     val insSpillSet = ins spillSet
488 :     val insReloadSet = ins reloadSet
489 :     val insKillSet =
490 : george 705 let
491 : george 958 val add = G.PPtHashTable.insert killSet
492 :     val look = G.PPtHashTable.find killSet
493 : leunga 744 val look = fn r => case look r of SOME s => s | NONE => []
494 : leunga 579 fun enter(r, []) = ()
495 :     | enter(r, pt::pts) = (add(pt, r::look pt); enter(r, pts))
496 : george 705 in enter
497 :     end
498 : monnier 467
499 : monnier 498 (* Mark all spill/reload locations *)
500 : leunga 744 fun markSpills(G.NODE{color, number, cell, defs, uses, ...}) =
501 : monnier 498 let fun spillIt(defs, uses) =
502 : leunga 744 (insSpillSet(cell, defs);
503 :     insReloadSet(cell, uses);
504 : monnier 498 (* Definitions but no use! *)
505 :     case uses of
506 : leunga 744 [] => insKillSet(cell, defs)
507 : monnier 498 | _ => ()
508 :     )
509 : george 705 val d = !defs
510 :     val u = !uses
511 :     in
512 :     case !color
513 :     of G.SPILLED => spillIt(d,u)
514 :     | G.SPILL_LOC _ => spillIt(d,u)
515 :     | G.MEMREG _ => spillIt(d,u)
516 :     | G.PSEUDO => spillIt(d,u)
517 :     | _ => ()
518 : monnier 498 end
519 : george 705 val _ = app markSpills nodesToSpill
520 : monnier 467
521 :     (* Rewrite all affected blocks *)
522 : george 909 fun rewriteAll (blknum, _) = let
523 :     val (_, CFG.BLOCK{insns as ref instrs, annotations, ...}) =
524 :     A.sub(blockTable, blknum)
525 :     val instrs =
526 :     spillRewrite{pt=progPt(blknum, length instrs),
527 :     instrs=instrs, annotations=annotations}
528 :     in
529 :     insns := instrs
530 :     end
531 : monnier 467
532 :    
533 : george 705 fun mark(G.NODE{color, ...}) =
534 :     (case !color
535 :     of PSEUDO => color := SPILLED
536 :     | SPILLED => ()
537 :     | SPILL_LOC _ => ()
538 :     | ALIASED _ => ()
539 :     | MEMREG _ => ()
540 :     | COLORED _ => error "mark: COLORED"
541 :     | REMOVED => error "mark: REMOVED"
542 :     (*esac*))
543 :     in
544 : blume 733 IntHashTable.appi rewriteAll affectedBlocks;
545 : george 705 app mark nodesToSpill;
546 :     rebuild(cellkind, graph)
547 :     end (* spill *)
548 :     in
549 :     { build = build,
550 :     spill = spill,
551 :     programPoint= fn{block,instr} => progPt(block,instr),
552 :     blockNum = blockNum,
553 :     instrNum = instrNum
554 :     }
555 :     end
556 :     end
557 : monnier 467

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