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 705 - (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 : monnier 498 val nodes = Intmap.new(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 :     val hasBeenSpilled = Intmap.mapWithDefault (spilledRegs,false)
181 :    
182 :     fun logGraph(header,G) =
183 : monnier 498 if !dump_graph then
184 : monnier 469 (TextIO.output(!debug_stream,
185 :     "-------------"^header^"-----------\n");
186 :     Core.dumpGraph G (!debug_stream)
187 :     )
188 :     else ()
189 :    
190 :     (*
191 :     * Build the interference graph
192 :     *)
193 :     fun buildGraph(G) =
194 : monnier 498 let val _ = if debug then print "build..." else ()
195 :     val moves = buildMethod(G,cellkind)
196 :     val worklists =
197 :     (Core.initWorkLists G) {moves=moves}
198 :     in (* if !count_dead then
199 : monnier 469 Intmap.app (fn (_,NODE{uses=ref [],...}) => dead := !dead + 1
200 :     | _ => ()) nodes
201 : monnier 498 else (); *)
202 : monnier 469 logGraph("build",G);
203 : monnier 498 if debug then
204 :     let val G.GRAPH{bitMatrix=ref(G.BM{elems, ...}), ...} = G
205 :     in print ("done: nodes="^Int.toString(Intmap.elems nodes)^
206 :     " edges="^Int.toString(!elems)^
207 :     " moves="^Int.toString(length moves)^
208 :     "\n")
209 :     end else ();
210 : monnier 469 worklists
211 :     end
212 :    
213 :     (*
214 :     * Potential spill phase
215 :     *)
216 :     fun chooseVictim{spillWkl} =
217 :     let fun dumpSpillCandidates(spillWkl) =
218 :     (print "Spill candidates:\n";
219 :     app (fn n => print(Core.show G n^" ")) spillWkl;
220 :     print "\n"
221 :     )
222 : monnier 498 (* Initialize if it is the first time we spill *)
223 :     val _ = if !spillFlag then () else SpillHeuristics.init()
224 :     (* Choose a node *)
225 : monnier 469 val {node,cost,spillWkl} =
226 :     SpillHeuristics.chooseSpillNode
227 : monnier 498 {graph=G, hasBeenSpilled=hasBeenSpilled,
228 : monnier 469 spillWkl=spillWkl}
229 :     handle SpillHeuristics.NoCandidate =>
230 :     (Core.dumpGraph G (!debug_stream);
231 :     dumpSpillCandidates(spillWkl);
232 :     error ("chooseVictim")
233 :     )
234 :     in if !debug_spill then
235 :     (case node of
236 :     NONE => ()
237 :     | SOME(best as NODE{defs,uses,...}) =>
238 :     print("Spilling node "^Core.show G best^
239 :     " cost="^Real.toString cost^
240 :     " defs="^Int.toString(length(!defs))^
241 :     " uses="^Int.toString(length(!uses))^"\n"
242 :     )
243 :     ) else ();
244 : george 545 {node=node,cost=cost,spillWkl=spillWkl}
245 : monnier 469 end
246 :    
247 :     (*
248 : monnier 475 * Mark spill nodes
249 : monnier 469 *)
250 : monnier 475 fun markSpillNodes nodesToSpill =
251 : george 705 let val marker = SPILLED
252 : monnier 475 fun loop [] = ()
253 :     | loop(NODE{color, ...}::ns) = (color := marker; loop ns)
254 :     in loop nodesToSpill end
255 : monnier 498
256 :     (* Mark nodes that are immediately aliased to mem regs;
257 :     * These are nodes that need also to be spilled
258 :     *)
259 :     fun markMemRegs [] = ()
260 :     | markMemRegs(NODE{number=r, color as ref(ALIASED
261 : george 705 (NODE{color=ref(col as MEMREG _), ...})), ...}::ns) =
262 :     (color := col;
263 : monnier 498 markMemRegs ns)
264 :     | markMemRegs(_::ns) = markMemRegs ns
265 :    
266 : monnier 469 (*
267 :     * Actual spill phase.
268 :     * Insert spill node and incrementally
269 :     * update the interference graph.
270 :     *)
271 :     fun actualSpills{spills} =
272 : monnier 498 let val _ = if debug then print "spill..." else ();
273 :     val _ = if isOn(mode,
274 :     SPILL_COALESCING+
275 :     SPILL_PROPAGATION+
276 :     SPILL_COLORING) then
277 :     markSpillNodes spills
278 : monnier 475 else ()
279 : monnier 498 val _ = if isOn(mode,SPILL_PROPAGATION+SPILL_COALESCING) then
280 :     Core.initMemMoves G
281 :     else ()
282 :     val _ = logGraph("actual spill",G);
283 : monnier 469 val {simplifyWkl,freezeWkl,moveWkl,spillWkl} =
284 :     Core.initWorkLists G
285 :     {moves=spillMethod{graph=G, cellkind=cellkind,
286 : monnier 498 spill=spill, spillSrc=spillSrc,
287 :     spillCopyTmp=spillCopyTmp,
288 :     renameSrc=renameSrc,
289 :     reload=reload, reloadDst=reloadDst,
290 : monnier 469 copyInstr=copyInstr, nodes=spills
291 : monnier 498 }
292 : monnier 469 }
293 : monnier 498 val _ = dumpFlowgraph(cfg_after_spill,"after spilling")
294 : monnier 469 in logGraph("rebuild",G);
295 : monnier 498 if debug then print "done\n" else ();
296 : monnier 469 rebuild_count := !rebuild_count + 1;
297 :     (simplifyWkl, moveWkl, freezeWkl, spillWkl, [])
298 :     end
299 :    
300 :     (*
301 :     * Main loop of the algorithm
302 :     *)
303 :     fun main(G) =
304 :     let
305 :    
306 :     (* Main loop *)
307 :     fun loop(simplifyWkl,moveWkl,freezeWkl,spillWkl,stack) =
308 :     let val iteratedCoal = Core.iteratedCoalescing G
309 :     val potentialSpill = Core.potentialSpillNode G
310 :     (* simplify/coalesce/freeze/potential spill phases
311 :     * simplifyWkl -- non-move related nodes with low degree
312 :     * moveWkl -- moves to be considered for coalescing
313 :     * freezeWkl -- move related nodes (with low degree)
314 :     * spillWkl -- potential spill nodes
315 :     * stack -- simplified nodes
316 :     *)
317 :     fun iterate(simplifyWkl,moveWkl,freezeWkl,spillWkl,stack) =
318 :     let (* perform iterated coalescing *)
319 :     val {stack} = iteratedCoal{simplifyWkl=simplifyWkl,
320 :     moveWkl=moveWkl,
321 :     freezeWkl=freezeWkl,
322 :     stack=stack}
323 :     in case spillWkl of
324 :     [] => stack (* nothing to spill *)
325 :     | _ =>
326 : monnier 498 if !pseudoCount = 0 (* all nodes simplified *)
327 :     then stack
328 :     else
329 : george 545 let val {node,cost,spillWkl} =
330 : monnier 469 chooseVictim{spillWkl=spillWkl}
331 : monnier 498 in case node of
332 : monnier 469 SOME node => (* spill node and continue *)
333 : monnier 498 let val _ = if debug then print "-" else ()
334 :     val {moveWkl,freezeWkl,stack} =
335 : george 545 potentialSpill{node=node,
336 :     cost=cost,
337 :     stack=stack}
338 : monnier 469 in iterate([],moveWkl,freezeWkl,spillWkl,stack)
339 :     end
340 :     | NONE => stack (* nothing to spill *)
341 :     end
342 :     end
343 :    
344 : leunga 576 val {spills} =
345 :     if K = 0 then
346 :     {spills=spillWkl}
347 :     else
348 :     let (* simplify the nodes *)
349 :     val stack = iterate
350 :     (simplifyWkl,moveWkl,freezeWkl,spillWkl,stack)
351 :     (* color the nodes *)
352 :     in (Core.select G) {stack=stack}
353 :     end
354 : monnier 469 in (* check for actual spills *)
355 :     case spills of
356 :     [] => ()
357 :     | spills =>
358 : monnier 498 (if isOn(mode,COPY_PROPAGATION) then ()
359 :     else loop(actualSpills{spills=spills})
360 : monnier 469 )
361 :     end
362 :    
363 :     val {simplifyWkl, moveWkl, freezeWkl, spillWkl} = buildGraph G
364 :    
365 :     in loop(simplifyWkl, moveWkl, freezeWkl, spillWkl, [])
366 :     end
367 :    
368 :     fun initSpillProh(from,to) =
369 :     let val markAsSpilled = Intmap.add spilledRegs
370 :     fun loop r =
371 :     if r <= to then (markAsSpilled(r,true); loop(r+1)) else ()
372 :     in loop from end
373 :    
374 : monnier 498 in dumpFlowgraph(cfg_before_ra,"before register allocation");
375 : monnier 469 app initSpillProh spillProh;
376 :     main(G); (* main loop *)
377 :     (* update the regmap *)
378 :     logGraph("done",G);
379 : monnier 498 if isOn(mode,COPY_PROPAGATION)
380 :     then Core.finishCP G
381 :     else Core.finishRA G
382 : monnier 469 ;
383 :     ra_count := !ra_count + 1;
384 : monnier 498 dumpFlowgraph(cfg_after_ra,"after register allocation");
385 :     (* Clean up spilling *)
386 :     SpillHeuristics.init()
387 : monnier 469 end
388 : monnier 498 end
389 : monnier 469
390 :     fun regallocs [] = ()
391 :     | regallocs(p::ps) = (regalloc p; regallocs ps)
392 :    
393 : george 545 in dumpFlowgraph(cfg_before_ras,"before register allocation");
394 :     regallocs params;
395 :     dumpFlowgraph(cfg_after_ras,"after register allocation");
396 : monnier 469 flowgraph
397 :     end
398 :    
399 :     end

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