Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Diff of /sml/trunk/src/MLRISC/x86/ra/x86Spill.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 247, Sat Apr 17 18:47:13 1999 UTC revision 498, Tue Dec 7 15:44:50 1999 UTC
# Line 1  Line 1 
1  (* X86Spill.sml  (* X86Spill.sml
2   *   *
3   * X86 spilling is complicated business.   * X86 spilling is complicated business.
4     * Allen: and it just got more complicated; now we have to recognize the regmap.
5   *)   *)
6  signature X86SPILL = sig  signature X86SPILL = sig
7    structure I : X86INSTR    structure I : X86INSTR
8    val spill :    val spill :
9      I.instruction * int * I.operand ->      I.instruction * (I.C.cell -> I.C.cell) * I.C.cell * I.operand ->
10        {code:I.instruction list, proh:int list, instr:I.instruction option}        {code:I.instruction list, proh:I.C.cell list, newReg:I.C.cell option}
11    
12    val reload :    val reload :
13      I.instruction * int * I.operand -> {code:I.instruction list, proh:int list}      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    
16    val fspill :    val fspill :
17      I.instruction * int * I.operand ->      I.instruction * (I.C.cell -> I.C.cell) * I.C.cell * I.operand ->
18        {code:I.instruction list, proh:int list, instr:I.instruction option}        {code:I.instruction list, proh:I.C.cell list, newReg:I.C.cell option}
19    
20    val freload :    val freload :
21      I.instruction * int * I.operand -> {code:I.instruction list, proh:int list}      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  end  end
24    
25    
26  functor X86Spill(structure Instr: X86INSTR  functor X86Spill(structure Instr: X86INSTR
27                   structure Asm : EMITTER_NEW where I = Instr (* XXX *)                   structure Props: INSN_PROPERTIES where I = Instr
   
28                   ) : X86SPILL = struct                   ) : X86SPILL = struct
29    
   (* XXX: Looks like the wrong thing is done with CMPL.  
    * That is to say, does not recognize memory arguments.  
    *)  
30    structure I = Instr    structure I = Instr
31    structure C = I.C    structure C = I.C
32    
33    fun error msg = MLRiscErrorMsg.impossible ("X86Spill: " ^ msg)    fun error msg = MLRiscErrorMsg.impossible ("X86Spill: " ^ msg)
34    
   type s = I.instruction * int * I.operand ->  
              {code:I.instruction list, proh:int list, instr:I.instruction option}  
   type r = I.instruction * int * I.operand -> {code:I.instruction list, proh:int list}  
   
   val newReg = C.newReg  
   
35    fun immed(I.Immed _) = true    fun immed(I.Immed _) = true
36      | immed(I.ImmedLabel _) = true      | immed(I.ImmedLabel _) = true
37      | immed(I.Const _) = true      | immed(I.Const _) = true
# Line 46  Line 39 
39      | immed _ = false      | immed _ = false
40    
41    fun immedOrReg(I.Direct r) = true    fun immedOrReg(I.Direct r) = true
42      | immedOrReg opnd = immed opnd      | immedOrReg(I.Immed _) = true
43        | immedOrReg(I.ImmedLabel _) = true
44        | immedOrReg(I.Const _) = true
45        | immedOrReg(I.LabelEA _) = true
46        | immedOrReg _ = false
47    
48      (* Annotate instruction *)
49      fun mark(instr,[]) = instr
50        | mark(instr,a::an) = mark(I.ANNOTATION{i=instr,a=a},an)
51    
52    fun eqEA(I.Displace{base=b1, disp=d1}, I.Displace{base=b2, disp=d2}) =    val newReg = C.newReg
       b1=b2 andalso  
        (case (d1, d2)  
          of (I.Immed i1, I.Immed i2) => i1 = i2  
           | _ => false  
        (*esac*))  
     | eqEA _ = false  
