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

Diff of /sml/trunk/src/MLRISC/ra/ra-spill.sml

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

revision 499, Tue Dec 7 15:44:50 1999 UTC revision 545, Thu Feb 24 13:56:44 2000 UTC
# Line 10  Line 10 
10   * and reload.  We rewrite 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     * (12/13/99) Some major caveats when spill coalescing/coloring is used:
14     * When parallel copies are generated and spill coalescing/coloring is used,
15     * two special cases have to be identified:
16     *
17     * Case 1 (spillLoc dst = spillLoc src)
18     *        Suppose we have a parallel copy
19     *             (u,v) <- (x,y)
20     *        where u has to be spilled and y has to reloaded.  When both
21     *        u and y are mapped to location M.  The following wrong code may
22     *        be generated:
23     *                M <- x  (spill u)
24     *                v <- M  (reload y)
25     *        This is incorrect.  Instead, we generate a dummy copy and
26     *        delay the spill after the reload, like this:
27     *
28     *               tmp <- x (save value of u)
29     *               v <- M   (reload y)
30     *               M <- tmp (spill u)
31     * Case 2 (spillLoc copyTmp = spillLoc src)
32     *        Another case that can cause problems is when the spill location of
33     *        the copy temporary is the same as that of one of the sources:
34     *
35     *              (a, b, v) <- (b, a, u)  where spillLoc(u) = spillLoc(tmp) = v
36     *
37     *        The incorrect code is
38     *              (a, b) <- (b, a)
39     *              v <- M
40     *        But then the shuffle code for the copy can clobber the location M.
41     *
42     *              tmp <- M
43     *              (a, b) <- (b, a)
44     *              v <- tmp
45     *
46     *       (Note that spillLoc copyTmp = spillLoc src can never happen)
47     *
48   * -- Allen   * -- Allen
49   *)   *)
50  functor RASpill(structure InsnProps : INSN_PROPERTIES  functor RASpill(structure InsnProps : INSN_PROPERTIES
# Line 108  Line 143 
143         annotations : Annotations.annotations ref (* annotations *)         annotations : Annotations.annotations ref (* annotations *)
144        } -> I.instruction list          (* reload code *)        } -> I.instruction list          (* reload code *)
145    
146       (* val spilledCopyTmps = MLRiscControl.getCounter "ra-spilled-copy-temps" *)
147    
148     (*     (*
149      * The following function performs spilling.      * The following function performs spilling.
150      *)      *)
151     fun spillRewrite     fun spillRewrite
152          {graph=G as G.GRAPH{showReg, spilledRegs, nodes,...},          {graph=G as G.GRAPH{showReg, spilledRegs, nodes, mode, ...},
153           spill : spill,           spill : spill,
154           spillCopyTmp : spillCopyTmp,           spillCopyTmp : spillCopyTmp,
155           spillSrc : spillSrc,           spillSrc : spillSrc,
# Line 126  Line 163 
163     let     let
164         val regmap = Core.spillRegmap G (* This is the current regmap *)         val regmap = Core.spillRegmap G (* This is the current regmap *)
165         val spillLocOf = Core.spillLoc G         val spillLocOf = Core.spillLoc G
166           val spillLocsOf = map spillLocOf
167         val getnode = Intmap.map nodes         val getnode = Intmap.map nodes
168    
169         val insnDefUse = P.defUse cellkind         val insnDefUse = P.defUse cellkind
# Line 143  Line 181 
181           | getLoc(G.NODE{color=ref(G.SPILLED c), ...}) = c           | getLoc(G.NODE{color=ref(G.SPILLED c), ...}) = c
182           | getLoc(G.NODE{number, ...}) = number           | getLoc(G.NODE{number, ...}) = number
183    
184           val parallelCopies = Word.andb(RACore.HAS_PARALLEL_COPIES, mode) <> 0w0
185         (*         (*
186          * Rewrite the instruction given that a bunch of registers have          * Rewrite the instruction given that a bunch of registers have
187          * to be spilled and reloaded.          * to be spilled and reloaded.
# Line 223  Line 262 
262             (*             (*
263              * Check whether the regToSpill is in a list              * Check whether the regToSpill is in a list
264              *)              *)
265             fun killable(regToSpill:int,[]) = false             fun contains(regToSpill:int,[]) = false
266               | killable(regToSpill,r::rs) =               | contains(regToSpill,r::rs) =
267                 r = regToSpill orelse killable(regToSpill,rs)                 r = regToSpill orelse contains(regToSpill,rs)
268    
269             (*             (*
270              * Insert spill code for an instruction.              * Insert spill code for an instruction.
# Line 267  Line 306 
306    
307             (*             (*
308              * Insert spill code for a destination of a copy              * Insert spill code for a destination of a copy
309                *    suppose d = r and we have a copy d <- s in
310                *    d1...dn <- s1...sn
311                *
312              *    d1...dn <- s1...sn              *    d1...dn <- s1...sn
313              * =>              * =>
314              *    spill code              *    spill s to spillLoc
315              *    d1...dn/r <- s1...sn/r              *    d1...dn/d <- s1...sn/s
316                *
317                *    However, if the spill code may ovewrite the spill location
318                *    shared by other uses, we do the following less
319                *    efficient scheme:
320                *
321                *    /* save the result of d */
322                *    d1...dn, tmp <- s1...sn, s
323                *    spill tmp to spillLoc /* spill d */
324              *              *
325              *)              *)
326             fun spillCopyDst(instr,regToSpill,spillLoc,kill) =             fun spillCopyDst(instr,regToSpill,spillLoc,kill,don'tOverwrite) =
327             let val (dst, src) = P.moveDstSrc instr             let val (dst, src) = P.moveDstSrc instr
328                 val (mvSrc,copyDst,copySrc,kill) =                 val (mvSrc,copyDst,copySrc,kill) =
329                      extractDef(regToSpill,dst,src,kill)                      extractDef(regToSpill,dst,src,kill)
# Line 287  Line 337 
337                    copy                    copy
338                   )                   )
339                 else (* normal spill *)                 else (* normal spill *)
340                     if contains(spillLoc, don'tOverwrite) then
341                     let (* cycle found *)
342                         (*val _ = print("Register r"^Int.toString regToSpill^
343                                      " overwrites ["^Int.toString spillLoc^"]\n")*)
344                         val tmp = I.C.newCell cellkind () (* new temporary *)
345                         val copy = copyInstr((tmp::copyDst, mvSrc::copySrc),
346                                                   instr)
347                         val spillCode = spillSrc{src=tmp,reg=regToSpill,
348                                                  spillLoc=spillLoc,
349                                                  annotations=annotations}
350                     in  copy @ spillCode
351                     end
352                     else
353                 let  (* spill the move instruction *)                 let  (* spill the move instruction *)
354                     val spillCode = spillSrc{src=mvSrc,reg=regToSpill,                     val spillCode = spillSrc{src=mvSrc,reg=regToSpill,
355                                              spillLoc=spillLoc,                                              spillLoc=spillLoc,
# Line 298  Line 361 
361             (*             (*
362              * Insert spill code for a copy              * Insert spill code for a copy
363              *)              *)
364             fun spillCopy(instr,regToSpill,spillLoc,kill) =             fun spillCopy(instr,regToSpill,spillLoc,kill,don'tOverwrite) =
365                 case P.moveTmpR instr of                 case P.moveTmpR instr of
366                   NONE => spillCopyDst(instr,regToSpill,spillLoc,kill)                   NONE => spillCopyDst(instr,regToSpill,spillLoc,kill,
367                                          don'tOverwrite)
368                 | SOME tmp =>                 | SOME tmp =>
369                     if regmap tmp = regToSpill                     if regmap tmp = regToSpill
370                     then [spillCopyTmp{copy=instr, spillLoc=spillLoc,                     then ((* spilledCopyTmps := !spilledCopyTmps + 1; *)
371                                        annotations=annotations}]                           [spillCopyTmp{copy=instr, spillLoc=spillLoc,
372                     else spillCopyDst(instr,regToSpill,spillLoc,kill)                                        annotations=annotations}])
373                       else spillCopyDst(instr,regToSpill,spillLoc,kill,
374                                          don'tOverwrite)
375    
376             (*             (*
377              * Insert spill code              * Insert spill code
378              *)              *)
379             fun spill(instr,regToSpill,spillLoc,killSet) =             fun spill(instr,regToSpill,spillLoc,killSet,don'tOverwrite) =
380             let val kill = killable(regToSpill,killSet)             let val kill = contains(regToSpill,killSet)
381             in  if P.moveInstr instr then             in  if P.moveInstr instr then
382                    spillCopy(instr,regToSpill,spillLoc,kill)                    spillCopy(instr,regToSpill,spillLoc,kill,don'tOverwrite)
383                 else                 else
384                    spillInstr(instr,regToSpill,spillLoc,kill)                    spillInstr(instr,regToSpill,spillLoc,kill)
385             end             end
# Line 323  Line 389 
389             fun hasDef(i,reg) = contains(#1(insnDefUse i),reg)             fun hasDef(i,reg) = contains(#1(insnDefUse i),reg)
390             fun hasUse(i,reg) = contains(#2(insnDefUse i),reg)             fun hasUse(i,reg) = contains(#2(insnDefUse i),reg)
391    
392             fun spillOneReg([],_,_,killSet) = []             fun spillOneReg([],_,_,_,_) = []
393               | spillOneReg(i::instrs,r,spillLoc,killSet) =               | spillOneReg(i::instrs,r,spillLoc,killSet,don'tOverwrite) =
394                 if hasDef(i,r)                 if hasDef(i,r)
395                 then                 then
396                  spillOneReg(spill(i,r,spillLoc,killSet)@instrs,                  spillOneReg(spill(i,r,spillLoc,killSet,don'tOverwrite)@instrs,
397                                    r,spillLoc,killSet)                                    r,spillLoc,killSet,don'tOverwrite)
398                 else i::spillOneReg(instrs,r,spillLoc,killSet)                 else i::spillOneReg(instrs,r,spillLoc,killSet,don'tOverwrite)
399    
400             fun reloadOneReg([],_,_) = []             fun reloadOneReg([],_,_) = []
401               | reloadOneReg(i::instrs,r,spillLoc) =               | reloadOneReg(i::instrs,r,spillLoc) =
# Line 339  Line 405 
405                 else i::reloadOneReg(instrs,r,spillLoc)                 else i::reloadOneReg(instrs,r,spillLoc)
406    
407             (* This function spills a set of registers for an instruction *)             (* This function spills a set of registers for an instruction *)
408             fun spillAll(instrs,[],killSet) = instrs             fun spillAll(instrs,[],killSet,don'tOverwrite) = instrs
409               | spillAll(instrs,r::rs,killSet) =               | spillAll(instrs,r::rs,killSet,don'tOverwrite) =
410                 let val node     = getnode r                 let val node     = getnode r
411                     val spillLoc = getLoc node                     val spillLoc = getLoc node
412                 in  spillAll(spillOneReg(instrs,r,spillLoc,killSet),                 in  spillAll(
413                              rs,killSet)                         spillOneReg(instrs,r,spillLoc,killSet,don'tOverwrite),
414                                rs,killSet,don'tOverwrite)
415                 end                 end
416    
417             (* This function reloads a set of registers for an instruction *)             (* This function reloads a set of registers for an instruction *)
# Line 367  Line 434 
434                           val spillRegs  = SL.uniq spillRegs                           val spillRegs  = SL.uniq spillRegs
435                           val reloadRegs = SL.uniq reloadRegs                           val reloadRegs = SL.uniq reloadRegs
436    
437                             (* spill locations that we can't overwrite if we
438                              * are spilling a parallel copy
439                              *)
440                             val don'tOverwrite =
441                                 if parallelCopies then spillLocsOf reloadRegs
442                                 else []
443    
444                           (*                           (*
445                           val Asm.S.STREAM{emit, ...} = Asm.makeStream[]                           val Asm.S.STREAM{emit, ...} = Asm.makeStream[]
446                           val regs = app (fn r =>                           val regs = app (fn r =>
447                                  print(Int.toString r^" ["^Int.toString                                  print(Int.toString(regmap r)^" ["^Int.toString
448                                            (getLoc (getnode r))^"] "))                                            (getLoc (getnode r))^"] "))
449                            *)                            *)
450    
451                           val instrs = spillAll([instr],spillRegs,killRegs)                           val instrs = spillAll([instr],spillRegs,killRegs,
452                                                   don'tOverwrite)
453    
454                           (*                           (*
455                           val _ =                           val _ =
# Line 395  Line 470 
470                                 (print "After:"; app (emit regmap) instrs;                                 (print "After:"; app (emit regmap) instrs;
471                                  print "------------------\n")                                  print "------------------\n")
472                            *)                            *)
473    
474                           fun concat([], l) = l                           fun concat([], l) = l
475                             | concat(a::b, l) = concat(b, a::l)                             | concat(a::b, l) = concat(b, a::l)
476                       in  loop(rest, dec pt, concat(instrs, newInstrs))                       in  loop(rest, dec pt, concat(instrs, newInstrs))

Legend:
Removed from v.499  
changed lines
  Added in v.545

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