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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 733 - (view) (download)

1 : monnier 469 (*
2 :     * This is the new register allocator based on
3 :     * the 'iterated register coalescing' scheme described
4 :     * in POPL'96, and TOPLAS v18 #3, pp 325-353.
5 :     *
6 : monnier 475 * Now with numerous extensions:
7 : monnier 469 *
8 : monnier 475 * 0. Dead copy elimination (optional)
9 : monnier 469 * 1. Priority based coalescing
10 :     * 2. Priority based freezing
11 :     * 3. Priority based spilling
12 : monnier 475 * 4. Biased selection (optional)
13 :     * 5. Spill Coalescing (optional)
14 :     * 6. Spill Propagation (optional)
15 :     * 7. Spill Coloring (optional)
16 :     *
17 :     * For details, please see the paper from
18 :     *
19 :     * http://cm.bell-labs.com/cm/cs/what/smlnj/compiler-notes/index.html
20 :     *
21 : monnier 469 * The basic structure of this register allocator is as follows:
22 :     * 1. RAGraph. This module enscapsulates the interference graph
23 :     * datatype (adjacency list + interference graph + node table)
24 :     * and contains nothing architecture specific.
25 :     * 2. RACore. This module implements the main part of the iterated
26 :     * coalescing algorithm, with frequency enhancements.
27 :     * 3. RA_FLOWGRAPH. This register allocator is parameterized
28 :     * with respect to this signature. This basically abstracts out
29 :     * the representation of the program flowgraph, and provide
30 :     * a few services to the main allocator, such as building the
31 :     * interference graph, rewriting the flowgraph after spilling,
32 :     * and rebuilding the interference graph after spilling.
33 :     * This module is responsible for caching any information necessary
34 :     * to make spilling fast.
35 :     * 4. This functor. This functor drives the entire process.
36 :     *
37 : monnier 475 * -- Allen Leung (leunga@cs.nyu.edu)
38 : monnier 469 *)
39 :    
40 :     functor RegisterAllocator
41 :     (SpillHeuristics : RA_SPILL_HEURISTICS)
42 :     (Flowgraph : RA_FLOWGRAPH) : RA =
43 :     struct
44 :    
45 :     structure F = Flowgraph
46 :     structure I = F.I
47 :     structure C = I.C
48 :     structure Core = RACore
49 :     structure G = Core.G
50 :    
51 :     type getreg = { pref : C.cell list,
52 :     stamp : int,
53 :     proh : int Array.array
54 :     } -> C.cell
55 :    
56 : monnier 498 type mode = word
57 :    
58 :     type raClient =
59 :     { cellkind : C.cellkind, (* kind of register *)
60 :     spillProh : (C.cell * C.cell) list, (* don't spill these *)
61 : leunga 576 memRegs : (C.cell * C.cell) list, (* memory registers *)
62 : monnier 498 K : int, (* number of colors *)
63 :     dedicated : bool Array.array, (* dedicated registers *)
64 :     getreg : getreg, (* how to find a color *)
65 :     copyInstr : F.Spill.copyInstr, (* how to make a copy *)
66 :     spill : F.Spill.spill, (* spill callback *)
67 :     spillSrc : F.Spill.spillSrc, (* spill callback *)
68 :     spillCopyTmp : F.Spill.spillCopyTmp, (* spill callback *)
69 :     reload : F.Spill.reload, (* reload callback *)
70 :     reloadDst : F.Spill.reloadDst, (* reload callback *)
71 :     renameSrc : F.Spill.renameSrc, (* rename callback *)
72 :     mode : mode (* mode *)
73 :     }
74 :    
75 :     val debug = false
76 :    
77 : leunga 576 val NO_OPTIMIZATION = 0wx0
78 :     val DEAD_COPY_ELIM = Core.DEAD_COPY_ELIM
79 :     val BIASED_SELECTION = Core.BIASED_SELECTION
80 :     val HAS_PARALLEL_COPIES = Core.HAS_PARALLEL_COPIES
81 :     val SPILL_COALESCING = 0wx100
82 :     val SPILL_COLORING = 0wx200
83 :     val SPILL_PROPAGATION = 0wx400
84 :     val COPY_PROPAGATION = 0wx800
85 : monnier 498
86 :     fun isOn(flag, mask) = Word.andb(flag,mask) <> 0w0
87 :    
88 : monnier 469 open G
89 :    
90 :     fun error msg = MLRiscErrorMsg.error("RegisterAllocator",msg)
91 :    
92 :     (*
93 : monnier 475 * Debugging flags + counters
94 : monnier 469 *)
95 :     val cfg_before_ra = MLRiscControl.getFlag "dump-cfg-before-ra"
96 :     val cfg_after_ra = MLRiscControl.getFlag "dump-cfg-after-ra"
97 :     val cfg_after_spill = MLRiscControl.getFlag "dump-cfg-after-spilling"
98 : george 545 val cfg_before_ras = MLRiscControl.getFlag "dump-cfg-before-all-ra"
99 :     val cfg_after_ras = MLRiscControl.getFlag "dump-cfg-after-all-ra"
100 : monnier 469 val dump_graph = MLRiscControl.getFlag "dump-interference-graph"
101 :     val debug_spill = MLRiscControl.getFlag "ra-debug-spilling"
102 :     val ra_count = MLRiscControl.getCounter "ra-count"
103 :     val rebuild_count = MLRiscControl.getCounter "ra-rebuild"
104 : monnier 498
105 :     (*
106 : monnier 469 val count_dead = MLRiscControl.getFlag "ra-count-dead-code"
107 :     val dead = MLRiscControl.getCounter "ra-dead-code"
108 : monnier 498 *)
109 : monnier 469 val debug_stream = MLRiscControl.debug_stream
110 :    
111 :     (*
112 :     * Optimization flags
113 :     *)
114 : monnier 498 (*
115 : monnier 469 val rematerialization = MLRiscControl.getFlag "ra-rematerialization"
116 : monnier 498 *)
117 : monnier 469
118 :     exception NodeTable
119 :    
120 :     (* This array is used for getreg.
121 :     * We allocate it once.
122 :     *)
123 :     val proh = Array.array(C.firstPseudo, ~1)
124 :    
125 :     (*
126 :     * Register allocator.
127 :     * spillProh is a list of registers that are not candidates for spills.
128 :     *)
129 : monnier 498 fun ra params flowgraph =
130 : monnier 469 let
131 :     (* Flowgraph methods *)
132 :     val {build=buildMethod, spill=spillMethod, ...} = F.services flowgraph
133 :    
134 : monnier 498 (* global spill location counter *)
135 : george 705 (* Note: spillLoc cannot be zero as negative locations are
136 :     * returned to the client to indicate spill locations.
137 :     *)
138 :     val spillLoc=ref 1
139 : monnier 498
140 :     (* How to dump the flowgraph *)
141 :     fun dumpFlowgraph(flag, title) =
142 :     if !flag then F.dumpFlowgraph(title, flowgraph,!debug_stream) else ()
143 :    
144 : monnier 469 (* Main function *)
145 :     fun regalloc{getreg, K, dedicated, copyInstr,
146 : monnier 498 spill, spillSrc, spillCopyTmp, renameSrc,
147 :     reload, reloadDst, spillProh, cellkind, mode,
148 : leunga 576 memRegs} =
149 : monnier 498 let val numCell = C.numCell cellkind ()
150 :     in if numCell = 0
151 : monnier 469 then ()
152 :     else
153 : monnier 498 let (* extract the regmap and blocks from the flowgraph *)
154 : monnier 469 val regmap = F.regmap flowgraph (* the register map *)
155 :    
156 :     (* the nodes table *)
157 : blume 733 val nodes = IntHashTable.mkTable(numCell,NodeTable)
158 : george 545 val mode = if isOn(HAS_PARALLEL_COPIES, mode) then
159 :     Word.orb(Core.SAVE_COPY_TEMPS, mode)
160 :     else mode
161 : monnier 469 (* create an empty interference graph *)
162 :     val G = G.newGraph{nodes=nodes,
163 :     K=K,
164 :     dedicated=dedicated,
165 : monnier 498 numRegs=numCell,
166 : monnier 469 maxRegs=C.maxCell,
167 :     regmap=regmap,
168 :     showReg=C.toString cellkind,
169 :     getreg=getreg,
170 :     getpair=fn _ => error "getpair",
171 :     firstPseudoR=C.firstPseudo,
172 : monnier 498 proh=proh,
173 :     mode=Word.orb(Flowgraph.mode,
174 :     Word.orb(mode,SpillHeuristics.mode)),
175 :     spillLoc=spillLoc,
176 : leunga 576 memRegs=memRegs
177 : monnier 469 }
178 : monnier 498 val G.GRAPH{spilledRegs, pseudoCount, spillFlag, ...} = G
179 : monnier 469
180 : blume 733 fun hasBeenSpilled i =
181 :     getOpt (IntHashTable.find spilledRegs i, false)
182 : monnier 469
183 :     fun logGraph(header,G) =
184 : monnier 498 if !dump_graph then
185 : monnier 469 (TextIO.output(!debug_stream,
186 :     "-------------"^header^"-----------\n");
187 :     Core.dumpGraph G (!debug_stream)
188 :     )
189 :     else ()
190 :    
191 :     (*
192 :     * Build the interference graph
193 :     *)
194 :     fun buildGraph(G) =
195 : monnier 498 let val _ = if debug then print "build..." else ()
196 :     val moves = buildMethod(G,cellkind)
197 :     val worklists =
198 :     (Core.initWorkLists G) {moves=moves}
199 :     in (* if !count_dead then
200 : blume 733 IntHashTable.appi (fn (_,NODE{uses=ref [],...}) => dead := !dead + 1
201 : monnier 469 | _ => ()) nodes
202 : monnier 498 else (); *)
203 : monnier 469 logGraph("build",G);
204 : monnier 498 if debug then
205 :     let val G.GRAPH{bitMatrix=ref(G.BM{elems, ...}), ...} = G
206 : blume 733 in print ("done: nodes="^
207 :     Int.toString(IntHashTable.numItems nodes)^
208 : monnier 498 " edges="^Int.toString(!elems)^
209 :     " moves="^Int.toString(length moves)^
210 :     "\n")
211 :     end else ();
212 : monnier 469 worklists
213 :     end
214 :    
215 :     (*
216 :     * Potential spill phase
217 :     *)
218 :     fun chooseVictim{spillWkl} =
219 :     let fun dumpSpillCandidates(spillWkl) =
220 :     (print "Spill candidates:\n";
221 :     app (fn n => print(Core.show G n^" ")) spillWkl;
222 :     print "\n"
223 :     )
224 : monnier 498 (* Initialize if it is the first time we spill *)
225 :     val _ = if !spillFlag then () else SpillHeuristics.init()
226 :     (* Choose a node *)
227 : monnier 469 val {node,cost,spillWkl} =
228 :     SpillHeuristics.chooseSpillNode
229 : monnier 498 {graph=G, hasBeenSpilled=hasBeenSpilled,
230 : monnier 469 spillWkl=spillWkl}
231 :     handle SpillHeuristics.NoCandidate =>
232 :     (Core.dumpGraph G (!debug_stream);
233 :     dumpSpillCandidates(spillWkl);
234 :     error ("chooseVictim")
235 :     )
236 :     in if !debug_spill then
237 :     (case node of
238 :     NONE => ()
239 :     | SOME(best as NODE{defs,uses,...}) =>
240 :     print("Spilling node "^Core.show G best^
241 :     " cost="^Real.toString cost^
242 :     " defs="^Int.toString(length(!defs))^
243 :     " uses="^Int.toString(length(!uses))^"\n"
244 :     )
245 :     ) else ();
246 : george 545 {node=node,cost=cost,spillWkl=spillWkl}
247 : monnier 469 end
248 :    
249 :     (*
250 : monnier 475 * Mark spill nodes
251 : monnier 469 *)
252 : monnier 475 fun markSpillNodes nodesToSpill =
253 : george 705 let val marker = SPILLED
254 : monnier 475 fun loop [] = ()
255 :     | loop(NODE{color, ...}::ns) = (color := marker; loop ns)
256 :     in loop nodesToSpill end
257 : monnier 498
258 :     (* Mark nodes that are immediately aliased to mem regs;
259 :     * These are nodes that need also to be spilled
260 :     *)
261 :     fun markMemRegs [] = ()
262 :     | markMemRegs(NODE{number=r, color as ref(ALIASED
263 : george 705 (NODE{color=ref(col as MEMREG _), ...})), ...}::ns) =
264 :     (color := col;
265 : monnier 498 markMemRegs ns)
266 :     | markMemRegs(_::ns) = markMemRegs ns
267 :    
268 : monnier 469 (*
269 :     * Actual spill phase.
270 :     * Insert spill node and incrementally
271 :     * update the interference graph.
272 :     *)
273 :     fun actualSpills{spills} =
274 : monnier 498 let val _ = if debug then print "spill..." else ();
275 :     val _ = if isOn(mode,
276 :     SPILL_COALESCING+
277 :     SPILL_PROPAGATION+
278 :     SPILL_COLORING) then
279 :     markSpillNodes spills
280 : monnier 475 else ()
281 : monnier 498 val _ = if isOn(mode,SPILL_PROPAGATION+SPILL_COALESCING) then
282 :     Core.initMemMoves G
283 :     else ()
284 :     val _ = logGraph("actual spill",G);
285 : monnier 469 val {simplifyWkl,freezeWkl,moveWkl,spillWkl} =
286 :     Core.initWorkLists G
287 :     {moves=spillMethod{graph=G, cellkind=cellkind,
288 : monnier 498 spill=spill, spillSrc=spillSrc,
289 :     spillCopyTmp=spillCopyTmp,
290 :     renameSrc=renameSrc,
291 :     reload=reload, reloadDst=reloadDst,
292 : monnier 469 copyInstr=copyInstr, nodes=spills
293 : monnier 498 }
294 : monnier 469 }
295 : monnier 498 val _ = dumpFlowgraph(cfg_after_spill,"after spilling")
296 : monnier 469 in logGraph("rebuild",G);
297 : monnier 498 if debug then print "done\n" else ();
298 : monnier 469 rebuild_count := !rebuild_count + 1;
299 :     (simplifyWkl, moveWkl, freezeWkl, spillWkl, [])
300 :     end
301 :    
302 :     (*
303 :     * Main loop of the algorithm
304 :     *)
305 :     fun main(G) =
306 :     let
307 :    
308 :     (* Main loop *)
309 :     fun loop(simplifyWkl,moveWkl,freezeWkl,spillWkl,stack) =
310 :     let val iteratedCoal = Core.iteratedCoalescing G
311 :     val potentialSpill = Core.potentialSpillNode G
312 :     (* simplify/coalesce/freeze/potential spill phases
313 :     * simplifyWkl -- non-move related nodes with low degree
314 :     * moveWkl -- moves to be considered for coalescing
315 :     * freezeWkl -- move related nodes (with low degree)
316 :     * spillWkl -- potential spill nodes
317 :     * stack -- simplified nodes
318 :     *)
319 :     fun iterate(simplifyWkl,moveWkl,freezeWkl,spillWkl,stack) =
320 :     let (* perform iterated coalescing *)
321 :     val {stack} = iteratedCoal{simplifyWkl=simplifyWkl,
322 :     moveWkl=moveWkl,
323 :     freezeWkl=freezeWkl,
324 :     stack=stack}
325 :     in case spillWkl of
326 :     [] => stack (* nothing to spill *)
327 :     | _ =>
328 : monnier 498 if !pseudoCount = 0 (* all nodes simplified *)
329 :     then stack
330 :     else
331 : george 545 let val {node,cost,spillWkl} =
332 : monnier 469 chooseVictim{spillWkl=spillWkl}
333 : monnier 498 in case node of
334 : monnier 469 SOME node => (* spill node and continue *)
335 : monnier 498 let val _ = if debug then print "-" else ()
336 :     val {moveWkl,freezeWkl,stack} =
337 : george 545 potentialSpill{node=node,
338 :     cost=cost,
339 :     stack=stack}
340 : monnier 469 in iterate([],moveWkl,freezeWkl,spillWkl,stack)
341 :     end
342 :     | NONE => stack (* nothing to spill *)
343 :     end
344 :     end
345 :    
346 : leunga 576 val {spills} =
347 :     if K = 0 then
348 :     {spills=spillWkl}
349 :     else
350 :     let (* simplify the nodes *)
351 :     val stack = iterate
352 :     (simplifyWkl,moveWkl,freezeWkl,spillWkl,stack)
353 :     (* color the nodes *)
354 :     in (Core.select G) {stack=stack}
355 :     end
356 : monnier 469 in (* check for actual spills *)
357 :     case spills of
358 :     [] => ()
359 :     | spills =>
360 : monnier 498 (if isOn(mode,COPY_PROPAGATION) then ()
361 :     else loop(actualSpills{spills=spills})
362 : monnier 469 )
363 :     end
364 :    
365 :     val {simplifyWkl, moveWkl, freezeWkl, spillWkl} = buildGraph G
366 :    
367 :     in loop(simplifyWkl, moveWkl, freezeWkl, spillWkl, [])
368 :     end
369 :    
370 :     fun initSpillProh(from,to) =
371 : blume 733 let val markAsSpilled = IntHashTable.insert spilledRegs
372 : monnier 469 fun loop r =
373 :     if r <= to then (markAsSpilled(r,true); loop(r+1)) else ()
374 :     in loop from end
375 :    
376 : monnier 498 in dumpFlowgraph(cfg_before_ra,"before register allocation");
377 : monnier 469 app initSpillProh spillProh;
378 :     main(G); (* main loop *)
379 :     (* update the regmap *)
380 :     logGraph("done",G);
381 : monnier 498 if isOn(mode,COPY_PROPAGATION)
382 :     then Core.finishCP G
383 :     else Core.finishRA G
384 : monnier 469 ;
385 :     ra_count := !ra_count + 1;
386 : monnier 498 dumpFlowgraph(cfg_after_ra,"after register allocation");
387 :     (* Clean up spilling *)
388 :     SpillHeuristics.init()
389 : monnier 469 end
390 : monnier 498 end
391 : monnier 469
392 :     fun regallocs [] = ()
393 :     | regallocs(p::ps) = (regalloc p; regallocs ps)
394 :    
395 : george 545 in dumpFlowgraph(cfg_before_ras,"before register allocation");
396 :     regallocs params;
397 :     dumpFlowgraph(cfg_after_ras,"after register allocation");
398 : monnier 469 flowgraph
399 :     end
400 :    
401 :     end

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