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

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