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 /MLRISC/releases/release-110.64/ra/ra-spill.sml
ViewVC logotype

Diff of /MLRISC/releases/release-110.64/ra/ra-spill.sml

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

revision 475, Wed Nov 10 22:59:58 1999 UTC revision 498, Tue Dec 7 15:44:50 1999 UTC
# Line 7  Line 7 
7   *   *
8   * The new code does things slightly differently.   * The new code does things slightly differently.
9   * Here, we are given an instruction and a list of registers to spill   * Here, we are given an instruction and a list of registers to spill
10   * and reload.  We write the instruction until all instances of these   * and reload.  We rewrite the instruction until all instances of these
11   * registers are rewritten.   * registers are rewritten.
12   *   *
13   * -- Allen   * -- Allen
14   *)   *)
15  functor RASpill(InsnProps : INSN_PROPERTIES) : RA_SPILL =  functor RASpill(structure InsnProps : INSN_PROPERTIES
16                    structure Asm       : INSTRUCTION_EMITTER
17                      sharing InsnProps.I = Asm.I
18                   ) : RA_SPILL =
19  struct  struct
20    
21     structure I      = InsnProps.I     structure I      = InsnProps.I
# Line 24  Line 27 
27    
28     fun error msg = MLRiscErrorMsg.error("RASpill",msg)     fun error msg = MLRiscErrorMsg.error("RASpill",msg)
29    
30       fun dec n = Word.toIntX(Word.fromInt n - 0w1)
31    
32     type copyInstr =     type copyInstr =
33            (C.cell list * C.cell list) * I.instruction -> I.instruction            (C.cell list * C.cell list) * I.instruction -> I.instruction list
34    
35       (*
36        * Spill the value associated with reg into spillLoc.
37        * All definitions of instr should be renamed to a new temporary newReg.
38        *)
39     type spill =     type spill =
40        {instr    : I.instruction,       (* instruction where spill is to occur *)        {instr    : I.instruction,       (* instruction where spill is to occur *)
41         reg      : C.cell,              (* register to spill *)         reg      : C.cell,              (* register to spill *)
42         spillLoc : int,                 (* logical spill location *)         spillLoc : int,                 (* logical spill location *)
        graph    : RAGraph.interferenceGraph, (* the current graph *)  
43         kill     : bool,                (* can we kill the current node? *)         kill     : bool,                (* can we kill the current node? *)
44         regmap   : C.cell -> C.cell,    (* current register map *)         regmap   : C.cell -> C.cell,    (* current register map *)
45         annotations : Annotations.annotations ref (* annotations *)         annotations : Annotations.annotations ref (* annotations *)
46        } ->        } ->
47        {code     : I.instruction list,  (* spill code *)        {code     : I.instruction list,  (* instruction + spill code *)
48         proh     : C.cell list,         (* prohibited from future spilling *)         proh     : C.cell list,         (* prohibited from future spilling *)
49         instr    : I.instruction option (* possibly changed instruction *)         newReg   : C.cell option        (* the spilled value is available here *)
50        }        }
51    
52       (* Spill the register src into spillLoc.
53        * The value is originally from register reg.
54        *)
55       type spillSrc =
56          {src      : C.cell,              (* register to spill from *)
57           reg      : C.cell,              (* the register *)
58           spillLoc : int,                 (* logical spill location *)
59           annotations : Annotations.annotations ref (* annotations *)
60          } -> I.instruction list          (* spill code *)
61    
62       (*
63        * Spill the temporary associated with a copy into spillLoc
64        *)
65       type spillCopyTmp =
66          {copy     : I.instruction,       (* copy to spill *)
67           spillLoc : int,                 (* logical spill location *)
68           annotations : Annotations.annotations ref (* annotations *)
69          } -> I.instruction               (* spill code *)
70    
71       (*
72        * Reload the value associated with reg from spillLoc.
73        * All uses of instr should be renamed to a new temporary newReg.
74        *)
75     type reload =     type reload =
76        {instr    : I.instruction,       (* instruction where spill is to occur *)        {instr    : I.instruction,       (* instruction where spill is to occur *)
77         reg      : C.cell,              (* register to spill *)         reg      : C.cell,              (* register to spill *)
78         spillLoc : int,                 (* logical spill location *)         spillLoc : int,                 (* logical spill location *)
        graph    : RAGraph.interferenceGraph, (* the current graph *)  
79         regmap   : C.cell -> C.cell,    (* current register map *)         regmap   : C.cell -> C.cell,    (* current register map *)
80         annotations : Annotations.annotations ref (* annotations *)         annotations : Annotations.annotations ref (* annotations *)
81        } ->        } ->
82        {code     : I.instruction list,  (* reload code *)        {code     : I.instruction list,  (* instr + reload code *)
83         proh     : C.cell list          (* prohibited from future spilling *)         proh     : C.cell list,         (* prohibited from future spilling *)
84           newReg   : C.cell option        (* the reloaded value is here *)
85          }
86    
87       (*
88        * Rename all uses fromSrc to toSrc
89        *)
90       type renameSrc =
91          {instr    : I.instruction,       (* instruction where spill is to occur *)
92           fromSrc  : C.cell,              (* register to rename *)
93           toSrc    : C.cell,              (* register to rename to *)
94           regmap   : C.cell -> C.cell     (* current register map *)
95          } ->
96          {code     : I.instruction list,  (* renamed instr *)
97           proh     : C.cell list,         (* prohibited from future spilling *)
98           newReg   : C.cell option        (* the renamed value is here *)
99        }        }
100    
101       (* Reload the register dst from spillLoc.
102        * The value is originally from register reg.
103        *)
104       type reloadDst =
105          {dst      : C.cell,              (* register to reload to *)
106           reg      : C.cell,              (* the register *)
107           spillLoc : int,                 (* logical spill location *)
108           annotations : Annotations.annotations ref (* annotations *)
109          } -> I.instruction list          (* reload code *)
110    
111     (*     (*
112      * The following function performs spilling.      * The following function performs spilling.
113      *)      *)
114     fun spillRewrite     fun spillRewrite
115          {graph=G as G.GRAPH{showReg, spilledRegs, nodes,...},          {graph=G as G.GRAPH{showReg, spilledRegs, nodes,...},
116           spill, reload, copyInstr, cellkind} =           spill : spill,
117             spillCopyTmp : spillCopyTmp,
118             spillSrc : spillSrc,
119             renameSrc : renameSrc,
120             reload : reload,
121             reloadDst : reloadDst,
122             copyInstr : copyInstr,
123             cellkind,
124             spillSet, reloadSet, killSet
125            } =
126     let     let
127         val regmap = Core.spillRegmap G (* This is the current regmap *)         val regmap = Core.spillRegmap G (* This is the current regmap *)
128         val spillLocOf = Core.spillLoc G         val spillLocOf = Core.spillLoc G
# Line 70  Line 134 
134         val enterSpill = Intmap.add spilledRegs         val enterSpill = Intmap.add spilledRegs
135         val addProh = app (fn r => enterSpill(r,true))         val addProh = app (fn r => enterSpill(r,true))
136    
137         fun add(NONE,l) = l         val getSpills  : int -> C.cell list = Intmap.mapWithDefault(spillSet,[])
138           | add(SOME i,l) = i::l         val getReloads : int -> C.cell list = Intmap.mapWithDefault(reloadSet,[])
139           val getKills   : int -> C.cell list = Intmap.mapWithDefault(killSet,[])
140    
141         fun getLoc(G.NODE{color=ref(G.ALIASED n), ...}) = getLoc n         fun getLoc(G.NODE{color=ref(G.ALIASED n), ...}) = getLoc n
142           | getLoc(G.NODE{color=ref(G.SPILLED ~1), number, ...}) = number           | getLoc(G.NODE{color=ref(G.SPILLED ~1), number, ...}) = number
# Line 80  Line 144 
144           | getLoc(G.NODE{number, ...}) = number           | getLoc(G.NODE{number, ...}) = number
145    
146         (*         (*
147            * Rewrite the instruction given that a bunch of registers have
148            * to be spilled and reloaded.
149            *)
150           fun spillRewrite{pt, instrs, annotations} =
151           let
152               (*
153          * Insert reloading code for an instruction.          * Insert reloading code for an instruction.
154          * Note: reload code goes after the instruction, if any.          * Note: reload code goes after the instruction, if any.
155          *)          *)
156         fun reloadInstr(instr,spillReg,spillLoc,annotations) =             fun reloadInstr(instr,regToSpill,spillLoc) =
157         let val {code,proh} =             let val {code, proh, newReg} =
158                reload{regmap=regmap,instr=instr,reg=spillReg,                    reload{regmap=regmap,instr=instr,reg=regToSpill,
159                       spillLoc=spillLoc,graph=G,annotations=annotations}                           spillLoc=spillLoc,annotations=annotations}
160               in  addProh(proh);
161                   code
162               end
163    
164               (*
165                * Renaming the source for an instruction.
166                *)
167               fun renameInstr(instr,regToSpill,toSrc) =
168               let val {code, proh, newReg} =
169                      renameSrc{regmap=regmap,instr=instr,
170                                fromSrc=regToSpill,toSrc=toSrc}
171         in  addProh(proh);         in  addProh(proh);
172             code             code
173         end         end
174    
175         (*         (*
176          * Remove uses of spillReg from a set of parallel copies.              * Remove uses of regToSpill from a set of parallel copies.
177          * If there are multiple uses, then return multiple moves.          * If there are multiple uses, then return multiple moves.
178          *)          *)
179         fun extractUses(spillReg, rds, rss) =             fun extractUses(regToSpill, rds, rss) =
180         let fun loop(rd::rds, rs::rss, newMvs, rds', rss') =             let fun loop(rd::rds, rs::rss, newRds, rds', rss') =
181                 if regmap rs = spillReg then                     if regmap rs = regToSpill then
182                    loop(rds, rss, ([rd], [rs])::newMvs, rds', rss')                        loop(rds, rss, rd::newRds, rds', rss')
183                 else                 else
184                    loop(rds, rss, newMvs, rd::rds', rs::rss')                        loop(rds, rss, newRds, rd::rds', rs::rss')
185               | loop(_, _, newMvs, rds', rss') = (newMvs, rds', rss')                   | loop(_, _, newRds, rds', rss') = (newRds, rds', rss')
186         in loop(rds, rss, [], [], []) end         in loop(rds, rss, [], [], []) end
187    
188         (*         (*
# Line 114  Line 195 
195          *    reload copies          *    reload copies
196          *          *
197          *)          *)
198         fun reloadCopySrc(instr,dst,src,spillReg,spillLoc,annotations) =             fun reloadCopySrc(instr,regToSpill,spillLoc) =
199         let val (mvs, copyDst, copySrc) = extractUses(spillReg, dst, src)             let val (dst, src) = P.moveDstSrc instr
200                   val (rds, copyDst, copySrc) = extractUses(regToSpill, dst, src)
201             fun processMoves([], reloadCode) = reloadCode             fun processMoves([], reloadCode) = reloadCode
202               | processMoves(mv::mvs, reloadCode) =                   | processMoves(rd::rds, reloadCode) =
203                 let val mv = copyInstr(mv, instr)                     let val code =
204                     val {code, proh} =                         reloadDst{spillLoc=spillLoc,reg=regToSpill,
205                       reload{regmap=regmap,instr=mv,spillLoc=spillLoc,                                   dst=rd,annotations=annotations}
206                              graph=G,reg=spillReg,annotations=annotations}                     in  processMoves(rds, code@reloadCode)
                in  addProh(proh);  
                    processMoves(mvs, code@reloadCode)  
