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

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