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 /sml/trunk/src/MLRISC/x86/mltree/x86RA.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/x86/mltree/x86RA.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 744 - (view) (download)

1 : leunga 744 (*
2 :     * X86 specific register allocator.
3 :     * This module abstracts out all the nasty RA business on the x86.
4 :     * So you should only have to write the callbacks.
5 :     *)
6 :    
7 :     functor X86RA
8 :     ( structure I : X86INSTR
9 :     structure InsnProps : INSN_PROPERTIES where I = I
10 :     structure F : FLOWGRAPH where I = I
11 :     structure Asm : INSTRUCTION_EMITTER where I = I
12 :    
13 :     (* Spilling heuristics determines which node should be spilled.
14 :     * You can use Chaitin, ChowHenessey, or one of your own.
15 :     *)
16 :     structure SpillHeur : RA_SPILL_HEURISTICS
17 :    
18 :     (* The Spill module figures out the strategies for inserting
19 :     * spill code. You can use RASpill, or RASpillWithRenaming,
20 :     * or write your own if you are feeling adventurous.
21 :     *)
22 :     structure Spill : RA_SPILL where I = I
23 :    
24 :     sharing F.P = Asm.P
25 :    
26 :     (* Should we use allocate register on the floating point stack?
27 :     * Note that this flag must match the one passed to the code generator
28 :     * module.
29 :     *)
30 :     val fast_floating_point : bool ref
31 :    
32 :     datatype raPhase = SPILL_PROPAGATION
33 :     | SPILL_COLORING
34 :    
35 :     (* Called before register allocation; perform your initialization here. *)
36 :     val beforeRA : unit -> unit
37 :    
38 :     (* Integer register allocation parameters *)
39 :     structure Int :
40 :     sig
41 :     val avail : I.C.cell list
42 :     val dedicated : I.C.cell list
43 :     val memRegs : I.C.cell list
44 :     val phases : raPhase list
45 :    
46 :     val spillLoc : Annotations.annotations ref *
47 :     RAGraph.logical_spill_id -> I.operand
48 :    
49 :     (* This function is called once before spilling begins *)
50 :     val spillInit : RAGraph.interferenceGraph -> unit
51 :    
52 :     end
53 :    
54 :     (* Floating point register allocation parameters *)
55 :     structure Float :
56 :     sig
57 :     (* Sethi-Ullman mode *)
58 :     val avail : I.C.cell list
59 :     val dedicated : I.C.cell list
60 :     val memRegs : I.C.cell list
61 :     val phases : raPhase list
62 :    
63 :     val spillLoc : Annotations.annotations ref *
64 :     RAGraph.logical_spill_id -> I.operand
65 :    
66 :     (* This function is called once before spilling begins *)
67 :     val spillInit : RAGraph.interferenceGraph -> unit
68 :    
69 :     (* When fast_floating_point is on, use these instead: *)
70 :     val fastMemRegs : I.C.cell list
71 :     val fastPhases : raPhase list
72 :     end
73 :    
74 :     ) : CLUSTER_OPTIMIZATION =
75 :     struct
76 :    
77 :     structure F = F
78 :     structure I = I
79 :     structure C = I.C
80 :    
81 :     val name = "X86RA"
82 :    
83 :     type flowgraph = F.cluster
84 :    
85 :     val intSpillCnt = MLRiscControl.getCounter "ra-int-spills"
86 :     val floatSpillCnt = MLRiscControl.getCounter "ra-float-spills"
87 :     val intReloadCnt = MLRiscControl.getCounter "ra-int-reloads"
88 :     val floatReloadCnt = MLRiscControl.getCounter "ra-float-reloads"
89 :     val intRenameCnt = MLRiscControl.getCounter "ra-int-renames"
90 :     val floatRenameCnt = MLRiscControl.getCounter "ra-float-renames"
91 :     val x86CfgDebugFlg = MLRiscControl.getFlag "x86-cfg-debug"
92 :    
93 :     (*
94 :     val deadcode = MLRiscControl.getCounter "x86-dead-code"
95 :     val deadblocks = MLRiscControl.getCounter "x86-dead-blocks"
96 :     *)
97 :    
98 :     structure PrintFlowGraph=
99 :     PrintCluster(structure Flowgraph=F
100 :     structure Asm = Asm)
101 :    
102 :     structure X86FP =
103 :     X86FP(structure X86Instr = I
104 :     structure X86Props = InsnProps
105 :     structure Flowgraph = F
106 :     structure Liveness = Liveness(F)
107 :     structure Asm = Asm
108 :     )
109 :    
110 :     structure X86Spill = X86Spill(structure Instr=I structure Props=InsnProps)
111 :    
112 :     (*
113 :     * Dead code elimination
114 :     *)
115 :     exception X86DeadCode
116 :     val affectedBlocks =
117 :     IntHashTable.mkTable(32,X86DeadCode) : bool IntHashTable.hash_table
118 :     val deadRegs =
119 :     IntHashTable.mkTable(32,X86DeadCode) : bool IntHashTable.hash_table
120 :     fun removeDeadCode(F.CLUSTER{blocks, ...}) =
121 :     let val find = IntHashTable.find deadRegs
122 :     fun isDead r =
123 :     case find (C.registerId r) of
124 :     SOME _ => true
125 :     | NONE => false
126 :     fun isAffected i = getOpt (IntHashTable.find affectedBlocks i, false)
127 :     fun isDeadInstr(I.ANNOTATION{i, ...}) = isDeadInstr i
128 :     | isDeadInstr(I.MOVE{dst=I.Direct rd, ...}) = isDead rd
129 :     | isDeadInstr(I.MOVE{dst=I.MemReg rd, ...}) = isDead rd
130 :     | isDeadInstr(I.COPY{dst=[rd], ...}) = isDead rd
131 :     | isDeadInstr _ = false
132 :     fun scan [] = ()
133 :     | scan(F.BBLOCK{blknum, insns, ...}::rest) =
134 :     (if isAffected blknum then
135 :     ((* deadblocks := !deadblocks + 1; *)
136 :     insns := elim(!insns, [])
137 :     ) else ();
138 :     scan rest)
139 :     | scan(_::rest) = scan rest
140 :     and elim([], code) = rev code
141 :     | elim(i::instrs, code) =
142 :     if isDeadInstr i then
143 :     ((* deadcode := !deadcode + 1; *) elim(instrs, code))
144 :     else elim(instrs, i::code)
145 :     in if IntHashTable.numItems affectedBlocks > 0 then
146 :     (scan blocks;
147 :     IntHashTable.clear deadRegs;
148 :     IntHashTable.clear affectedBlocks)
149 :     else ()
150 :     end
151 :    
152 :     (* This function finds out which pseudo memory registers are unused.
153 :     * Those that are unused are made available for spilling.
154 :     * The register allocator calls this function right before spilling
155 :     * a set of nodes.
156 :     *)
157 :     val firstSpill = ref true
158 :     val firstFPSpill = ref true
159 :    
160 :     fun spillInit(graph, I.C.GP) =
161 :     if !firstSpill then (* only do this once! *)
162 :     (Int.spillInit graph;
163 :     firstSpill := false
164 :     )
165 :     else ()
166 :     | spillInit(graph, I.C.FP) =
167 :     if !firstFPSpill then
168 :     (Float.spillInit graph;
169 :     firstFPSpill := false
170 :     )
171 :     else ()
172 :    
173 :     (* This is the generic register allocator *)
174 :     structure Ra =
175 :     RegisterAllocator
176 :     (SpillHeur)
177 :     (MemoryRA (* for memory coalescing *)
178 :     (RADeadCodeElim (* do the funky dead code elimination stuff *)
179 :     (ClusterRA
180 :     (structure Flowgraph = F
181 :     structure Asm = Asm
182 :     structure InsnProps = InsnProps
183 :     structure Spill = Spill
184 :     )
185 :     )
186 :     (fun cellkind I.C.GP = true | cellkind _ = false
187 :     val deadRegs = deadRegs
188 :     val affectedBlocks = affectedBlocks
189 :     val spillInit = spillInit
190 :     )
191 :     )
192 :     )
193 :    
194 :    
195 :     (* -------------------------------------------------------------------
196 :     * Floating point stuff
197 :     * -------------------------------------------------------------------*)
198 :     val KF32 = length Float.avail
199 :     structure FR32 = GetReg(val nRegs=KF32
200 :     val available=map C.registerId Float.avail
201 :     val first=C.registerId(I.C.ST 8))
202 :    
203 :     val availF8 = C.Regs C.FP {from=0, to=6, step=1}
204 :     val KF8 = length availF8
205 :     structure FR8 = GetReg(val nRegs=KF8
206 :     val available=map C.registerId availF8
207 :     val first=C.registerId(I.C.ST 0))
208 :    
209 :     (* -------------------------------------------------------------------
210 :     * Callbacks for floating point K=32
211 :     * -------------------------------------------------------------------*)
212 :     fun copyInstrF((rds as [_], rss as [_]), _) =
213 :     I.FCOPY{dst=rds, src=rss, tmp=NONE}
214 :     | copyInstrF((rds, rss), I.FCOPY{tmp, ...}) =
215 :     I.FCOPY{dst=rds, src=rss, tmp=tmp}
216 :     | copyInstrF(x, I.ANNOTATION{i,a}) =
217 :     I.ANNOTATION{i=copyInstrF(x, i), a=a}
218 :    
219 :     val copyInstrF = fn x => [copyInstrF x]
220 :    
221 :     fun getFregLoc(an, Ra.FRAME loc) = Float.spillLoc(an, loc)
222 :     | getFregLoc(an, Ra.MEM_REG r) = I.FDirect r
223 :    
224 :     (* spill floating point *)
225 :     fun spillF{instr, reg, spillLoc, kill, annotations=an} =
226 :     (floatSpillCnt := !floatSpillCnt + 1;
227 :     X86Spill.fspill(instr, reg, getFregLoc(an, spillLoc))
228 :     )
229 :    
230 :     fun spillFreg{src, reg, spillLoc, annotations=an} =
231 :     (floatSpillCnt := !floatSpillCnt + 1;
232 :     [I.FLDL(I.FDirect(src)), I.FSTPL(getFregLoc(an, spillLoc))]
233 :     )
234 :    
235 :     fun spillFcopyTmp{copy=I.FCOPY{dst, src, ...}, spillLoc,
236 :     annotations=an} =
237 :     (floatSpillCnt := !floatSpillCnt + 1;
238 :     I.FCOPY{dst=dst, src=src, tmp=SOME(getFregLoc(an, spillLoc))}
239 :     )
240 :     | spillFcopyTmp{copy=I.ANNOTATION{i,a}, spillLoc, annotations} =
241 :     let val i = spillFcopyTmp{copy=i, spillLoc=spillLoc,
242 :     annotations=annotations}
243 :     in I.ANNOTATION{i=i, a=a} end
244 :    
245 :     (* rename floating point *)
246 :     fun renameF{instr, fromSrc, toSrc} =
247 :     (floatRenameCnt := !floatRenameCnt + 1;
248 :     X86Spill.freload(instr, fromSrc, I.FDirect toSrc)
249 :     )
250 :    
251 :     (* reload floating point *)
252 :     fun reloadF{instr, reg, spillLoc, annotations=an} =
253 :     (floatReloadCnt := !floatReloadCnt + 1;
254 :     X86Spill.freload(instr, reg, getFregLoc(an, spillLoc))
255 :     )
256 :    
257 :     fun reloadFreg{dst, reg, spillLoc, annotations=an} =
258 :     (floatReloadCnt := !floatReloadCnt + 1;
259 :     [I.FLDL(getFregLoc(an, spillLoc)), I.FSTPL(I.FDirect dst)]
260 :     )
261 :    
262 :     (* -------------------------------------------------------------------
263 :     * Callbacks for floating point K=7
264 :     * -------------------------------------------------------------------*)
265 :     fun FMemReg f = let val fx = C.registerNum f
266 :     in if fx >= 8 andalso fx < 32
267 :     then I.FDirect f else I.FPR f
268 :     end
269 :    
270 :     fun copyInstrF'((rds as [d], rss as [s]), _) =
271 :     I.FMOVE{fsize=I.FP64,src=FMemReg s,dst=FMemReg d}
272 :     | copyInstrF'((rds, rss), I.FCOPY{tmp, ...}) =
273 :     I.FCOPY{dst=rds, src=rss, tmp=tmp}
274 :     | copyInstrF'(x, I.ANNOTATION{i, a}) =
275 :     I.ANNOTATION{i=copyInstrF'(x,i), a=a}
276 :    
277 :     val copyInstrF' = fn x => [copyInstrF' x]
278 :    
279 :     fun spillFreg'{src, reg, spillLoc, annotations=an} =
280 :     (floatSpillCnt := !floatSpillCnt + 1;
281 :     [I.FMOVE{fsize=I.FP64, src=FMemReg src, dst=getFregLoc(an,spillLoc)}]
282 :     )
283 :    
284 :     fun renameF'{instr, fromSrc, toSrc} =
285 :     (floatRenameCnt := !floatRenameCnt + 1;
286 :     X86Spill.freload(instr, fromSrc, I.FPR toSrc)
287 :     )
288 :    
289 :     fun reloadFreg'{dst, reg, spillLoc, annotations=an} =
290 :     (floatReloadCnt := !floatReloadCnt + 1;
291 :     [I.FMOVE{fsize=I.FP64, dst=FMemReg dst, src=getFregLoc(an,spillLoc)}]
292 :     )
293 :    
294 :     (* -------------------------------------------------------------------
295 :     * Integer 8 stuff
296 :     * -------------------------------------------------------------------*)
297 :     fun memToMemMove{dst, src} =
298 :     let val tmp = I.C.newReg()
299 :     in [I.MOVE{mvOp=I.MOVL,src=src,dst=I.Direct tmp},
300 :     I.MOVE{mvOp=I.MOVL,src=I.Direct tmp,dst=dst}
301 :     ]
302 :     end
303 :    
304 :     fun copyInstrR((rds as [d], rss as [s]), _) =
305 :     if C.sameColor(d,s) then [] else
306 :     let val dx = C.registerNum d and sx = C.registerNum s
307 :     in case (dx >= 8 andalso dx < 32, sx >= 8 andalso sx < 32) of
308 :     (false, false) => [I.COPY{dst=rds, src=rss, tmp=NONE}]
309 :     | (true, false) => [I.MOVE{mvOp=I.MOVL,src=I.Direct s,
310 :     dst=I.MemReg d}]
311 :     | (false, true) => [I.MOVE{mvOp=I.MOVL,src=I.MemReg s,
312 :     dst=I.Direct d}]
313 :     | (true, true) => memToMemMove{src=I.MemReg s, dst=I.MemReg d}
314 :     end
315 :     | copyInstrR((rds, rss), I.COPY{tmp, ...}) =
316 :     [I.COPY{dst=rds, src=rss, tmp=tmp}]
317 :     | copyInstrR(x, I.ANNOTATION{i, a}) =
318 :     copyInstrR(x, i) (* XXX *)
319 :    
320 :    
321 :     fun getRegLoc(an, Ra.FRAME loc) = Int.spillLoc(an, loc)
322 :     | getRegLoc(an, Ra.MEM_REG r) = I.MemReg r
323 :    
324 :     (* No, logical spill locations... *)
325 :    
326 :     structure GR8 = GetReg(val nRegs=8
327 :     val available=map C.registerId Int.avail
328 :     val first=0)
329 :    
330 :     val K8 = length Int.avail
331 :    
332 :     (* register allocation for general purpose registers *)
333 :     fun spillR8{instr, reg, spillLoc, kill, annotations=an} =
334 :     (intSpillCnt := !intSpillCnt + 1;
335 :     X86Spill.spill(instr, reg, getRegLoc(an, spillLoc))
336 :     )
337 :    
338 :     fun isMemReg r = let val x = C.registerNum r
339 :     in x >= 8 andalso x < 32 end
340 :    
341 :     fun spillReg{src, reg, spillLoc, annotations=an} =
342 :     let val _ = intSpillCnt := !intSpillCnt + 1;
343 :     val dstLoc = getRegLoc(an,spillLoc)
344 :     val isMemReg = isMemReg src
345 :     val srcLoc = if isMemReg then I.MemReg src else I.Direct src
346 :     in if InsnProps.eqOpn(srcLoc, dstLoc) then []
347 :     else if isMemReg then memToMemMove{dst=dstLoc, src=srcLoc}
348 :     else [I.MOVE{mvOp=I.MOVL, src=srcLoc, dst=dstLoc}]
349 :     end
350 :    
351 :     fun spillCopyTmp{copy=I.COPY{src, dst,...}, spillLoc, annotations=an} =
352 :     (intSpillCnt := !intSpillCnt + 1;
353 :     I.COPY{dst=dst, src=src, tmp=SOME(getRegLoc(an, spillLoc))}
354 :     )
355 :    
356 :     fun renameR8{instr, fromSrc, toSrc} =
357 :     (intRenameCnt := !intRenameCnt + 1;
358 :     X86Spill.reload(instr, fromSrc, I.Direct toSrc)
359 :     )
360 :    
361 :     fun reloadR8{instr, reg, spillLoc, annotations=an} =
362 :     (intReloadCnt := !intReloadCnt + 1;
363 :     X86Spill.reload(instr, reg, getRegLoc(an,spillLoc))
364 :     )
365 :    
366 :     fun reloadReg{dst, reg, spillLoc, annotations=an} =
367 :     let val _ = intReloadCnt := !intReloadCnt + 1
368 :     val srcLoc = getRegLoc(an, spillLoc)
369 :     val isMemReg = isMemReg dst
370 :     val dstLoc = if isMemReg then I.MemReg dst else I.Direct dst
371 :     in if InsnProps.eqOpn(srcLoc,dstLoc) then []
372 :     else if isMemReg then memToMemMove{dst=dstLoc, src=srcLoc}
373 :     else [I.MOVE{mvOp=I.MOVL, src=srcLoc, dst=dstLoc}]
374 :     end
375 :    
376 :     fun resetRA() =
377 :     (firstSpill := true;
378 :     firstFPSpill := true;
379 :     IntHashTable.clear affectedBlocks;
380 :     IntHashTable.clear deadRegs;
381 :     if !fast_floating_point then FR8.reset() else FR32.reset();
382 :     GR8.reset()
383 :     )
384 :    
385 :     (* Dedicated + available registers *)
386 :     fun mark(a, l) = app (fn r => Array.update(a, C.registerId r, true)) l
387 :    
388 :     val dedicatedR = Array.array(32,false)
389 :     val dedicatedF32 = Array.array(64,false)
390 :     val dedicatedF8 = Array.array(64,false)
391 :     val _ = mark(dedicatedR, Int.dedicated)
392 :     val _ = mark(dedicatedF32, Float.dedicated)
393 :    
394 :    
395 :     fun phases ps =
396 :     let fun f([], m) = m
397 :     | f(SPILL_PROPAGATION::ps, m) = f(ps, Ra.SPILL_PROPAGATION+m)
398 :     | f(SPILL_COLORING::ps, m) = f(ps, Ra.SPILL_COLORING+m)
399 :     in f(ps, Ra.NO_OPTIMIZATION)
400 :     end
401 :    
402 :     (* RA parameters *)
403 :    
404 :     (* How to allocate integer registers:
405 :     * Perform register alocation + memory allocation
406 :     *)
407 :     val RAInt = {spill = spillR8,
408 :     spillSrc = spillReg,
409 :     spillCopyTmp= spillCopyTmp,
410 :     reload = reloadR8,
411 :     reloadDst = reloadReg,
412 :     renameSrc = renameR8,
413 :     copyInstr = copyInstrR,
414 :     K = K8,
415 :     getreg = GR8.getreg,
416 :     cellkind = I.C.GP,
417 :     dedicated = dedicatedR,
418 :     spillProh = [],
419 :     memRegs = Int.memRegs,
420 :     mode = phases(Int.phases)
421 :     } : Ra.raClient
422 :    
423 :     (* How to allocate floating point registers:
424 :     * Allocate all fp registers on the stack. This is the easy way.
425 :     *)
426 :     val RAFP32 ={spill = spillF,
427 :     spillSrc = spillFreg,
428 :     spillCopyTmp= spillFcopyTmp,
429 :     reload = reloadF,
430 :     reloadDst = reloadFreg,
431 :     renameSrc = renameF,
432 :     copyInstr = copyInstrF,
433 :     K = KF32,
434 :     getreg = FR32.getreg,
435 :     cellkind = I.C.FP,
436 :     dedicated = dedicatedF32,
437 :     spillProh = [],
438 :     memRegs = Float.memRegs,
439 :     mode = phases(Float.phases)
440 :     } : Ra.raClient
441 :    
442 :     (* How to allocate floating point registers:
443 :     * Allocate fp registers on the %st stack. Also perform
444 :     * memory allcoation.
445 :     *)
446 :     val RAFP8 ={spill = spillF,
447 :     spillSrc = spillFreg',
448 :     spillCopyTmp= spillFcopyTmp,
449 :     reload = reloadF,
450 :     reloadDst = reloadFreg',
451 :     renameSrc = renameF',
452 :     copyInstr = copyInstrF',
453 :     K = KF8,
454 :     getreg = FR8.getreg,
455 :     cellkind = I.C.FP,
456 :     dedicated = dedicatedF8,
457 :     spillProh = [],
458 :     memRegs = Float.fastMemRegs,
459 :     mode = phases(Float.fastPhases)
460 :     } : Ra.raClient
461 :    
462 :     (* Two RA modes, fast and normal *)
463 :     val fast_fp = [RAInt, RAFP8]
464 :     val normal_fp = [RAInt, RAFP32]
465 :    
466 :     (* The main ra routine *)
467 :     fun run cluster =
468 :     let val printGraph =
469 :     if !x86CfgDebugFlg then
470 :     PrintFlowGraph.printCluster(!MLRiscControl.debug_stream)
471 :     else fn msg => fn _ => ()
472 :    
473 :     val _ = beforeRA()
474 :     val _ = resetRA()
475 :    
476 :     (* generic register allocator *)
477 :    
478 :     val cluster = Ra.ra
479 :     (if !fast_floating_point then fast_fp else normal_fp)
480 :     cluster
481 :    
482 :     val _ = removeDeadCode cluster
483 :    
484 :     val _ = printGraph "\t---After register allocation K=8---\n" cluster
485 :    
486 :     (* Run the FP translation phase when fast floating point has
487 :     * been enabled
488 :     *)
489 :     val cluster =
490 :     if !fast_floating_point andalso I.C.numCell I.C.FP () > 0 then
491 :     let val cluster = X86FP.run cluster
492 :     in printGraph "\t---After X86 FP translation ---\n" cluster;
493 :     cluster
494 :     end
495 :     else cluster
496 :     in cluster
497 :     end
498 :    
499 :     end

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