Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /MLRISC/trunk/amd64/ra/amd64RegAlloc.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


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

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