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

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