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

Diff of /MLRISC/trunk/ra/mem-ra.sml

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

revision 651, Thu Jun 1 18:34:03 2000 UTC revision 705, Wed Sep 27 18:44:44 2000 UTC
# Line 34  Line 34 
34    
35    fun isOn(flag,mask) = Word.andb(flag,mask) <> 0w0    fun isOn(flag,mask) = Word.andb(flag,mask) <> 0w0
36    
37      fun isMemLoc(SPILLED) = true
38        | isMemLoc(SPILL_LOC _) = true
39        | isMemLoc(MEMREG _) = true
40        | isMemLoc _ = false
41    (*    (*
42     * Spill coalescing.     * Spill coalescing.
43     * Coalesce non-interfering moves between spilled nodes,     * Coalesce non-interfering moves between spilled nodes,
44     * in non-increasing order of move cost.     * in non-increasing order of move cost.
45     *)     *)
46    fun spillCoalescing(GRAPH{bitMatrix, ...}) =    fun spillCoalescing(GRAPH{bitMatrix, ...}) = let
47    let val member = BM.member(!bitMatrix)        val member = BM.member(!bitMatrix)
48        val addEdge = BM.add(!bitMatrix)        val addEdge = BM.add(!bitMatrix)
49    in  fn nodesToSpill =>    in
50        let      fn nodesToSpill => let
51            (* Find moves between two spilled nodes *)            (* Find moves between two spilled nodes *)
52            fun collectMoves([], mv') = mv'            fun collectMoves([], mv') = mv'
53              | collectMoves(NODE{movelist, color=ref(SPILLED _), ...}::ns, mv') =          | collectMoves(NODE{movelist, color, ...}::ns, mv') = let
54                let fun ins([], mv') = collectMoves(ns, mv')              fun ins([], mv') = collectMoves(ns, mv')
55                      | ins(MV{status=ref(COALESCED | CONSTRAINED), ...}::mvs,                | ins(MV{status=ref(COALESCED | CONSTRAINED), ...}::mvs, mv') =
56                            mv') = ins(mvs, mv')                    ins(mvs, mv')
57                      | ins((mv as MV{dst, src, ...})::mvs, mv') =                | ins((mv as MV{dst, src, ...})::mvs, mv') = let
58                         (case (chase dst, chase src) of                    val NODE{color=ref cd, number=nd, ...} = chase dst
59                            (NODE{color=ref(SPILLED x), number=d, ...},                    val NODE{color=ref cs, number=ns, ...} = chase src
60                             NODE{color=ref(SPILLED y), number=s, ...}) =>                  in
61                                if d = s orelse            (* trival move *)                    if nd=ns then ins(mvs, mv')
62                                   (x >= 0 andalso y >= 0) (* both are fixed *)                    else (case (cd, cs)
63                                then ins(mvs, mv')                      of (MEMREG _, MEMREG _) => ins(mvs, mv')
64                                else ins(mvs, MV.add(mv, mv'))                       |  _ =>
65                          | _ => ins(mvs, mv')                          if isMemLoc cd andalso isMemLoc cs then
66                         )                            ins(mvs, MV.add(mv, mv'))
67                in  ins(!movelist, mv') end                          else
68              | collectMoves(_::ns, mv') = collectMoves(ns, mv')                            ins(mvs, mv')
69                       (*esac*))
70            val mvs = collectMoves(nodesToSpill, MV.EMPTY)                  end
71              in
72                if isMemLoc (!color) then ins(!movelist, mv')
73                else collectMoves(ns, mv')
74              end
75    
76            (* Coalesce moves between two spilled nodes *)            (* Coalesce moves between two spilled nodes *)
77            fun coalesceMoves(MV.EMPTY) = ()            fun coalesceMoves(MV.EMPTY) = ()
# Line 71  Line 79 
79                let val dst as NODE{color=colorDst, ...} = chase dst                let val dst as NODE{color=colorDst, ...} = chase dst
80                    val src = chase src                    val src = chase src
81    
82                    (* Make sure that dst is the non-mem reg node *)                (* Make sure that dst has not been assigned a spill location *)
83                    val (dst, src) =                    val (dst, src) =
84                         case !colorDst of                  case !colorDst of SPILLED => (dst, src) | _ => (src, dst)
                          SPILLED ~1 => (dst, src)  
                        | _ => (src, dst)  
85    
86                    val dst as NODE{number=d, color=colorDst, adj=adjDst,                    val dst as NODE{number=d, color=colorDst, adj=adjDst,
87                                    defs=defsDst, uses=usesDst,  ...} = dst                                    defs=defsDst, uses=usesDst,  ...} = dst
# Line 87  Line 93 
93                      | union((n as NODE{color, adj=adjT,                      | union((n as NODE{color, adj=adjT,
94                                         number=t, ...})::adjDst, adjSrc) =                                         number=t, ...})::adjDst, adjSrc) =
95                        (case !color of                        (case !color of
96                           (SPILLED _ | PSEUDO) =>                       (SPILLED | MEMREG _ | SPILL_LOC _ | PSEUDO) =>
97                             if addEdge(s, t) then                             if addEdge(s, t) then
98                                (adjT := src :: !adjT; union(adjDst, n::adjSrc))                                (adjT := src :: !adjT; union(adjDst, n::adjSrc))
99                             else union(adjDst, adjSrc)                             else union(adjDst, adjSrc)
# Line 96  Line 102 
102                             else union(adjDst, adjSrc)                             else union(adjDst, adjSrc)
103                         | _ => union(adjDst, adjSrc)                         | _ => union(adjDst, adjSrc)
104                        )                        )
105    
106                    val mvs = MV.merge(l,r)                    val mvs = MV.merge(l,r)
107                in  if d = s then          (* trivial *)  
108                       coalesceMoves mvs                fun f() =
                   else  
                   (case !colorDst of  
                     SPILLED x =>  
                        if x >= 0 orelse  (* both dst and src are mem regs *)  
                           member(d, s)   (* they interfere *)  
                        then  
                          ((* print("Bad "^Int.toString d ^  
                                    "<->"^Int.toString s^"\n")*))  
                        else  
109                           ((* print(Int.toString d ^"<->"^Int.toString s^"\n");*)                           ((* print(Int.toString d ^"<->"^Int.toString s^"\n");*)
110                            ra_spill_coal := !ra_spill_coal + 1;                            ra_spill_coal := !ra_spill_coal + 1;
111                             (* unify *)                             (* unify *)
112                            colorDst := ALIASED src;                            colorDst := ALIASED src;
113                            adjSrc := union(!adjDst, !adjSrc);                            adjSrc := union(!adjDst, !adjSrc);
114                            if x >= 0 then ()                   defsSrc := concat(!defsDst, !defsSrc);
115                            else                   usesSrc := concat(!usesDst, !usesSrc);
116                              (defsSrc := concat(!defsDst, !defsSrc);                   coalesceMoves mvs)
117                               usesSrc := concat(!usesDst, !usesSrc))            in
118                           )                if d = s then coalesceMoves mvs
119                     | _ => error "coalesceMoves";                else (case !colorDst
120                     coalesceMoves mvs                  of MEMREG _ => coalesceMoves mvs
121                    )                   | SPILLED =>
122                end                      if member(d,s) then coalesceMoves mvs else f()
123       in  coalesceMoves mvs                   | SPILL_LOC loc =>
124                        if member(d,s) then coalesceMoves mvs else f()
125                     | _ => error "coalesceMoves"
126                   (*esac*))
127       end       end
128         in coalesceMoves(collectMoves(nodesToSpill, MV.EMPTY))
129    end    end
130      end (*spillCoalesce*)
131    
132    (*    (*
133     * Spill propagation.     * Spill propagation.
# Line 185  Line 188 
188                      )                      )
189                   else                   else
190                      case (!dstCol, !srcCol) of                      case (!dstCol, !srcCol) of
191                        (SPILLED x, PSEUDO) => savings(x)                        (SPILLED, PSEUDO) => savings(~1)
192                      | (PSEUDO, SPILLED x) => savings(x)                      | (MEMREG m, PSEUDO) => savings(m)
193                        | (SPILL_LOC s, PSEUDO) => savings(~s)
194                        | (PSEUDO, SPILLED) => savings(~1)
195                        | (PSEUDO, MEMREG m) => savings(m)
196                        | (PSEUDO, SPILL_LOC s) => savings(~s)
197                      | _ => (if debug then print "0 (other)\n" else ();                      | _ => (if debug then print "0 (other)\n" else ();
198                              moveSavings(mvs, pinned, total))                              moveSavings(mvs, pinned, total))
199                end                end
# Line 263  Line 270 
270          | insertAll(NODE{adj, ...}::nodes, worklist) =          | insertAll(NODE{adj, ...}::nodes, worklist) =
271               insertAll(nodes, insert(!adj, worklist))               insertAll(nodes, insert(!adj, worklist))
272    
273        val marker = SPILLED(~1)        val marker = SPILLED
274    
275        (* Process all nodes from the worklist *)        (* Process all nodes from the worklist *)
276        fun propagate([], spilled) = spilled        fun propagate([], spilled) = spilled
# Line 298  Line 305 
305    
306        (* Initialize worklist *)        (* Initialize worklist *)
307        fun init([], worklist) = worklist        fun init([], worklist) = worklist
308          | init(NODE{adj, color=ref(SPILLED _), ...}::rest, worklist) =          | init(NODE{adj, color=ref(c), ...}::rest, worklist) =
309               if isMemLoc (c) then
310              init(rest, insert(!adj, worklist))              init(rest, insert(!adj, worklist))
311          | init(_::rest, worklist) = init(rest, worklist)             else
312                 init(rest, worklist)
313    
314        (*        (*
315         * Iterate between spill coalescing and propagation         * Iterate between spill coalescing and propagation
# Line 328  Line 337 
337     *    Spilled copy temporaries are assigned its own set of colors and     *    Spilled copy temporaries are assigned its own set of colors and
338     * cannot share with another other nodes.   They can share colors with     * cannot share with another other nodes.   They can share colors with
339     * themselves however.     * themselves however.
340       *
341       * spillLoc is the first available (logical) spill location.
342     *)     *)
343    fun spillColoring(GRAPH{spillLoc, copyTmps, mode, ...}) nodesToSpill =  
344    let val proh     = A.array(length nodesToSpill, ~1)    fun spillColoring(GRAPH{spillLoc, copyTmps, mode, ...}) nodesToSpill = let
345        val firstLoc = !spillLoc      val proh = A.array(length nodesToSpill, ~1)
346        val _ = spillLoc := firstLoc - 1 (* allocate one location first *)      val firstColor= !spillLoc
347    
348        fun colorCopyTmps(tmps) =      fun colorCopyTmps(tmps) = let
349        let fun loop([], found) = found        fun spillTmp(NODE{color as ref(SPILLED), ...}, found) =
350              | loop(NODE{color as ref(SPILLED ~1), ...}::tmps, found) =             (color := SPILL_LOC(firstColor); true)
351                  (color := SPILLED firstLoc; loop(tmps, true))          | spillTmp(_, found) = found
352              | loop(_::tmps, found) = loop(tmps, found)      in
353        in  if loop(tmps, false) then        if List.foldl spillTmp false tmps then
354               (spillLoc := !spillLoc - 1; firstLoc - 1)          (spillLoc := !spillLoc + 1; firstColor + 1)
355            else firstLoc        else firstColor
       end  
   
       fun selectColor([], firstColor, currLoc) = ()  
         | selectColor(NODE{color as ref(SPILLED ~1), number, adj, ...}::nodes,  
                       firstColor, currLoc) =  
           let fun neighbors [] = ()  
                 | neighbors(n::ns) =  
                   let fun mark(NODE{color=ref(SPILLED loc), ...}) =  
                            (if loc >= ~1 then () (* no location yet *)  
                             else A.update(proh, firstLoc - loc, number);  
                             neighbors ns  
                            )  
                         | mark(NODE{color=ref(ALIASED n), ...}) = mark n  
                         | mark _ = neighbors ns  
                   in  mark n end  
               val _ = neighbors(!adj)  
               fun findColor(loc, startingPoint) =  
                   let val loc = if loc < firstColor then !spillLoc + 1 else loc  
                   in  if A.sub(proh, firstLoc - loc) <> number then loc (* ok *)  
                       else if loc = startingPoint then (* new location *)  
                       let val loc = !spillLoc  
                       in  spillLoc := loc - 1; loc end  
                       else findColor(loc - 1, startingPoint)  
                   end  
               val currLoc = if currLoc < firstColor then !spillLoc + 1  
                             else currLoc  
               val loc = findColor(currLoc, currLoc)  
               (* val _ = print("Spill("^Int.toString number^")="^  
                             Int.toString loc^"\n") *)  
           in  color := SPILLED loc; (* mark with color *)  
               selectColor(nodes, firstColor, loc - 1)  
356            end            end
         | selectColor(_::nodes, firstColor, currLoc) =  
               selectColor(nodes, firstColor, currLoc)  
357    
358        (* color the copy temporaries first *)        (* color the copy temporaries first *)
359         val firstColor = if isOn(mode, RACore.HAS_PARALLEL_COPIES)      val firstColor =
360                          then colorCopyTmps(!copyTmps) else firstLoc        if isOn(mode, RACore.HAS_PARALLEL_COPIES) then
361            colorCopyTmps(!copyTmps)
362          else firstColor
363    
364        fun selectColor([], _, lastLoc) = (spillLoc := lastLoc)
365          | selectColor(NODE{color as ref(SPILLED), number, adj, ...}::nodes,
366                        currLoc, lastLoc) =
367            let
368              fun neighbors(NODE{color=ref(SPILL_LOC s), ...}) =
369                    A.update(proh, s - firstColor, number)
370                | neighbors(NODE{color=ref(ALIASED n), ...}) = neighbors n
371                | neighbors _ = ()
372    
373              val _ =  app neighbors (!adj)
374    
375              fun findColor(loc, startingPt) =
376                if loc = lastLoc then findColor(firstColor, startingPt)
377                else if A.sub(proh, loc-firstColor) <> number then (loc, lastLoc)
378                else if loc  = startingPt then (lastLoc, lastLoc+1)
379                     else findColor(loc+1, startingPt)
380    
381              val (loc, lastLoc) = findColor(currLoc + 1, currLoc)
382    
383            in
384              color := SPILL_LOC(loc); (* mark with color *)
385              selectColor(nodes, loc, lastLoc)
386            end
387          | selectColor(_::nodes, currLoc, lastLoc) =
388              selectColor(nodes, currLoc, lastLoc)
389      in
390        (* color the rest of the spilled nodes *)        (* color the rest of the spilled nodes *)
391    in  selectColor(nodesToSpill, firstColor, !spillLoc)      selectColor(nodesToSpill, firstColor, !spillLoc + 1)
392    end    end (* spillColoring *)
393    
394    end (* local *)    end (* local *)
395    
# Line 405  Line 412 
412         * These are nodes that need also to be spilled         * These are nodes that need also to be spilled
413         *)         *)
414        fun markMemRegs [] = ()        fun markMemRegs [] = ()
415          | markMemRegs(NODE{number=r, color as ref(ALIASED          | markMemRegs(NODE{number=r,
416                       (NODE{color=ref(col as SPILLED c), ...})), ...}::ns) =                             color as ref(ALIASED
417             (if c >= 0 then color := col else ();                                          (NODE{color=ref(col), ...})), ...}::ns) =
418              markMemRegs ns)             (case col of MEMREG _ => color := col | _ => ();
419                markMemRegs(ns))
420          | markMemRegs(_::ns) = markMemRegs ns          | markMemRegs(_::ns) = markMemRegs ns
421    
422        (*        (*

Legend:
Removed from v.651  
changed lines
  Added in v.705

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