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/trunk/ra/mem-ra.sml
ViewVC logotype

Annotation of /MLRISC/trunk/ra/mem-ra.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 733 - (view) (download)
Original Path: sml/trunk/src/MLRISC/ra/mem-ra.sml

1 : george 554 (*
2 :     * This module implements the memory coalescing capability of the
3 :     * register allocator.
4 :     *)
5 :     functor MemoryRA(Flowgraph : RA_FLOWGRAPH) : RA_FLOWGRAPH =
6 :     struct
7 :    
8 :     structure G = RAGraph
9 :     structure A = Array
10 :     structure W = Word
11 :    
12 : leunga 585 val debug = false
13 :    
14 : george 554 open G RACore
15 :    
16 :     val ra_spill_coal = MLRiscControl.getCounter "ra-spill-coalescing"
17 :     val ra_spill_prop = MLRiscControl.getCounter "ra-spill-propagation"
18 :    
19 :     local
20 :    
21 :     fun error msg = MLRiscErrorMsg.error("RACore", msg)
22 :    
23 :     (* No overflow checking necessary here *)
24 :     fun x + y = W.toIntX(W.+(W.fromInt x, W.fromInt y))
25 :     fun x - y = W.toIntX(W.-(W.fromInt x, W.fromInt y))
26 :    
27 :     fun concat([], b) = b
28 :     | concat(x::a, b) = concat(a, x::b)
29 :    
30 :     fun chase(NODE{color=ref(ALIASED n),...}) = chase n
31 :     | chase n = n
32 :    
33 :     in
34 :    
35 :     fun isOn(flag,mask) = Word.andb(flag,mask) <> 0w0
36 :    
37 : george 705 fun isMemLoc(SPILLED) = true
38 :     | isMemLoc(SPILL_LOC _) = true
39 :     | isMemLoc(MEMREG _) = true
40 :     | isMemLoc _ = false
41 : george 554 (*
42 :     * Spill coalescing.
43 :     * Coalesce non-interfering moves between spilled nodes,
44 :     * in non-increasing order of move cost.
45 :     *)
46 : george 705 fun spillCoalescing(GRAPH{bitMatrix, ...}) = let
47 :     val member = BM.member(!bitMatrix)
48 : george 554 val addEdge = BM.add(!bitMatrix)
49 : george 705 in
50 :     fn nodesToSpill => let
51 :     (* Find moves between two spilled nodes *)
52 :     fun collectMoves([], mv') = mv'
53 :     | collectMoves(NODE{movelist, color, ...}::ns, mv') = let
54 :     fun ins([], mv') = collectMoves(ns, mv')
55 :     | ins(MV{status=ref(COALESCED | CONSTRAINED), ...}::mvs, mv') =
56 :     ins(mvs, mv')
57 :     | ins((mv as MV{dst, src, ...})::mvs, mv') = let
58 :     val NODE{color=ref cd, number=nd, ...} = chase dst
59 :     val NODE{color=ref cs, number=ns, ...} = chase src
60 :     in
61 :     if nd=ns then ins(mvs, mv')
62 :     else (case (cd, cs)
63 :     of (MEMREG _, MEMREG _) => ins(mvs, mv')
64 :     | _ =>
65 :     if isMemLoc cd andalso isMemLoc cs then
66 :     ins(mvs, MV.add(mv, mv'))
67 :     else
68 :     ins(mvs, mv')
69 :     (*esac*))
70 :     end
71 :     in
72 :     if isMemLoc (!color) then ins(!movelist, mv')
73 :     else collectMoves(ns, mv')
74 :     end
75 : george 554
76 : george 705 (* Coalesce moves between two spilled nodes *)
77 :     fun coalesceMoves(MV.EMPTY) = ()
78 :     | coalesceMoves(MV.TREE(MV{dst, src, cost, ...}, _, l, r)) =
79 :     let val dst as NODE{color=colorDst, ...} = chase dst
80 :     val src = chase src
81 : george 554
82 : george 705 (* Make sure that dst has not been assigned a spill location *)
83 :     val (dst, src) =
84 :     case !colorDst of SPILLED => (dst, src) | _ => (src, dst)
85 : george 554
86 : george 705 val dst as NODE{number=d, color=colorDst, adj=adjDst,
87 :     defs=defsDst, uses=usesDst, ...} = dst
88 :     val src as NODE{number=s, color=colorSrc, adj=adjSrc,
89 :     defs=defsSrc, uses=usesSrc, ...} = src
90 :    
91 :     (* combine adjacency lists *)
92 :     fun union([], adjSrc) = adjSrc
93 :     | union((n as NODE{color, adj=adjT,
94 :     number=t, ...})::adjDst, adjSrc) =
95 :     (case !color of
96 :     (SPILLED | MEMREG _ | SPILL_LOC _ | PSEUDO) =>
97 :     if addEdge(s, t) then
98 :     (adjT := src :: !adjT; union(adjDst, n::adjSrc))
99 :     else union(adjDst, adjSrc)
100 :     | COLORED _ =>
101 :     if addEdge(s, t) then union(adjDst, n::adjSrc)
102 :     else union(adjDst, adjSrc)
103 :     | _ => union(adjDst, adjSrc)
104 :     )
105 :    
106 :     val mvs = MV.merge(l,r)
107 :    
108 :     fun f() =
109 :     ((* print(Int.toString d ^"<->"^Int.toString s^"\n");*)
110 :     ra_spill_coal := !ra_spill_coal + 1;
111 :     (* unify *)
112 :     colorDst := ALIASED src;
113 :     adjSrc := union(!adjDst, !adjSrc);
114 :     defsSrc := concat(!defsDst, !defsSrc);
115 :     usesSrc := concat(!usesDst, !usesSrc);
116 :     coalesceMoves mvs)
117 :     in
118 :     if d = s then coalesceMoves mvs
119 :     else (case !colorDst
120 :     of MEMREG _ => coalesceMoves mvs
121 :     | SPILLED =>
122 :     if member(d,s) then coalesceMoves mvs else f()
123 :     | SPILL_LOC loc =>
124 :     if member(d,s) then coalesceMoves mvs else f()
125 :     | _ => error "coalesceMoves"
126 :     (*esac*))
127 :     end
128 :     in coalesceMoves(collectMoves(nodesToSpill, MV.EMPTY))
129 : george 554 end
130 : george 705 end (*spillCoalesce*)
131 : george 554
132 :     (*
133 :     * Spill propagation.
134 : leunga 585 * This one uses a simple local lookahead algorithm.
135 : george 554 *)
136 :     fun spillPropagation(G as GRAPH{bitMatrix, memRegs, ...}) nodesToSpill =
137 :     let val spillCoalescing = spillCoalescing G
138 :     exception SpillProp
139 : blume 733 val visited =
140 :     IntHashTable.mkTable(32, SpillProp) : bool IntHashTable.hash_table
141 :     fun hasBeenVisited i = getOpt (IntHashTable.find visited i, false)
142 :     val markAsVisited = IntHashTable.insert visited
143 : george 554 val member = BM.member(!bitMatrix)
144 :    
145 :     (* compute savings due to spill coalescing.
146 :     * The move list must be associated with a colorable node.
147 :     * The pinned flag is to prevent the spill node from coalescing
148 :     * two different fixed memory registers.
149 :     *)
150 : leunga 585 fun coalescingSavings
151 :     (node as NODE{number=me, movelist, pri=ref spillcost, ...}) =
152 :     let fun interferes(x,[]) = false
153 :     | interferes(x,NODE{number=y, ...}::ns) =
154 :     x = y orelse member(x,y) orelse interferes(x, ns)
155 :    
156 :     fun moveSavings([], pinned, total) = (pinned, total+total)
157 :     | moveSavings(MV{status=ref(CONSTRAINED | COALESCED), ...}::mvs,
158 :     pinned, total) =
159 :     moveSavings(mvs, pinned, total)
160 :     | moveSavings(MV{dst, src, cost, ...}::mvs, pinned, total) =
161 :     let val NODE{number=d, color=dstCol, ...} = chase dst
162 :     val NODE{number=s, color=srcCol, ...} = chase src
163 :    
164 :     (* How much can be saved by coalescing with the memory
165 :     * location x.
166 :     *)
167 :     fun savings(x) =
168 :     if member(d, s) then
169 :     (if debug then print "interfere\n" else ();
170 :     moveSavings(mvs, pinned, total))
171 :     else if x = ~1 then
172 :     (if debug then print (Int.toString cost^"\n") else ();
173 :     moveSavings(mvs, pinned, total+cost))
174 :     else if pinned >= 0 andalso pinned <> x then
175 :     (* already coalesced with another mem reg *)
176 :     (if debug then print "pinned\n" else ();
177 :     moveSavings(mvs, pinned, total))
178 :     else
179 :     (if debug then print (Int.toString cost^"\n") else ();
180 :     moveSavings(mvs, x, total+cost))
181 :    
182 :     val _ = if debug then
183 :     (print("Savings "^Int.toString d^" <-> "^
184 :     Int.toString s^"=")
185 :     ) else ()
186 :     in if d = s then
187 :     (if debug then print "0 (trivial)\n" else ();
188 :     moveSavings(mvs, pinned, total)
189 :     )
190 :     else
191 :     case (!dstCol, !srcCol) of
192 : george 705 (SPILLED, PSEUDO) => savings(~1)
193 :     | (MEMREG m, PSEUDO) => savings(m)
194 :     | (SPILL_LOC s, PSEUDO) => savings(~s)
195 :     | (PSEUDO, SPILLED) => savings(~1)
196 :     | (PSEUDO, MEMREG m) => savings(m)
197 :     | (PSEUDO, SPILL_LOC s) => savings(~s)
198 : leunga 585 | _ => (if debug then print "0 (other)\n" else ();
199 :     moveSavings(mvs, pinned, total))
200 :     end
201 :    
202 :     (* Find initial budget *)
203 :     val _ = if debug then
204 :     print("Trying to propagate "^Int.toString me^
205 :     " spill cost="^Int.toString spillcost^"\n")
206 :     else ()
207 :    
208 :     val (pinned, savings) = moveSavings(!movelist, ~1, 0)
209 :     val budget = spillcost - savings
210 :     val S = [node]
211 :    
212 :     (* Find lookahead nodes *)
213 :     fun lookaheads([], L) = L
214 :     | lookaheads(MV{cost, dst, src, ...}::mvs, L) =
215 :     let val dst as NODE{number=d, ...} = chase dst
216 :     val src as NODE{number=s, ...} = chase src
217 :     fun check(n, node as NODE{color=ref PSEUDO, ...}) =
218 :     if n = me orelse member(n, me) then
219 :     lookaheads(mvs, L)
220 :     else
221 :     add(n, node, L, [])
222 :     | check _ = lookaheads(mvs, L)
223 :     and add(x, x', (l as (c,n' as NODE{number=y, ...}))::L, L') =
224 :     if x = y then
225 :     lookaheads(mvs, (cost+c, n')::List.revAppend(L', L))
226 :     else add(x, x', L, l::L')
227 :     | add(x, x', [], L') =
228 :     lookaheads(mvs, (cost, x')::L')
229 :     in if d = me then check(s, src) else check(d, dst)
230 :     end
231 :    
232 :     (* Now try to improve it by also propagating the lookahead nodes *)
233 :     fun improve([], pinned, budget, S) = (budget, S)
234 :     | improve((cost, node as NODE{number=n, movelist, pri, ...})::L,
235 :     pinned, budget, S) =
236 :     if interferes(n, S) then
237 :     (if debug then
238 :     print ("Excluding "^Int.toString n^" (interferes)\n")
239 :     else ();
240 :     improve(L, pinned, budget, S))
241 :     else
242 :     let val (pinned', savings) = moveSavings(!movelist, pinned, 0)
243 :     val defUseSavings = cost+cost
244 :     val spillcost = !pri
245 :     val budget' = budget - savings - defUseSavings + spillcost
246 :     in if budget' <= budget then
247 :     (if debug then print ("Including "^Int.toString n^"\n")
248 :     else ();
249 :     improve(L, pinned', budget', node::S)
250 :     )
251 : george 554 else
252 : leunga 585 (if debug then print ("Excluding "^Int.toString n^"\n")
253 :     else ();
254 :     improve(L, pinned, budget, S))
255 :     end
256 : george 554
257 : leunga 585 in if budget <= 0 then (budget, S)
258 :     else improve(lookaheads(!movelist, []), pinned, budget, S)
259 :     end
260 :    
261 : george 554 (* Insert all spillable neighbors onto the worklist *)
262 :     fun insert([], worklist) = worklist
263 :     | insert((node as NODE{color=ref PSEUDO, number, ...})::adj, worklist) =
264 :     if hasBeenVisited number
265 :     then insert(adj, worklist)
266 :     else (markAsVisited (number, true);
267 :     insert(adj, node::worklist))
268 :     | insert(_::adj, worklist) = insert(adj, worklist)
269 :    
270 : leunga 585 fun insertAll([], worklist) = worklist
271 :     | insertAll(NODE{adj, ...}::nodes, worklist) =
272 :     insertAll(nodes, insert(!adj, worklist))
273 :    
274 : george 705 val marker = SPILLED
275 : george 554
276 :     (* Process all nodes from the worklist *)
277 :     fun propagate([], spilled) = spilled
278 : leunga 585 | propagate((node as NODE{color=ref PSEUDO, ...})::worklist,
279 : george 554 spilled) =
280 : leunga 585 let val (budget, S) = coalescingSavings(node)
281 :     fun spillNodes([]) = ()
282 :     | spillNodes(NODE{color, ...}::nodes) =
283 :     (ra_spill_prop := !ra_spill_prop + 1;
284 :     color := marker; (* spill the node *)
285 :     spillNodes nodes
286 :     )
287 :    
288 :     in if budget <= 0
289 : george 554 then (* propagate spill *)
290 : leunga 585 (if debug then
291 :     (print("Propagating ");
292 :     app (fn NODE{number=x, ...} => print(Int.toString x^" "))
293 :     S;
294 :     print "\n")
295 :     else ();
296 :     spillNodes S;
297 : george 554 (* run spill coalescing *)
298 : leunga 585 spillCoalescing S;
299 :     propagate(insertAll(S, worklist), List.revAppend(S,spilled))
300 : george 554 )
301 :     else
302 :     propagate(worklist, spilled)
303 :     end
304 :     | propagate(_::worklist, spilled) =
305 :     propagate(worklist, spilled)
306 :    
307 :     (* Initialize worklist *)
308 :     fun init([], worklist) = worklist
309 : george 705 | init(NODE{adj, color=ref(c), ...}::rest, worklist) =
310 :     if isMemLoc (c) then
311 :     init(rest, insert(!adj, worklist))
312 :     else
313 :     init(rest, worklist)
314 : george 554
315 :     (*
316 :     * Iterate between spill coalescing and propagation
317 :     *)
318 :     fun iterate(spillWorkList, spilled) =
319 :     let (* run one round of coalescing first *)
320 :     val _ = spillCoalescing spillWorkList
321 :     val propagationWorkList = init(spillWorkList, [])
322 :     (* iterate on our own spill nodes *)
323 :     val spilled = propagate(propagationWorkList, spilled)
324 :     (* try the memory registers too *)
325 :     val spilled = propagate(!memRegs, spilled)
326 :     in spilled
327 :     end
328 :    
329 :     in iterate(nodesToSpill, nodesToSpill)
330 :     end
331 :    
332 : leunga 585
333 : george 554 (*
334 :     * Spill coloring.
335 :     * Assign logical spill locations to all the spill nodes.
336 :     *
337 :     * IMPORTANT BUG FIX:
338 :     * Spilled copy temporaries are assigned its own set of colors and
339 :     * cannot share with another other nodes. They can share colors with
340 :     * themselves however.
341 : george 705 *
342 :     * spillLoc is the first available (logical) spill location.
343 : george 554 *)
344 :    
345 : george 705 fun spillColoring(GRAPH{spillLoc, copyTmps, mode, ...}) nodesToSpill = let
346 :     val proh = A.array(length nodesToSpill, ~1)
347 :     val firstColor= !spillLoc
348 : george 554
349 : george 705 fun colorCopyTmps(tmps) = let
350 :     fun spillTmp(NODE{color as ref(SPILLED), ...}, found) =
351 :     (color := SPILL_LOC(firstColor); true)
352 :     | spillTmp(_, found) = found
353 :     in
354 :     if List.foldl spillTmp false tmps then
355 :     (spillLoc := !spillLoc + 1; firstColor + 1)
356 :     else firstColor
357 :     end
358 : george 554
359 : george 705 (* color the copy temporaries first *)
360 :     val firstColor =
361 :     if isOn(mode, RACore.HAS_PARALLEL_COPIES) then
362 :     colorCopyTmps(!copyTmps)
363 :     else firstColor
364 : george 554
365 : george 705 fun selectColor([], _, lastLoc) = (spillLoc := lastLoc)
366 :     | selectColor(NODE{color as ref(SPILLED), number, adj, ...}::nodes,
367 :     currLoc, lastLoc) =
368 :     let
369 :     fun neighbors(NODE{color=ref(SPILL_LOC s), ...}) =
370 :     A.update(proh, s - firstColor, number)
371 :     | neighbors(NODE{color=ref(ALIASED n), ...}) = neighbors n
372 :     | neighbors _ = ()
373 :    
374 :     val _ = app neighbors (!adj)
375 :    
376 :     fun findColor(loc, startingPt) =
377 :     if loc = lastLoc then findColor(firstColor, startingPt)
378 :     else if A.sub(proh, loc-firstColor) <> number then (loc, lastLoc)
379 :     else if loc = startingPt then (lastLoc, lastLoc+1)
380 :     else findColor(loc+1, startingPt)
381 :    
382 :     val (loc, lastLoc) = findColor(currLoc + 1, currLoc)
383 :    
384 :     in
385 :     color := SPILL_LOC(loc); (* mark with color *)
386 :     selectColor(nodes, loc, lastLoc)
387 :     end
388 :     | selectColor(_::nodes, currLoc, lastLoc) =
389 :     selectColor(nodes, currLoc, lastLoc)
390 :     in
391 :     (* color the rest of the spilled nodes *)
392 :     selectColor(nodesToSpill, firstColor, !spillLoc + 1)
393 :     end (* spillColoring *)
394 :    
395 : george 554 end (* local *)
396 :    
397 :     structure F = Flowgraph
398 :    
399 :     open F
400 :    
401 :     val SPILL_COALESCING = 0wx100
402 :     val SPILL_COLORING = 0wx200
403 :     val SPILL_PROPAGATION = 0wx400
404 :    
405 :     (*
406 :     * New services that also perform memory allocation
407 :     *)
408 :     fun services f =
409 :     let val {build, spill=spillMethod,
410 :     blockNum, instrNum, programPoint} = F.services f
411 :    
412 :     (* Mark nodes that are immediately aliased to mem regs;
413 :     * These are nodes that need also to be spilled
414 :     *)
415 :     fun markMemRegs [] = ()
416 : george 705 | markMemRegs(NODE{number=r,
417 :     color as ref(ALIASED
418 :     (NODE{color=ref(col), ...})), ...}::ns) =
419 :     (case col of MEMREG _ => color := col | _ => ();
420 :     markMemRegs(ns))
421 : george 554 | markMemRegs(_::ns) = markMemRegs ns
422 :    
423 :     (*
424 :     * Actual spill phase.
425 :     * Perform the memory coalescing phases first, before doing an
426 :     * actual spill.
427 :     *)
428 :     fun spillIt{graph = G as GRAPH{mode, ...}, nodes,
429 :     copyInstr, spill, spillSrc, spillCopyTmp,
430 :     reload, reloadDst, renameSrc, cellkind} =
431 :     let val nodes = if isOn(mode,SPILL_PROPAGATION) then
432 :     spillPropagation G nodes else nodes
433 :     val _ = if isOn(mode,SPILL_COALESCING) then
434 :     spillCoalescing G nodes else ()
435 :     val _ = if isOn(mode,SPILL_COLORING) then
436 :     spillColoring G nodes else ()
437 :     val _ = if isOn(mode,SPILL_COALESCING+SPILL_PROPAGATION)
438 :     then markMemRegs nodes else ()
439 :     in spillMethod
440 :     {graph=G, nodes=nodes, copyInstr=copyInstr,
441 :     spill=spill, spillSrc=spillSrc, spillCopyTmp=spillCopyTmp,
442 :     reload=reload, reloadDst=reloadDst,
443 :     renameSrc=renameSrc, cellkind=cellkind}
444 :     end
445 :     in {build=build, spill=spillIt, programPoint=programPoint,
446 :     blockNum=blockNum, instrNum=instrNum}
447 :     end
448 :    
449 :     end

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