207                 end                 end
208             val reloadCode = processMoves(mvs, [])                 val reloadCode = processMoves(rds, [])
209         in  case copyDst of         in  case copyDst of
210               [] => reloadCode               [] => reloadCode
211             | _  => copyInstr((copyDst, copySrc), instr)::reloadCode                 | _  => copyInstr((copyDst, copySrc), instr) @ reloadCode
212         end         end
213    
214         (*         (*
215          * Insert reload code          * Insert reload code
216          *)          *)
217         fun reload(instr,spillReg,spillLoc,annotations) =             fun reload(instr,regToSpill,spillLoc) =
218             if P.moveInstr instr then             if P.moveInstr instr then
219                let val (dst,src) = P.moveDstSrc instr                    reloadCopySrc(instr,regToSpill,spillLoc)
               in  case dst of  
                     [_] => reloadInstr(instr,spillReg,spillLoc,annotations)  
                   | _   => reloadCopySrc(instr,dst,src,spillReg,  
                                          spillLoc,annotations)  
               end  
220             else             else
221                reloadInstr(instr,spillReg,spillLoc,annotations)                    reloadInstr(instr,regToSpill,spillLoc)
222    
223         (*         (*
224          * Check whether the spillReg is in a list              * Check whether the regToSpill is in a list
225          *)          *)
226         fun killable(spillReg:int,[]) = false             fun killable(regToSpill:int,[]) = false
227           | killable(spillReg,r::rs) = r = spillReg orelse killable(spillReg,rs)               | killable(regToSpill,r::rs) =
228                   r = regToSpill orelse killable(regToSpill,rs)
229    
230         (*         (*
231          * Insert spill code for an instruction.          * Insert spill code for an instruction.
232          * Spill code occur after the instruction.          * Spill code occur after the instruction.
233          * If the value in spillReg is never used, the client also              * If the value in regToSpill is never used, the client also
234          * has the opportunity to remove the instruction.          * has the opportunity to remove the instruction.
235          *)          *)
236         fun spillInstr(instr,spillReg,spillLoc,annotations,kill) =             fun spillInstr(instr,regToSpill,spillLoc,kill) =
237         let val {code, instr, proh} =             let val {code, proh, newReg} =
238                spill{regmap=regmap, instr=instr,                spill{regmap=regmap, instr=instr,
239                      graph=G, kill=kill, spillLoc=spillLoc,                          kill=kill, spillLoc=spillLoc,
240                      reg=spillReg, annotations=annotations}                          reg=regToSpill, annotations=annotations}
241         in  addProh(proh);         in  addProh(proh);
242             add(instr,code)                 code
243         end         end
244    
245         (* Remove the definition spillReg <- from             (* Remove the definition regToSpill <- from
246          * parallel copies rds <- rss.          * parallel copies rds <- rss.
247          * Note, there is a guarantee that spillReg is not aliased              * Note, there is a guarantee that regToSpill is not aliased
248          * to another register in the rds set.          * to another register in the rds set.
249          *)          *)
250         fun extractDef(spillReg,rds,rss,kill) =             fun extractDef(regToSpill,rds,rss,kill) =
251         let fun loop(rd::rds, rs::rss, rds', rss') =         let fun loop(rd::rds, rs::rss, rds', rss') =
252                 if spillLocOf rd = spillLocOf rs then                 if spillLocOf rd = spillLocOf rs then
253                    ([rd], [rs], rds@rds', rss@rss', true)                        (rs, rds@rds', rss@rss', true)
254                 else if regmap rd = spillReg then                     else if regmap rd = regToSpill then
255                    ([rd], [rs], rds@rds', rss@rss', kill)                        (rs, rds@rds', rss@rss', kill)
256                 else loop(rds, rss, rd::rds', rs::rss')                 else loop(rds, rss, rd::rds', rs::rss')
257               | loop _ = error "extractDef"                   | loop _ =
258                         (print("rds=");
259                          app (fn r => print(Int.toString r^":"^
260                                             Int.toString(spillLocOf r)^" ")) rds;
261                          print("\nrss=");
262                          app (fn r => print(Int.toString r^":"^
263                                             Int.toString(spillLocOf r)^" ")) rss;
264                          print "\n";
265                          error("extractDef: "^Int.toString regToSpill))
266         in loop(rds, rss, [], []) end         in loop(rds, rss, [], []) end
267    
268         (*         (*
# Line 189  Line 273 
273          *    d1...dn/r <- s1...sn/r          *    d1...dn/r <- s1...sn/r
274          *          *
275          *)          *)
276         fun spillCopyDst(instr,spillReg,spillLoc,annotations,kill) =             fun spillCopyDst(instr,regToSpill,spillLoc,kill) =
277         let val (dst, src) = P.moveDstSrc instr         let val (dst, src) = P.moveDstSrc instr
278             val (mvDst,mvSrc,copyDst,copySrc,kill) =                 val (mvSrc,copyDst,copySrc,kill) =
279                  extractDef(spillReg,dst,src,kill)                      extractDef(regToSpill,dst,src,kill)
280             val copy = copyInstr((copyDst,copySrc),instr)                 val copy = case copyDst of
281                                [] => []
282                              | _  => copyInstr((copyDst,copySrc),instr)
283         in  if kill         in  if kill
284             then (* kill the move *)             then (* kill the move *)
285               ((* print ("Copy "^Int.toString(hd mvDst)^" <- "^               ((* print ("Copy "^Int.toString(hd mvDst)^" <- "^
286                               Int.toString(hd mvSrc)^" removed\n"); *)                               Int.toString(hd mvSrc)^" removed\n"); *)
287                [copy]                    copy
288               )               )
289             else (* normal spill *)             else (* normal spill *)
290             let val mvInstr = copyInstr((mvDst,mvSrc),instr)                 let  (* spill the move instruction *)
291                   (* spill the move instruction *)                     val spillCode = spillSrc{src=mvSrc,reg=regToSpill,
292                 val spillCode = spillInstr(mvInstr,spillReg,spillLoc,                                              spillLoc=spillLoc,
293                                            annotations,false)                                              annotations=annotations}
294             in  spillCode @ [copy]                 in  spillCode @ copy
295             end             end
296         end         end
297    
298         (*         (*
299          * Insert spill code for a copy          * Insert spill code for a copy
300          *)          *)
301         fun spillCopy(instr,spillReg,spillLoc,annotations,kill) =             fun spillCopy(instr,regToSpill,spillLoc,kill) =
302             case P.moveTmpR instr of             case P.moveTmpR instr of
303               NONE => spillCopyDst(instr,spillReg,spillLoc,annotations,kill)                   NONE => spillCopyDst(instr,regToSpill,spillLoc,kill)
304             | SOME tmp =>             | SOME tmp =>
305                 if regmap tmp = spillReg                     if regmap tmp = regToSpill
306                 then spillInstr(instr,spillReg,spillLoc,annotations,false)                     then [spillCopyTmp{copy=instr, spillLoc=spillLoc,
307                 else spillCopyDst(instr,spillReg,spillLoc,annotations,kill)                                        annotations=annotations}]
308                       else spillCopyDst(instr,regToSpill,spillLoc,kill)
309    
310         (*         (*
311          * Insert spill code          * Insert spill code
312          *)          *)
313         fun spill(instr,spillReg,spillLoc,annotations,killSet) =             fun spill(instr,regToSpill,spillLoc,killSet) =
314         let val kill = killable(spillReg,killSet)             let val kill = killable(regToSpill,killSet)
315         in  if P.moveInstr instr then         in  if P.moveInstr instr then
316                spillCopy(instr,spillReg,spillLoc,annotations,kill)                    spillCopy(instr,regToSpill,spillLoc,kill)
317             else             else
318                spillInstr(instr,spillReg,spillLoc,annotations,kill)                    spillInstr(instr,regToSpill,spillLoc,kill)
319         end         end
320    
321         (*             fun contains([],reg) = false
         * Rewrite the instruction given that a bunch of registers have  
         * to be spilled and reloaded.  
         *)  
        fun rewrite{spillRegs,reloadRegs,killRegs,instr,annotations} =  
        let fun contains([],reg) = false  
