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 475 - (view) (download)
Original Path: sml/branches/SMLNJ/src/MLRISC/ra/ra.sml

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 :     datatype mode = REGISTER_ALLOCATION | COPY_PROPAGATION
52 :    
53 :     datatype optimization = DEAD_COPY_ELIM
54 : monnier 475 | SPILL_PROPAGATION
55 : monnier 469 | SPILL_COALESCING
56 :     | SPILL_COLORING
57 : monnier 475 | BIASED_SELECTION
58 : monnier 469
59 :     type getreg = { pref : C.cell list,
60 :     stamp : int,
61 :     proh : int Array.array
62 :     } -> C.cell
63 :    
64 :     open G
65 :    
66 :     fun error msg = MLRiscErrorMsg.error("RegisterAllocator",msg)
67 :    
68 :     (*
69 : monnier 475 * Debugging flags + counters
70 : monnier 469 *)
71 :     val cfg_before_ra = MLRiscControl.getFlag "dump-cfg-before-ra"
72 :     val cfg_after_ra = MLRiscControl.getFlag "dump-cfg-after-ra"
73 :     val cfg_after_spill = MLRiscControl.getFlag "dump-cfg-after-spilling"
74 :     val dump_graph = MLRiscControl.getFlag "dump-interference-graph"
75 :     val debug_spill = MLRiscControl.getFlag "ra-debug-spilling"
76 :     val ra_count = MLRiscControl.getCounter "ra-count"
77 :     val rebuild_count = MLRiscControl.getCounter "ra-rebuild"
78 :     val count_dead = MLRiscControl.getFlag "ra-count-dead-code"
79 :     val dead = MLRiscControl.getCounter "ra-dead-code"
80 :     val debug_stream = MLRiscControl.debug_stream
81 :    
82 :     (*
83 :     * Optimization flags
84 :     *)
85 :     val rematerialization = MLRiscControl.getFlag "ra-rematerialization"
86 :    
87 :     exception NodeTable
88 :    
89 :     (* This array is used for getreg.
90 :     * We allocate it once.
91 :     *)
92 :     val proh = Array.array(C.firstPseudo, ~1)
93 :    
94 :     (*
95 :     * Register allocator.
96 :     * spillProh is a list of registers that are not candidates for spills.
97 :     *)
98 :     fun ra mode params flowgraph =
99 :     let
100 :     (* Flowgraph methods *)
101 :     val {build=buildMethod, spill=spillMethod, ...} = F.services flowgraph
102 :    
103 :     (* Main function *)
104 :     fun regalloc{getreg, K, dedicated, copyInstr,
105 :     spill, reload, spillProh, cellkind, optimizations} =
106 :     if C.numCell cellkind () = 0
107 :     then ()
108 :     else
109 : monnier 475 let fun getOpt([], dce, sp, sc, scolor, bs) = (dce, sp, sc, scolor, bs)
110 :     | getOpt(DEAD_COPY_ELIM::opts, dce, sp, sc, scolor, bs) =
111 :     getOpt(opts, true, sp, sc, scolor, bs)
112 :     | getOpt(SPILL_PROPAGATION::opts, dce, sp, sc, scolor, bs) =
113 :     getOpt(opts, dce, true, sc, scolor, bs)
114 :     | getOpt(SPILL_COALESCING::opts, dce, sp, sc, scolor, bs) =
115 :     getOpt(opts, dce, sp, true, scolor, bs)
116 :     | getOpt(SPILL_COLORING::opts, dce, sp, sc, scolor, bs) =
117 :     getOpt(opts, dce, sp, sc, true, bs)
118 :     | getOpt(BIASED_SELECTION::opts, dce, sp, sc, scolor, bs) =
119 :     getOpt(opts, dce, sp, sc, scolor, true)
120 : monnier 469
121 : monnier 475 val (deadCopyElim, spillProp, spillCoalescing,
122 :     spillColoring, biasedSelection) =
123 :     getOpt(optimizations, false, false, false, false, false)
124 : monnier 469
125 :     (* extract the regmap and blocks from the flowgraph *)
126 :     val regmap = F.regmap flowgraph (* the register map *)
127 :    
128 :     (* the nodes table *)
129 :     val nodes = Intmap.new(32,NodeTable)
130 :     (* create an empty interference graph *)
131 :     val G = G.newGraph{nodes=nodes,
132 :     K=K,
133 :     dedicated=dedicated,
134 :     numRegs=C.numCell cellkind (),
135 :     maxRegs=C.maxCell,
136 :     regmap=regmap,
137 :     showReg=C.toString cellkind,
138 :     getreg=getreg,
139 :     getpair=fn _ => error "getpair",
140 :     firstPseudoR=C.firstPseudo,
141 :     proh=proh
142 :     }
143 :     val G.GRAPH{spilledRegs,...} = G
144 :    
145 :     val hasBeenSpilled = Intmap.mapWithDefault (spilledRegs,false)
146 :    
147 :     fun logGraph(header,G) =
148 :     if !dump_graph then
149 :     (TextIO.output(!debug_stream,
150 :     "-------------"^header^"-----------\n");
151 :     Core.dumpGraph G (!debug_stream)
152 :     )
153 :     else ()
154 :    
155 :     (*
156 :     * Build the interference graph
157 :     *)
158 :     fun buildGraph(G) =
159 :     let val moves = buildMethod(G,cellkind)
160 :     val worklists = (Core.initWorkLists G)
161 :     {moves=moves, deadCopyElim=deadCopyElim}
162 :     in if !count_dead then
163 :     Intmap.app (fn (_,NODE{uses=ref [],...}) => dead := !dead + 1
164 :     | _ => ()) nodes
165 :     else ();
166 :     logGraph("build",G);
167 :     worklists
168 :     end
169 :    
170 :     (*
171 :     * Potential spill phase
172 :     *)
173 :     fun chooseVictim{spillWkl} =
174 :     let fun dumpSpillCandidates(spillWkl) =
175 :     (print "Spill candidates:\n";
176 :     app (fn n => print(Core.show G n^" ")) spillWkl;
177 :     print "\n"
178 :     )
179 :     val {node,cost,spillWkl} =
180 :     SpillHeuristics.chooseSpillNode
181 :     {hasBeenSpilled=hasBeenSpilled,
182 :     spillWkl=spillWkl}
183 :     handle SpillHeuristics.NoCandidate =>
184 :     (Core.dumpGraph G (!debug_stream);
185 :     dumpSpillCandidates(spillWkl);
186 :     error ("chooseVictim")
187 :     )
188 :     in if !debug_spill then
189 :     (case node of
190 :     NONE => ()
191 :     | SOME(best as NODE{defs,uses,...}) =>
192 :     print("Spilling node "^Core.show G best^
193 :     " cost="^Real.toString cost^
194 :     " defs="^Int.toString(length(!defs))^
195 :     " uses="^Int.toString(length(!uses))^"\n"
196 :     )
197 :     ) else ();
198 :     {node=node,spillWkl=spillWkl}
199 :     end
200 :    
201 :     (*
202 : monnier 475 * Mark spill nodes
203 : monnier 469 *)
204 : monnier 475 fun markSpillNodes nodesToSpill =
205 :     let val marker = SPILLED(~1)
206 :     fun loop [] = ()
207 :     | loop(NODE{color, ...}::ns) = (color := marker; loop ns)
208 :     in loop nodesToSpill end
209 :    
210 : monnier 469 (*
211 :     * Actual spill phase.
212 :     * Insert spill node and incrementally
213 :     * update the interference graph.
214 :     *)
215 :     fun actualSpills{spills} =
216 : monnier 475 let val _ = if spillProp orelse spillCoalescing orelse
217 :     spillColoring then markSpillNodes spills
218 :     else ()
219 :     val spills = if spillProp then
220 :     Core.spillPropagation G spills else spills
221 :     val _ = if spillCoalescing then
222 : monnier 469 Core.spillCoalescing G spills else ()
223 :     val _ = if spillColoring then
224 :     Core.spillColoring G spills else ()
225 :     val {simplifyWkl,freezeWkl,moveWkl,spillWkl} =
226 :     Core.initWorkLists G
227 :     {moves=spillMethod{graph=G, cellkind=cellkind,
228 :     spill=spill, reload=reload,
229 :     copyInstr=copyInstr, nodes=spills
230 :     },
231 :     deadCopyElim=deadCopyElim
232 :     }
233 :     val _ = if !cfg_after_spill then
234 :     F.dumpFlowgraph("after spilling",
235 :     flowgraph,!debug_stream)
236 :     else ()
237 :     in logGraph("rebuild",G);
238 :     rebuild_count := !rebuild_count + 1;
239 :     (simplifyWkl, moveWkl, freezeWkl, spillWkl, [])
240 :     end
241 :    
242 :     (*
243 :     * Main loop of the algorithm
244 :     *)
245 :     fun main(G) =
246 :     let
247 :    
248 :     (* Main loop *)
249 :     fun loop(simplifyWkl,moveWkl,freezeWkl,spillWkl,stack) =
250 :     let val iteratedCoal = Core.iteratedCoalescing G
251 :     val potentialSpill = Core.potentialSpillNode G
252 :     (* simplify/coalesce/freeze/potential spill phases
253 :     * simplifyWkl -- non-move related nodes with low degree
254 :     * moveWkl -- moves to be considered for coalescing
255 :     * freezeWkl -- move related nodes (with low degree)
256 :     * spillWkl -- potential spill nodes
257 :     * stack -- simplified nodes
258 :     *)
259 :     fun iterate(simplifyWkl,moveWkl,freezeWkl,spillWkl,stack) =
260 :     let (* perform iterated coalescing *)
261 :     val {stack} = iteratedCoal{simplifyWkl=simplifyWkl,
262 :     moveWkl=moveWkl,
263 :     freezeWkl=freezeWkl,
264 :     stack=stack}
265 :     in case spillWkl of
266 :     [] => stack (* nothing to spill *)
267 :     | _ =>
268 :     let val {node,spillWkl} =
269 :     chooseVictim{spillWkl=spillWkl}
270 :     in case node of
271 :     SOME node => (* spill node and continue *)
272 :     let val {moveWkl,freezeWkl,stack} =
273 :     potentialSpill{node=node,stack=stack}
274 :     in iterate([],moveWkl,freezeWkl,spillWkl,stack)
275 :     end
276 :     | NONE => stack (* nothing to spill *)
277 :     end
278 :     end
279 :    
280 :     (* simplify the nodes *)
281 :     val stack = iterate
282 :     (simplifyWkl,moveWkl,freezeWkl,spillWkl,stack)
283 :     (* color the nodes *)
284 :     val {spills} = (Core.select G)
285 : monnier 475 {stack=stack, biased= biasedSelection}
286 : monnier 469 in (* check for actual spills *)
287 :     case spills of
288 :     [] => ()
289 :     | spills =>
290 :     (case mode of
291 :     REGISTER_ALLOCATION => loop(actualSpills{spills=spills})
292 :     | COPY_PROPAGATION => ()
293 :     )
294 :     end
295 :    
296 :     val {simplifyWkl, moveWkl, freezeWkl, spillWkl} = buildGraph G
297 :    
298 :     in loop(simplifyWkl, moveWkl, freezeWkl, spillWkl, [])
299 :     end
300 :    
301 :     fun initSpillProh(from,to) =
302 :     let val markAsSpilled = Intmap.add spilledRegs
303 :     fun loop r =
304 :     if r <= to then (markAsSpilled(r,true); loop(r+1)) else ()
305 :     in loop from end
306 :    
307 :     in if !cfg_before_ra then
308 :     F.dumpFlowgraph("before register allocation",
309 :     flowgraph,!debug_stream)
310 :     else ();
311 :     app initSpillProh spillProh;
312 :     main(G); (* main loop *)
313 :     (* update the regmap *)
314 :     logGraph("done",G);
315 :     case mode of
316 :     REGISTER_ALLOCATION => Core.finishRA G
317 :     | COPY_PROPAGATION => Core.finishCP G
318 :     ;
319 :     ra_count := !ra_count + 1;
320 :     if !cfg_after_ra then
321 :     F.dumpFlowgraph("after register allocation",
322 :     flowgraph,!debug_stream)
323 :     else ()
324 :     end
325 :    
326 :     fun regallocs [] = ()
327 :     | regallocs(p::ps) = (regalloc p; regallocs ps)
328 :    
329 :     in regallocs params;
330 :     flowgraph
331 :     end
332 :    
333 :     end

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