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

Parent Directory | Revision Log | Patch

	revision 475, Wed Nov 10 22:59:58 1999 UTC	revision 498, Tue Dec 7 15:44:50 1999 UTC
#	Line 48	Line 48
48	structure Core   = RACore	structure Core   = RACore
49	structure G      = Core.G	structure G      = Core.G
50
	datatype mode = REGISTER_ALLOCATION | COPY_PROPAGATION
	datatype optimization = DEAD_COPY_ELIM
	| SPILL_PROPAGATION
	| SPILL_COALESCING
	| SPILL_COLORING
	| BIASED_SELECTION
51	type getreg = { pref  : C.cell list,	type getreg = { pref  : C.cell list,
52	stamp : int,	stamp : int,
53	proh  : int Array.array	proh  : int Array.array
54	} -> C.cell	} -> C.cell
55
56		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	open G	open G
89
90	fun error msg = MLRiscErrorMsg.error("RegisterAllocator",msg)	fun error msg = MLRiscErrorMsg.error("RegisterAllocator",msg)
#	Line 75	Line 99
99	val debug_spill       = MLRiscControl.getFlag "ra-debug-spilling"	val debug_spill       = MLRiscControl.getFlag "ra-debug-spilling"
100	val ra_count          = MLRiscControl.getCounter "ra-count"	val ra_count          = MLRiscControl.getCounter "ra-count"
101	val rebuild_count     = MLRiscControl.getCounter "ra-rebuild"	val rebuild_count     = MLRiscControl.getCounter "ra-rebuild"
102
103		(*
104	val count_dead        = MLRiscControl.getFlag "ra-count-dead-code"	val count_dead        = MLRiscControl.getFlag "ra-count-dead-code"
105	val dead              = MLRiscControl.getCounter "ra-dead-code"	val dead              = MLRiscControl.getCounter "ra-dead-code"
106		*)
107	val debug_stream      = MLRiscControl.debug_stream	val debug_stream      = MLRiscControl.debug_stream
108
109	(*	(*
110	* Optimization flags	* Optimization flags
111	*)	*)
112		(*
113	val rematerialization = MLRiscControl.getFlag "ra-rematerialization"	val rematerialization = MLRiscControl.getFlag "ra-rematerialization"
114		*)
115
116	exception NodeTable	exception NodeTable
117
#	Line 95	Line 124
124	* Register allocator.	* Register allocator.
125	*    spillProh is a list of registers that are not candidates for spills.	*    spillProh is a list of registers that are not candidates for spills.
126	*)	*)
127	fun ra mode params flowgraph =	fun ra params flowgraph =
128	let	let
129	(* Flowgraph methods *)	(* Flowgraph methods *)
130	val {build=buildMethod, spill=spillMethod, ...} = F.services flowgraph	val {build=buildMethod, spill=spillMethod, ...} = F.services flowgraph
131
132		(* 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	(* Main function *)	(* Main function *)
140	fun regalloc{getreg, K, dedicated, copyInstr,	fun regalloc{getreg, K, dedicated, copyInstr,
141	spill, reload, spillProh, cellkind, optimizations} =	spill, spillSrc, spillCopyTmp, renameSrc,
142	if C.numCell cellkind () = 0	reload, reloadDst, spillProh, cellkind, mode,
143		firstMemReg, numMemRegs} =
144		let val numCell = C.numCell cellkind ()
145		in  if numCell = 0
146	then ()	then ()
147	else	else
148	let fun getOpt([], dce, sp, sc, scolor, bs) = (dce, sp, sc, scolor, bs)	let (* extract the regmap and blocks from the flowgraph *)
	| getOpt(DEAD_COPY_ELIM::opts, dce, sp, sc, scolor, bs) =
	getOpt(opts, true, sp, sc, scolor, bs)
	| getOpt(SPILL_PROPAGATION::opts, dce, sp, sc, scolor, bs) =
	getOpt(opts, dce, true, sc, scolor, bs)
	| getOpt(SPILL_COALESCING::opts, dce, sp, sc, scolor, bs) =
	getOpt(opts, dce, sp, true, scolor, bs)
	| getOpt(SPILL_COLORING::opts, dce, sp, sc, scolor, bs) =
	getOpt(opts, dce, sp, sc, true, bs)
	| getOpt(BIASED_SELECTION::opts, dce, sp, sc, scolor, bs) =
	getOpt(opts, dce, sp, sc, scolor, true)
	val (deadCopyElim, spillProp, spillCoalescing,
	spillColoring, biasedSelection) =
	getOpt(optimizations, false, false, false, false, false)
	(* extract the regmap and blocks from the flowgraph *)
149	val regmap = F.regmap flowgraph (* the register map *)	val regmap = F.regmap flowgraph (* the register map *)
150
151	(* the nodes table *)	(* the nodes table *)
152	val nodes  = Intmap.new(32,NodeTable)	val nodes  = Intmap.new(numCell,NodeTable)
153	(* create an empty interference graph *)	(* create an empty interference graph *)
154	val G      = G.newGraph{nodes=nodes,	val G      = G.newGraph{nodes=nodes,
155	K=K,	K=K,
156	dedicated=dedicated,	dedicated=dedicated,
157	numRegs=C.numCell cellkind (),	numRegs=numCell,
158	maxRegs=C.maxCell,	maxRegs=C.maxCell,
159	regmap=regmap,	regmap=regmap,
160	showReg=C.toString cellkind,	showReg=C.toString cellkind,
161	getreg=getreg,	getreg=getreg,
162	getpair=fn _ => error "getpair",	getpair=fn _ => error "getpair",
163	firstPseudoR=C.firstPseudo,	firstPseudoR=C.firstPseudo,
164	proh=proh	proh=proh,
165		mode=Word.orb(Flowgraph.mode,
166		Word.orb(mode,SpillHeuristics.mode)),
167		spillLoc=spillLoc,
168		firstMemReg=firstMemReg,
169		numMemRegs=numMemRegs
170	}	}
171	val G.GRAPH{spilledRegs,...} = G	val G.GRAPH{spilledRegs, pseudoCount, spillFlag, ...} = G
172
173	val hasBeenSpilled = Intmap.mapWithDefault (spilledRegs,false)	val hasBeenSpilled = Intmap.mapWithDefault (spilledRegs,false)
174
#	Line 156	Line 184
184	* Build the interference graph	* Build the interference graph
185	*)	*)
186	fun buildGraph(G) =	fun buildGraph(G) =
187	let val moves = buildMethod(G,cellkind)	let val _ = if debug then print "build..." else ()
188	val worklists = (Core.initWorkLists G)	val moves = buildMethod(G,cellkind)
189	{moves=moves, deadCopyElim=deadCopyElim}	val worklists =
190	in  if !count_dead then	(Core.initWorkLists G) {moves=moves}
191		in  (* if !count_dead then
192	Intmap.app (fn (_,NODE{uses=ref [],...}) => dead := !dead + 1	Intmap.app (fn (_,NODE{uses=ref [],...}) => dead := !dead + 1
193	| _ => ()) nodes	| _ => ()) nodes
194	else ();	else (); *)
195	logGraph("build",G);	logGraph("build",G);
196		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	worklists	worklists
204	end	end
205
#	Line 176	Line 212
212	app (fn n => print(Core.show G n^" ")) spillWkl;	app (fn n => print(Core.show G n^" ")) spillWkl;
213	print "\n"	print "\n"
214	)	)
215		(* Initialize if it is the first time we spill *)
216		val _ = if !spillFlag then () else SpillHeuristics.init()
217		(* Choose a node *)
218	val {node,cost,spillWkl} =	val {node,cost,spillWkl} =
219	SpillHeuristics.chooseSpillNode	SpillHeuristics.chooseSpillNode
220	{hasBeenSpilled=hasBeenSpilled,	{graph=G, hasBeenSpilled=hasBeenSpilled,
221	spillWkl=spillWkl}	spillWkl=spillWkl}
222	handle SpillHeuristics.NoCandidate =>	handle SpillHeuristics.NoCandidate =>
223	(Core.dumpGraph G (!debug_stream);	(Core.dumpGraph G (!debug_stream);
#	Line 207	Line 246
246	| loop(NODE{color, ...}::ns) = (color := marker; loop ns)	| loop(NODE{color, ...}::ns) = (color := marker; loop ns)
247	in  loop nodesToSpill end	in  loop nodesToSpill end
248
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	(*	(*
260	* Actual spill phase.	* Actual spill phase.
261	*   Insert spill node and incrementally	*   Insert spill node and incrementally
262	*   update the interference graph.	*   update the interference graph.
263	*)	*)
264	fun actualSpills{spills} =	fun actualSpills{spills} =
265	let val _ = if spillProp orelse spillCoalescing orelse	let val _ = if debug then print "spill..." else ();
266	spillColoring then markSpillNodes spills	val _ = if isOn(mode,
267		SPILL_COALESCING+
268		SPILL_PROPAGATION+
269		SPILL_COLORING) then
270		markSpillNodes spills
271	else ()	else ()
272	val spills = if spillProp then	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	Core.spillPropagation G spills else spills
277	val _ = if spillCoalescing then	val _ = if isOn(mode,SPILL_COALESCING) then
278	Core.spillCoalescing G spills else ()	Core.spillCoalescing G spills else ()
279	val _ = if spillColoring then	val _ = if isOn(mode,SPILL_COLORING) then
280	Core.spillColoring G spills else ()	Core.spillColoring G spills else ()
281		val _ = if isOn(mode,SPILL_COALESCING+SPILL_PROPAGATION) then
282		markMemRegs spills else ()
283		val _ = logGraph("actual spill",G);
284	val {simplifyWkl,freezeWkl,moveWkl,spillWkl} =	val {simplifyWkl,freezeWkl,moveWkl,spillWkl} =
285	Core.initWorkLists G	Core.initWorkLists G
286	{moves=spillMethod{graph=G, cellkind=cellkind,	{moves=spillMethod{graph=G, cellkind=cellkind,
287	spill=spill, reload=reload,	spill=spill, spillSrc=spillSrc,
288		spillCopyTmp=spillCopyTmp,
289		renameSrc=renameSrc,
290		reload=reload, reloadDst=reloadDst,
291	copyInstr=copyInstr, nodes=spills	copyInstr=copyInstr, nodes=spills
	},
	deadCopyElim=deadCopyElim
292	}	}
293	val _ = if !cfg_after_spill then	}
294	F.dumpFlowgraph("after spilling",	val _ = dumpFlowgraph(cfg_after_spill,"after spilling")
	flowgraph,!debug_stream)
	else ()
295	in  logGraph("rebuild",G);	in  logGraph("rebuild",G);
296		if debug then print "done\n" else ();
297	rebuild_count := !rebuild_count + 1;	rebuild_count := !rebuild_count + 1;
298	(simplifyWkl, moveWkl, freezeWkl, spillWkl, [])	(simplifyWkl, moveWkl, freezeWkl, spillWkl, [])
299	end	end
#	Line 265	Line 324
324	in  case spillWkl of	in  case spillWkl of
325	[] => stack (* nothing to spill *)	[] => stack (* nothing to spill *)
326	|  _ =>	|  _ =>
327		if !pseudoCount = 0 (* all nodes simplified *)
328		then stack
329		else
330	let val {node,spillWkl} =	let val {node,spillWkl} =
331	chooseVictim{spillWkl=spillWkl}	chooseVictim{spillWkl=spillWkl}
332	in  case node of	in  case node of
333	SOME node => (* spill node and continue *)	SOME node => (* spill node and continue *)
334	let val {moveWkl,freezeWkl,stack} =	let val _ = if debug then print "-" else ()
335		val {moveWkl,freezeWkl,stack} =
336	potentialSpill{node=node,stack=stack}	potentialSpill{node=node,stack=stack}
337	in  iterate([],moveWkl,freezeWkl,spillWkl,stack)	in  iterate([],moveWkl,freezeWkl,spillWkl,stack)
338	end	end
#	Line 281	Line 344
344	val stack = iterate	val stack = iterate
345	(simplifyWkl,moveWkl,freezeWkl,spillWkl,stack)	(simplifyWkl,moveWkl,freezeWkl,spillWkl,stack)
346	(* color the nodes *)	(* color the nodes *)
347	val {spills} = (Core.select G)	val {spills} = (Core.select G) {stack=stack}
	{stack=stack, biased= biasedSelection}
348	in  (* check for actual spills *)	in  (* check for actual spills *)
349	case spills of	case spills of
350	[] => ()	[] => ()
351	| spills =>	| spills =>
352	(case mode of	(if isOn(mode,COPY_PROPAGATION) then ()
353	REGISTER_ALLOCATION => loop(actualSpills{spills=spills})	else loop(actualSpills{spills=spills})
	| COPY_PROPAGATION => ()
354	)	)
355	end	end
356
#	Line 304	Line 365
365	if r <= to then (markAsSpilled(r,true); loop(r+1)) else ()	if r <= to then (markAsSpilled(r,true); loop(r+1)) else ()
366	in  loop from end	in  loop from end
367
368	in  if !cfg_before_ra then	in  dumpFlowgraph(cfg_before_ra,"before register allocation");
	F.dumpFlowgraph("before register allocation",
	flowgraph,!debug_stream)
	else ();
369	app initSpillProh spillProh;	app initSpillProh spillProh;
370	main(G); (* main loop *)	main(G); (* main loop *)
371	(* update the regmap *)	(* update the regmap *)
372	logGraph("done",G);	logGraph("done",G);
373	case mode of	if isOn(mode,COPY_PROPAGATION)
374	REGISTER_ALLOCATION => Core.finishRA G	then Core.finishCP G
375	| COPY_PROPAGATION => Core.finishCP G	else Core.finishRA G
376	;	;
377	ra_count := !ra_count + 1;	ra_count := !ra_count + 1;
378	if !cfg_after_ra then	dumpFlowgraph(cfg_after_ra,"after register allocation");
379	F.dumpFlowgraph("after register allocation",	(* Clean up spilling *)
380	flowgraph,!debug_stream)	SpillHeuristics.init()
381	else ()	end
382	end	end
383
384	fun regallocs [] = ()	fun regallocs [] = ()

---

Colored Diff Long Colored Diff Unidiff Context Diff Side by Side

Legend: Removed from v.475   changed lines   Added in v.498

---

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