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 545 - (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 :     K : int, (* number of colors *)
62 :     dedicated : bool Array.array, (* dedicated registers *)
63 :     getreg : getreg, (* how to find a color *)
64 :     copyInstr : F.Spill.copyInstr, (* how to make a copy *)
65 :     spill : F.Spill.spill, (* spill callback *)
66 :     spillSrc : F.Spill.spillSrc, (* spill callback *)
67 :     spillCopyTmp : F.Spill.spillCopyTmp, (* spill callback *)
68 :     reload : F.Spill.reload, (* reload callback *)
69 :     reloadDst : F.Spill.reloadDst, (* reload callback *)
70 :     renameSrc : F.Spill.renameSrc, (* rename callback *)
71 :     firstMemReg : C.cell,
72 :     numMemRegs : int,
73 :     mode : mode (* mode *)
74 :     }
75 :    
76 :     val debug = false
77 :    
78 : george 545 val NO_OPTIMIZATION = 0wx0
79 :     val DEAD_COPY_ELIM = Core.DEAD_COPY_ELIM
80 :     val BIASED_SELECTION = Core.BIASED_SELECTION
81 :     val HAS_PARALLEL_COPIES = Core.HAS_PARALLEL_COPIES
82 :     val SPILL_COALESCING = 0wx100
83 :     val SPILL_COLORING = 0wx200
84 :     val SPILL_PROPAGATION = 0wx400
85 :     val COPY_PROPAGATION = 0wx800
86 : monnier 498
87 :     fun isOn(flag, mask) = Word.andb(flag,mask) <> 0w0
88 :    
89 : monnier 469 open G
90 :    
91 :     fun error msg = MLRiscErrorMsg.error("RegisterAllocator",msg)
92 :    
93 :     (*
94 : monnier 475 * Debugging flags + counters
95 : monnier 469 *)
96 :     val cfg_before_ra = MLRiscControl.getFlag "dump-cfg-before-ra"
97 :     val cfg_after_ra = MLRiscControl.getFlag "dump-cfg-after-ra"
98 :     val cfg_after_spill = MLRiscControl.getFlag "dump-cfg-after-spilling"
99 : george 545 val cfg_before_ras = MLRiscControl.getFlag "dump-cfg-before-all-ra"
100 :     val cfg_after_ras = MLRiscControl.getFlag "dump-cfg-after-all-ra"
101 : monnier 469 val dump_graph = MLRiscControl.getFlag "dump-interference-graph"
102 :     val debug_spill = MLRiscControl.getFlag "ra-debug-spilling"
103 :     val ra_count = MLRiscControl.getCounter "ra-count"
104 :     val rebuild_count = MLRiscControl.getCounter "ra-rebuild"
105 : monnier 498
106 :     (*
107 : monnier 469 val count_dead = MLRiscControl.getFlag "ra-count-dead-code"
108 :     val dead = MLRiscControl.getCounter "ra-dead-code"
109 : monnier 498 *)
110 : monnier 469 val debug_stream = MLRiscControl.debug_stream
111 :    
112 :     (*
113 :     * Optimization flags
114 :     *)
115 : monnier 498 (*
116 : monnier 469 val rematerialization = MLRiscControl.getFlag "ra-rematerialization"
117 : monnier 498 *)
118 : monnier 469
119 :     exception NodeTable
120 :    
121 :     (* This array is used for getreg.
122 :     * We allocate it once.
123 :     *)
124 :     val proh = Array.array(C.firstPseudo, ~1)
125 :    
126 :     (*
127 :     * Register allocator.
128 :     * spillProh is a list of registers that are not candidates for spills.
129 :     *)
130 : monnier 498 fun ra params flowgraph =
131 : monnier 469 let
132 :     (* Flowgraph methods *)
133 :     val {build=buildMethod, spill=spillMethod, ...} = F.services flowgraph
134 :    
135 : monnier 498 (* global spill location counter *)
136 :     val spillLoc=ref ~256
137 :    
138 :     (* How to dump the flowgraph *)
139 :     fun dumpFlowgraph(flag, title) =
140 :     if !flag then F.dumpFlowgraph(title, flowgraph,!debug_stream) else ()
141 :    
142 : monnier 469 (* Main function *)
143 :     fun regalloc{getreg, K, dedicated, copyInstr,
144 : monnier 498 spill, spillSrc, spillCopyTmp, renameSrc,
145 :     reload, reloadDst, spillProh, cellkind, mode,
146 :     firstMemReg, numMemRegs} =
147 :     let val numCell = C.numCell cellkind ()
148 :     in if numCell = 0
149 : monnier 469 then ()
150 :     else
151 : monnier 498 let (* extract the regmap and blocks from the flowgraph *)
152 : monnier 469 val regmap = F.regmap flowgraph (* the register map *)
153 :    
154 :     (* the nodes table *)
155 : monnier 498 val nodes = Intmap.new(numCell,NodeTable)
156 : george 545 val mode = if isOn(HAS_PARALLEL_COPIES, mode) then
157 :     Word.orb(Core.SAVE_COPY_TEMPS, mode)
158 :     else mode
159 : monnier 469 (* create an empty interference graph *)
160 :     val G = G.newGraph{nodes=nodes,
161 :     K=K,
162 :     dedicated=dedicated,
163 : monnier 498 numRegs=numCell,
164 : monnier 469 maxRegs=C.maxCell,
165 :     regmap=regmap,
166 :     showReg=C.toString cellkind,
167 :     getreg=getreg,
168 :     getpair=fn _ => error "getpair",
169 :     firstPseudoR=C.firstPseudo,
170 : monnier 498 proh=proh,
171 :     mode=Word.orb(Flowgraph.mode,
172 :     Word.orb(mode,SpillHeuristics.mode)),
173 :     spillLoc=spillLoc,
174 :     firstMemReg=firstMemReg,
175 :     numMemRegs=numMemRegs
176 : monnier 469 }
177 : monnier 498 val G.GRAPH{spilledRegs, pseudoCount, spillFlag, ...} = G
178 : monnier 469
179 :     val hasBeenSpilled = Intmap.mapWithDefault (spilledRegs,false)
180 :    
181 :     fun logGraph(header,G) =
182 : monnier 498 if !dump_graph then
183 : monnier 469 (TextIO.output(!debug_stream,
184 :     "-------------"^header^"-----------\n");
185 :     Core.dumpGraph G (!debug_stream)
186 :     )
187 :     else ()
188 :    
189 :     (*
190 :     * Build the interference graph
191 :     *)
192 :     fun buildGraph(G) =
193 : monnier 498 let val _ = if debug then print "build..." else ()
194 :     val moves = buildMethod(G,cellkind)
195 :     val worklists =
196 :     (Core.initWorkLists G) {moves=moves}
197 :     in (* if !count_dead then
198 : monnier 469 Intmap.app (fn (_,NODE{uses=ref [],...}) => dead := !dead + 1
199 :     | _ => ()) nodes
200 : monnier 498 else (); *)
201 : monnier 469 logGraph("build",G);
202 : monnier 498 if debug then
203 :     let val G.GRAPH{bitMatrix=ref(G.BM{elems, ...}), ...} = G
204 :     in print ("done: nodes="^Int.toString(Intmap.elems nodes)^
205 :     " edges="^Int.toString(!elems)^
206 :     " moves="^Int.toString(length moves)^
207 :     "\n")
208 :     end else ();
209 : monnier 469 worklists
210 :     end
211 :    
212 :     (*
213 :     * Potential spill phase
214 :     *)
215 :     fun chooseVictim{spillWkl} =
216 :     let fun dumpSpillCandidates(spillWkl) =
217 :     (print "Spill candidates:\n";
218 :     app (fn n => print(Core.show G n^" ")) spillWkl;
219 :     print "\n"
220 :     )
221 : monnier 498 (* Initialize if it is the first time we spill *)
222 :     val _ = if !spillFlag then () else SpillHeuristics.init()
223 :     (* Choose a node *)
224 : monnier 469 val {node,cost,spillWkl} =
225 :     SpillHeuristics.chooseSpillNode
226 : monnier 498 {graph=G, hasBeenSpilled=hasBeenSpilled,
227 : monnier 469 spillWkl=spillWkl}
228 :     handle SpillHeuristics.NoCandidate =>
229 :     (Core.dumpGraph G (!debug_stream);
230 :     dumpSpillCandidates(spillWkl);
231 :     error ("chooseVictim")
232 :     )
233 :     in if !debug_spill then
234 :     (case node of
235 :     NONE => ()
236 :     | SOME(best as NODE{defs,uses,...}) =>
237 :     print("Spilling node "^Core.show G best^
238 :     " cost="^Real.toString cost^
239 :     " defs="^Int.toString(length(!defs))^
240 :     " uses="^Int.toString(length(!uses))^"\n"
241 :     )
242 :     ) else ();
243 : george 545 {node=node,cost=cost,spillWkl=spillWkl}
244 : monnier 469 end
245 :    
246 :     (*
247 : monnier 475 * Mark spill nodes
248 : monnier 469 *)
249 : monnier 475 fun markSpillNodes nodesToSpill =
250 :     let val marker = SPILLED(~1)
251 :     fun loop [] = ()
252 :     | loop(NODE{color, ...}::ns) = (color := marker; loop ns)
253 :     in loop nodesToSpill end
254 : monnier 498
255 :     (* Mark nodes that are immediately aliased to mem regs;
256 :     * These are nodes that need also to be spilled
257 :     *)
258 :     fun markMemRegs [] = ()
259 :     | markMemRegs(NODE{number=r, color as ref(ALIASED
260 :     (NODE{color=ref(col as SPILLED c), ...})), ...}::ns) =
261 :     (if c >= 0 then color := col else ();
262 :     markMemRegs ns)
263 :     | markMemRegs(_::ns) = markMemRegs ns
264 :    
265 : monnier 469 (*
266 :     * Actual spill phase.
267 :     * Insert spill node and incrementally
268 :     * update the interference graph.
269 :     *)
270 :     fun actualSpills{spills} =
271 : monnier 498 let val _ = if debug then print "spill..." else ();
272 :     val _ = if isOn(mode,
273 :     SPILL_COALESCING+
274 :     SPILL_PROPAGATION+
275 :     SPILL_COLORING) then
276 :     markSpillNodes spills
277 : monnier 475 else ()
278 : monnier 498 val _ = if isOn(mode,SPILL_PROPAGATION+SPILL_COALESCING) then
279 :     Core.initMemMoves G
280 :     else ()
281 : george 545 (*
282 : monnier 498 val spills = if isOn(mode,SPILL_PROPAGATION) then
283 :     Core.spillPropagation G spills else spills
284 :     val _ = if isOn(mode,SPILL_COALESCING) then
285 : monnier 469 Core.spillCoalescing G spills else ()
286 : monnier 498 val _ = if isOn(mode,SPILL_COLORING) then
287 : monnier 469 Core.spillColoring G spills else ()
288 : monnier 498 val _ = if isOn(mode,SPILL_COALESCING+SPILL_PROPAGATION) then
289 :     markMemRegs spills else ()
290 : george 545 *)
291 : monnier 498 val _ = logGraph("actual spill",G);
292 : monnier 469 val {simplifyWkl,freezeWkl,moveWkl,spillWkl} =
293 :     Core.initWorkLists G
294 :     {moves=spillMethod{graph=G, cellkind=cellkind,
295 : monnier 498 spill=spill, spillSrc=spillSrc,
296 :     spillCopyTmp=spillCopyTmp,
297 :     renameSrc=renameSrc,
298 :     reload=reload, reloadDst=reloadDst,
299 : monnier 469 copyInstr=copyInstr, nodes=spills
300 : monnier 498 }
301 : monnier 469 }
302 : monnier 498 val _ = dumpFlowgraph(cfg_after_spill,"after spilling")
303 : monnier 469 in logGraph("rebuild",G);
304 : monnier 498 if debug then print "done\n" else ();
305 : monnier 469 rebuild_count := !rebuild_count + 1;
306 :     (simplifyWkl, moveWkl, freezeWkl, spillWkl, [])
307 :     end
308 :    
309 :     (*
310 :     * Main loop of the algorithm
311 :     *)
312 :     fun main(G) =
313 :     let
314 :    
315 :     (* Main loop *)
316 :     fun loop(simplifyWkl,moveWkl,freezeWkl,spillWkl,stack) =
317 :     let val iteratedCoal = Core.iteratedCoalescing G
318 :     val potentialSpill = Core.potentialSpillNode G
319 :     (* simplify/coalesce/freeze/potential spill phases
320 :     * simplifyWkl -- non-move related nodes with low degree
321 :     * moveWkl -- moves to be considered for coalescing
322 :     * freezeWkl -- move related nodes (with low degree)
323 :     * spillWkl -- potential spill nodes
324 :     * stack -- simplified nodes
325 :     *)
326 :     fun iterate(simplifyWkl,moveWkl,freezeWkl,spillWkl,stack) =
327 :     let (* perform iterated coalescing *)
328 :     val {stack} = iteratedCoal{simplifyWkl=simplifyWkl,
329 :     moveWkl=moveWkl,
330 :     freezeWkl=freezeWkl,
331 :     stack=stack}
332 :     in case spillWkl of
333 :     [] => stack (* nothing to spill *)
334 :     | _ =>
335 : monnier 498 if !pseudoCount = 0 (* all nodes simplified *)
336 :     then stack
337 :     else
338 : george 545 let val {node,cost,spillWkl} =
339 : monnier 469 chooseVictim{spillWkl=spillWkl}
340 : monnier 498 in case node of
341 : monnier 469 SOME node => (* spill node and continue *)
342 : monnier 498 let val _ = if debug then print "-" else ()
343 :     val {moveWkl,freezeWkl,stack} =
344 : george 545 potentialSpill{node=node,
345 :     cost=cost,
346 :     stack=stack}
347 : monnier 469 in iterate([],moveWkl,freezeWkl,spillWkl,stack)
348 :     end
349 :     | NONE => stack (* nothing to spill *)
350 :     end
351 :     end
352 :    
353 :     (* simplify the nodes *)
354 :     val stack = iterate
355 :     (simplifyWkl,moveWkl,freezeWkl,spillWkl,stack)
356 :     (* color the nodes *)
357 : monnier 498 val {spills} = (Core.select G) {stack=stack}
358 : monnier 469 in (* check for actual spills *)
359 :     case spills of
360 :     [] => ()
361 :     | spills =>
362 : monnier 498 (if isOn(mode,COPY_PROPAGATION) then ()
363 :     else loop(actualSpills{spills=spills})
364 : monnier 469 )
365 :     end
366 :    
367 :     val {simplifyWkl, moveWkl, freezeWkl, spillWkl} = buildGraph G
368 :    
369 :     in loop(simplifyWkl, moveWkl, freezeWkl, spillWkl, [])
370 :     end
371 :    
372 :     fun initSpillProh(from,to) =
373 :     let val markAsSpilled = Intmap.add spilledRegs
374 :     fun loop r =
375 :     if r <= to then (markAsSpilled(r,true); loop(r+1)) else ()
376 :     in loop from end
377 :    
378 : monnier 498 in dumpFlowgraph(cfg_before_ra,"before register allocation");
379 : monnier 469 app initSpillProh spillProh;
380 :     main(G); (* main loop *)
381 :     (* update the regmap *)
382 :     logGraph("done",G);
383 : monnier 498 if isOn(mode,COPY_PROPAGATION)
384 :     then Core.finishCP G
385 :     else Core.finishRA G
386 : monnier 469 ;
387 :     ra_count := !ra_count + 1;
388 : monnier 498 dumpFlowgraph(cfg_after_ra,"after register allocation");
389 :     (* Clean up spilling *)
390 :     SpillHeuristics.init()
391 : monnier 469 end
392 : monnier 498 end
393 : monnier 469
394 :     fun regallocs [] = ()
395 :     | regallocs(p::ps) = (regalloc p; regallocs ps)
396 :    
397 : george 545 in dumpFlowgraph(cfg_before_ras,"before register allocation");
398 :     regallocs params;
399 :     dumpFlowgraph(cfg_after_ras,"after register allocation");
400 : monnier 469 flowgraph
401 :     end
402 :    
403 :     end

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