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.84/ra/ra-iteratedCoalescing.sml
ViewVC logotype

Annotation of /MLRISC/releases/release-110.84/ra/ra-iteratedCoalescing.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 469 - (view) (download)
Original Path: sml/branches/SMLNJ/src/MLRISC/ra/ra-iteratedCoalescing.sml

1 : monnier 427 (** Graph coloring register allocation. graph
2 :     ** Implements the 'iterated register coalescing' scheme described
3 :     ** in POPL'96, and TOPLAS v18 #3, pp 325-353.
4 :     **)
5 :     (*
6 :     * This is a reorganization of the old iterated coalescing
7 :     * register allocator using a more modular implementation.
8 :     *
9 :     * --- Allen
10 :     *)
11 :     functor RegAllocator
12 :     (structure RaArch : RA_ARCH_PARAMS)
13 :     (structure RaUser : RA_USER_PARAMS
14 :     where I = RaArch.I
15 :     where B = RaArch.Liveness.F.B
16 :     ) : RA =
17 :     struct
18 :    
19 :     structure F = RaArch.Liveness.F
20 :     structure Core = RACore
21 :     structure G = Core.G
22 :     structure A = Array
23 :     structure I = RaArch.I
24 :     structure C = I.C
25 :     structure P = RaArch.InsnProps
26 :     structure SL = SortedList
27 :    
28 :     datatype mode = REGISTER_ALLOCATION | COPY_PROPAGATION
29 :    
30 :     open G
31 :    
32 :     fun error msg = MLRiscErrorMsg.error("IteratedCoalescing",msg)
33 :    
34 :     (*
35 :     * Debugging flags
36 :     *)
37 :     val cfg_before_ra = MLRiscControl.getFlag "dump-cfg-before-ra"
38 :     val cfg_after_ra = MLRiscControl.getFlag "dump-cfg-after-ra"
39 :     val cfg_after_spill = MLRiscControl.getFlag "dump-cfg-after-spilling"
40 :     val dump_graph = MLRiscControl.getFlag "dump-interference-graph"
41 :     val ra_count = MLRiscControl.getCounter "ra-count"
42 :     val rewrite = MLRiscControl.getCounter "ra-rewrites"
43 :    
44 :     (*
45 :     * Set of dedicated registers.
46 :     * Note: I'm using an array for testing for dedicated registers.
47 :     * Hopefully this is now a bit faster than before. -- Allen
48 :     *)
49 :     val spillRegSentinel = ~1 (* what is this? *)
50 :     val dedicated = SL.uniq(RaUser.dedicated)
51 :     val firstPseudoR = RaArch.firstPseudoR
52 :     val dedicatedRegs = A.array(firstPseudoR,false)
53 :     val _ = app (fn r => if r >= 0 andalso r < firstPseudoR then
54 :     A.update(dedicatedRegs,r,true) else ()) dedicated
55 :     fun isDedicated r = r < 0 orelse r < firstPseudoR andalso
56 :     Unsafe.Array.sub(dedicatedRegs,r)
57 :     (* Note: The following is no long necessary!
58 :     * Note: This function maintains the order of members in rset
59 :     * which is important when dealing with parallel copies.
60 :     *)
61 :     fun rmvDedicated rset =
62 :     let fun loop(x::xs, xs') = loop(xs, if isDedicated x then xs' else x::xs')
63 :     | loop([], xs') = xs'
64 :     in loop(rset,[])
65 :     end
66 :    
67 : monnier 469
68 : monnier 427 (* register mapping functions *)
69 :     fun uniqMap(f, l) = SL.uniq(map f l)
70 :    
71 :     fun prList (l:int list,msg:string) =
72 :     let fun pr [] = print "\n"
73 :     | pr (x::xs) = (print (Int.toString x ^ " "); pr xs)
74 :     in print msg; pr l
75 :     end
76 :    
77 :     (* debugging *)
78 :     fun printBlocks(blks, regmap, annotations) =
79 :     let val regmap = C.lookup regmap
80 :     val RaArch.AsmEmitter.S.STREAM{emit,...} =
81 :     AsmStream.withStream TextIO.stdOut
82 :     RaArch.AsmEmitter.makeStream annotations
83 :     val emit = emit regmap
84 :     fun prBlks([]) = print"\n"
85 :     | prBlks(F.BBLOCK{blknum,insns,liveOut,liveIn,
86 :     succ,pred,...}::blocks)=
87 :     let
88 :     fun regset cellset = map regmap (RaArch.regSet(cellset))
89 :     fun pr [] = prList(regset(!liveOut), "liveOut: ")
90 :     | pr (instr::rest) = (emit instr; pr rest)
91 :     fun blkNum(F.BBLOCK{blknum, ...},_) = blknum
92 :     | blkNum(F.ENTRY{blknum, ...},_) = blknum
93 :     | blkNum(F.EXIT{blknum, ...},_) = blknum
94 :     | blkNum _ = error "printBlocks.prBlks.blkNum"
95 :     in
96 :     print("BLOCK" ^ Int.toString blknum ^ "\n");
97 :     prList(regset (!liveIn), "LiveIn :");
98 :     prList(map blkNum (!pred),"predecessors: ");
99 :     case !insns of [] => print "empty instruction sequence\n"
100 :     | l => pr(rev l)
101 :     (*esac*);
102 :     prList(map blkNum (!succ),"successors: ");
103 :     prBlks(blocks)
104 :     end
105 :     | prBlks(F.LABEL lab::blocks) =
106 :     (print(Label.nameOf lab^":\n"); prBlks(blocks))
107 :     | prBlks(F.PSEUDO pOp::blocks) = (print (F.P.toString pOp); prBlks(blocks))
108 :     | prBlks(_::blocks) = prBlks(blocks)
109 :     in prBlks blks
110 :     end
111 :    
112 :     fun debug(flag, msg, blocks, regmap, annotations) =
113 :     if !flag then
114 :     (print ("------------------" ^ msg ^ " ----------------\n");
115 :     printBlocks(blocks,regmap,annotations))
116 :     else ()
117 :    
118 :    
119 :     (* Utility functions *)
120 :     fun newNode(num, col) =
121 :     NODE{number=num,
122 :     color=ref col,
123 :     degree=ref 0,
124 :     adj=ref [],
125 :     movecnt = ref 0,
126 :     movelist = ref []}
127 :    
128 :     fun nodeNumber(NODE{number, ...}) = number
129 :    
130 :     fun chase(NODE{color=ref(ALIASED r), ...}) = chase r
131 :     | chase x = x
132 :    
133 :     fun nodeMember(_, []) = false
134 :     | nodeMember(node as NODE{number=x, ...}, NODE{number=y,...}::rest) =
135 :     x = y orelse nodeMember(node, rest)
136 :    
137 :    
138 :     fun isMoveRelated(NODE{movecnt=ref 0, ...}) = false
139 :     | isMoveRelated _ = true
140 :    
141 :     exception PrevSpills
142 :     val prevSpills = Intmap.new(32,PrevSpills) : bool Intmap.intmap
143 :     val isSpilled = Intmap.mapWithDefault(prevSpills,false)
144 :     val enterSpilled = Intmap.add prevSpills
145 :     fun markAsSpilled r = enterSpilled(r,true)
146 :    
147 :     (*
148 :     * This is the new register allocator!
149 :     *)
150 :     fun ra mode prohibit
151 :     (cluster as F.CLUSTER{regmap,blocks,annotations=ref an,...}) =
152 :     if RaArch.numRegs() = 0 then cluster
153 :     else
154 :     let
155 :     val _ = Intmap.clear prevSpills
156 :     val _ = app (fn (i,j) =>
157 :     let fun loop(i) =
158 :     if i <= j then (markAsSpilled i; loop(i+1)) else ()
159 :     in loop i end) prohibit
160 :    
161 :     (* number of blocks *)
162 :     val numBlocks = foldr (fn (F.BBLOCK _,n) => n + 1 | (_,n) => n) 0 blocks
163 :    
164 :     val blockDU = A.array(numBlocks,[] : (node list * node list) list)
165 :     val cblocks = A.array(numBlocks,F.LABEL(Label.newLabel ""))
166 :     val numOfBlocks = A.length cblocks
167 :    
168 :     (* remainInfo: blocks where spill nodes are defined and used. *)
169 :     type info = int list Intmap.intmap
170 :     val remainInfo : (info * info) option ref = ref NONE
171 :    
172 :     fun cleanupSpillInfo() = remainInfo := NONE
173 :    
174 :     (**
175 :     ** Build blockDU and cblocks.
176 :     ** This is done once per RA.
177 :     **)
178 :     fun initialize() =
179 :     let val nodes = Intmap.new(32,Nodes)
180 :     fun mkNode i =
181 :     newNode(i, if i < firstPseudoR then COLORED(i) else PSEUDO)
182 :     val lookupNodes = Intmap.map nodes
183 :     val enterNodes = Intmap.add nodes
184 :     fun newnode n =
185 :     lookupNodes n
186 :     handle _ =>
187 :     let val node = mkNode n
188 :     in enterNodes (n, node); node
189 :     end
190 :     fun blockDefUse((b as F.BBLOCK{insns,liveOut,succ, ...})::blks, n) =
191 :     let fun insnDefUse insn =
192 :     let val (d,u) = RaArch.defUse insn
193 :     fun rmv [] = []
194 :     | rmv (l as [x]) =
195 :     if isDedicated x then [] else [newnode x]
196 :     | rmv set = map newnode (rmvDedicated set)
197 :     in (rmv d, rmv u) end
198 :     in Unsafe.Array.update(cblocks, n, b);
199 :     Unsafe.Array.update(blockDU, n, map insnDefUse (!insns));
200 :     case !succ of
201 :     [(F.EXIT _,_)] =>
202 :     app (fn i => (newnode i; ()))
203 :     (rmvDedicated(RaArch.regSet(!liveOut)))
204 :     | _ => ();
205 :     blockDefUse(blks, n+1)
206 :     end
207 :     | blockDefUse(_::blks, n) = blockDefUse(blks, n)
208 :     | blockDefUse([], _) = ()
209 :    
210 :     (* if copy propagation was done prior to register allocation
211 :     * then some nodes may already be aliased.
212 :     *)
213 :     fun updateAliases() =
214 :     let val alias = Intmap.mapInt regmap
215 :     fun fixup(num, NODE{color, ...}) =
216 :     if num < firstPseudoR then ()
217 :     else let val reg = alias num
218 :     in if reg=num then () else
219 :     color := ALIASED(newnode reg)
220 :     end
221 :     in Intmap.app fixup nodes end
222 :     in blockDefUse(blocks,0);
223 :     updateAliases();
224 :     nodes
225 :     end
226 :    
227 :     (**
228 :     ** Run liveness analysis
229 :     **)
230 : monnier 469 fun liveness(nodes,blocks) =
231 : monnier 427 let val getnode = Intmap.map nodes
232 :     fun regmap i =
233 :     let val node = getnode i
234 :     in case node
235 :     of NODE{color= ref (COLORED r), ...} => r
236 :     | NODE{color=ref PSEUDO, ...} => nodeNumber node
237 :     | NODE{color=ref(ALIASED r), ...} => nodeNumber(chase node)
238 :     | _ => error "liveness.regmap"
239 :     end handle _ => i (* XXX *)
240 :     in RaArch.Liveness.liveness(blocks, regmap)
241 :     end
242 :    
243 : monnier 469 (*
244 :     * Given a set of registers, remove all spilled and dedicated nodes.
245 :     * NOTE: we assume that dedicated registers are NEVER entered into
246 :     * nodes Intmap.
247 :     *)
248 :     fun collectNodes(getnode,regs) =
249 :     let fun loop([],xs) = xs
250 :     | loop(r::rs,xs) =
251 :     (case chase(getnode r) of
252 :     NODE{color=ref(COLORED ~1),...} => loop(rs,xs)
253 :     | x => loop(rs,x::xs)
254 :     ) handle _ => loop(rs,xs) (* dedicated *)
255 :     in loop(regs,[]) end
256 : monnier 427
257 : monnier 469
258 : monnier 427 (**
259 :     ** Builds the interference graph and initialMove list
260 :     **)
261 :     fun build(graph as GRAPH{bitMatrix,nodes,...}) =
262 :     let (* The movecnt field is used to (lazily) record members in the
263 :     * live set. Deleted members are removed during an
264 :     * addEdgeForallLive operation.
265 :     *)
266 :     val getnode = Intmap.map nodes
267 :     val chaseReg = chase o getnode
268 :     val chaseRegs = map chaseReg
269 :     val addEdge = Core.addEdge graph
270 :     val member = BM.member bitMatrix
271 :     fun memBitMatrix(NODE{number=x,...}, NODE{number=y,...}) =
272 :     member (if x<y then (x, y) else (y, x))
273 :    
274 : monnier 469 fun delete(NODE{movecnt, ...}) = movecnt:=0
275 : monnier 427 fun insert((node as NODE{movecnt as ref 0, ...})::rest, live) =
276 :     (movecnt:=1; insert(rest, node::live))
277 :     | insert(_::rest, live) = insert(rest, live)
278 :     | insert([], live) = live
279 :     fun addEdgeForallLive([], live) = live
280 :     | addEdgeForallLive(d::ds, live) =
281 :     let fun f ([], pruned) = pruned
282 :     | f ((n as NODE{movecnt as ref 1, ...})::rest, pruned) =
283 :     (addEdge(d, n); f(rest, n::pruned))
284 :     | f (_::rest, pruned) = f(rest, pruned)
285 :     in addEdgeForallLive(ds, f(live, []))
286 :     end
287 :     fun forallBlocks(~1, mvs) = mvs
288 :     | forallBlocks(n, mvs) =
289 :     let val F.BBLOCK{insns, liveOut, ...} = A.sub(cblocks, n)
290 :     val bdu = A.sub(blockDU, n)
291 :     fun doBlock([], _, live, mvs) =
292 :     (app (fn NODE{movecnt, ...} => movecnt := 0) live;
293 :     forallBlocks(n-1, mvs))
294 :     | doBlock(instr::rest, (def',use')::bdu, live', mvs) =
295 :     let val def = map chase def'
296 :     val use = map chase use'
297 :     (* move instructions are treated specially *)
298 :     (* There is a subtle interaction between parallel
299 :     moves and interference graph construction. When we
300 :     have {d1, ... dn} <- {s1, ... sn} and liveOut we
301 :     should make di interfere with:
302 :    
303 :     liveOut U {d1, ... dn} U ({s1, ... sn} \ {si})
304 :    
305 :     This is not currently done.
306 :     *)
307 :     fun zip(d::defs, u::uses) =
308 :     if isDedicated d orelse
309 :     isDedicated u then zip(defs, uses)
310 :     else
311 :     let val d as NODE{number=x,...} = chaseReg d
312 :     val u as NODE{number=y,...} = chaseReg u
313 :     in if x = y then zip(defs,uses)
314 :     else
315 :     MV{dst=d, src=u, status=ref WORKLIST}::
316 :     zip(defs, uses)
317 :     end
318 :     | zip([],[]) = mvs
319 :    
320 :     (* Assumes that the move temporary
321 :     * if present is always the
322 :     * first thing on the definition list.
323 :     *)
324 :     val moves =
325 :     if P.moveInstr instr then
326 :     let val (defs,uses) = RaArch.defUse instr
327 :     val defs =
328 :     case defs of
329 :     [] => []
330 :     | _::rest => case P.moveTmpR instr of
331 :     SOME _ => rest
332 :     | NONE => defs
333 :     in zip(defs,uses)
334 :     end
335 :     else mvs
336 :     val live =
337 :     if length def > 1 then
338 :     addEdgeForallLive(def, insert(def, live'))
339 :     else addEdgeForallLive(def, live')
340 :     in app delete def;
341 :     doBlock(rest, bdu, insert(use,live), moves)
342 :     end
343 : monnier 469 val lout = collectNodes(getnode,RaArch.regSet(!liveOut))
344 : monnier 427 in doBlock(!insns, bdu, insert(lout, []), mvs)
345 :     end
346 :     (* Filter moves that already have an interference.
347 :     * Also initialize the movelist and movecnt fields at this time.
348 :     *)
349 :     fun filter [] = []
350 :     | filter (MV{src=NODE{color=ref(COLORED _), ...},
351 :     dst=NODE{color=ref(COLORED _), ...}, ...}::rest) =
352 :     filter rest
353 :     | filter ((mv as MV{src, dst, ...})::rest) =
354 :     if memBitMatrix(src, dst) then filter rest
355 :     else let
356 :     fun info(u as NODE{color=ref PSEUDO, movecnt, movelist,...}) =
357 :     (movelist := mv :: !movelist; movecnt := 1 + !movecnt)
358 :     | info _ = ()
359 :     in info src; info dst; mv::filter rest
360 :     end
361 :     in filter(forallBlocks(numOfBlocks-1, []))
362 :     end (* build *)
363 :    
364 :     (**
365 :     ** select a spill node
366 :     **)
367 :     fun selectSpill (GRAPH{nodes,spillFlag,K,...},
368 :     {simplifyWkl, spillWkl, stack, moveWkl, freezeWkl}) =
369 :     let (* duCount: compute the def/use points of spilled nodes. *)
370 :     val getnode = Intmap.map nodes
371 :     val chaseReg = chase o getnode
372 :     fun duCount spillable =
373 :     let val size = length spillable
374 :     exception Info
375 :     val defInfo : info = Intmap.new(size,Info)
376 :     val useInfo : info = Intmap.new(size,Info)
377 :     val addDef = Intmap.add defInfo
378 :     val addUse = Intmap.add useInfo
379 :     val getDefs = Intmap.mapWithDefault (defInfo,[])
380 :     val getUses = Intmap.mapWithDefault (useInfo,[])
381 :    
382 :     (* doblocks ---
383 :     * updates the defInfo and useInfo tables to indicate
384 :     * the blocks where spillable live ranges are defined and used.
385 :     *)
386 :     fun doblocks ~1 = ()
387 :     | doblocks blknum =
388 :     let val bdu = A.sub(blockDU,blknum)
389 :     fun iter [] = ()
390 :     | iter((def',use')::rest) =
391 :     let val def = uniqMap(nodeNumber o chase, def')
392 :     val use = uniqMap(nodeNumber o chase, use')
393 :     fun updateDef n = addDef(n, blknum::getDefs n)
394 :     fun updateUse n = addUse(n, blknum::getUses n)
395 :     in app updateDef (SL.intersect(def,spillable));
396 :     app updateUse (SL.intersect(use,spillable));
397 :     iter rest
398 :     end
399 :     in iter(bdu);
400 :     doblocks(blknum-1)
401 :     end
402 :    
403 :     (* If a node is live going out of an block terminated by
404 :     * an escaping branch, it may be necessary to reload the
405 :     * the node just prior to taking the branch. We will therefore
406 :     * record this as a definition of the node.
407 :     *)
408 :     fun doBBlocks n =
409 :     let val F.BBLOCK{blknum,liveIn,liveOut,succ,...} =
410 :     A.sub(cblocks,n)
411 :     val liveout =
412 : monnier 469 uniqMap (nodeNumber,
413 :     collectNodes(getnode,RaArch.regSet(!liveOut)))
414 : monnier 427 in case !succ of
415 :     [(F.EXIT _,_)] =>
416 :     (case SL.intersect(spillable,liveout)
417 :     of [] => doBBlocks(n+1)
418 :     | some =>
419 :     (app (fn n => addDef(n, blknum::getDefs n)) some;
420 :     doBBlocks (n+1))
421 :     (*esac*))
422 :     | _ => doBBlocks(n+1)
423 :     (*esac*)
424 :     end (* doBBlocks *)
425 :     in doblocks (numOfBlocks - 1);
426 :     doBBlocks 0 handle _ => ();
427 :     (defInfo,useInfo)
428 :     end (* duCount *)
429 :    
430 :     (* Since the spillWkl is not actively maintained, the set of
431 :     * spillable nodes for which def/use info is needed is a subset
432 :     * of spillWkl.
433 :     *)
434 :     fun remainingNodes() =
435 :     let fun prune [] = []
436 :     | prune((n as NODE{color=ref PSEUDO, ...}) ::ns) =
437 :     n::prune ns
438 :     | prune((n as NODE{color=ref(ALIASED _), ...})::ns) =
439 :     prune(chase n::ns)
440 :     | prune(_::ns) = prune ns
441 :     in case !remainInfo of
442 :     SOME info => prune spillWkl
443 :     | NONE =>
444 :     let (* first time spilling *)
445 :     val spillable = prune ( spillWkl)
446 :     in remainInfo :=
447 :     (case spillable
448 :     of [] => NONE
449 :     | _ => SOME(duCount(uniqMap(nodeNumber, spillable)))
450 :     (*esac*));
451 :     spillable
452 :     end
453 :     end
454 :    
455 :     (** apply the Chaitin heuristic to find the spill node **)
456 :     fun chaitinHeuristic(spillable) =
457 :     let val infinity = 1000000.0
458 :     val infinityi= 1000000
459 :     val SOME(dinfo,uinfo) = !remainInfo
460 :     val getdInfo = Intmap.map dinfo
461 :     val getuInfo = Intmap.map uinfo
462 :     fun coreDump [] = ()
463 :     | coreDump ((node as NODE{number, degree, adj, ...})::rest) =
464 :     (print(concat
465 :     ["number =", Int.toString number,
466 :     " node =", Int.toString(nodeNumber (chase node)),
467 :     " degree = ", Int.toString (!degree),
468 :     " adj = "]);
469 :     prList(map (nodeNumber o chase) (!adj), "");
470 :     print "\n";
471 :     coreDump rest)
472 :     fun iter([],node,cmin) =
473 :     if node <> ~1 then
474 :     (if !cfg_after_spill then
475 :     print("Spilling node "^Int.toString node^
476 :     " cost="^Real.toString cmin^"\n") else ();
477 :     getnode node
478 :     )
479 :     else (coreDump spillable;
480 :     prList(Intmap.keys prevSpills,"PrevSpills: ");
481 :     error "chaitinHeuristic.iter")
482 :     | iter((node as NODE{number, degree, ...})::rest,cnode,cmin) =
483 :     let
484 :     (* An exeception will be raised if the node is defined
485 :     * but not used. This is not a suitable node to spill.
486 :     *)
487 :     val cost =
488 :     (length(getdInfo number) handle _ => 0) +
489 :     (length(getuInfo number) handle _ => infinityi)
490 :     val heuristic = real cost / real (!degree)
491 :     in
492 :     if heuristic < cmin andalso not(isSpilled number)
493 :     then iter(rest, number, heuristic)
494 :     else iter(rest, cnode, cmin)
495 :     end
496 :     in iter(spillable, ~1, infinity)
497 :     end
498 :     in case mode of
499 :     COPY_PROPAGATION =>
500 :     {spillWkl=[], simplifyWkl=[], stack=[], moveWkl=[], freezeWkl=[]}
501 :     | REGISTER_ALLOCATION =>
502 :     (case remainingNodes() of
503 :     [] => {spillWkl=[], simplifyWkl=simplifyWkl,
504 :     stack=stack, moveWkl=moveWkl, freezeWkl=freezeWkl}
505 :     | spillWkl =>
506 :     let val spillNode = chaitinHeuristic(spillWkl)
507 :     val simpWkl =
508 :     if isMoveRelated spillNode
509 :     then spillNode::Core.wklFromFrozen(K,spillNode)
510 :     else [spillNode]
511 :     in spillFlag:=true;
512 :     {simplifyWkl=simpWkl,
513 :     spillWkl = spillWkl,
514 :     freezeWkl = freezeWkl,
515 :     stack = stack,
516 :     moveWkl = moveWkl}
517 :     end
518 :     (*esac*))
519 :     end (* selectSpill *)
520 :    
521 :    
522 :     (** rewriteGraph(spillList) -
523 :     ** an unsuccessful round of coloring has taken
524 :     ** place with nodes in spillList having been spilled. The
525 :     ** flowgraph must be updated and the entire process repeated.
526 :     **)
527 :     fun rewriteGraph (graph as GRAPH{nodes,...}, spillList) =
528 :     let val _ = rewrite := !rewrite + 1
529 :     val SOME(dInfo,uInfo) = !remainInfo
530 :     val getnode = Intmap.map nodes
531 :     val enternode = Intmap.add nodes
532 :     val chaseReg = chase o getnode
533 :     val chaseRegs = map chaseReg
534 :    
535 :     fun newdu (d, u) =
536 :     let fun rmv([],nodes) = nodes
537 :     | rmv(r::rs,nodes) =
538 :     let val node = chase(getnode r) handle _ =>
539 :     let val n = newNode(r, PSEUDO)
540 :     in enternode (r, n); n
541 :     end
542 :     in rmv(rs,node::nodes) end
543 :     fun rmv' rs = rmv(rmvDedicated rs,[])
544 :     in (rmv' d, rmv' u)
545 :     end (* newdu *)
546 :    
547 :     val defUse = newdu o RaArch.defUse
548 :    
549 :     (* blocks where spill code is required for node n *)
550 :     fun affectedBlocks node =
551 :     let val n = nodeNumber node
552 :     in SL.merge(SL.uniq(Intmap.mapWithDefault (dInfo,[]) n),
553 :     SL.uniq(Intmap.mapWithDefault (uInfo,[]) n))
554 :     end
555 :    
556 :     val mapr = C.lookup regmap
557 :     val markProh = app markAsSpilled
558 :    
559 :     (* Insert spill code into the affected blocks *)
560 :     fun doBlocks([], _) = ()
561 :     | doBlocks(blknum::rest, node) =
562 :     let val F.BBLOCK{insns, liveOut, name, ...} =
563 :     A.sub(cblocks, blknum)
564 :     val bdu = A.sub(blockDU, blknum)
565 : monnier 469 val liveOut = collectNodes(getnode,RaArch.regSet(!liveOut))
566 : monnier 427 val spillReg = nodeNumber node
567 :    
568 :     (* note: the instruction list start out in reverse order. *)
569 :     fun doInstrs([], [], newI, newBDU) =
570 :     (rev newI, rev newBDU)
571 :     | doInstrs(instr::rest, (du as (d,u))::bDU, newI, newBDU) =
572 :     let val defs=map chase d
573 :     val uses=map chase u
574 :    
575 :     fun outputInstrs(instrs, I, bDU) =
576 :     {newI=instrs @ I,
577 :     newBDU=(map defUse instrs) @ bDU}
578 :    
579 :     fun newReloadCopy(rds, rss) =
580 :     let fun f(rd::rds, rs::rss, rds', rss') =
581 :     if mapr rs = spillReg
582 :     then(([rd], [rs]), (rds@rds', rss@rss'))
583 :     else f(rds, rss, rd::rds', rs::rss')
584 :     | f([], [], _, _) = error "newReloadCopy.f"
585 :     in f(rds, rss, [], []) end
586 :    
587 :     (* insert reloading code and continue *)
588 :     fun reloadInstr(instr, du, newI, newBDU)=
589 :     let val {code, proh} =
590 :     RaUser.reload{regmap=mapr, instr=instr,
591 :     reg=spillReg, id=name}
592 :     val _ = markProh proh
593 :     val {newI, newBDU} =
594 :     outputInstrs(code, newI, newBDU)
595 :     in doInstrs(rest, bDU, newI, newBDU) end
596 :    
597 :     (* insert reload code for copies. *)
598 :     fun reloadCopy(du, instr, newI, newBDU) =
599 :     if nodeMember(node, #2 du) then
600 :     (case (P.moveDstSrc(instr))
601 :     of ([d], [u]) =>
602 :     reloadInstr(instr,du,newI,newBDU)
603 :     | (defs, uses) =>
604 :     let val (mv, cpy) = newReloadCopy(defs, uses)
605 :     val cpyInstr = RaUser.copyInstr(cpy, instr)
606 :     val duCpy = defUse cpyInstr
607 :     val {code, proh} =
608 :     RaUser.reload
609 :     {regmap=mapr,
610 :     instr=RaUser.copyInstr(mv, instr),
611 :     reg=spillReg, id=name}
612 :     val _ = markProh proh
613 :     val {newI, newBDU} =
614 :     outputInstrs(code, newI, newBDU)
615 :     in (* recurse to deal with multiple uses *)
616 :     reloadCopy(duCpy, cpyInstr, newI, newBDU)
617 :     end
618 :     (*esac*))
619 :     else
620 :     doInstrs(rest, bDU, instr::newI, du::newBDU)
621 :    
622 :     (* insert reload code *)
623 :     fun reload(du as (d,u), instr, newI, newBDU) =
624 :     if P.moveInstr(instr) then
625 :     reloadCopy(du, instr, newI, newBDU)
626 :     else if nodeMember(node, u) then
627 :     let val {code, proh} =
628 :     RaUser.reload{regmap=mapr, instr=instr,
629 :     reg=spillReg, id=name}
630 :     val {newI, newBDU} =
631 :     outputInstrs(code, newI, newBDU)
632 :     val _ = markProh proh
633 :     in doInstrs(rest, bDU, newI, newBDU)
634 :     end
635 :     else
636 :     doInstrs(rest, bDU, instr::newI, du::newBDU)
637 :    
638 :    
639 :     fun spillInstr(instr, newI, newBDU) =
640 :     let val {code, instr, proh} =
641 :     RaUser.spill{regmap=mapr, instr=instr, reg=spillReg, id=name}
642 :     val _ = markProh proh
643 :     val {newI, newBDU} = outputInstrs(code, newI, newBDU)
644 :     in case instr
645 :     of NONE => doInstrs(rest, bDU, newI, newBDU)
646 :     | SOME instr =>
647 :     reload(defUse instr, instr, newI, newBDU)
648 :     end
649 :    
650 :     fun spillCopy() =
651 :     let (* Note:: There is a guarantee that the node
652 :     * will never be aliased to another register.
653 :     *)
654 :     fun newSpillCopy(rds, rss) =
655 :     let fun f(rd::rds, rs::rss, rds', rss') =
656 :     if mapr rd = spillReg then
657 :     (([rd], [rs]), (rds@rds', rss@rss'))
658 :     else f(rds, rss, rd::rds', rs::rss')
659 :     | f([], [], _, _) = error "newSpillCopy"
660 :     in f(rds, rss, [], []) end
661 :    
662 :     fun spillCpyDst() =
663 :     let val (mv, cpy) = newSpillCopy(P.moveDstSrc(instr))
664 :     val (newI, newBDU) =
665 :     (case cpy
666 :     of ([],[]) => (newI, newBDU)
667 :     | _ => let val cpyInstr = RaUser.copyInstr(cpy, instr)
668 :     in (cpyInstr::newI, defUse cpyInstr::newBDU)
669 :     end
670 :     (*esac*))
671 :     val instr = RaUser.copyInstr(mv, instr)
672 :     in spillInstr(instr, newI, newBDU)
673 :     end
674 :     in case P.moveTmpR instr
675 :     of NONE => spillCpyDst()
676 :     | SOME r =>
677 :     if mapr r=spillReg
678 :     then spillInstr(instr, newI, newBDU)
679 :     else spillCpyDst()
680 :     (*esac*)
681 :     end (* spillCopy *)
682 :     in (* insert spill code *)
683 :     if nodeMember(node, defs) then
684 :     if P.moveInstr instr then spillCopy()
685 :     else spillInstr(instr, newI, newBDU)
686 :     else
687 :     reload((defs,uses), instr, newI, newBDU)
688 :     end
689 :    
690 :     (* special action if the last instruction is an escaping
691 :     * branch and the node is live across the branch.
692 :     * We discover if the node needs to be spilled or reloaded.
693 :     *)
694 :     fun blockEnd(instrs as instr::rest, bDU as du::bdu) =
695 :     let fun escapes [] = false
696 :     | escapes (P.ESCAPES::_) = true
697 :     | escapes (_::targets) = escapes targets
698 :     in if nodeMember(node, liveOut) then
699 :     (case P.instrKind instr
700 :     of P.IK_JUMP =>
701 :     if escapes(P.branchTargets instr) then let
702 :     val {code,...} =
703 :     RaUser.reload{regmap=mapr, instr=instr, reg=spillReg, id=name}
704 :     val reloadDU = map defUse code
705 :     in (rev code@rest, rev reloadDU@bdu)
706 :     end
707 :     else (instrs, bDU)
708 :     | _ => (instrs, bDU)
709 :     (*esac*))
710 :     else (instrs, bDU)
711 :     end
712 :     | blockEnd([],[]) = ([], [])
713 :    
714 :     val (newInstrs, newBdu) =
715 :     doInstrs(!insns, bdu, [], [])
716 :     val (newInstrs, newBdu) = blockEnd(newInstrs, newBdu)
717 :     in insns := newInstrs;
718 :     A.update(blockDU, blknum, newBdu);
719 :     doBlocks(rest, node)
720 :     end (* doBlocks *)
721 :    
722 :     (* The optimistic coloring selection may come up with a node
723 :     * that has already been spilled. Must be careful not to spill
724 :     * it twice.
725 :     *)
726 :     fun glue [] = ()
727 :     | glue((node as NODE{number, color, ...})::rest) =
728 :     (if not(isSpilled number) then
729 :     (doBlocks(affectedBlocks node, node)
730 :     before color := COLORED(spillRegSentinel)
731 :     )
732 :     else ();
733 :     glue rest
734 :     )
735 :    
736 :     (* redoAlgorithm
737 :     * -- rerun graph coloring but note that spilling may
738 :     * have introduced new registers.
739 :     *)
740 :     fun redoAlgorithm(spillList) =
741 :     let val _ = app (markAsSpilled o nodeNumber) spillList
742 :     fun init(_, NODE{color=ref PSEUDO, degree, adj,
743 :     movecnt, movelist, ...}) =
744 :     (degree:=0; adj := []; movecnt:=0; movelist:=[])
745 :     | init _ = ()
746 :     in Intmap.app init nodes
747 :     end
748 :     in glue(spillList);
749 :     redoAlgorithm(spillList);
750 :     debug(cfg_after_spill,"after spilling",blocks,regmap,an)
751 :     end (* rewriteGraph *)
752 :    
753 :     (**
754 :     ** The main driver
755 :     **)
756 :     fun graphColoring(nodes) =
757 :     let (* Create an empty interference graph *)
758 :     val graph = newGraph
759 :     {nodes=nodes,
760 :     K=RaUser.nFreeRegs,
761 :     numRegs=RaArch.numRegs(),
762 :     regmap=regmap,
763 :     getreg=RaUser.getreg,
764 :     firstPseudoR=firstPseudoR
765 :     }
766 :     val moves = build graph (* build interference graph *)
767 :     val worklists = Core.makeWorkLists graph moves
768 :     val simpCoalFz = Core.simplifyCoalesceFreeze graph
769 :    
770 :     (* Note: freezeWkl or spillWkl are maintained lazily. *)
771 :     fun iterate wl =
772 :     case simpCoalFz wl of
773 :     wl as {spillWkl= _::_, ...} => iterate(selectSpill(graph,wl))
774 :     | wl =>
775 :     (case mode of
776 :     COPY_PROPAGATION => Core.finishCP graph
777 :     | REGISTER_ALLOCATION =>
778 :     (case Core.optimisticSpilling graph wl of
779 :     [] => Core.finishRA graph
780 :     | spills => (rewriteGraph(graph,spills);
781 :     graphColoring(nodes))
782 :     )
783 :     )
784 :     in if !dump_graph then Core.dumpGraph graph else ();
785 :     debug(cfg_before_ra,"before register allocation",blocks,regmap,an);
786 :     iterate worklists
787 :     end
788 : monnier 469 val nodes = initialize()
789 :     in liveness(nodes,blocks); (* run liveness analysis *)
790 :     graphColoring(nodes);
791 : monnier 427 debug(cfg_after_ra,"after register allocation",blocks,regmap,an);
792 :     ra_count := !ra_count + 1;
793 :     cluster
794 :     end
795 :    
796 :     end

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