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 743, Thu Dec 7 15:31:24 2000 UTC revision 744, Fri Dec 8 04:11:42 2000 UTC
# Line 47  Line 47 
47   *   *
48   * -- Allen   * -- Allen
49   *)   *)
50  functor RASpill(structure InsnProps : INSN_PROPERTIES  
51    local
52    
53       val debug = false
54    
55    in
56    
57    functor RASpill
58       (structure InsnProps : INSN_PROPERTIES
59                  structure Asm       : INSTRUCTION_EMITTER                  structure Asm       : INSTRUCTION_EMITTER
60                    sharing InsnProps.I = Asm.I                    sharing InsnProps.I = Asm.I
61                 ) : RA_SPILL =                 ) : RA_SPILL =
# Line 56  Line 64 
64     structure I      = InsnProps.I     structure I      = InsnProps.I
65     structure P      = InsnProps     structure P      = InsnProps
66     structure C      = I.C     structure C      = I.C
    structure G      = RAGraph  
67     structure Core   = RACore     structure Core   = RACore
68     structure SL     = SortedList     structure G      = Core.G
69    
70     fun error msg = MLRiscErrorMsg.error("RASpill",msg)     fun error msg = MLRiscErrorMsg.error("RASpill",msg)
71    
72     fun dec n = Word.toIntX(Word.fromInt n - 0w1)     fun dec n = Word.toIntX(Word.fromInt n - 0w1)
73    
74     type copyInstr =     structure T = RASpillTypes(I)
75            (C.cell list * C.cell list) * I.instruction -> I.instruction list     open T
76    
77     (*     fun uniq s = C.SortedCells.return(C.SortedCells.uniq s)
78      * Spill the value associated with reg into spillLoc.     val i2s    = Int.toString
79      * All definitions of instr should be renamed to a new temporary newReg.  
80      *)     val Asm.S.STREAM{emit, ...} = Asm.makeStream[]
    type spill =  
       {instr    : I.instruction,       (* instruction where spill is to occur *)  
        reg      : C.cell,              (* register to spill *)  
        spillLoc : int,                 (* logical spill location *)  
        kill     : bool,                (* can we kill the current node? *)  
        regmap   : C.cell -> C.cell,    (* current register map *)  
        annotations : Annotations.annotations ref (* annotations *)  
       } ->  
       {code     : I.instruction list,  (* instruction + spill code *)  
        proh     : C.cell list,         (* prohibited from future spilling *)  
        newReg   : C.cell option        (* the spilled value is available here *)  
       }  
   
    (* Spill the register src into spillLoc.  
     * The value is originally from register reg.  
     *)  
    type spillSrc =  
       {src      : C.cell,              (* register to spill from *)  
        reg      : C.cell,              (* the register *)  
        spillLoc : int,                 (* logical spill location *)  
        annotations : Annotations.annotations ref (* annotations *)  
       } -> I.instruction list          (* spill code *)  
   
    (*  
     * Spill the temporary associated with a copy into spillLoc  
     *)  
    type spillCopyTmp =  
       {copy     : I.instruction,       (* copy to spill *)  
        spillLoc : int,                 (* logical spill location *)  
        annotations : Annotations.annotations ref (* annotations *)  
       } -> I.instruction               (* spill code *)  
   
    (*  
     * Reload the value associated with reg from spillLoc.  
     * All uses of instr should be renamed to a new temporary newReg.  
     *)  
    type reload =  
       {instr    : I.instruction,       (* instruction where spill is to occur *)  
        reg      : C.cell,              (* register to spill *)  
        spillLoc : int,                 (* logical spill location *)  
        regmap   : C.cell -> C.cell,    (* current register map *)  
        annotations : Annotations.annotations ref (* annotations *)  
       } ->  
       {code     : I.instruction list,  (* instr + reload code *)  
        proh     : C.cell list,         (* prohibited from future spilling *)  
        newReg   : C.cell option        (* the reloaded value is here *)  
       }  
   
    (*  
     * Rename all uses fromSrc to toSrc  
     *)  
    type renameSrc =  
       {instr    : I.instruction,       (* instruction where spill is to occur *)  
        fromSrc  : C.cell,              (* register to rename *)  
        toSrc    : C.cell,              (* register to rename to *)  
        regmap   : C.cell -> C.cell     (* current register map *)  
       } ->  
       {code     : I.instruction list,  (* renamed instr *)  
        proh     : C.cell list,         (* prohibited from future spilling *)  
        newReg   : C.cell option        (* the renamed value is here *)  
       }  
   
    (* Reload the register dst from spillLoc.  
     * The value is originally from register reg.  
     *)  
    type reloadDst =  
       {dst      : C.cell,              (* register to reload to *)  
        reg      : C.cell,              (* the register *)  
        spillLoc : int,                 (* logical spill location *)  
        annotations : Annotations.annotations ref (* annotations *)  
       } -> I.instruction list          (* reload code *)  
