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/ra/x86Spill.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/x86/ra/x86Spill.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 565 - (view) (download)

1 : monnier 247 (* X86Spill.sml
2 :     *
3 :     * X86 spilling is complicated business.
4 : monnier 498 * Allen: and it just got more complicated; now we have to recognize the regmap.
5 : george 545 * I've also improved the spilling code so that more instructions are
6 :     * recognized. Addressing modes are now folded into the existing instruction
7 :     * whenever possible. This eliminates some redundant temporaries which were
8 :     * introduced before.
9 : monnier 247 *)
10 :     signature X86SPILL = sig
11 :     structure I : X86INSTR
12 :     val spill :
13 : monnier 498 I.instruction * (I.C.cell -> I.C.cell) * I.C.cell * I.operand ->
14 :     {code:I.instruction list, proh:I.C.cell list, newReg:I.C.cell option}
15 : monnier 247
16 :     val reload :
17 : monnier 498 I.instruction * (I.C.cell -> I.C.cell) * I.C.cell * I.operand ->
18 :     {code:I.instruction list, proh:I.C.cell list, newReg:I.C.cell option}
19 : monnier 247
20 :     val fspill :
21 : monnier 498 I.instruction * (I.C.cell -> I.C.cell) * I.C.cell * I.operand ->
22 :     {code:I.instruction list, proh:I.C.cell list, newReg:I.C.cell option}
23 : monnier 247
24 :     val freload :
25 : monnier 498 I.instruction * (I.C.cell -> I.C.cell) * I.C.cell * I.operand ->
26 :     {code:I.instruction list, proh:I.C.cell list, newReg:I.C.cell option}
27 : monnier 247 end
28 :    
29 :    
30 :     functor X86Spill(structure Instr: X86INSTR
31 : monnier 498 structure Props: INSN_PROPERTIES where I = Instr
32 :     ) : X86SPILL = struct
33 : monnier 247
34 : monnier 429 structure I = Instr
35 :     structure C = I.C
36 : monnier 247
37 : monnier 411 fun error msg = MLRiscErrorMsg.impossible("X86Spill: "^ msg)
38 : monnier 247
39 :     fun immed(I.Immed _) = true
40 :     | immed(I.ImmedLabel _) = true
41 :     | immed _ = false
42 :    
43 :     fun immedOrReg(I.Direct r) = true
44 : monnier 498 | immedOrReg(I.Immed _) = true
45 :     | immedOrReg(I.ImmedLabel _) = true
46 :     | immedOrReg _ = false
47 : monnier 247
48 : george 545 fun isMemory(I.MemReg _) = true
49 :     | isMemory(I.Displace _) = true
50 :     | isMemory(I.Indexed _) = true
51 :     | isMemory(I.LabelEA _) = true
52 :     | isMemory _ = false
53 :    
54 : monnier 498 (* Annotate instruction *)
55 :     fun mark(instr,[]) = instr
56 :     | mark(instr,a::an) = mark(I.ANNOTATION{i=instr,a=a},an)
57 : monnier 247
58 : monnier 498 val newReg = C.newReg
59 :    
60 : monnier 247 (* XXX:: Need to go through all the cases where 'done' is used
61 :     * to make sure that a the src cannot contain the register
62 :     * being spilled.
63 :     *)
64 : monnier 498 fun spill(instr, regmap, reg, spillLoc) =
65 :     let fun done(instr, an) = {code=[mark(instr, an)], proh=[], newReg=NONE}
66 :     fun spillIt(instr,an) =
67 :     case instr of
68 :     I.CALL(addr, defs, uses, mem) =>
69 :     done(I.CALL(addr, C.rmvReg(reg,defs), uses, mem), an)
70 : george 545 | I.MOVE{mvOp as (I.MOVZBL|I.MOVSBL|I.MOVZWL|I.MOVSWL), src, dst} =>
71 : monnier 498 let val tmpR = newReg() val tmp = I.Direct tmpR
72 :     in {proh=[tmpR], newReg=SOME tmpR,
73 : george 545 code=[mark(I.MOVE{mvOp=mvOp, src=src, dst=tmp}, an),
74 : monnier 498 I.MOVE{mvOp=I.MOVL, src=tmp, dst=spillLoc}]
75 :     }
76 :     end
77 :     | I.MOVE{mvOp, src as I.Direct rs, dst} =>
78 :     if regmap rs=reg then {code=[], proh=[], newReg=NONE}
79 :     else done(I.MOVE{mvOp=mvOp, src=src, dst=spillLoc}, an)
80 :     | I.MOVE{mvOp, src, dst=I.Direct _} =>
81 :     if Props.eqOpn(src, spillLoc) then {code=[], proh=[], newReg=NONE}
82 :     else if immed src then
83 :     done(I.MOVE{mvOp=mvOp, src=src, dst=spillLoc}, an)
84 :     else
85 :     let val tmpR = newReg()
86 :     val tmp = I.Direct tmpR
87 :     in {proh=[tmpR],
88 :     newReg=SOME tmpR,
89 :     code=[mark(I.MOVE{mvOp=mvOp, src=src, dst=tmp}, an),
90 :     I.MOVE{mvOp=mvOp, src=tmp, dst=spillLoc}]
91 :     }
92 :     end
93 :     | I.LEA{addr, r32} =>
94 :     let val tmpR = newReg()
95 :     in {proh=[tmpR],
96 :     newReg=SOME tmpR,
97 :     code=[mark(I.LEA{addr=addr, r32=tmpR}, an),
98 :     I.MOVE{mvOp=I.MOVL, src=I.Direct tmpR, dst=spillLoc}]
99 :     }
100 :     end
101 : george 545 | I.BINARY{binOp=I.XORL, src as I.Direct rs, dst=I.Direct rd} =>
102 :     if rs=rd then
103 :     {proh=[],
104 :     code=[mark(I.MOVE{mvOp=I.MOVL, src=I.Immed 0, dst=spillLoc}, an)],
105 :     newReg=NONE
106 :     }
107 :     else
108 :     {proh=[],
109 :     code=[mark(I.BINARY{binOp=I.XORL, src=src, dst=spillLoc}, an)],
110 :     newReg=NONE
111 :     }
112 : monnier 498 | I.BINARY{binOp, src, dst} => (* note: dst = reg *)
113 :     if immedOrReg src then
114 :     {proh=[],
115 :     code=[(* I.MOVE{mvOp=I.MOVL, src=dst, dst=spillLoc}, XXX *)
116 :     mark(I.BINARY{binOp=binOp, src=src, dst=spillLoc}, an)
117 :     ],
118 :     newReg=NONE
119 :     }
120 :     else
121 :     let val tmpR = newReg()
122 :     val tmp = I.Direct tmpR
123 :     in {proh=[tmpR],
124 :     code=[(* I.MOVE{mvOp=I.MOVL, src=dst, dst=spillLoc}, XXX *)
125 :     I.MOVE{mvOp=I.MOVL, src=src, dst=tmp},
126 :     mark(I.BINARY{binOp=binOp, src=tmp, dst=spillLoc}, an)
127 :     ],
128 :     newReg=NONE
129 :     }
130 : monnier 247 end
131 : monnier 498 | I.MULTDIV _ => error "spill: MULTDIV"
132 :     | I.MUL3{src1, src2, dst} =>
133 :     let val tmpR = newReg()
134 :     in {proh=[tmpR], newReg=SOME tmpR,
135 :     code=[mark(I.MUL3{src1=src1, src2=src2, dst=tmpR}, an),
136 :     I.MOVE{mvOp=I.MOVL, src=I.Direct tmpR, dst=spillLoc}]
137 :     }
138 :     end
139 :     | I.UNARY{unOp, opnd} => done(I.UNARY{unOp=unOp, opnd=spillLoc}, an)
140 : george 545 | I.SET{cond, opnd} => done(I.SET{cond=cond, opnd=spillLoc}, an)
141 : monnier 498 | I.POP _ => done(I.POP spillLoc, an)
142 :     | I.COPY _ => error "spill: COPY"
143 :     | I.FNSTSW => error "spill: FNSTSW"
144 :     | I.ANNOTATION{i,a} => spillIt(i, a::an)
145 :     | _ => error "spill"
146 :     in spillIt(instr, [])
147 :     end (* spill *)
148 : monnier 247
149 : monnier 498 fun reload(instr, regmap, reg, spillLoc) =
150 :     let fun operand(rt, opnd) =
151 : monnier 247 (case opnd
152 : monnier 498 of I.Direct r => if regmap r=reg then I.Direct rt else opnd
153 : monnier 411 | I.Displace{base, disp, mem} =>
154 : monnier 498 if regmap base=reg then I.Displace{base=rt, disp=disp, mem=mem}
155 :     else opnd
156 : monnier 411 | I.Indexed{base=NONE, index, scale, disp, mem=mem} =>
157 : monnier 498 if regmap index=reg then
158 : monnier 411 I.Indexed{base=NONE, index=rt, scale=scale, disp=disp, mem=mem}
159 : monnier 247 else opnd
160 : monnier 411 | I.Indexed{base as SOME b, index, scale, disp, mem=mem} =>
161 : monnier 498 if regmap b=reg then
162 : monnier 247 operand(rt, I.Indexed{base=SOME rt, index=index,
163 : monnier 411 scale=scale, disp=disp, mem=mem})
164 : monnier 498 else if regmap index=reg then
165 : monnier 411 I.Indexed{base=base, index=rt, scale=scale, disp=disp, mem=mem}
166 : monnier 247 else opnd
167 :     | opnd => opnd
168 :     (*esac*))
169 :    
170 : monnier 498 fun done(instr, an) = {code=[mark(instr, an)], proh=[], newReg=NONE}
171 :    
172 :     (* This version assumes that the value of tmpR is killed *)
173 :     fun withTmp(f, an) =
174 :     let val tmpR = newReg()
175 :     in {newReg=NONE,
176 :     proh=[tmpR],
177 :     code=[I.MOVE{mvOp=I.MOVL, src=spillLoc, dst=I.Direct tmpR},
178 :     mark(f tmpR, an)
179 :     ]
180 :     }
181 : monnier 247 end
182 : monnier 498
183 :     (* This version assumes that the value of tmpR is available afterwards *)
184 :     fun withTmp'(f, an) =
185 :     let val tmpR = newReg()
186 :     val tmp = I.Direct tmpR
187 :     in {newReg=SOME tmpR,
188 :     proh=[tmpR],
189 :     code=[I.MOVE{mvOp=I.MOVL, src=spillLoc, dst=I.Direct tmpR},
190 :     mark(f tmpR, an)
191 :     ]
192 :     }
193 :     end
194 :    
195 : george 545 fun replace(opn as I.Direct r) = if regmap r = reg then spillLoc else opn
196 :     | replace opn = opn
197 :    
198 :     (* Fold in a memory operand if possible. Makes sure that both operands
199 :     * are not in memory. lsrc cannot be immediate.
200 :     *)
201 :     fun reloadCmp(cmp, lsrc, rsrc, an) =
202 :     let fun reloadIt() =
203 :     withTmp(fn tmpR =>
204 :     cmp{lsrc=operand(tmpR, lsrc), rsrc=operand(tmpR, rsrc)}, an)
205 :     in if immedOrReg lsrc andalso immedOrReg rsrc then
206 :     let val lsrc' = replace lsrc
207 :     val rsrc' = replace rsrc
208 :     in if isMemory lsrc' andalso isMemory rsrc' then
209 :     reloadIt()
210 :     else
211 :     done(cmp{lsrc=lsrc', rsrc=rsrc'}, an)
212 :     end
213 :     else reloadIt()
214 :     end
215 :    
216 :     (* Fold in a memory operand if possible. Makes sure that the right
217 :     * operand is not in memory and left operand is not an immediate.
218 :     * lsrc rsrc
219 :     * AL, imm8 opc1 A8
220 :     * EAX, imm32 opc1 A9
221 :     * r/m8, imm8 opc2 F6/0 ib
222 :     * r/m32, imm32 opc2 F7/0 id
223 :     * r/m32, r32 opc3 85/r
224 :     *)
225 :     fun reloadTest(test, lsrc, rsrc, an) =
226 :     let fun reloadIt() =
227 :     withTmp(fn tmpR =>
228 :     test{lsrc=operand(tmpR, lsrc), rsrc=operand(tmpR, rsrc)}, an)
229 :     in if immedOrReg lsrc andalso immedOrReg rsrc then
230 :     let val lsrc = replace lsrc
231 :     val rsrc = replace rsrc
232 :     in if isMemory rsrc then
233 :     if isMemory lsrc then reloadIt()
234 :     else (* it is commutative! *)
235 :     done(test{lsrc=rsrc, rsrc=lsrc}, an)
236 :     else
237 :     done(test{lsrc=lsrc, rsrc=rsrc}, an)
238 :     end
239 :     else reloadIt()
240 :     end
241 :    
242 :     fun reloadPush(push, arg as I.Direct _, an) =
243 :     done(push(replace arg), an)
244 :     | reloadPush(push, arg, an) =
245 :     withTmp(fn tmpR => push(operand(tmpR, arg)), an)
246 :    
247 :     fun reloadReal(realOp, opnd, an) =
248 :     withTmp'(fn tmpR => realOp(operand(tmpR, opnd)), an)
249 :    
250 : monnier 498 fun reloadIt(instr, an) =
251 : monnier 247 case instr
252 : monnier 498 of I.JMP(I.Direct _, labs) => done(I.JMP(spillLoc, labs), an)
253 :     | I.JMP(opnd, labs) => withTmp(fn t => I.JMP(operand(t, opnd), labs), an)
254 :     | I.JCC{opnd=I.Direct _, cond} => done(I.JCC{opnd=spillLoc, cond=cond}, an)
255 : monnier 247 | I.JCC{opnd, cond} =>
256 : monnier 498 withTmp(fn t => I.JCC{opnd=operand(t,opnd), cond=cond}, an)
257 :     | I.CALL(opnd, defs, uses, mem) =>
258 :     let val tmpR = newReg()
259 :     in {proh=[tmpR],
260 :     newReg=NONE,
261 :     code=[mark(
262 :     I.CALL(operand(tmpR, opnd), defs, C.rmvReg(reg,uses), mem),
263 :     an)]
264 :     }
265 : monnier 429 end
266 : george 545 | I.MOVE{mvOp, src as I.Direct _, dst as I.Direct _} =>
267 :     done(I.MOVE{mvOp=mvOp, src=replace src, dst=dst},an)
268 : monnier 247 | I.MOVE{mvOp, src, dst as I.Direct _} =>
269 : monnier 498 withTmp'(fn t =>I.MOVE{mvOp=mvOp, src=operand(t, src), dst=dst},an)
270 : monnier 247 | I.MOVE{mvOp, src as I.Direct _, dst} =>
271 : monnier 498 if Props.eqOpn(dst, spillLoc) then {code=[], proh=[], newReg=NONE}
272 : monnier 247 else withTmp
273 : monnier 498 (fn t =>
274 :     I.MOVE{mvOp=mvOp, src=operand(t, src), dst=operand(t, dst)}, an)
275 : monnier 247 | I.MOVE{mvOp, src, dst} =>
276 :     withTmp
277 : monnier 498 (fn t =>
278 :     I.MOVE{mvOp=mvOp, src=operand(t, src), dst=operand(t, dst)}, an)
279 : monnier 247 | I.LEA{r32, addr} =>
280 : monnier 498 withTmp'(fn tmpR => I.LEA{r32=r32, addr=operand(tmpR, addr)}, an)
281 : george 545 | I.CMPL{lsrc, rsrc} => reloadCmp(I.CMPL, lsrc, rsrc, an)
282 :     | I.CMPW{lsrc, rsrc} => reloadCmp(I.CMPW, lsrc, rsrc, an)
283 :     | I.CMPB{lsrc, rsrc} => reloadCmp(I.CMPB, lsrc, rsrc, an)
284 :     | I.TESTL{lsrc, rsrc} => reloadTest(I.TESTL, lsrc, rsrc, an)
285 :     | I.TESTW{lsrc, rsrc} => reloadTest(I.TESTW, lsrc, rsrc, an)
286 :     | I.TESTB{lsrc, rsrc} => reloadTest(I.TESTB, lsrc, rsrc, an)
287 : monnier 247 | I.BINARY{binOp, src, dst as I.Direct _} =>
288 : george 545 (case src of
289 :     I.Direct _ =>
290 :     done(I.BINARY{binOp=binOp, src=replace src, dst=dst},an)
291 :     | _ => withTmp(fn tmpR =>
292 :     I.BINARY{binOp=binOp, src=operand(tmpR, src), dst=dst}, an)
293 :     )
294 : monnier 247 | I.BINARY{binOp, src, dst} =>
295 : monnier 498 withTmp(fn tmpR => I.BINARY{binOp=binOp, src=operand(tmpR, src),
296 :     dst=operand(tmpR, dst)}, an)
297 : george 545 | I.MULTDIV{multDivOp, src as I.Direct _} =>
298 :     done(I.MULTDIV{multDivOp=multDivOp, src=replace src}, an)
299 :     | I.MULTDIV{multDivOp, src} =>
300 : monnier 498 withTmp(fn tmpR =>
301 :     I.MULTDIV{multDivOp=multDivOp, src=operand(tmpR, src)}, an)
302 : monnier 247 | I.MUL3{src1, src2, dst} =>
303 :     withTmp(fn tmpR =>
304 :     I.MUL3{src1=operand(tmpR, src1), src2=src2,
305 : monnier 498 dst=if regmap dst = reg then error "reload:MUL3" else dst}, an)
306 : monnier 247 | I.UNARY{unOp, opnd} =>
307 : monnier 498 withTmp'(fn tmpR => I.UNARY{unOp=unOp, opnd=operand(tmpR, opnd)}, an)
308 : george 545 | I.SET{cond, opnd} =>
309 :     withTmp'(fn tmpR => I.SET{cond=cond, opnd=operand(tmpR, opnd)}, an)
310 :     | I.PUSHL arg => reloadPush(I.PUSHL, arg, an)
311 :     | I.PUSHW arg => reloadPush(I.PUSHW, arg, an)
312 :     | I.PUSHB arg => reloadPush(I.PUSHB, arg, an)
313 : monnier 247 | I.COPY _ => error "reload:COPY"
314 : george 545 | I.FILD opnd => reloadReal(I.FILD, opnd, an)
315 : leunga 565 | I.FILDL opnd => reloadReal(I.FILDL, opnd, an)
316 :     | I.FILDLL opnd => reloadReal(I.FILDLL, opnd, an)
317 : george 555 | I.FLDT opnd => reloadReal(I.FLDT, opnd, an)
318 : george 545 | I.FLDL opnd => reloadReal(I.FLDL, opnd, an)
319 :     | I.FLDS opnd => reloadReal(I.FLDS, opnd, an)
320 : george 555 | I.FSTPT opnd => reloadReal(I.FSTPT, opnd, an)
321 : george 545 | I.FSTPL opnd => reloadReal(I.FSTPL, opnd, an)
322 :     | I.FSTPS opnd => reloadReal(I.FSTPS, opnd, an)
323 :     | I.FENV{fenvOp, opnd} => reloadReal(fn opnd =>
324 :     I.FENV{fenvOp=fenvOp,opnd=opnd}, opnd, an)
325 : monnier 247 | I.FBINARY{binOp, src, dst} =>
326 : monnier 498 withTmp'(fn tmpR =>
327 :     I.FBINARY{binOp=binOp, src=operand(tmpR, src), dst=dst}, an)
328 : leunga 565 | I.FIBINARY{binOp, src} =>
329 :     withTmp'(fn tmpR => I.FIBINARY{binOp=binOp, src=operand(tmpR, src)}, an)
330 : monnier 498 | I.ANNOTATION{i,a} => reloadIt(i, a::an)
331 : monnier 247 | _ => error "reload"
332 : monnier 498 in reloadIt(instr, [])
333 : monnier 247 end (*reload*)
334 :    
335 : monnier 498 fun fspill(instr, regmap, reg, spillLoc) =
336 :     let fun spillIt(instr, an) =
337 :     (case instr of
338 : george 545 I.FSTPL _ => {proh=[], code=[mark(I.FSTPL spillLoc, an)], newReg=NONE}
339 :     | I.FSTPS _ => {proh=[], code=[mark(I.FSTPS spillLoc, an)], newReg=NONE}
340 : monnier 429 | I.CALL(opnd, defs, uses, mem) =>
341 :     {proh=[],
342 : monnier 498 code=[mark(I.CALL(opnd, C.rmvFreg(reg,defs), uses, mem), an)],
343 :     newReg=NONE}
344 :     | I.ANNOTATION{i,a} => spillIt(i, a::an)
345 : monnier 247 | _ => error "fspill"
346 : monnier 498 (*esac*))
347 :     in spillIt(instr, [])
348 :     end (* fspill *)
349 : monnier 247
350 : monnier 498 fun freload(instr, regmap, reg, spillLoc) =
351 :     let fun reloadIt(instr, an) =
352 :     (case instr of
353 : george 555 I.FLDT opnd => {code=[mark(I.FLDT spillLoc, an)], proh=[], newReg=NONE}
354 :     | I.FLDL opnd => {code=[mark(I.FLDL spillLoc, an)], proh=[], newReg=NONE}
355 : george 545 | I.FLDS opnd => {code=[mark(I.FLDS spillLoc, an)], proh=[], newReg=NONE}
356 : monnier 247 | I.FBINARY{binOp, src=I.FDirect f, dst} =>
357 : monnier 498 if regmap f = reg then
358 :     {code=[mark(I.FBINARY{binOp=binOp, src=spillLoc, dst=dst}, an)],
359 :     proh=[],
360 :     newReg=NONE}
361 : monnier 247 else error "freload:FBINARY"
362 : monnier 429 | I.CALL(opnd, defs, uses, mem) =>
363 :     {proh=[],
364 : monnier 498 code=[mark(I.CALL(opnd, C.rmvFreg(reg,defs), uses, mem), an)],
365 :     newReg=NONE}
366 :     | I.ANNOTATION{i,a} => reloadIt(i, a::an)
367 : monnier 247 | _ => error "freload"
368 : monnier 498 (*esac*))
369 :     in reloadIt(instr, [])
370 :     end (* freload *)
371 :    
372 : monnier 411 end

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