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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1125 - (view) (download)

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