53    
54    (* XXX:: Need to go through all the cases where 'done' is used    (* XXX:: Need to go through all the cases where 'done' is used
55     * to make sure that a the src cannot contain the register     * to make sure that a the src cannot contain the register
56     * being spilled.     * being spilled.
57     *)     *)
58    fun spill(instr, reg, spillLoc) = let    fun spill(instr, regmap, reg, spillLoc) =
59      fun done code = {code=code, proh=[], instr=NONE}    let fun done(instr, an) = {code=[mark(instr, an)], proh=[], newReg=NONE}
60      fun rewrite new old = if old=reg then new else old        fun spillIt(instr,an) =
61    in        case instr of
62      case instr          I.CALL(addr, defs, uses, mem) =>
63      of I.CALL(opnd, (r,f,c), uses) => let            done(I.CALL(addr, C.rmvReg(reg,defs), uses, mem), an)
64           val tmpR = newReg()        | I.MOVE{mvOp=I.MOVZX, src, dst} =>
65         in            let val tmpR = newReg() val tmp = I.Direct tmpR
66           {proh=[tmpR],            in  {proh=[tmpR], newReg=SOME tmpR,
67            instr=SOME(I.CALL(opnd, (map (rewrite tmpR) r,f,c), uses)),                 code=[mark(I.MOVE{mvOp=I.MOVZX, src=src, dst=tmp}, an),
68            code=[I.MOVE{mvOp=I.MOVL, src=I.Direct tmpR, dst=spillLoc}] }                       I.MOVE{mvOp=I.MOVL, src=tmp, dst=spillLoc}]
69         end                }
      | I.MOVE{mvOp=I.MOVZX, src, dst} => let(* dst must always be a register *)  
          val tmpR = newReg()  
        in  
          {proh=[tmpR],  
           instr=SOME(I.MOVE{mvOp=I.MOVZX, src=src, dst=I.Direct tmpR}),  
           code=[I.MOVE{mvOp=I.MOVL, src=I.Direct tmpR, dst=spillLoc}]}  
