Annotation of /MLRISC/trunk/amd64/ra/amd64RegAlloc.sml

Parent Directory | Revision Log

---

Revision 2793 - (view) (download)

1 :	mrainey	2619	(* amd64RegAlloc.sml
2 :			*
3 :			* Ties together the GP and FP register allocators.
4 :			*)
5 :
6 :			functor AMD64RegAlloc (
7 :			structure I : AMD64INSTR
8 :			structure SpillHeur : RA_SPILL_HEURISTICS
9 :			structure Props : AMD64INSN_PROPERTIES
10 :			where I = I
11 :			structure CFG : CONTROL_FLOW_GRAPH
12 :			where I = I
13 :			structure Spill : RA_SPILL
14 :			where I = I
15 :			structure Asm : INSTRUCTION_EMITTER
16 :			where I = I
17 :			and S.P = CFG.P
18 :
19 :			type spill_info
20 :			datatype spill_operand_kind = SPILL_LOC
21 :			| CONST_VAL
22 :
23 :			val beforeRA : CFG.cfg -> spill_info
24 :
25 :			datatype ra_phase = SPILL_PROPAGATION
26 :			| SPILL_COLORING
27 :
28 :			structure Int : sig
29 :			val avail : CellsBasis.cell list
30 :			val dedicated : CellsBasis.cell list
31 :			val spillLoc : {info:spill_info,
32 :			an :Annotations.annotations ref,
33 :			cell:CellsBasis.cell, (* spilled cell *)
34 :			id :RAGraph.logical_spill_id
35 :			} ->
36 :			{opnd: I.ea,
37 :			kind: spill_operand_kind
38 :			}
39 :			val spillInit : RAGraph.interferenceGraph -> unit
40 :			val phases : ra_phase list
41 :			end
42 :
43 :			structure Float : sig
44 :			val avail : CellsBasis.cell list
45 :			val dedicated : CellsBasis.cell list
46 :			val spillLoc : spill_info * Annotations.annotations ref *
47 :			RAGraph.logical_spill_id -> I.ea
48 :			val spillInit : RAGraph.interferenceGraph -> unit
49 :			val phases : ra_phase list
50 :			end
51 :
52 :			) : CFG_OPTIMIZATION =
53 :			struct
54 :
55 :			datatype ra_phase = datatype ra_phase
56 :
57 :			fun error msg = MLRiscErrorMsg.error ("AMD64RA", msg)
58 :			fun inc c = c := !c + 1
59 :
60 :			val intSpillCnt =
61 :			MLRiscControl.mkCounter ("ra-int-spills", "RA int spill count")
62 :			val intReloadCnt =
63 :			MLRiscControl.mkCounter ("ra-int-reloads", "RA int reload count")
64 :			val intRenameCnt =
65 :			MLRiscControl.mkCounter ("ra-int-renames", "RA int rename count")
66 :			val floatSpillCnt =
67 :			MLRiscControl.mkCounter ("ra-float-spills", "RA float spill count")
68 :			val floatReloadCnt =
69 :			MLRiscControl.mkCounter ("ra-float-reloads", "RA float reload count")
70 :			val floatRenameCnt =
71 :			MLRiscControl.mkCounter ("ra-float-renames", "RA float rename count")
72 :
73 :			structure CB = CellsBasis
74 :			structure C = I.C
75 :
76 :			val firstSpill = ref true
77 :			val firstFPSpill = ref true
78 :
79 :			fun spillInit (graph, CB.GP) =
80 :			if !firstSpill then (* only do this once! *)
81 :			(Int.spillInit graph;
82 :			firstSpill := false
83 :			)
84 :			else ()
85 :			| spillInit(graph, CB.FP) =
86 :			if !firstFPSpill then
87 :			(Float.spillInit graph;
88 :			firstFPSpill := false
89 :			)
90 :			else ()
91 :			| spillInit _ = error "spillInit"
92 :
93 :			(*
94 :			* Dead code elimination
95 :			*)
96 :			exception AMD64DeadCode
97 :			val affectedBlocks =
98 :			IntHashTable.mkTable(32, AMD64DeadCode) : bool IntHashTable.hash_table
99 :			val deadRegs =
100 :			IntHashTable.mkTable(32, AMD64DeadCode) : bool IntHashTable.hash_table
101 :
102 :			fun removeDeadCode(cfg as Graph.GRAPH graph) = let
103 :			val blocks = #nodes graph ()
104 :			val find = IntHashTable.find deadRegs
105 :			fun isDead r =
106 :			case find (CB.cellId r) of
107 :			SOME _ => true
108 :			| NONE => false
109 :			fun isAffected i = getOpt (IntHashTable.find affectedBlocks i, false)
110 :			fun isDeadInstr(I.ANNOTATION{i, ...}) = isDeadInstr i
111 :			| isDeadInstr(I.INSTR(I.MOVE{dst=I.Direct (_,rd), ...})) = isDead rd
112 :			| isDeadInstr(I.COPY{k=CB.GP, dst=[rd], ...}) = isDead rd
113 :			| isDeadInstr _ = false
114 :			fun scan [] = ()
115 :			| scan((blknum, CFG.BLOCK{insns, ...})::rest) =
116 :			(if isAffected blknum then
117 :			((* deadblocks := !deadblocks + 1; *)
118 :			insns := elim(!insns, [])
119 :			) else ();
120 :			scan rest)
121 :			and elim([], code) = rev code
122 :			| elim(i::instrs, code) =
123 :			if isDeadInstr i then
124 :			((* deadcode := !deadcode + 1; *) elim(instrs, code))
125 :			else elim(instrs, i::code)
126 :			in
127 :			if (IntHashTable.numItems affectedBlocks > 0)
128 :			then (
129 :			scan blocks;
130 :			IntHashTable.clear deadRegs;
131 :			IntHashTable.clear affectedBlocks)
132 :			else ()
133 :			end
134 :
135 :			structure CFG = CFG
136 :
137 :			(* use the standard register allocator *)
138 :			structure RA =
139 :			RegisterAllocator
140 :			(SpillHeur)
141 :			(MemoryRA
142 :			(RADeadCodeElim
143 :			(ClusterRA
144 :			(structure Flowgraph = CFG
145 :			structure Asm = Asm
146 :			structure InsnProps = Props
147 :			structure Spill = Spill
148 :			)
149 :			)
150 :			(fun cellkind CB.GP = true | cellkind _ = false
151 :			val deadRegs = deadRegs
152 :			val affectedBlocks = affectedBlocks
153 :			val spillInit = spillInit
154 :			)
155 :			)
156 :			)
157 :			structure PrintFlowgraph =
158 :			PrintFlowgraph (structure CFG = CFG
159 :			structure Asm = Asm)
160 :			structure SpillInstr = AMD64SpillInstr (
161 :			structure I = I
162 :			structure Props = Props)
163 :			val spillFInstr = SpillInstr.spill CB.FP
164 :			val reloadFInstr = SpillInstr.reload CB.FP
165 :			val spillInstr = SpillInstr.spill CB.GP
166 :			val reloadInstr = SpillInstr.reload CB.GP
167 :
168 :			val name = "AMD64RegAlloc"
169 :			val amd64CfgDebugFlg =
170 :			MLRiscControl.mkFlag ("amd64-cfg-debug", "amd64 CFG debug mode")
171 :
172 :			val nGPRegs = length Int.avail + length Int.dedicated
173 :			val nFPRegs = length Float.avail + length Float.dedicated
174 :
175 :			structure GPR = GetReg
176 :			(val nRegs = nGPRegs
177 :			val available = map CB.registerId Int.avail
178 :			val first = CB.registerId (I.C.GPReg 0))
179 :			structure FPR = GetReg
180 :			(val nRegs = nFPRegs
181 :			val available = map CB.registerId Float.avail
182 :			val first = CB.registerId (I.C.FPReg 0))
183 :
184 :			local
185 :			val dedicatedR = Array.array (nGPRegs, false)
186 :			val dedicatedF = Array.array (nFPRegs, false)
187 :			fun set (dedicated, []) = ()
188 :			| set (dedicated, r :: rs) = (
189 :			Array.update (dedicated, r, true);
190 :			set (dedicated, rs))
191 :			val _ = set (dedicatedR, map CB.registerId Int.dedicated)
192 :			val _ = set (dedicatedF, map CB.registerId Float.dedicated)
193 :			fun isDedicated dedicated r =
194 :			r < Array.length dedicated andalso Array.sub (dedicated, r)
195 :			in
196 :			val isDedicatedR = isDedicated dedicatedR
197 :			val isDedicatedF = isDedicated dedicatedF
198 :			end (* local *)
199 :
200 :			fun copy {dst, src, tmp} = I.COPY {k=CB.GP, sz=64, dst=dst, src=src, tmp=tmp}
201 :			fun fcopy{dst, src, tmp} = I.COPY{k=CB.FP, sz=64, dst=dst, src=src, tmp=tmp}
202 :			fun annotate ([], i) = i
203 :			| annotate (a :: an, i) = annotate (an, I.ANNOTATION {a=a, i=i})
204 :
205 :			fun resetRA() = (
206 :			firstSpill := true;
207 :			firstFPSpill := true;
208 :			IntHashTable.clear affectedBlocks;
209 :			IntHashTable.clear deadRegs;
210 :			GPR.reset ();
211 :			FPR.reset ())
212 :
213 :			fun getRegLoc(s, an, cell, RA.FRAME loc) =
214 :			Int.spillLoc {info=s, an=an, cell=cell, id=loc}
215 :			| getRegLoc(s, an, cell, RA.MEM_REG r) =
216 :			error "memory registers unsupported"
217 :
218 :			fun spillR s {annotations=an, kill, reg, spillLoc, instr} = let
219 :			fun annotate([], i) = i
220 :			| annotate(a::an, i) = annotate(an, I.ANNOTATION{a=a, i=i})
221 :			(* preserve annotation on instruction *)
222 :			fun spill(instrAn, I.ANNOTATION{a,i}) = spill(a::instrAn, i)
223 :			| spill(instrAn, I.KILL{regs, spilled}) =
224 :			{code=[annotate (instrAn,
225 :			I.KILL {regs=C.rmvReg (reg, regs),
226 :			spilled=C.addReg (reg, spilled)})],
227 :			proh = [], newReg=NONE}
228 :			| spill(instrAn, I.LIVE _) = error "spill: LIVE"
229 :			| spill(_, I.COPY _) = error "spill: COPY"
230 :			| spill(instrAn, I.INSTR _) = (case getRegLoc (s, an, reg, spillLoc)
231 :			of {opnd=spillLoc, kind=SPILL_LOC} =>
232 :			(inc intSpillCnt;
233 :			spillInstr (annotate(instrAn, instr), reg, spillLoc))
234 :			| _ => (* don't have to spill a constant *)
235 :			{code=[], newReg=NONE, proh=[]}
236 :			(* end case *))
237 :			in
238 :			spill([], instr)
239 :			end (* spillR *)
240 :
241 :			fun spillReg s {src, reg, spillLoc, annotations=an} = let
242 :			val _ = inc intSpillCnt
243 :			val {opnd=dstLoc, kind} = getRegLoc (s, an, reg, spillLoc)
244 :			val srcLoc = I.Direct (64, src)
245 :			in
246 :			if kind = CONST_VAL orelse Props.eqOpn (srcLoc, dstLoc)
247 :			then []
248 :			else [I.move {mvOp=I.MOVQ, src=srcLoc, dst=dstLoc}]
249 :			end (* spillReg *)
250 :
251 :			fun spillCopyTmp s {copy=I.COPY{k=CB.GP, src, dst,...},
252 :			reg, spillLoc, annotations=an} =
253 :			(case getRegLoc (s, an, reg, spillLoc)
254 :			of {opnd=tmp, kind=SPILL_LOC} => (
255 :			inc intSpillCnt;
256 :			copy{dst=dst, src=src, tmp=SOME tmp})
257 :			| _ => error "spillCopyTmp"
258 :			(* end case *))
259 :			| spillCopyTmp s {copy=I.ANNOTATION{i, a}, reg, spillLoc, annotations} =
260 :			I.ANNOTATION{i=spillCopyTmp s {copy=i, reg=reg, spillLoc=spillLoc,
261 :			annotations=annotations}, a=a}
262 :			| spillCopyTmp _ _ = error "spillCopyTmp"
263 :
264 :			fun reloadR s {annotations=an, reg, spillLoc, instr} = let
265 :			fun reload (instrAn, I.ANNOTATION{a,i}) = reload (a::instrAn, i)
266 :			| reload(instrAn, I.LIVE{regs, spilled}) =
267 :			{code=[I.LIVE{regs=C.rmvReg(reg, regs),
268 :			spilled=C.addReg(reg, spilled)}],
269 :			proh=[], newReg=NONE}
270 :			| reload(_, I.KILL _) = error "reload: KILL"
271 :			| reload (_, I.COPY _) = error "reload: COPY"
272 :			| reload(instrAn, instr as I.INSTR _) = (
273 :			inc intReloadCnt;
274 :			reloadInstr (annotate(instrAn, instr), reg,
275 :			#opnd(getRegLoc(s,an,reg,spillLoc))))
276 :			in
277 :			reload([], instr)
278 :			end (* reloadR *)
279 :
280 :			fun reloadReg s {dst, reg, spillLoc, annotations=an} = let
281 :			val _ = inc intReloadCnt
282 :			val srcLoc = #opnd (getRegLoc (s, an, reg, spillLoc))
283 :			val dstLoc = I.Direct (64, dst)
284 :			in
285 :			if Props.eqOpn(srcLoc,dstLoc)
286 :			then []
287 :			else [I.move{mvOp=I.MOVQ, src=srcLoc, dst=dstLoc}]
288 :			end (* reloadReg *)
289 :
290 :			fun renameR {instr, fromSrc, toSrc} = (
291 :			inc intRenameCnt;
292 :			reloadInstr (instr, fromSrc, I.Direct (64, toSrc)))
293 :
294 :			fun copyInstrR ((rds as [d], rss as [s]), _) =
295 :			if CB.sameColor(d,s) then [] else [copy {dst=rds, src=rss, tmp=NONE}]
296 :			| copyInstrR((rds, rss), I.COPY{k=CB.GP, tmp, ...}) =
297 :			[copy{dst=rds, src=rss, tmp=tmp}]
298 :			| copyInstrR(x, I.ANNOTATION{i, a}) =
299 :			copyInstrR (x, i) (* XXX *)
300 :			| copyInstrR _ = error "copyInstrR"
301 :
302 :			fun phases ps = let
303 :			fun f ([], m) = m
304 :			| f (SPILL_PROPAGATION::ps, m) = f (ps, RA.SPILL_PROPAGATION+m)
305 :			| f (SPILL_COLORING::ps, m) = f (ps, RA.SPILL_COLORING+m)
306 :			in
307 :			f (ps, RA.NO_OPTIMIZATION)
308 :			end
309 :
310 :			fun raInt s = {
311 :			spill = spillR s,
312 :			spillSrc = spillReg s,
313 :			spillCopyTmp= spillCopyTmp s,
314 :			reload = reloadR s,
315 :			reloadDst = reloadReg s,
316 :			renameSrc = renameR,
317 :			copyInstr = copyInstrR,
318 :			K = length Int.avail,
319 :			getreg = GPR.getreg,
320 :			cellkind = CB.GP,
321 :			dedicated = isDedicatedR,
322 :			spillProh = [],
323 :			memRegs = [],
324 :			mode = phases Int.phases
325 :			} : RA.raClient
326 :
327 :			fun getFregLoc (s, an, RA.FRAME loc) = Float.spillLoc (s, an, loc)
328 :			| getFregLoc (s, an, RA.MEM_REG r) = I.FDirect r
329 :
330 :			fun spillF s {annotations=an, kill, reg, spillLoc, instr} = let
331 :			(* preserve annotation on instruction *)
332 :			fun spill(instrAn, I.ANNOTATION{a, i}) = spill(a::instrAn, i)
333 :			| spill(instrAn, I.KILL{regs, spilled}) =
334 :			{code=[annotate (instrAn,
335 :			I.KILL {regs=C.rmvFreg(reg, regs),
336 :			spilled=C.addFreg(reg, spilled)})],
337 :			proh = [], newReg=NONE}
338 :			| spill(instrAn, I.LIVE _) = error "spillF: LIVE"
339 :			| spill(_, I.COPY _) = error "spillF: COPY"
340 :			| spill(instrAn, I.INSTR _) = (
341 :			inc floatSpillCnt;
342 :			spillFInstr (instr, reg, getFregLoc (s, an, spillLoc)))
343 :			in
344 :			spill([], instr)
345 :			end (* spillF *)
346 :
347 :			fun spillFreg s {src, reg, spillLoc, annotations=an} = (
348 :			inc floatSpillCnt;
349 :			let val dst = getFregLoc (s, an, spillLoc)
350 :			in
351 :			if Props.eqOpn (I.Direct (64, src), dst)
352 :			then []
353 :			else [I.fmove {fmvOp=I.MOVSD, src=I.FDirect src, dst=dst}]
354 :			end)
355 :
356 :			fun spillFcopyTmp s {copy=I.COPY{k=CB.FP, dst, src, ...}, spillLoc, reg,
357 :			annotations=an} = (
358 :			inc floatSpillCnt;
359 :			fcopy {dst=dst, src=src, tmp=SOME (getFregLoc (s, an, spillLoc))})
360 :			| spillFcopyTmp s {copy=I.ANNOTATION{i,a}, spillLoc, reg, annotations} =
361 :			let val i = spillFcopyTmp s {copy=i, spillLoc=spillLoc, reg=reg,
362 :			annotations=annotations}
363 :			in I.ANNOTATION{i=i, a=a} end
364 :			| spillFcopyTmp _ _ = error "spillFcopyTmp"
365 :
366 :			fun reloadF s {annotations=an,reg,spillLoc,instr} = let
367 :			fun reload (instrAn, I.ANNOTATION{a,i}) = reload(a::instrAn, i)
368 :			| reload(instrAn, I.LIVE{regs, spilled}) =
369 :			{code=[I.LIVE{regs=C.rmvFreg(reg, regs),
370 :			spilled=C.addFreg(reg, spilled)}],
371 :			proh=[], newReg=NONE}
372 :			| reload(_, I.KILL _) = error "reloadF: KILL"
373 :			| reload (_, I.COPY _) = error "reloadF: COPY"
374 :			| reload(instrAn, instr as I.INSTR _) = (
375 :			inc floatReloadCnt;
376 :			reloadFInstr (instr, reg, getFregLoc(s, an, spillLoc)))
377 :			in
378 :			reload([], instr)
379 :			end (* reloadF *)
380 :
381 :			fun reloadFreg s {dst, reg, spillLoc, annotations=an} =
382 :			(inc floatReloadCnt;
383 :			let val srcLoc = getFregLoc (s, an, spillLoc)
384 :			val dstLoc = I.FDirect dst
385 :			in
386 :			if Props.eqOpn (srcLoc, dstLoc)
387 :			then []
388 :			else [I.fmove {fmvOp=I.MOVSD, src=srcLoc, dst=dstLoc}]
389 :			end)
390 :
391 :			fun copyInstrF((rds as [_], rss as [_]), _) =
392 :			fcopy{dst=rds, src=rss, tmp=NONE}
393 :			| copyInstrF((rds, rss), I.COPY{k=CB.FP, tmp, ...}) =
394 :			fcopy{dst=rds, src=rss, tmp=tmp}
395 :			| copyInstrF(x, I.ANNOTATION{i,a}) =
396 :			I.ANNOTATION{i=copyInstrF (x, i), a=a}
397 :			| copyInstrF _ = error "copyInstrF"
398 :
399 :			val copyInstrF = fn x => [copyInstrF x]
400 :
401 :			fun renameF {instr, fromSrc, toSrc} = (
402 :			inc floatRenameCnt;
403 :			reloadFInstr (instr, fromSrc, I.FDirect toSrc))
404 :
405 :			fun raFloat s = {
406 :			spill = spillF s,
407 :			spillSrc = spillFreg s,
408 :			spillCopyTmp= spillFcopyTmp s,
409 :			reload = reloadF s,
410 :			reloadDst = reloadFreg s,
411 :			renameSrc = renameF,
412 :			copyInstr = copyInstrF,
413 :			K = length Float.avail,
414 :			getreg = FPR.getreg,
415 :			cellkind = CB.FP,
416 :			dedicated = isDedicatedF,
417 :			spillProh = [],
418 :			memRegs = [],
419 :			mode = phases Float.phases
420 :			} : RA.raClient
421 :
422 :			fun run cfg = let
423 :	mrainey	2793	val printCFG = if !amd64CfgDebugFlg
424 :	mrainey	2619	then PrintFlowgraph.printCFG (!MLRiscControl.debug_stream)
425 :			else fn msg => fn _ => ()
426 :	mrainey	2793	val _ = printCFG "\t---Before register allocation---\n" cfg;
427 :	mrainey	2619	val s = beforeRA cfg
428 :			val _ = resetRA ()
429 :			val cfg' = RA.ra [raInt s, raFloat s] cfg
430 :	mrainey	2793	in
431 :	mrainey	2619	removeDeadCode cfg';
432 :			printCFG "\t---After register allocation---\n" cfg';
433 :			cfg'
434 :			end (* run *)
435 :
436 :	mrainey	2793	end (* AMD64RegAlloc *)

---

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