322               | contains(r::rs,reg) = regmap r = reg orelse contains(rs,reg)               | contains(r::rs,reg) = regmap r = reg orelse contains(rs,reg)
323             fun hasDef(i,reg) = contains(#1(insnDefUse i),reg)             fun hasDef(i,reg) = contains(#1(insnDefUse i),reg)
324             fun hasUse(i,reg) = contains(#2(insnDefUse i),reg)             fun hasUse(i,reg) = contains(#2(insnDefUse i),reg)
# Line 245  Line 327 
327               | spillOneReg(i::instrs,r,spillLoc,killSet) =               | spillOneReg(i::instrs,r,spillLoc,killSet) =
328                 if hasDef(i,r)                 if hasDef(i,r)
329                 then                 then
330                  spillOneReg(spill(i,r,spillLoc,annotations,killSet)@instrs,                  spillOneReg(spill(i,r,spillLoc,killSet)@instrs,
331                                    r,spillLoc,killSet)                                    r,spillLoc,killSet)
332                 else i::spillOneReg(instrs,r,spillLoc,killSet)                 else i::spillOneReg(instrs,r,spillLoc,killSet)
333    
334             fun reloadOneReg([],_,_) = []             fun reloadOneReg([],_,_) = []
335               | reloadOneReg(i::instrs,r,spillLoc) =               | reloadOneReg(i::instrs,r,spillLoc) =
336                 if hasUse(i,r)                 if hasUse(i,r)
337                 then reloadOneReg(reload(i,r,spillLoc,annotations)@instrs,                 then reloadOneReg(reload(i,r,spillLoc)@instrs,
338                                   r,spillLoc)                                   r,spillLoc)
339                 else i::reloadOneReg(instrs,r,spillLoc)                 else i::reloadOneReg(instrs,r,spillLoc)
340    
# Line 273  Line 355 
355                 in  reloadAll(reloadOneReg(instrs,r,spillLoc),rs)                 in  reloadAll(reloadOneReg(instrs,r,spillLoc),rs)
356                 end                 end
357    
358               fun loop([], pt, newInstrs) = newInstrs
359                 | loop(instr::rest, pt, newInstrs) =
360                   let val spillRegs = getSpills pt
361                       val reloadRegs = getReloads pt
362                   in  case (spillRegs, reloadRegs) of
363                         ([], []) => loop(rest, dec pt, instr::newInstrs)
364                       | _ =>
365             (* Eliminate duplicates from the spill/reload candidates *)             (* Eliminate duplicates from the spill/reload candidates *)
366                         let val killRegs   = getKills pt
367             val spillRegs  = SL.uniq spillRegs             val spillRegs  = SL.uniq spillRegs
368             val reloadRegs = SL.uniq reloadRegs             val reloadRegs = SL.uniq reloadRegs
369    
370                             (*
371                             val Asm.S.STREAM{emit, ...} = Asm.makeStream[]
372                             val regs = app (fn r =>
373                                    print(Int.toString r^" ["^Int.toString
374                                              (getLoc (getnode r))^"] "))
375                              *)
376    
377             val instrs = spillAll([instr],spillRegs,killRegs)             val instrs = spillAll([instr],spillRegs,killRegs)
378    
379                             (*
380                             val _ =
381                                   (print("pt="^Int.toString pt^"\n");
382                                    if spillRegs = [] then () else
383                                       (print("Spilling ");
384                                        regs spillRegs; print "\n");
385                                    if reloadRegs = [] then () else
386                                       (print("Reloading ");
387                                        regs reloadRegs; print "\n");
388                                    print "Before:"; emit regmap instr)
389                              *)
390    
391             val instrs = reloadAll(instrs,reloadRegs)             val instrs = reloadAll(instrs,reloadRegs)
392         in  { code = instrs }  
393                             (*
394                             val _ =
395                                   (print "After:"; app (emit regmap) instrs;
396                                    print "------------------\n")
397                              *)
398                             fun concat([], l) = l
399                               | concat(a::b, l) = concat(b, a::l)
400                         in  loop(rest, dec pt, concat(instrs, newInstrs))
401                         end
402                    end
403           in  loop(rev instrs, pt, [])
404         end         end
405     in  rewrite     in  spillRewrite
406     end     end
407    
408  end  end

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

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