Annotation of /sml/trunk/src/compiler/CodeGen/main/regalloc.sml

Parent Directory | Revision Log

---

Revision 576 - (view) (download)

1 :	monnier	427	(*
2 :			* This functor factors out the machine independent part of the register
3 :			* allocator. This works well for RISC machines; not applicable to x86.
4 :			*)
5 :	monnier	475	functor RegAlloc
6 :	monnier	427	(structure I : INSTRUCTIONS
7 :			structure MachSpec : MACH_SPEC
8 :			structure Flowgraph : FLOWGRAPH
9 :			structure CpsRegs : CPSREGS
10 :			structure InsnProps : INSN_PROPERTIES
11 :			structure Rewrite : REWRITE_INSTRUCTIONS
12 :			structure Asm : INSTRUCTION_EMITTER
13 :			sharing CpsRegs.T.Constant=Flowgraph.I.Constant
14 :			sharing InsnProps.I = Flowgraph.I = Asm.I = Rewrite.I = I
15 :			sharing Asm.P = CpsRegs.T.PseudoOp = Flowgraph.P
16 :
17 :	monnier	469	(* Is this a pure instruction *)
18 :			val pure : I.instruction -> bool
19 :	monnier	427
20 :			(* These functions are used to create copy instructions for
21 :			* integer and floating point registers. Given dst/src lists,
22 :			* and a copy instruction, return a new copy instruction with the same
23 :			* temporary as the old one.
24 :			*)
25 :	monnier	498	val copyR : (int list * int list) * I.instruction -> I.instruction
26 :			val copyF : (int list * int list) * I.instruction -> I.instruction
27 :	monnier	427
28 :			(* These functions are used to spill the temporary used in the copy
29 :			* onto some stack offset.
30 :			*)
31 :			val spillCopyTmp : I.instruction * int -> I.instruction
32 :			val spillFcopyTmp : I.instruction * int -> I.instruction
33 :
34 :			(*
35 :			* These functions are used to spill a register onto some stack offset
36 :			*)
37 :			val spillInstrR : I.C.cell * int -> I.instruction list
38 :			val spillInstrF : I.C.cell * int -> I.instruction list
39 :
40 :			(*
41 :			* These functions are used to reload a register from some stack offset,
42 :			* and concatenate the reload code with the given instruction list.
43 :			*)
44 :			val reloadInstrR : I.C.cell * int * I.instruction list -> I.instruction list
45 :			val reloadInstrF : I.C.cell * int * I.instruction list -> I.instruction list
46 :			) : REGALLOC =
47 :			struct
48 :
49 :			structure F = Flowgraph
50 :			structure I = F.I
51 :			structure P = InsnProps
52 :			structure Cells = I.C
53 :
54 :			(* Counters for register allocation *)
55 :			val intSpillsCnt = MLRiscControl.getCounter "ra-int-spills"
56 :			val intReloadsCnt = MLRiscControl.getCounter "ra-int-reloads"
57 :	monnier	498	val intRenamesCnt = MLRiscControl.getCounter "ra-int-renames"
58 :	monnier	427	val floatSpillsCnt = MLRiscControl.getCounter "ra-float-spills"
59 :			val floatReloadsCnt = MLRiscControl.getCounter "ra-float-reloads"
60 :	monnier	498	val floatRenamesCnt = MLRiscControl.getCounter "ra-float-renames"
61 :	monnier	427
62 :			fun error msg = MLRiscErrorMsg.error(MachSpec.architecture,msg)
63 :
64 :			val itow = Word.fromInt
65 :
66 :	monnier	498	(*
67 :			* Make arithmetic non-overflow trapping.
68 :			* This makes sure that if we happen to run the compiler for a long
69 :			* period of time overflowing counters will not crash the compiler.
70 :			*)
71 :			fun x + y = Word.toIntX(Word.+(Word.fromInt x, Word.fromInt y))
72 :			fun x - y = Word.toIntX(Word.-(Word.fromInt x, Word.fromInt y))
73 :
74 :	monnier	427	(* GetReg specialized to integer and floating point registers *)
75 :			local
76 :			val {low,high} = Cells.cellRange Cells.GP
77 :			in
78 :			structure GR = GetReg(val first=low val nRegs=high-low+1
79 :			val available=CpsRegs.availR)
80 :	monnier	469	val dedicatedR = Array.array(high+1,false)
81 :			val _ = app (fn r => Array.update(dedicatedR,r,true)) CpsRegs.dedicatedR
82 :
83 :	monnier	427	end
84 :			local
85 :			val {low,high} = Cells.cellRange Cells.FP
86 :			in
87 :			structure FR = GetReg(val first=low val nRegs=high-low+1
88 :			val available=CpsRegs.availF)
89 :	monnier	469	val dedicatedF = Array.array(high+1,false)
90 :			val _ = app (fn r => Array.update(dedicatedF,r,true)) CpsRegs.dedicatedF
91 :	monnier	427	end
92 :
93 :			exception RegSpills and FregSpills
94 :			val initialSpillOffset = MachSpec.initialSpillOffset
95 :			val spillOffset = ref initialSpillOffset
96 :			val spillAreaSz = MachSpec.spillAreaSz
97 :			val regspills : int Intmap.intmap = Intmap.new(0,RegSpills)
98 :			val fregspills : int Intmap.intmap = Intmap.new(0,FregSpills)
99 :			val lookupReg = Intmap.map regspills
100 :			val enterReg = Intmap.add regspills
101 :			val lookupFreg = Intmap.map fregspills
102 :			val enterFreg = Intmap.add fregspills
103 :
104 :			fun spillInit() =
105 :			((* Reset the regspills/fregspills map by need. *)
106 :			if !spillOffset = initialSpillOffset then ()
107 :			else (Intmap.clear regspills;
108 :			Intmap.clear fregspills
109 :			)
110 :			;
111 :			spillOffset := initialSpillOffset
112 :			)
113 :
114 :			fun newOffset offset =
115 :			if offset >= spillAreaSz then error "spill area too small"
116 :			else spillOffset := offset
117 :
118 :			(* Get spill location for integer registers *)
119 :			fun getRegLoc reg = lookupReg reg handle _ =>
120 :			let val offset = !spillOffset
121 :			in newOffset(offset+4);
122 :			enterReg (reg,offset);
123 :			offset
124 :			end
125 :
126 :			(* Get spill location for floating point registers *)
127 :			fun getFregLoc freg = lookupFreg freg handle _ =>
128 :			let val offset = !spillOffset
129 :			val aligned = Word.toIntX (Word.andb(itow (offset+7), itow ~8))
130 :			in
131 :			newOffset(aligned+8);
132 :			enterFreg (freg, aligned);
133 :			aligned
134 :			end
135 :
136 :			(* Spill integer register *)
137 :	monnier	498	fun spillR{annotations,kill=true,regmap,reg,spillLoc,instr} =
138 :			if pure instr then {code=[], proh=[], newReg=NONE}
139 :	monnier	469	else spillR{annotations=annotations,kill=false,
140 :			regmap=regmap,spillLoc=spillLoc,
141 :	monnier	498	reg=reg,instr=instr}
142 :			| spillR{annotations,kill,regmap,reg,spillLoc,instr} =
143 :	monnier	469	let val _ = intSpillsCnt := !intSpillsCnt + 1
144 :	monnier	498	val loc = getRegLoc spillLoc
145 :			val newR = Cells.newReg()
146 :			val instr' = Rewrite.rewriteDef(regmap, instr, reg, newR)
147 :			in {code=instr'::spillInstrR(newR,loc), proh=[newR], newReg=SOME newR}
148 :	monnier	427	end
149 :
150 :	monnier	498	fun spillReg{annotations,src,reg,spillLoc} =
151 :			(intSpillsCnt := !intSpillsCnt + 1;
152 :			spillInstrR(src,getRegLoc spillLoc)
153 :			)
154 :
155 :			fun spillTmp{annotations,copy,spillLoc} =
156 :			(intSpillsCnt := !intSpillsCnt + 1;
157 :			spillCopyTmp(copy,getRegLoc spillLoc)
158 :			)
159 :
160 :	monnier	427	(* Spill floating point register *)
161 :	monnier	498	fun spillF{annotations,kill=true,regmap,reg,spillLoc,instr} =
162 :			if pure instr then {code=[], proh=[], newReg=NONE}
163 :	monnier	469	else spillF{annotations=annotations,kill=false,
164 :			regmap=regmap,spillLoc=spillLoc,
165 :	monnier	498	reg=reg,instr=instr}
166 :			| spillF{annotations,kill,regmap,reg,spillLoc,instr} =
167 :	monnier	469	let val _ = floatSpillsCnt := !floatSpillsCnt + 1
168 :	monnier	498	val loc = getFregLoc spillLoc
169 :			val newR = Cells.newFreg()
170 :			val instr' = Rewrite.frewriteDef(regmap, instr, reg, newR)
171 :			in {code=instr'::spillInstrF(newR,loc), proh=[newR], newReg=SOME newR}
172 :	monnier	427	end
173 :
174 :	monnier	498	fun spillFreg{annotations,reg,src,spillLoc} =
175 :			(floatSpillsCnt := !floatSpillsCnt + 1;
176 :			spillInstrF(src,getFregLoc spillLoc)
177 :			)
178 :
179 :			fun spillFtmp{annotations,copy,spillLoc} =
180 :			(floatSpillsCnt := !floatSpillsCnt + 1;
181 :			spillFcopyTmp(copy,getFregLoc spillLoc)
182 :			)
183 :
184 :			(* Rename integer register *)
185 :			fun renameR{regmap,fromSrc,toSrc,instr} =
186 :			let val _ = intRenamesCnt := !intRenamesCnt + 1
187 :			val instr' = Rewrite.rewriteUse(regmap, instr, fromSrc, toSrc)
188 :			in {code=[instr'], proh=[], newReg=SOME toSrc}
189 :			end
190 :
191 :	monnier	427	(* Reload integer register *)
192 :	monnier	498	fun reloadR{annotations,regmap,reg,spillLoc,instr} =
193 :			let val _ = intReloadsCnt := !intReloadsCnt + 1
194 :			val loc = getRegLoc spillLoc
195 :			val newR = Cells.newReg()
196 :			val instr' = Rewrite.rewriteUse(regmap, instr, reg, newR)
197 :			in {code=reloadInstrR(newR,loc,[instr']), proh=[newR], newReg=SOME newR}
198 :	monnier	427	end
199 :	monnier	498
200 :			fun reloadReg{annotations,reg,dst,spillLoc} =
201 :			(intReloadsCnt := !intReloadsCnt + 1;
202 :			reloadInstrR(dst,getRegLoc spillLoc,[])
203 :			)
204 :	monnier	427
205 :	monnier	498	(* Rename floating point register *)
206 :			fun renameF{regmap,fromSrc,toSrc,instr} =
207 :			let val _ = floatRenamesCnt := !floatRenamesCnt + 1
208 :			val instr' = Rewrite.frewriteUse(regmap, instr, fromSrc, toSrc)
209 :			in {code=[instr'], proh=[], newReg=SOME toSrc}
210 :			end
211 :
212 :	monnier	427	(* Reload floating point register *)
213 :	monnier	498	fun reloadF{annotations,regmap,reg,spillLoc,instr} =
214 :			let val _ = floatReloadsCnt := !floatReloadsCnt + 1
215 :			val loc = getFregLoc(spillLoc)
216 :			val newR = Cells.newFreg()
217 :			val instr' = Rewrite.frewriteUse(regmap, instr, reg, newR)
218 :			in {code=reloadInstrF(newR,loc,[instr']), proh=[newR], newReg=SOME newR}
219 :	monnier	427	end
220 :
221 :	monnier	498	fun reloadFreg{annotations,reg,dst,spillLoc} =
222 :			(floatReloadsCnt := !floatReloadsCnt + 1;
223 :			reloadInstrF(dst,getFregLoc spillLoc,[])
224 :			)
225 :
226 :	monnier	469	(* The generic register allocator *)
227 :			structure Ra =
228 :			RegisterAllocator
229 :	monnier	498	(ChaitinSpillHeur)
230 :			(* (ChowHennessySpillHeur) *)
231 :	monnier	469	(ClusterRA
232 :			(structure Flowgraph = F
233 :			structure Asm = Asm
234 :			structure InsnProps = InsnProps
235 :			)
236 :	monnier	427	)
237 :
238 :	monnier	469	val KR = length CpsRegs.availR
239 :			val KF = length CpsRegs.availF
240 :	monnier	427
241 :	monnier	469	val params =
242 :	monnier	498	[ { cellkind = I.C.GP,
243 :			getreg = GR.getreg,
244 :			spill = spillR,
245 :			spillSrc = spillReg,
246 :			spillCopyTmp = spillTmp,
247 :			reload = reloadR,
248 :			reloadDst = reloadReg,
249 :			renameSrc = renameR,
250 :			K = KR,
251 :			dedicated = dedicatedR,
252 :			copyInstr = fn i => [copyR i],
253 :			spillProh = [],
254 :	leunga	576	memRegs = [],
255 :	george	546	mode = Word.orb(Ra.SPILL_COLORING, Ra.HAS_PARALLEL_COPIES)
256 :	monnier	469	},
257 :	monnier	498	{ cellkind = I.C.FP,
258 :			getreg = FR.getreg,
259 :			spill = spillF,
260 :			spillSrc = spillFreg,
261 :			spillCopyTmp = spillFtmp,
262 :			reload = reloadF,
263 :			reloadDst = reloadFreg,
264 :			renameSrc = renameF,
265 :			K = KF,
266 :			dedicated = dedicatedF,
267 :			copyInstr = fn i => [copyF i],
268 :			spillProh = [],
269 :	leunga	576	memRegs = [],
270 :	monnier	498	mode = Ra.NO_OPTIMIZATION
271 :	monnier	469	}
272 :	monnier	498	] : Ra.raClient list
273 :	monnier	469
274 :	monnier	427	fun ra cluster =
275 :	monnier	469	(spillInit();
276 :			GR.reset();
277 :			FR.reset();
278 :	monnier	498	Ra.ra params cluster
279 :	monnier	469	)
280 :	monnier	427
281 :			end

---

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