70         end         end
71       | I.MOVE{mvOp, src as I.Direct rs, dst} =>       | I.MOVE{mvOp, src as I.Direct rs, dst} =>
72          if rs=reg then {code=[], proh=[], instr=NONE}            if regmap rs=reg then {code=[], proh=[], newReg=NONE}
73          else done [I.MOVE{mvOp=mvOp, src=src, dst=spillLoc}]            else done(I.MOVE{mvOp=mvOp, src=src, dst=spillLoc}, an)
74       | I.MOVE{mvOp, src, dst=I.Direct _} =>       | I.MOVE{mvOp, src, dst=I.Direct _} =>
75          if immed src then done [I.MOVE{mvOp=mvOp, src=src, dst=spillLoc}]            if Props.eqOpn(src, spillLoc) then {code=[], proh=[], newReg=NONE}
76          else if eqEA(src, spillLoc) then {code=[], proh=[], instr=NONE}            else if immed src then
77          else let               done(I.MOVE{mvOp=mvOp, src=src, dst=spillLoc}, an)
78              val tmpR = newReg()            else
79            in            let val tmpR = newReg()
80              {instr=SOME(I.MOVE{mvOp=mvOp, src=src, dst=I.Direct tmpR}),                val tmp  = I.Direct tmpR
81               proh=[tmpR],            in  {proh=[tmpR],
82               code=[I.MOVE{mvOp=mvOp, src=I.Direct tmpR, dst=spillLoc}]}                 newReg=SOME tmpR,
83                   code=[mark(I.MOVE{mvOp=mvOp, src=src, dst=tmp}, an),
84                         I.MOVE{mvOp=mvOp, src=tmp, dst=spillLoc}]
85                  }
86            end            end
87       | I.LEA{addr, r32} => let        | I.LEA{addr, r32} =>
88           val tmpR = newReg()            let val tmpR = newReg()
89         in {instr=SOME(I.LEA{addr=addr, r32=tmpR}),            in  {proh=[tmpR],
90             proh=[tmpR],                 newReg=SOME tmpR,
91             code=[I.MOVE{mvOp=I.MOVL, src=I.Direct tmpR, dst=spillLoc}]}                 code=[mark(I.LEA{addr=addr, r32=tmpR}, an),
92                         I.MOVE{mvOp=I.MOVL, src=I.Direct tmpR, dst=spillLoc}]
93                  }
94         end         end
95       | I.BINARY{binOp, src, dst} =>        | I.BINARY{binOp, src, dst} => (* note: dst = reg *)
96         if immedOrReg src then         if immedOrReg src then
97           {instr=SOME(I.BINARY{binOp=binOp, src=src, dst=spillLoc}),               {proh=[],
98            proh=[],                code=[(* I.MOVE{mvOp=I.MOVL, src=dst, dst=spillLoc}, XXX *)
99            code=[]}                      mark(I.BINARY{binOp=binOp, src=src, dst=spillLoc}, an)
100         else let                     ],
101             val tmpR = newReg()                newReg=NONE
102           in               }
103             {instr=SOME(I.MOVE{mvOp=I.MOVL, src=src, dst=I.Direct tmpR}),            else
104              proh=[tmpR],            let val tmpR = newReg()
105              code=[I.BINARY{binOp=binOp, src=I.Direct tmpR, dst=spillLoc}]}                val tmp  = I.Direct tmpR
106              in  {proh=[tmpR],
107                   code=[(* I.MOVE{mvOp=I.MOVL, src=dst, dst=spillLoc}, XXX *)
108                         I.MOVE{mvOp=I.MOVL, src=src, dst=tmp},
109                         mark(I.BINARY{binOp=binOp, src=tmp, dst=spillLoc}, an)
110                        ],
111                   newReg=NONE
112                  }
113           end           end
114       | I.MULTDIV _ => error "spill: MULTDIV"       | I.MULTDIV _ => error "spill: MULTDIV"
115       | I.MUL3{src1, src2, dst} => let        | I.MUL3{src1, src2, dst} =>
116           val tmpR = newReg()            let val tmpR = newReg()
117         in            in  {proh=[tmpR], newReg=SOME tmpR,
118           {instr=SOME(I.MUL3{src1=src1, src2=src2, dst=tmpR}),                 code=[mark(I.MUL3{src1=src1, src2=src2, dst=tmpR}, an),
119            proh=[tmpR],                       I.MOVE{mvOp=I.MOVL, src=I.Direct tmpR, dst=spillLoc}]
120            code=[I.MOVE{mvOp=I.MOVL, src=I.Direct tmpR, dst=spillLoc}]}                }
121         end         end
122       | I.UNARY{unOp, opnd} => done [I.UNARY{unOp=unOp, opnd=spillLoc}]        | I.UNARY{unOp, opnd} => done(I.UNARY{unOp=unOp, opnd=spillLoc}, an)
123       | I.POP _ => done [I.POP spillLoc]        | I.POP _ => done(I.POP spillLoc, an)
124       | I.COPY _ => error "spill: COPY"       | I.COPY _ => error "spill: COPY"
125       | I.FNSTSW  => error "spill: FNSTSW"       | I.FNSTSW  => error "spill: FNSTSW"
126          | I.ANNOTATION{i,a} => spillIt(i, a::an)
127       | _ => error "spill"       | _ => error "spill"
128    end    in  spillIt(instr, [])
129      end (* spill *)
130    
131    fun reload(instr, reg, spillLoc) = let    fun reload(instr, regmap, reg, spillLoc) =
132      fun operand(rt, opnd) =    let fun operand(rt, opnd) =
133        (case opnd        (case opnd
134         of I.Direct r => if r=reg then I.Direct rt else opnd         of I.Direct r => if regmap r=reg then I.Direct rt else opnd
135          | I.Displace{base, disp} =>          | I.Displace{base, disp, mem} =>
136             if base=reg then I.Displace{base=rt, disp=disp} else opnd             if regmap base=reg then I.Displace{base=rt, disp=disp, mem=mem}
         | I.Indexed{base=NONE, index, scale, disp} =>  
            if index=reg then  
              I.Indexed{base=NONE, index=rt, scale=scale, disp=disp}  
137             else opnd             else opnd
138          | I.Indexed{base as SOME b, index, scale, disp} =>          | I.Indexed{base=NONE, index, scale, disp, mem=mem} =>
139             if b=reg then             if regmap index=reg then
140                 I.Indexed{base=NONE, index=rt, scale=scale, disp=disp, mem=mem}
141               else opnd
142            | I.Indexed{base as SOME b, index, scale, disp, mem=mem} =>
143               if regmap b=reg then
144               operand(rt, I.Indexed{base=SOME rt, index=index,               operand(rt, I.Indexed{base=SOME rt, index=index,
145                                     scale=scale, disp=disp})                                     scale=scale, disp=disp, mem=mem})
146             else if index=reg then             else if regmap index=reg then
147               I.Indexed{base=base, index=rt, scale=scale, disp=disp}               I.Indexed{base=base, index=rt, scale=scale, disp=disp, mem=mem}
148                  else opnd                  else opnd
149          | opnd => opnd          | opnd => opnd
150        (*esac*))        (*esac*))
151    
152      fun uses(I.Direct r) = r = reg      (* XXX *)      fun done(instr, an) = {code=[mark(instr, an)], proh=[], newReg=NONE}
153        | uses(I.Displace{base, disp}) = base=reg  
154        | uses(I.Indexed{base=NONE, index, scale, disp}) = index=reg      (* This version assumes that the value of tmpR is killed *)
155        | uses(I.Indexed{base=SOME b, index, scale, disp})= b=reg orelse index=reg      fun withTmp(f, an) =
156        | uses _ = false      let val tmpR = newReg()
157      fun done c = {code=c, proh=[]}      in  {newReg=NONE,
158      fun rewrite rt r = if r=reg then rt else r           proh=[tmpR],
159      fun ldSpillLoc (tmpR) = I.MOVE{mvOp=I.MOVL, src=spillLoc, dst=I.Direct tmpR}           code=[I.MOVE{mvOp=I.MOVL, src=spillLoc, dst=I.Direct tmpR},
160      fun withTmp f = let                 mark(f tmpR, an)
161        val tmpR = newReg()                ]
162      in {code=[ldSpillLoc(tmpR), f tmpR], proh=[tmpR]}          }
163        end
164    
165        (* This version assumes that the value of tmpR is available afterwards *)
166        fun withTmp'(f, an) =
167        let val tmpR = newReg()
168            val tmp  = I.Direct tmpR
169        in  {newReg=SOME tmpR,
170             proh=[tmpR],
171             code=[I.MOVE{mvOp=I.MOVL, src=spillLoc, dst=I.Direct tmpR},
172                   mark(f tmpR, an)
173                  ]
174            }
175      end      end
176    in  
177        fun reloadIt(instr, an) =
178      case instr      case instr
179      of I.JMP(I.Direct _, labs) => {code=[I.JMP(spillLoc, labs)], proh=[]}      of I.JMP(I.Direct _, labs) => done(I.JMP(spillLoc, labs), an)
180       | I.JMP(opnd, labs) => withTmp(fn tmpR => I.JMP(operand(tmpR, opnd), labs))       | I.JMP(opnd, labs) => withTmp(fn t => I.JMP(operand(t, opnd), labs), an)
181       | I.JCC{opnd=I.Direct _, cond} => done[I.JCC{opnd=spillLoc, cond=cond}]       | I.JCC{opnd=I.Direct _, cond} => done(I.JCC{opnd=spillLoc, cond=cond}, an)
182       | I.JCC{opnd, cond} =>       | I.JCC{opnd, cond} =>
183          withTmp(fn tmpR => I.JCC{opnd=operand(tmpR, opnd), cond=cond})            withTmp(fn t => I.JCC{opnd=operand(t,opnd), cond=cond}, an)
184       | I.CALL(opnd, defs, uses as (r,f,c)) =>       | I.CALL(opnd, defs, uses, mem) =>
185          withTmp(fn tmpR =>         let val tmpR = newReg()
186                    I.CALL(operand(tmpR, opnd), defs, (map (rewrite tmpR) r, f,c)))         in  {proh=[tmpR],
187                newReg=NONE,
188                code=[mark(
189                       I.CALL(operand(tmpR, opnd), defs, C.rmvReg(reg,uses), mem),
190                      an)]
191               }
192           end
193       | I.MOVE{mvOp, src, dst as I.Direct _} =>       | I.MOVE{mvOp, src, dst as I.Direct _} =>
194          withTmp(fn tmpR =>I.MOVE{mvOp=mvOp, src=operand(tmpR, src), dst=dst})          withTmp'(fn t =>I.MOVE{mvOp=mvOp, src=operand(t, src), dst=dst},an)
195       | I.MOVE{mvOp, src as I.Direct _, dst} =>       | I.MOVE{mvOp, src as I.Direct _, dst} =>
196          if eqEA(dst, spillLoc) then {code=[], proh=[]}          if Props.eqOpn(dst, spillLoc) then {code=[], proh=[], newReg=NONE}
197          else withTmp          else withTmp
198            (fn tmpR =>            (fn t =>
199               I.MOVE{mvOp=mvOp, src=operand(tmpR, src), dst=operand(tmpR, dst)})               I.MOVE{mvOp=mvOp, src=operand(t, src), dst=operand(t, dst)}, an)
200       | I.MOVE{mvOp, src, dst} =>       | I.MOVE{mvOp, src, dst} =>
201          withTmp          withTmp
202           (fn tmpR =>           (fn t =>
203              I.MOVE{mvOp=mvOp, src=operand(tmpR, src), dst=operand(tmpR, dst)})              I.MOVE{mvOp=mvOp, src=operand(t, src), dst=operand(t, dst)}, an)
204       | I.LEA{r32, addr} =>       | I.LEA{r32, addr} =>
205          withTmp(fn tmpR => I.LEA{r32=r32, addr=operand(tmpR, addr)})          withTmp'(fn tmpR => I.LEA{r32=r32, addr=operand(tmpR, addr)}, an)
206       | I.CMP{lsrc, rsrc} =>       | I.CMP{lsrc, rsrc} =>
207          withTmp(fn tmpR => I.CMP{lsrc=operand(tmpR, lsrc), rsrc=operand(tmpR, rsrc)})          withTmp(fn tmpR =>
208              I.CMP{lsrc=operand(tmpR, lsrc), rsrc=operand(tmpR, rsrc)}, an)
209       | I.BINARY{binOp, src, dst as I.Direct _} =>       | I.BINARY{binOp, src, dst as I.Direct _} =>
210          withTmp(fn tmpR => I.BINARY{binOp=binOp, src=operand(tmpR, src), dst=dst})          withTmp(fn tmpR =>
211                I.BINARY{binOp=binOp, src=operand(tmpR, src), dst=dst}, an)
212       | I.BINARY{binOp, src, dst} =>       | I.BINARY{binOp, src, dst} =>
213          withTmp          withTmp(fn tmpR => I.BINARY{binOp=binOp, src=operand(tmpR, src),
214           (fn tmpR =>                                                   dst=operand(tmpR, dst)}, an)
             I.BINARY{binOp=binOp, src=operand(tmpR, src), dst=operand(tmpR,dst)})  