81    
82     (* val spilledCopyTmps = MLRiscControl.getCounter "ra-spilled-copy-temps" *)     (* val spilledCopyTmps = MLRiscControl.getCounter "ra-spilled-copy-temps" *)
83    
# Line 161  Line 97 
97           spillSet, reloadSet, killSet           spillSet, reloadSet, killSet
98          } =          } =
99     let     let
100         val regmap = Core.spillRegmap G (* This is the current regmap *)         (* Must do this to make sure the interference graph is
101         val spillLocOf = Core.spillLoc G          * reflected to the cells
102            *)
103           val _ = Core.updateCellAliases G
104    
105           val getSpillLoc = Core.spillLoc G
106           fun spillLocOf(C.CELL{id, ...}) = getSpillLoc id
107         val spillLocsOf = map spillLocOf         val spillLocsOf = map spillLocOf
108         val getnode = IntHashTable.lookup nodes         val getnode = IntHashTable.lookup nodes
109           val getnode = fn C.CELL{id, ...} => getnode id
110    
111         val insnDefUse = P.defUse cellkind         val insnDefUse = P.defUse cellkind
112    
113         (* Merge prohibited registers *)         (* Merge prohibited registers *)
114         val enterSpill = IntHashTable.insert spilledRegs         val enterSpill = IntHashTable.insert spilledRegs
115         val addProh = app (fn r => enterSpill(r,true))         val addProh = app (fn c => enterSpill(C.registerId c,true))
116    
117         val getSpills  : int -> C.cell list =         val getSpills  = G.PPtHashTable.find spillSet
118             fn i => getOpt (IntHashTable.find spillSet i, [])         val getSpills  = fn p => case getSpills p of SOME s => s | NONE => []
119         val getReloads : int -> C.cell list =         val getReloads = G.PPtHashTable.find reloadSet
120             fn i => getOpt (IntHashTable.find reloadSet i, [])         val getReloads = fn p => case getReloads p of SOME s => s | NONE => []
121         val getKills   : int -> C.cell list =         val getKills   = G.PPtHashTable.find killSet
122             fn i => getOpt (IntHashTable.find killSet i, [])         val getKills   = fn p => case getKills p of SOME s => s | NONE => []
123    
124         fun getLoc(G.NODE{color=ref(G.ALIASED n), ...}) = getLoc n         fun getLoc(G.NODE{color=ref(G.ALIASED n), ...}) = getLoc n
125           | getLoc(G.NODE{color=ref(G.SPILLED), number, ...}) = number           | getLoc(G.NODE{color=ref(G.MEMREG(_, m)), ...}) = G.MEM_REG m
126           | getLoc(G.NODE{color=ref(G.MEMREG m), ...}) = m           | getLoc(G.NODE{color=ref(G.SPILL_LOC s), ...}) = G.FRAME s
127           | getLoc(G.NODE{color=ref(G.SPILL_LOC s), ...}) = ~s           | getLoc(G.NODE{color=ref(G.SPILLED), number, ...}) = G.FRAME number
128           | getLoc(G.NODE{number, ...}) = number           | getLoc(G.NODE{color=ref(G.PSEUDO), number, ...}) = G.FRAME number
129             | getLoc _ = error "getLoc"
130    
131           fun printRegs regs =
132               app (fn r => print(C.toString r^" ["^
133                                  Core.spillLocToString G (C.cellId r)^"] ")) regs
134    
135           val parallelCopies = Word.andb(Core.HAS_PARALLEL_COPIES, mode) <> 0w0
136    
137           fun chase(C.CELL{col=ref(C.ALIASED c), ...}) = chase c
138             | chase c = c
139    
140           fun cellId(C.CELL{id, ...}) = id
141    
142           fun sameCell(C.CELL{id=x,...}, C.CELL{id=y, ...}) = x=y
143    
144           fun same(x,regToSpill) = sameCell(chase x,regToSpill)
145    
        val parallelCopies = Word.andb(RACore.HAS_PARALLEL_COPIES, mode) <> 0w0  
