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 4862 - (view) (download)

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

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