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

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