215       | I.MULTDIV{multDivOp, src} =>       | I.MULTDIV{multDivOp, src} =>
216          withTmp(fn tmpR => I.MULTDIV{multDivOp=multDivOp, src=operand(tmpR, src)})          withTmp(fn tmpR =>
217                I.MULTDIV{multDivOp=multDivOp, src=operand(tmpR, src)}, an)
218       | I.MUL3{src1, src2, dst} =>       | I.MUL3{src1, src2, dst} =>
219          withTmp(fn tmpR =>          withTmp(fn tmpR =>
220            I.MUL3{src1=operand(tmpR, src1), src2=src2,            I.MUL3{src1=operand(tmpR, src1), src2=src2,
221                   dst=if dst = reg then error "reload:MUL3" else dst})                   dst=if regmap dst = reg then error "reload:MUL3" else dst}, an)
222       | I.UNARY{unOp, opnd} =>       | I.UNARY{unOp, opnd} =>
223          withTmp(fn tmpR => I.UNARY{unOp=unOp, opnd=operand(tmpR, opnd)})          withTmp'(fn tmpR => I.UNARY{unOp=unOp, opnd=operand(tmpR, opnd)}, an)
224       | I.PUSH arg => withTmp(fn tmpR => I.PUSH(operand(tmpR, arg)))       | I.PUSH arg => withTmp(fn tmpR => I.PUSH(operand(tmpR, arg)), an)
225       | I.COPY _ => error "reload:COPY"       | I.COPY _ => error "reload:COPY"
226       | I.FILD opnd => withTmp(fn tmpR => I.FILD(operand(tmpR, opnd)))       | I.FILD opnd => withTmp'(fn tmpR => I.FILD(operand(tmpR, opnd)), an)
227       | I.FLD opnd =>       | I.FLD opnd => withTmp'(fn tmpR => I.FLD(operand(tmpR, opnd)), an)
228          withTmp (fn tmpR => I.FLD(operand(tmpR, opnd)))       | I.FSTP opnd => withTmp'(fn tmpR => I.FSTP(operand(tmpR, opnd)), an)
      | I.FSTP opnd =>  
         withTmp(fn tmpR => I.FSTP(operand(tmpR, opnd)))  
