Annotation of /sml/trunk/src/MLRISC/ra/ra.sml

Parent Directory | 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