146         (*         (*
147          * Rewrite the instruction given that a bunch of registers have          * Rewrite the instruction given that a bunch of registers have
148          * to be spilled and reloaded.          * to be spilled and reloaded.
# Line 198  Line 155 
155              *)              *)
156             fun reloadInstr(instr,regToSpill,spillLoc) =             fun reloadInstr(instr,regToSpill,spillLoc) =
157             let val {code, proh, newReg} =             let val {code, proh, newReg} =
158                    reload{regmap=regmap,instr=instr,reg=regToSpill,                    reload{instr=instr,reg=regToSpill,
159                           spillLoc=spillLoc,annotations=annotations}                           spillLoc=spillLoc,annotations=annotations}
160             in  addProh(proh);             in  addProh(proh);
161                 code                 code
# Line 209  Line 166 
166              *)              *)
167             fun renameInstr(instr,regToSpill,toSrc) =             fun renameInstr(instr,regToSpill,toSrc) =
168             let val {code, proh, newReg} =             let val {code, proh, newReg} =
169                    renameSrc{regmap=regmap,instr=instr,                    renameSrc{instr=instr, fromSrc=regToSpill,toSrc=toSrc}
                             fromSrc=regToSpill,toSrc=toSrc}  
170             in  addProh(proh);             in  addProh(proh);
171                 code                 code
172             end             end
# Line 221  Line 177 
177              *)              *)
178             fun extractUses(regToSpill, rds, rss) =             fun extractUses(regToSpill, rds, rss) =
179             let fun loop(rd::rds, rs::rss, newRds, rds', rss') =             let fun loop(rd::rds, rs::rss, newRds, rds', rss') =
180                     if regmap rs = regToSpill then                     if same(rs,regToSpill) then
181                        loop(rds, rss, rd::newRds, rds', rss')                        loop(rds, rss, rd::newRds, rds', rss')
182                     else                     else
183                        loop(rds, rss, newRds, rd::rds', rs::rss')                        loop(rds, rss, newRds, rd::rds', rs::rss')
# Line 264  Line 220 
220                    reloadInstr(instr,regToSpill,spillLoc)                    reloadInstr(instr,regToSpill,spillLoc)
221    
222             (*             (*
223              * Check whether the regToSpill is in a list              * Check whether the id is in a list
224              *)              *)
225             fun contains(regToSpill:int,[]) = false             fun containsId(id,[]) = false
226               | contains(regToSpill,r::rs) =               | containsId(id:C.cell_id,r::rs) = r = id orelse containsId(id,rs)
227                 r = regToSpill orelse contains(regToSpill,rs)             fun spillConflict(G.FRAME loc, rs) = containsId(~loc, rs)
228                 | spillConflict(G.MEM_REG(C.CELL{id, ...}), rs) =
229                     containsId(id, rs)
230    
231               fun contains(r',[]) = false
232                 | contains(r',r::rs) = sameCell(r',r) orelse contains(r',rs)
233    
234             (*             (*
235              * Insert spill code for an instruction.              * Insert spill code for an instruction.
# Line 278  Line 239 
239              *)              *)
240             fun spillInstr(instr,regToSpill,spillLoc,kill) =             fun spillInstr(instr,regToSpill,spillLoc,kill) =
241             let val {code, proh, newReg} =             let val {code, proh, newReg} =
242                    spill{regmap=regmap, instr=instr,                    spill{instr=instr,
243                          kill=kill, spillLoc=spillLoc,                          kill=kill, spillLoc=spillLoc,
244                          reg=regToSpill, annotations=annotations}                          reg=regToSpill, annotations=annotations}
245             in  addProh(proh);             in  addProh(proh);
# Line 294  Line 255 
255             let fun loop(rd::rds, rs::rss, rds', rss') =             let fun loop(rd::rds, rs::rss, rds', rss') =
256                     if spillLocOf rd = spillLocOf rs then                     if spillLocOf rd = spillLocOf rs then
257                        (rs, rds@rds', rss@rss', true)                        (rs, rds@rds', rss@rss', true)
258                     else if regmap rd = regToSpill then                     else if same(rd, regToSpill) then
259                        (rs, rds@rds', rss@rss', kill)                        (rs, rds@rds', rss@rss', kill)
260                     else loop(rds, rss, rd::rds', rs::rss')                     else loop(rds, rss, rd::rds', rs::rss')
261                   | loop _ =                   | loop _ =
262                       (print("rds=");                       (print("rds=");
263                        app (fn r => print(Int.toString r^":"^                        app (fn r => print(C.toString r^":"^
264                                           Int.toString(spillLocOf r)^" ")) rds;                                           i2s(spillLocOf r)^" ")) rds;
265                        print("\nrss=");                        print("\nrss=");
266                        app (fn r => print(Int.toString r^":"^                        app (fn r => print(C.toString r^":"^
267                                           Int.toString(spillLocOf r)^" ")) rss;                                           i2s(spillLocOf r)^" ")) rss;
268                        print "\n";                        print "\n";
269                        error("extractDef: "^Int.toString regToSpill))                        error("extractDef: "^C.toString regToSpill))
270             in loop(rds, rss, [], []) end             in loop(rds, rss, [], []) end
271    
272             (*             (*
# Line 341  Line 302 
302                    copy                    copy
303                   )                   )
304                 else (* normal spill *)                 else (* normal spill *)
305                   if contains(spillLoc, don'tOverwrite) then                   if spillConflict(spillLoc, don'tOverwrite) then
306                   let (* cycle found *)                   let (* cycle found *)
307                       (*val _ = print("Register r"^Int.toString regToSpill^                       (*val _ = print("Register r"^Int.toString regToSpill^
308                                    " overwrites ["^Int.toString spillLoc^"]\n")*)                                    " overwrites ["^Int.toString spillLoc^"]\n")*)
309                       val tmp = I.C.newCell cellkind () (* new temporary *)                       val tmp = I.C.newVar regToSpill (* new temporary *)
310                       val copy = copyInstr((tmp::copyDst, mvSrc::copySrc),                       val copy = copyInstr((tmp::copyDst, mvSrc::copySrc),
311                                                 instr)                                                 instr)
312                       val spillCode = spillSrc{src=tmp,reg=regToSpill,                       val spillCode = spillSrc{src=tmp,reg=regToSpill,
# Line 370  Line 331 
331                   NONE => spillCopyDst(instr,regToSpill,spillLoc,kill,                   NONE => spillCopyDst(instr,regToSpill,spillLoc,kill,
332                                        don'tOverwrite)                                        don'tOverwrite)
333                 | SOME tmp =>                 | SOME tmp =>
334                     if regmap tmp = regToSpill                     if same(tmp, regToSpill)
335                     then ((* spilledCopyTmps := !spilledCopyTmps + 1; *)                     then ((* spilledCopyTmps := !spilledCopyTmps + 1; *)
336                           [spillCopyTmp{copy=instr, spillLoc=spillLoc,                           [spillCopyTmp{copy=instr, spillLoc=spillLoc,
337                                        annotations=annotations}])                                        annotations=annotations}])
# Line 389  Line 350 
350             end             end
351    
352             fun contains([],reg) = false             fun contains([],reg) = false
353               | contains(r::rs,reg) = regmap r = reg orelse contains(rs,reg)               | contains(r::rs,reg) = same(r,reg) orelse contains(rs,reg)
354             fun hasDef(i,reg) = contains(#1(insnDefUse i),reg)             fun hasDef(i,reg) = contains(#1(insnDefUse i),reg)
355             fun hasUse(i,reg) = contains(#2(insnDefUse i),reg)             fun hasUse(i,reg) = contains(#2(insnDefUse i),reg)
356    
# Line 435  Line 396 
396                     | _ =>                     | _ =>
397                       (* Eliminate duplicates from the spill/reload candidates *)                       (* Eliminate duplicates from the spill/reload candidates *)
398                       let val killRegs   = getKills pt                       let val killRegs   = getKills pt
399                           val spillRegs  = SL.uniq spillRegs                           val spillRegs  = uniq spillRegs
400                           val reloadRegs = SL.uniq reloadRegs                           val reloadRegs = uniq reloadRegs
401    
402                           (* spill locations that we can't overwrite if we                           (* spill locations that we can't overwrite if we
403                            * are spilling a parallel copy                            * are spilling a parallel copy
# Line 445  Line 406 
406                               if parallelCopies then spillLocsOf reloadRegs                               if parallelCopies then spillLocsOf reloadRegs
407                               else []                               else []
408    
                          (*  
                          val Asm.S.STREAM{emit, ...} = Asm.makeStream[]  
                          val regs = app (fn r =>  
                                 print(Int.toString(regmap r)^" ["^Int.toString  
                                           (getLoc (getnode r))^"] "))  
                           *)  
   
409                           val instrs = spillAll([instr],spillRegs,killRegs,                           val instrs = spillAll([instr],spillRegs,killRegs,
410                                                 don'tOverwrite)                                                 don'tOverwrite)
411    
412                           (*                           val _ = if debug then
413                           val _ =                                 (print("pt="^i2s pt^"\n");
414                                 (print("pt="^Int.toString pt^"\n");                                  case spillRegs of
415                                  if spillRegs = [] then () else                                    [] => ()
416                                     (print("Spilling ");                                  |  _ => (print("Spilling ");
417                                      regs spillRegs; print "\n");                                           printRegs spillRegs;
418                                  if reloadRegs = [] then () else                                           print "\n");
419                                     (print("Reloading ");                                  case reloadRegs of
420                                      regs reloadRegs; print "\n");                                    [] => ()
421                                  print "Before:"; emit regmap instr)                                  | _  => (print("Reloading ");
422                            *)                                           printRegs reloadRegs;
423                                             print "\n");
424                                    print "Before:"; emit instr
425                                   ) else ()
426    
427                           val instrs = reloadAll(instrs,reloadRegs)                           val instrs = reloadAll(instrs,reloadRegs)
428    
429                           (*                           val _ =  if debug then
430                           val _ =                                 (print "After:"; app emit instrs;
                                (print "After:"; app (emit regmap) instrs;  
431                                  print "------------------\n")                                  print "------------------\n")
432                            *)                                 else ()
433    
434                           fun concat([], l) = l                           fun concat([], l) = l
435                             | concat(a::b, l) = concat(b, a::l)                             | concat(a::b, l) = concat(b, a::l)
# Line 485  Line 441 
441     in  spillRewrite     in  spillRewrite
442     end     end
443  end  end
444    
445    end (* local *)

Legend:
Removed from v.743  
changed lines
  Added in v.744

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