229       | I.FBINARY{binOp, src, dst} =>       | I.FBINARY{binOp, src, dst} =>
230          withTmp(fn tmpR =>          withTmp'(fn tmpR =>
231                    I.FBINARY{binOp=binOp, src=operand(tmpR, src), dst=dst})                   I.FBINARY{binOp=binOp, src=operand(tmpR, src), dst=dst}, an)
232    
233         | I.ANNOTATION{i,a} => reloadIt(i, a::an)
234       | _ => error "reload"       | _ => error "reload"
235      in reloadIt(instr, [])
236    end (*reload*)    end (*reload*)
237    
238    fun fspill(instr, reg, spillLoc) =    fun fspill(instr, regmap, reg, spillLoc) =
239      (case instr    let fun spillIt(instr, an) =
240        of I.FSTP _ => {proh=[], instr=NONE, code=[I.FSTP spillLoc]}        (case instr of
241             I.FSTP _ => {proh=[], code=[mark(I.FSTP spillLoc, an)], newReg=NONE}
242           | I.CALL(opnd, defs, uses, mem) =>
243             {proh=[],
244              code=[mark(I.CALL(opnd, C.rmvFreg(reg,defs), uses, mem), an)],
245              newReg=NONE}
246           | I.ANNOTATION{i,a} => spillIt(i, a::an)
247         | _ => error "fspill"         | _ => error "fspill"
248      (*esac*))      (*esac*))
249      in  spillIt(instr, [])
250      end (* fspill *)
251    
252    fun freload(instr, reg, spillLoc) =    fun freload(instr, regmap, reg, spillLoc) =
253      (case instr    let fun reloadIt(instr, an) =
254        of I.FLD opnd => {code=[I.FLD spillLoc], proh=[]}        (case instr of
255             I.FLD opnd => {code=[mark(I.FLD spillLoc, an)], proh=[], newReg=NONE}
256         | I.FBINARY{binOp, src=I.FDirect f, dst} =>         | I.FBINARY{binOp, src=I.FDirect f, dst} =>
257             if f = reg then             if regmap f = reg then
258               {code=[I.FBINARY{binOp=binOp, src=spillLoc, dst=dst}],               {code=[mark(I.FBINARY{binOp=binOp, src=spillLoc, dst=dst}, an)],
259                proh=[]}                proh=[],
260                  newReg=NONE}
261             else error "freload:FBINARY"             else error "freload:FBINARY"
262           | I.CALL(opnd, defs, uses, mem) =>
263             {proh=[],
264              code=[mark(I.CALL(opnd, C.rmvFreg(reg,defs), uses, mem), an)],
265              newReg=NONE}
266           | I.ANNOTATION{i,a} => reloadIt(i, a::an)
267         | _  => error "freload"         | _  => error "freload"
268      (*esac*))      (*esac*))
269      in  reloadIt(instr, [])
270      end (* freload *)
271    
272  end  end

Legend:
Removed from v.247  
changed lines
  Added in v.498

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