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

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