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 554 - (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 :     open G RACore
13 :    
14 :     val ra_spill_coal = MLRiscControl.getCounter "ra-spill-coalescing"
15 :     val ra_spill_prop = MLRiscControl.getCounter "ra-spill-propagation"
16 :    
17 :     local
18 :    
19 :     fun error msg = MLRiscErrorMsg.error("RACore", msg)
20 :    
21 :     (* No overflow checking necessary here *)
22 :     fun x + y = W.toIntX(W.+(W.fromInt x, W.fromInt y))
23 :     fun x - y = W.toIntX(W.-(W.fromInt x, W.fromInt y))
24 :    
25 :     fun concat([], b) = b
26 :     | concat(x::a, b) = concat(a, x::b)
27 :    
28 :     fun chase(NODE{color=ref(ALIASED n),...}) = chase n
29 :     | chase n = n
30 :    
31 :     in
32 :    
33 :     fun isOn(flag,mask) = Word.andb(flag,mask) <> 0w0
34 :    
35 :     (*
36 :     * Spill coalescing.
37 :     * Coalesce non-interfering moves between spilled nodes,
38 :     * in non-increasing order of move cost.
39 :     *)
40 :     fun spillCoalescing(GRAPH{bitMatrix, ...}) =
41 :     let val member = BM.member(!bitMatrix)
42 :     val addEdge = BM.add(!bitMatrix)
43 :     in fn nodesToSpill =>
44 :     let
45 :     (* Find moves between two spilled nodes *)
46 :     fun collectMoves([], mv') = mv'
47 :     | collectMoves(NODE{movelist, color=ref(SPILLED _), ...}::ns, mv') =
48 :     let fun ins([], mv') = collectMoves(ns, mv')
49 :     | ins(MV{status=ref(COALESCED | CONSTRAINED), ...}::mvs,
50 :     mv') = ins(mvs, mv')
51 :     | ins((mv as MV{dst, src, ...})::mvs, mv') =
52 :     (case (chase dst, chase src) of
53 :     (NODE{color=ref(SPILLED x), number=d, ...},
54 :     NODE{color=ref(SPILLED y), number=s, ...}) =>
55 :     if d = s orelse (* trival move *)
56 :     (x >= 0 andalso y >= 0) (* both are fixed *)
57 :     then ins(mvs, mv')
58 :     else ins(mvs, MV.add(mv, mv'))
59 :     | _ => ins(mvs, mv')
60 :     )
61 :     in ins(!movelist, mv') end
62 :     | collectMoves(_::ns, mv') = collectMoves(ns, mv')
63 :    
64 :     val mvs = collectMoves(nodesToSpill, MV.EMPTY)
65 :    
66 :     (* Coalesce moves between two spilled nodes *)
67 :     fun coalesceMoves(MV.EMPTY) = ()
68 :     | coalesceMoves(MV.TREE(MV{dst, src, cost, ...}, _, l, r)) =
69 :     let val dst as NODE{color=colorDst, ...} = chase dst
70 :     val src = chase src
71 :    
72 :     (* Make sure that dst is the non-mem reg node *)
73 :     val (dst, src) =
74 :     case !colorDst of
75 :     SPILLED ~1 => (dst, src)
76 :     | _ => (src, dst)
77 :    
78 :     val dst as NODE{number=d, color=colorDst, adj=adjDst,
79 :     defs=defsDst, uses=usesDst, ...} = dst
80 :     val src as NODE{number=s, color=colorSrc, adj=adjSrc,
81 :     defs=defsSrc, uses=usesSrc, ...} = src
82 :    
83 :     (* combine adjacency lists *)
84 :     fun union([], adjSrc) = adjSrc
85 :     | union((n as NODE{color, adj=adjT,
86 :     number=t, ...})::adjDst, adjSrc) =
87 :     (case !color of
88 :     (SPILLED _ | PSEUDO) =>
89 :     if addEdge(s, t) then
90 :     (adjT := src :: !adjT; union(adjDst, n::adjSrc))
91 :     else union(adjDst, adjSrc)
92 :     | COLORED _ =>
93 :     if addEdge(s, t) then union(adjDst, n::adjSrc)
94 :     else union(adjDst, adjSrc)
95 :     | _ => union(adjDst, adjSrc)
96 :     )
97 :     val mvs = MV.merge(l,r)
98 :     in if d = s then (* trivial *)
99 :     coalesceMoves mvs
100 :     else
101 :     (case !colorDst of
102 :     SPILLED x =>
103 :     if x >= 0 orelse (* both dst and src are mem regs *)
104 :     member(d, s) (* they interfere *)
105 :     then
106 :     ((* print("Bad "^Int.toString d ^
107 :     "<->"^Int.toString s^"\n")*))
108 :     else
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 :     if x >= 0 then ()
115 :     else
116 :     (defsSrc := concat(!defsDst, !defsSrc);
117 :     usesSrc := concat(!usesDst, !usesSrc))
118 :     )
119 :     | _ => error "coalesceMoves";
120 :     coalesceMoves mvs
121 :     )
122 :     end
123 :     in coalesceMoves mvs
124 :     end
125 :     end
126 :    
127 :     (*
128 :     * Spill propagation.
129 :     *)
130 :     fun spillPropagation(G as GRAPH{bitMatrix, memRegs, ...}) nodesToSpill =
131 :     let val spillCoalescing = spillCoalescing G
132 :     exception SpillProp
133 :     val visited = Intmap.new(32, SpillProp) : bool Intmap.intmap
134 :     val hasBeenVisited = Intmap.mapWithDefault (visited, false)
135 :     val markAsVisited = Intmap.add visited
136 :     val member = BM.member(!bitMatrix)
137 :    
138 :     (* compute savings due to spill coalescing.
139 :     * The move list must be associated with a colorable node.
140 :     * The pinned flag is to prevent the spill node from coalescing
141 :     * two different fixed memory registers.
142 :     *)
143 :     fun coalescingSavings([], pinned, sc) = (pinned, sc+sc)
144 :     | coalescingSavings(MV{status=ref(CONSTRAINED | COALESCED), ...}::mvs,
145 :     pinned, sc) = coalescingSavings(mvs, pinned, sc)
146 :     | coalescingSavings(MV{dst, src, cost, ...}::mvs, pinned, sc) =
147 :     let val NODE{number=d, color=dstCol, ...} = chase dst
148 :     val NODE{number=s, color=srcCol, ...} = chase src
149 :     fun savings(x) =
150 :     if member(d, s) then coalescingSavings(mvs, pinned, sc)
151 :     else if x = ~1 then coalescingSavings(mvs, pinned, sc+cost)
152 :     else if pinned >= 0 andalso pinned <> x then
153 :     (* already coalesced with another mem reg *)
154 :     coalescingSavings(mvs, pinned, sc)
155 :     else
156 :     (* coalescingSavings(mvs, x, sc+cost) *) (* XXX *)
157 :     coalescingSavings(mvs, x, sc+cost)
158 :     in if d = s then
159 :     coalescingSavings(mvs, pinned, sc)
160 :     else
161 :     case (!dstCol, !srcCol) of
162 :     (SPILLED x, PSEUDO) => savings(x)
163 :     | (PSEUDO, SPILLED x) => savings(x)
164 :     | _ => coalescingSavings(mvs, pinned, sc)
165 :     end
166 :    
167 :     (* Insert all spillable neighbors onto the worklist *)
168 :     fun insert([], worklist) = worklist
169 :     | insert((node as NODE{color=ref PSEUDO, number, ...})::adj, worklist) =
170 :     if hasBeenVisited number
171 :     then insert(adj, worklist)
172 :     else (markAsVisited (number, true);
173 :     insert(adj, node::worklist))
174 :     | insert(_::adj, worklist) = insert(adj, worklist)
175 :    
176 :     val marker = SPILLED(~1)
177 :    
178 :     (* Process all nodes from the worklist *)
179 :     fun propagate([], spilled) = spilled
180 :     | propagate((node as NODE{color as ref PSEUDO,
181 :     pri=ref spillcost, number,
182 :     adj, movelist, ...})::worklist,
183 :     spilled) =
184 :     let val (pinned, savings) = coalescingSavings(!movelist, ~1, 0)
185 :     in (* if (if pinned >= 0 then savings > spillcost
186 :     else savings >= spillcost) *) (* XXX *)
187 :     if savings >= spillcost
188 :     then (* propagate spill *)
189 :     (ra_spill_prop := !ra_spill_prop + 1;
190 :     color := marker; (* spill the node *)
191 :     (* print("Propagating "^Int.toString number^" "^
192 :     "savings="^Int.toString(savings)^
193 :     " cost="^Int.toString spillcost^"\n"); *)
194 :     (* run spill coalescing *)
195 :     spillCoalescing [node];
196 :     propagate(insert(!adj, worklist), node::spilled)
197 :     )
198 :     else
199 :     propagate(worklist, spilled)
200 :     end
201 :     | propagate(_::worklist, spilled) =
202 :     propagate(worklist, spilled)
203 :    
204 :     (* Initialize worklist *)
205 :     fun init([], worklist) = worklist
206 :     | init(NODE{adj, color=ref(SPILLED _), ...}::rest, worklist) =
207 :     init(rest, insert(!adj, worklist))
208 :     | init(_::rest, worklist) = init(rest, worklist)
209 :    
210 :     (*
211 :     * Iterate between spill coalescing and propagation
212 :     *)
213 :     fun iterate(spillWorkList, spilled) =
214 :     let (* run one round of coalescing first *)
215 :     val _ = spillCoalescing spillWorkList
216 :     val propagationWorkList = init(spillWorkList, [])
217 :     (* iterate on our own spill nodes *)
218 :     val spilled = propagate(propagationWorkList, spilled)
219 :     (* try the memory registers too *)
220 :     val spilled = propagate(!memRegs, spilled)
221 :     in spilled
222 :     end
223 :    
224 :     in iterate(nodesToSpill, nodesToSpill)
225 :     end
226 :    
227 :     (*
228 :     * Spill coloring.
229 :     * Assign logical spill locations to all the spill nodes.
230 :     *
231 :     * IMPORTANT BUG FIX:
232 :     * Spilled copy temporaries are assigned its own set of colors and
233 :     * cannot share with another other nodes. They can share colors with
234 :     * themselves however.
235 :     *)
236 :     fun spillColoring(GRAPH{spillLoc, copyTmps, mode, ...}) nodesToSpill =
237 :     let val proh = A.array(length nodesToSpill, ~1)
238 :     val firstLoc = !spillLoc
239 :     val _ = spillLoc := firstLoc - 1 (* allocate one location first *)
240 :    
241 :     fun colorCopyTmps(tmps) =
242 :     let fun loop([], found) = found
243 :     | loop(NODE{color as ref(SPILLED ~1), ...}::tmps, found) =
244 :     (color := SPILLED firstLoc; loop(tmps, true))
245 :     | loop(_::tmps, found) = loop(tmps, found)
246 :     in if loop(tmps, false) then
247 :     (spillLoc := !spillLoc - 1; firstLoc - 1)
248 :     else firstLoc
249 :     end
250 :    
251 :     fun selectColor([], firstColor, currLoc) = ()
252 :     | selectColor(NODE{color as ref(SPILLED ~1), number, adj, ...}::nodes,
253 :     firstColor, currLoc) =
254 :     let fun neighbors [] = ()
255 :     | neighbors(n::ns) =
256 :     let fun mark(NODE{color=ref(SPILLED loc), ...}) =
257 :     (if loc >= ~1 then () (* no location yet *)
258 :     else A.update(proh, firstLoc - loc, number);
259 :     neighbors ns
260 :     )
261 :     | mark(NODE{color=ref(ALIASED n), ...}) = mark n
262 :     | mark _ = neighbors ns
263 :     in mark n end
264 :     val _ = neighbors(!adj)
265 :     fun findColor(loc, startingPoint) =
266 :     let val loc = if loc < firstColor then !spillLoc + 1 else loc
267 :     in if A.sub(proh, firstLoc - loc) <> number then loc (* ok *)
268 :     else if loc = startingPoint then (* new location *)
269 :     let val loc = !spillLoc
270 :     in spillLoc := loc - 1; loc end
271 :     else findColor(loc - 1, startingPoint)
272 :     end
273 :     val currLoc = if currLoc < firstColor then !spillLoc + 1
274 :     else currLoc
275 :     val loc = findColor(currLoc, currLoc)
276 :     (* val _ = print("Spill("^Int.toString number^")="^
277 :     Int.toString loc^"\n") *)
278 :     in color := SPILLED loc; (* mark with color *)
279 :     selectColor(nodes, firstColor, loc - 1)
280 :     end
281 :     | selectColor(_::nodes, firstColor, currLoc) =
282 :     selectColor(nodes, firstColor, currLoc)
283 :    
284 :     (* color the copy temporaries first *)
285 :     val firstColor = if isOn(mode, RACore.HAS_PARALLEL_COPIES)
286 :     then colorCopyTmps(!copyTmps) else firstLoc
287 :     (* color the rest of the spilled nodes *)
288 :     in selectColor(nodesToSpill, firstColor, !spillLoc)
289 :     end
290 :    
291 :     end (* local *)
292 :    
293 :     structure F = Flowgraph
294 :    
295 :     open F
296 :    
297 :     val SPILL_COALESCING = 0wx100
298 :     val SPILL_COLORING = 0wx200
299 :     val SPILL_PROPAGATION = 0wx400
300 :    
301 :     (*
302 :     * New services that also perform memory allocation
303 :     *)
304 :     fun services f =
305 :     let val {build, spill=spillMethod,
306 :     blockNum, instrNum, programPoint} = F.services f
307 :    
308 :     (* Mark nodes that are immediately aliased to mem regs;
309 :     * These are nodes that need also to be spilled
310 :     *)
311 :     fun markMemRegs [] = ()
312 :     | markMemRegs(NODE{number=r, color as ref(ALIASED
313 :     (NODE{color=ref(col as SPILLED c), ...})), ...}::ns) =
314 :     (if c >= 0 then color := col else ();
315 :     markMemRegs ns)
316 :     | markMemRegs(_::ns) = markMemRegs ns
317 :    
318 :     (*
319 :     * Actual spill phase.
320 :     * Perform the memory coalescing phases first, before doing an
321 :     * actual spill.
322 :     *)
323 :     fun spillIt{graph = G as GRAPH{mode, ...}, nodes,
324 :     copyInstr, spill, spillSrc, spillCopyTmp,
325 :     reload, reloadDst, renameSrc, cellkind} =
326 :     let val nodes = if isOn(mode,SPILL_PROPAGATION) then
327 :     spillPropagation G nodes else nodes
328 :     val _ = if isOn(mode,SPILL_COALESCING) then
329 :     spillCoalescing G nodes else ()
330 :     val _ = if isOn(mode,SPILL_COLORING) then
331 :     spillColoring G nodes else ()
332 :     val _ = if isOn(mode,SPILL_COALESCING+SPILL_PROPAGATION)
333 :     then markMemRegs nodes else ()
334 :     in spillMethod
335 :     {graph=G, nodes=nodes, copyInstr=copyInstr,
336 :     spill=spill, spillSrc=spillSrc, spillCopyTmp=spillCopyTmp,
337 :     reload=reload, reloadDst=reloadDst,
338 :     renameSrc=renameSrc, cellkind=cellkind}
339 :     end
340 :     in {build=build, spill=spillIt, programPoint=programPoint,
341 :     blockNum=blockNum, instrNum=instrNum}
342 :     end
343 :    
344 :     end

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