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

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