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 2805 - (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 2805 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