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/compiler/CodeGen/x86/x86CG.sml
ViewVC logotype

Annotation of /sml/trunk/src/compiler/CodeGen/x86/x86CG.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 576 - (view) (download)

1 : monnier 429 (*
2 : monnier 498 * X86 specific backend. This one uses the new RA8 scheme.
3 : monnier 429 *)
4 :     structure X86CG =
5 :     MachineGen
6 :     ( structure I = X86Instr
7 :     structure F = X86FlowGraph
8 :     structure R = X86CpsRegs
9 :     structure CG = Control.CG
10 : monnier 247
11 : monnier 429 structure MachSpec = X86Spec
12 :     structure PseudoOps = X86PseudoOps
13 :     structure CpsRegs = X86CpsRegs
14 : george 555 structure InsnProps = X86Props
15 : monnier 429 structure Asm = X86AsmEmitter
16 : george 555 structure Shuffle = X86Shuffle
17 : monnier 247
18 : monnier 498 val spill = CPSRegions.spill
19 :     val stack = CPSRegions.stack
20 : monnier 429 val esp = I.C.esp
21 : monnier 247
22 : monnier 429 fun error msg = MLRiscErrorMsg.error("X86CG",msg)
23 : monnier 247
24 : monnier 429 structure MLTreeComp=
25 :     X86(structure X86Instr=X86Instr
26 :     structure X86MLTree=X86MLTree
27 : george 555 structure ExtensionComp = SMLNJMLTreeExtComp
28 :     (structure I = X86Instr
29 :     structure T = X86MLTree
30 :     )
31 : monnier 429 val tempMem=I.Displace{base=esp, disp=I.Immed 304, mem=stack}
32 : george 546 datatype arch = Pentium | PentiumPro | PentiumII | PentiumIII
33 :     val arch = ref Pentium (* Lowest common denominator *)
34 : monnier 429 )
35 : monnier 247
36 : monnier 429 structure X86Jumps =
37 :     X86Jumps(structure Instr=X86Instr
38 :     structure AsmEmitter=X86AsmEmitter
39 :     structure Shuffle=X86Shuffle
40 :     structure MCEmitter=X86MCEmitter)
41 :    
42 :     structure BackPatch =
43 :     BackPatch(structure Jumps=X86Jumps
44 :     structure Emitter=X86MCEmitter
45 :     structure Props=InsnProps
46 :     structure Flowgraph=X86FlowGraph
47 :     structure Asm=X86AsmEmitter
48 :     structure CodeString=CodeString)
49 : monnier 247
50 : monnier 429 structure PrintFlowGraph=
51 : george 546 PrintCluster(structure Flowgraph=X86FlowGraph
52 :     structure Asm = X86AsmEmitter)
53 : monnier 247
54 : monnier 498 structure X86Spill = X86Spill(structure Instr=I structure Props=InsnProps)
55 : monnier 247
56 : monnier 429 val toInt32 = Int32.fromInt
57 : monnier 469 fun cacheOffset r = I.Immed(toInt32(X86Runtime.vregStart +
58 :     Word.toIntX(Word.<<(Word.fromInt(r-8),0w2))))
59 : monnier 247
60 : monnier 429 val intSpillCnt = MLRiscControl.getCounter "ra-int-spills"
61 :     val floatSpillCnt = MLRiscControl.getCounter "ra-float-spills"
62 :     val intReloadCnt = MLRiscControl.getCounter "ra-int-reloads"
63 :     val floatReloadCnt = MLRiscControl.getCounter "ra-float-reloads"
64 : monnier 498 val intRenameCnt = MLRiscControl.getCounter "ra-int-renames"
65 :     val floatRenameCnt = MLRiscControl.getCounter "ra-float-renames"
66 : monnier 429 val x86CfgDebugFlg = MLRiscControl.getFlag "x86-cfg-debug"
67 : monnier 498 (*
68 :     val deadcode = MLRiscControl.getCounter "x86-dead-code"
69 :     val deadblocks = MLRiscControl.getCounter "x86-dead-blocks"
70 :     *)
71 : monnier 469
72 : monnier 429 structure RA =
73 :     struct
74 :     structure F = F
75 : monnier 469
76 : monnier 498 (* For dead code elimination *)
77 :     exception X86DeadCode
78 :     val affectedBlocks = Intmap.new(32,X86DeadCode) : bool Intmap.intmap
79 :     val deadRegs = Intmap.new(32,X86DeadCode) : bool Intmap.intmap
80 :     fun removeDeadCode(F.CLUSTER{blocks, ...}) =
81 :     let val isDead = Intmap.mapWithDefault(deadRegs, false)
82 :     val isAffected = Intmap.mapWithDefault(affectedBlocks, false)
83 :     fun isDeadInstr(I.ANNOTATION{i, ...}) = isDeadInstr i
84 :     | isDeadInstr(I.MOVE{dst=I.Direct rd, ...}) = isDead rd
85 : george 546 | isDeadInstr(I.MOVE{dst=I.MemReg rd, ...}) = isDead rd
86 : monnier 498 | isDeadInstr(I.COPY{dst=[rd], ...}) = isDead rd
87 :     | isDeadInstr _ = false
88 :     fun scan [] = ()
89 :     | scan(F.BBLOCK{blknum, insns, ...}::rest) =
90 :     (if isAffected blknum then
91 :     ((* deadblocks := !deadblocks + 1; *)
92 :     insns := elim(!insns, [])
93 :     ) else ();
94 :     scan rest)
95 :     | scan(_::rest) = scan rest
96 :     and elim([], code) = rev code
97 :     | elim(i::instrs, code) =
98 :     if isDeadInstr i then
99 :     ((* deadcode := !deadcode + 1; *) elim(instrs, code))
100 :     else elim(instrs, i::code)
101 :     in if Intmap.elems affectedBlocks > 0 then scan blocks else ()
102 :     end
103 : george 546
104 :     (* This function finds out which pseudo memory registers are unused.
105 :     * Those that are unused are made available for spilling.
106 :     * The register allocator calls this function right before spilling
107 :     * a set of nodes.
108 :     *)
109 :     local
110 :     open RAGraph
111 :     in
112 :     val firstSpill = ref true
113 :     fun spillInit(GRAPH{nodes, ...}, I.C.GP) =
114 :     if !firstSpill then (* only do this once! *)
115 :     let val lookup = Intmap.map nodes
116 :     fun find(r, free) =
117 :     if r >= 10 then (* note, %8 and %9 are reserved! *)
118 :     let val free =
119 :     case lookup r of
120 :     NODE{uses=ref [], defs=ref [], ...} =>
121 :     cacheOffset r::free
122 :     | _ => free
123 :     in find(r-1, free) end
124 :     else
125 :     free
126 :     val free = find(31 (* X86Runtime.numVregs+8-1 *), [])
127 :     in firstSpill := false;
128 :     X86StackSpills.setAvailableOffsets free
129 :     end
130 :     else ()
131 :     | spillInit(GRAPH{nodes, ...}, _) = ()
132 :     end
133 :    
134 : monnier 469 (* This is the generic register allocator *)
135 :     structure Ra =
136 :     RegisterAllocator
137 : monnier 498 (ChowHennessySpillHeur)
138 : george 546 (MemoryRA (* for memory coalescing *)
139 :     (RADeadCodeElim (* do the funky dead code elimination stuff *)
140 :     (ClusterRA
141 :     (structure Flowgraph = F
142 :     structure Asm = X86AsmEmitter
143 :     structure InsnProps = InsnProps
144 :     )
145 :     )
146 :     (fun cellkind I.C.GP = true | cellkind _ = false
147 :     val deadRegs = deadRegs
148 :     val affectedBlocks = affectedBlocks
149 :     val spillInit = spillInit
150 :     )
151 :     )
152 :     )
153 : monnier 469
154 :    
155 :     (* -------------------------------------------------------------------
156 :     * Floating point stuff
157 :     * -------------------------------------------------------------------*)
158 : monnier 429 structure FR = GetReg(val nRegs=32
159 :     val available=R.availF
160 :     val first=32)
161 : monnier 469
162 :     val KF = length R.availF
163 : monnier 429
164 : monnier 469 fun copyInstrF((rds as [_], rss as [_]), _) =
165 : monnier 498 [I.FCOPY{dst=rds, src=rss, tmp=NONE}]
166 : monnier 469 | copyInstrF((rds, rss), I.FCOPY{tmp, ...}) =
167 : monnier 498 [I.FCOPY{dst=rds, src=rss, tmp=tmp}]
168 : monnier 429
169 : monnier 498 fun getFregLoc loc =
170 :     I.Displace{base=esp, disp=X86StackSpills.getFregLoc loc, mem=spill}
171 : monnier 429
172 : monnier 469 (* spill floating point *)
173 : monnier 498 fun spillF{instr, reg, spillLoc, kill, regmap, annotations} =
174 :     (floatSpillCnt := !floatSpillCnt + 1;
175 :     X86Spill.fspill(instr, regmap, reg, getFregLoc spillLoc)
176 :     )
177 : monnier 429
178 : monnier 498 fun spillFreg{src, reg, spillLoc, annotations} =
179 :     (floatSpillCnt := !floatSpillCnt + 1;
180 : george 546 [I.FLDL(I.FDirect(src)), I.FSTPL(getFregLoc spillLoc)]
181 : monnier 498 )
182 :    
183 :     fun spillFcopyTmp{copy=I.FCOPY{dst, src, ...}, spillLoc, annotations} =
184 :     (floatSpillCnt := !floatSpillCnt + 1;
185 :     I.FCOPY{dst=dst, src=src, tmp=SOME(getFregLoc spillLoc)}
186 :     )
187 :    
188 :     (* rename floating point *)
189 :     fun renameF{instr, fromSrc, toSrc, regmap} =
190 :     (floatRenameCnt := !floatRenameCnt + 1;
191 :     X86Spill.freload(instr, regmap, fromSrc, I.FDirect toSrc)
192 :     )
193 :    
194 : monnier 469 (* reload floating point *)
195 : monnier 498 fun reloadF{instr, reg, spillLoc, regmap, annotations} =
196 :     (floatReloadCnt := !floatReloadCnt + 1;
197 :     X86Spill.freload(instr, regmap, reg, getFregLoc spillLoc)
198 :     )
199 : monnier 469
200 : monnier 498 fun reloadFreg{dst, reg, spillLoc, annotations} =
201 :     (floatReloadCnt := !floatReloadCnt + 1;
202 : george 546 [I.FLDL(getFregLoc spillLoc), I.FSTPL(I.FDirect dst)]
203 : monnier 498 )
204 :    
205 : monnier 469 (* -------------------------------------------------------------------
206 : monnier 498 * Integer 8 stuff
207 : monnier 469 * -------------------------------------------------------------------*)
208 : monnier 498 fun memToMemMove{dst, src} =
209 :     let val tmp = I.C.newReg()
210 :     in [I.MOVE{mvOp=I.MOVL,src=src,dst=I.Direct tmp},
211 :     I.MOVE{mvOp=I.MOVL,src=I.Direct tmp,dst=dst}
212 :     ]
213 :     end
214 : monnier 469
215 : monnier 498 fun copyInstrR((rds as [d], rss as [s]), _) =
216 :     if d = s then [] else
217 :     (case (d >= 8 andalso d < 32, s >= 8 andalso s < 32) of
218 :     (false, false) => [I.COPY{dst=rds, src=rss, tmp=NONE}]
219 :     | (true, false) => [I.MOVE{mvOp=I.MOVL,src=I.Direct s,dst=I.MemReg d}]
220 :     | (false, true) => [I.MOVE{mvOp=I.MOVL,src=I.MemReg s,dst=I.Direct d}]
221 :     | (true, true) => memToMemMove{src=I.MemReg s, dst=I.MemReg d}
222 :     )
223 : monnier 469 | copyInstrR((rds, rss), I.COPY{tmp, ...}) =
224 : monnier 498 [I.COPY{dst=rds, src=rss, tmp=tmp}]
225 : monnier 429
226 : monnier 498 val getRegLoc' = X86StackSpills.getRegLoc
227 : monnier 469
228 : monnier 498 fun getRegLoc(spillLoc) =
229 : george 546 (* Is it a memory register? *)
230 :     if spillLoc >= 0 then I.MemReg spillLoc
231 :     (* No, logical spill locations... *)
232 :     else I.Displace{base=esp, disp=getRegLoc' spillLoc, mem=spill}
233 :    
234 : monnier 429
235 :     structure GR8 = GetReg(val nRegs=8 val available=X86CpsRegs.availR
236 :     val first=0)
237 :    
238 : monnier 469 val K8 = length X86CpsRegs.availR
239 : monnier 429
240 :     (* register allocation for general purpose registers *)
241 : monnier 498 fun spillR8{instr, reg, spillLoc, kill, regmap, annotations} =
242 :     (intSpillCnt := !intSpillCnt + 1;
243 :     X86Spill.spill(instr, regmap, reg, getRegLoc spillLoc)
244 :     )
245 : monnier 469
246 : monnier 498 fun spillReg{src, reg, spillLoc, annotations} =
247 :     let val _ = intSpillCnt := !intSpillCnt + 1;
248 :     val dstLoc = getRegLoc spillLoc
249 :     val isMemReg = src >= 8 andalso src < 32
250 :     val srcLoc = if isMemReg then I.MemReg src else I.Direct src
251 :     in if InsnProps.eqOpn(srcLoc, dstLoc) then []
252 :     else if isMemReg then memToMemMove{dst=dstLoc, src=srcLoc}
253 :     else [I.MOVE{mvOp=I.MOVL, src=srcLoc, dst=dstLoc}]
254 :     end
255 :    
256 :     fun spillCopyTmp{copy=I.COPY{src, dst,...}, spillLoc, annotations} =
257 :     (intSpillCnt := !intSpillCnt + 1;
258 :     I.COPY{dst=dst, src=src, tmp=SOME(getRegLoc spillLoc)}
259 :     )
260 :    
261 :     fun renameR8{instr, fromSrc, toSrc, regmap} =
262 :     (intRenameCnt := !intRenameCnt + 1;
263 :     X86Spill.reload(instr, regmap, fromSrc, I.Direct toSrc)
264 :     )
265 :    
266 :     fun reloadR8{instr, reg, spillLoc, regmap, annotations} =
267 :     (intReloadCnt := !intReloadCnt + 1;
268 :     X86Spill.reload(instr, regmap, reg, getRegLoc spillLoc)
269 :     )
270 :    
271 :     fun reloadReg{dst, reg, spillLoc, annotations} =
272 :     let val _ = intReloadCnt := !intReloadCnt + 1
273 :     val srcLoc = getRegLoc spillLoc
274 :     val isMemReg = dst >= 8 andalso dst < 32
275 :     val dstLoc = if isMemReg then I.MemReg dst else I.Direct dst
276 :     in if InsnProps.eqOpn(srcLoc,dstLoc) then []
277 :     else if isMemReg then memToMemMove{dst=dstLoc, src=srcLoc}
278 :     else [I.MOVE{mvOp=I.MOVL, src=srcLoc, dst=dstLoc}]
279 :     end
280 :    
281 : monnier 429 fun spillInit () =
282 : monnier 498 (firstSpill := true;
283 :     Intmap.clear affectedBlocks;
284 :     Intmap.clear deadRegs;
285 :     X86StackSpills.init(); FR.reset(); GR8.reset())
286 : monnier 469
287 :     (* Dedicated + available registers *)
288 :     fun mark(a, l) = app (fn r => Array.update(a, r, true)) l
289 :    
290 :     val dedicatedR = Array.array(32,false)
291 :     val dedicatedF = Array.array(64,false)
292 :     val _ = mark(dedicatedR, R.dedicatedR)
293 :     val _ = mark(dedicatedF, R.dedicatedF)
294 :    
295 :     fun ra(cluster as F.CLUSTER{regmap, ...}) =
296 : monnier 498 let val printGraph =
297 : monnier 469 if !x86CfgDebugFlg then
298 :     PrintFlowGraph.printCluster(!CG.printFlowgraphStream)
299 :     else fn msg => fn _ => ()
300 : monnier 429
301 : monnier 469 val _ = spillInit()
302 : monnier 429
303 : monnier 469 (* generic register allocator *)
304 : monnier 498
305 :     val cluster = Ra.ra
306 : monnier 469 [ {spill = spillR8,
307 : monnier 498 spillSrc = spillReg,
308 :     spillCopyTmp= spillCopyTmp,
309 : monnier 469 reload = reloadR8,
310 : monnier 498 reloadDst = reloadReg,
311 :     renameSrc = renameR8,
312 : monnier 469 copyInstr = copyInstrR,
313 :     K = K8,
314 :     getreg = GR8.getreg,
315 :     cellkind = I.C.GP,
316 :     dedicated = dedicatedR,
317 : george 546 spillProh = [],
318 : leunga 576 memRegs = [(8,31)],
319 : monnier 498 mode = Ra.SPILL_PROPAGATION+Ra.SPILL_COLORING
320 : monnier 469 },
321 :     {spill = spillF,
322 : monnier 498 spillSrc = spillFreg,
323 :     spillCopyTmp= spillFcopyTmp,
324 : monnier 469 reload = reloadF,
325 : monnier 498 reloadDst = reloadFreg,
326 :     renameSrc = renameF,
327 : monnier 469 copyInstr = copyInstrF,
328 :     K = KF,
329 :     getreg = FR.getreg,
330 :     cellkind = I.C.FP,
331 :     dedicated = dedicatedF,
332 :     spillProh = [],
333 : leunga 576 memRegs = [],
334 : monnier 498 mode = Ra.SPILL_PROPAGATION
335 : monnier 469 }] cluster
336 : monnier 498 val _ = removeDeadCode cluster
337 : monnier 469 val _ = printGraph "\t---After register allocation K=8---\n" cluster
338 :     in cluster
339 : monnier 247 end
340 :    
341 : monnier 429 end (* RegAllocation *)
342 : monnier 247
343 : monnier 429 )
344 : monnier 247

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