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 469 - (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 :     * Now with numerous extension:
7 :     *
8 :     * 1. Priority based coalescing
9 :     * 2. Priority based freezing
10 :     * 3. Priority based spilling
11 :     * 4. Biased coloring (optional)
12 :     * 5. Rematerialization (optional)
13 :     * 6. Register pair coloring (to support Sparc, C6, and others)
14 :     * 7. Splitting (optional)
15 :     *
16 :     * The basic structure of this register allocator is as follows:
17 :     * 1. RAGraph. This module enscapsulates the interference graph
18 :     * datatype (adjacency list + interference graph + node table)
19 :     * and contains nothing architecture specific.
20 :     * 2. RACore. This module implements the main part of the iterated
21 :     * coalescing algorithm, with frequency enhancements.
22 :     * 3. RA_FLOWGRAPH. This register allocator is parameterized
23 :     * with respect to this signature. This basically abstracts out
24 :     * the representation of the program flowgraph, and provide
25 :     * a few services to the main allocator, such as building the
26 :     * interference graph, rewriting the flowgraph after spilling,
27 :     * and rebuilding the interference graph after spilling.
28 :     * This module is responsible for caching any information necessary
29 :     * to make spilling fast.
30 :     * 4. This functor. This functor drives the entire process.
31 :     *
32 :     * -- Allen
33 :     *)
34 :    
35 :     functor RegisterAllocator
36 :     (SpillHeuristics : RA_SPILL_HEURISTICS)
37 :     (Flowgraph : RA_FLOWGRAPH) : RA =
38 :     struct
39 :    
40 :     structure F = Flowgraph
41 :     structure I = F.I
42 :     structure C = I.C
43 :     structure Core = RACore
44 :     structure G = Core.G
45 :    
46 :     datatype mode = REGISTER_ALLOCATION | COPY_PROPAGATION
47 :    
48 :     datatype optimization = DEAD_COPY_ELIM
49 :     | SPILL_COALESCING
50 :     | SPILL_COLORING
51 :    
52 :     type getreg = { pref : C.cell list,
53 :     stamp : int,
54 :     proh : int Array.array
55 :     } -> C.cell
56 :    
57 :     open G
58 :    
59 :     fun error msg = MLRiscErrorMsg.error("RegisterAllocator",msg)
60 :    
61 :     (*
62 :     * Debugging flags
63 :     *)
64 :     val cfg_before_ra = MLRiscControl.getFlag "dump-cfg-before-ra"
65 :     val cfg_after_ra = MLRiscControl.getFlag "dump-cfg-after-ra"
66 :     val cfg_after_spill = MLRiscControl.getFlag "dump-cfg-after-spilling"
67 :     val dump_graph = MLRiscControl.getFlag "dump-interference-graph"
68 :     val debug_spill = MLRiscControl.getFlag "ra-debug-spilling"
69 :     val ra_count = MLRiscControl.getCounter "ra-count"
70 :     val rebuild_count = MLRiscControl.getCounter "ra-rebuild"
71 :     val count_dead = MLRiscControl.getFlag "ra-count-dead-code"
72 :     val dead = MLRiscControl.getCounter "ra-dead-code"
73 :     val debug_stream = MLRiscControl.debug_stream
74 :    
75 :     (*
76 :     * Optimization flags
77 :     *)
78 :     val biasedColoring = MLRiscControl.getFlag "ra-biased-coloring"
79 :     val rematerialization = MLRiscControl.getFlag "ra-rematerialization"
80 :    
81 :     exception NodeTable
82 :    
83 :     (* This array is used for getreg.
84 :     * We allocate it once.
85 :     *)
86 :     val proh = Array.array(C.firstPseudo, ~1)
87 :    
88 :     (*
89 :     * Register allocator.
90 :     * spillProh is a list of registers that are not candidates for spills.
91 :     *)
92 :     fun ra mode params flowgraph =
93 :     let
94 :     (* Flowgraph methods *)
95 :     val {build=buildMethod, spill=spillMethod, ...} = F.services flowgraph
96 :    
97 :     (* Main function *)
98 :     fun regalloc{getreg, K, dedicated, copyInstr,
99 :     spill, reload, spillProh, cellkind, optimizations} =
100 :     if C.numCell cellkind () = 0
101 :     then ()
102 :     else
103 :     let fun getOpt([], dce, sc, sp) = (dce, sc, sp)
104 :     | getOpt(DEAD_COPY_ELIM::opts, dce, sc, sp) =
105 :     getOpt(opts, true, sc, sp)
106 :     | getOpt(SPILL_COALESCING::opts, dce, sc, sp) =
107 :     getOpt(opts, dce, true, sp)
108 :     | getOpt(SPILL_COLORING::opts, dce, sc, sp) =
109 :     getOpt(opts, dce, sc, true)
110 :    
111 :     val (deadCopyElim, spillCoalescing, spillColoring) =
112 :     getOpt(optimizations, false, false, false)
113 :    
114 :     (* extract the regmap and blocks from the flowgraph *)
115 :     val regmap = F.regmap flowgraph (* the register map *)
116 :    
117 :     (* the nodes table *)
118 :     val nodes = Intmap.new(32,NodeTable)
119 :     (* create an empty interference graph *)
120 :     val G = G.newGraph{nodes=nodes,
121 :     K=K,
122 :     dedicated=dedicated,
123 :     numRegs=C.numCell cellkind (),
124 :     maxRegs=C.maxCell,
125 :     regmap=regmap,
126 :     showReg=C.toString cellkind,
127 :     getreg=getreg,
128 :     getpair=fn _ => error "getpair",
129 :     firstPseudoR=C.firstPseudo,
130 :     proh=proh
131 :     }
132 :     val G.GRAPH{spilledRegs,...} = G
133 :    
134 :     val hasBeenSpilled = Intmap.mapWithDefault (spilledRegs,false)
135 :    
136 :     fun logGraph(header,G) =
137 :     if !dump_graph then
138 :     (TextIO.output(!debug_stream,
139 :     "-------------"^header^"-----------\n");
140 :     Core.dumpGraph G (!debug_stream)
141 :     )
142 :     else ()
143 :    
144 :     (*
145 :     * Build the interference graph
146 :     *)
147 :     fun buildGraph(G) =
148 :     let val moves = buildMethod(G,cellkind)
149 :     val worklists = (Core.initWorkLists G)
150 :     {moves=moves, deadCopyElim=deadCopyElim}
151 :     in if !count_dead then
152 :     Intmap.app (fn (_,NODE{uses=ref [],...}) => dead := !dead + 1
153 :     | _ => ()) nodes
154 :     else ();
155 :     logGraph("build",G);
156 :     worklists
157 :     end
158 :    
159 :     (*
160 :     * Potential spill phase
161 :     *)
162 :     fun chooseVictim{spillWkl} =
163 :     let fun dumpSpillCandidates(spillWkl) =
164 :     (print "Spill candidates:\n";
165 :     app (fn n => print(Core.show G n^" ")) spillWkl;
166 :     print "\n"
167 :     )
168 :     val {node,cost,spillWkl} =
169 :     SpillHeuristics.chooseSpillNode
170 :     {hasBeenSpilled=hasBeenSpilled,
171 :     spillWkl=spillWkl}
172 :     handle SpillHeuristics.NoCandidate =>
173 :     (Core.dumpGraph G (!debug_stream);
174 :     dumpSpillCandidates(spillWkl);
175 :     error ("chooseVictim")
176 :     )
177 :     in if !debug_spill then
178 :     (case node of
179 :     NONE => ()
180 :     | SOME(best as NODE{defs,uses,...}) =>
181 :     print("Spilling node "^Core.show G best^
182 :     " cost="^Real.toString cost^
183 :     " defs="^Int.toString(length(!defs))^
184 :     " uses="^Int.toString(length(!uses))^"\n"
185 :     )
186 :     ) else ();
187 :     {node=node,spillWkl=spillWkl}
188 :     end
189 :    
190 :     (*
191 :     * Rematerialization
192 :     *)
193 :     fun rematerialize{node} = error "rematerialize"
194 :    
195 :     (*
196 :     * Splitting
197 :     *)
198 :     fun split{node} = error "split"
199 :    
200 :     (*
201 :     * Actual spill phase.
202 :     * Insert spill node and incrementally
203 :     * update the interference graph.
204 :     *)
205 :     fun actualSpills{spills} =
206 :     let val _ = if spillCoalescing then
207 :     Core.spillCoalescing G spills else ()
208 :     val _ = if spillColoring then
209 :     Core.spillColoring G spills else ()
210 :     val {simplifyWkl,freezeWkl,moveWkl,spillWkl} =
211 :     Core.initWorkLists G
212 :     {moves=spillMethod{graph=G, cellkind=cellkind,
213 :     spill=spill, reload=reload,
214 :     copyInstr=copyInstr, nodes=spills
215 :     },
216 :     deadCopyElim=deadCopyElim
217 :     }
218 :     val _ = if !cfg_after_spill then
219 :     F.dumpFlowgraph("after spilling",
220 :     flowgraph,!debug_stream)
221 :     else ()
222 :     in logGraph("rebuild",G);
223 :     rebuild_count := !rebuild_count + 1;
224 :     (simplifyWkl, moveWkl, freezeWkl, spillWkl, [])
225 :     end
226 :    
227 :     (*
228 :     * Main loop of the algorithm
229 :     *)
230 :     fun main(G) =
231 :     let
232 :    
233 :     (* Main loop *)
234 :     fun loop(simplifyWkl,moveWkl,freezeWkl,spillWkl,stack) =
235 :     let val iteratedCoal = Core.iteratedCoalescing G
236 :     val potentialSpill = Core.potentialSpillNode G
237 :     (* simplify/coalesce/freeze/potential spill phases
238 :     * simplifyWkl -- non-move related nodes with low degree
239 :     * moveWkl -- moves to be considered for coalescing
240 :     * freezeWkl -- move related nodes (with low degree)
241 :     * spillWkl -- potential spill nodes
242 :     * stack -- simplified nodes
243 :     *)
244 :     fun iterate(simplifyWkl,moveWkl,freezeWkl,spillWkl,stack) =
245 :     let (* perform iterated coalescing *)
246 :     val {stack} = iteratedCoal{simplifyWkl=simplifyWkl,
247 :     moveWkl=moveWkl,
248 :     freezeWkl=freezeWkl,
249 :     stack=stack}
250 :     in case spillWkl of
251 :     [] => stack (* nothing to spill *)
252 :     | _ =>
253 :     let val {node,spillWkl} =
254 :     chooseVictim{spillWkl=spillWkl}
255 :     in case node of
256 :     SOME node => (* spill node and continue *)
257 :     let val {moveWkl,freezeWkl,stack} =
258 :     potentialSpill{node=node,stack=stack}
259 :     in iterate([],moveWkl,freezeWkl,spillWkl,stack)
260 :     end
261 :     | NONE => stack (* nothing to spill *)
262 :     end
263 :     end
264 :    
265 :     (* simplify the nodes *)
266 :     val stack = iterate
267 :     (simplifyWkl,moveWkl,freezeWkl,spillWkl,stack)
268 :     (* color the nodes *)
269 :     val {spills} = (Core.select G)
270 :     {stack=stack, biased= !biasedColoring}
271 :     in (* check for actual spills *)
272 :     case spills of
273 :     [] => ()
274 :     | spills =>
275 :     (case mode of
276 :     REGISTER_ALLOCATION => loop(actualSpills{spills=spills})
277 :     | COPY_PROPAGATION => ()
278 :     )
279 :     end
280 :    
281 :     val {simplifyWkl, moveWkl, freezeWkl, spillWkl} = buildGraph G
282 :    
283 :     in loop(simplifyWkl, moveWkl, freezeWkl, spillWkl, [])
284 :     end
285 :    
286 :     fun initSpillProh(from,to) =
287 :     let val markAsSpilled = Intmap.add spilledRegs
288 :     fun loop r =
289 :     if r <= to then (markAsSpilled(r,true); loop(r+1)) else ()
290 :     in loop from end
291 :    
292 :     in if !cfg_before_ra then
293 :     F.dumpFlowgraph("before register allocation",
294 :     flowgraph,!debug_stream)
295 :     else ();
296 :     app initSpillProh spillProh;
297 :     main(G); (* main loop *)
298 :     (* update the regmap *)
299 :     logGraph("done",G);
300 :     case mode of
301 :     REGISTER_ALLOCATION => Core.finishRA G
302 :     | COPY_PROPAGATION => Core.finishCP G
303 :     ;
304 :     ra_count := !ra_count + 1;
305 :     if !cfg_after_ra then
306 :     F.dumpFlowgraph("after register allocation",
307 :     flowgraph,!debug_stream)
308 :     else ()
309 :     end
310 :    
311 :     fun regallocs [] = ()
312 :     | regallocs(p::ps) = (regalloc p; regallocs ps)
313 :    
314 :     in regallocs params;
315 :     flowgraph
316 :     end
317 :    
318 :     end

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