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
 [smlnj] / MLRISC / trunk / ra / mem-ra.sml

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

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
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)
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
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
87                                    defs=defsDst, uses=usesDst,  ...} = dst                                    defs=defsDst, uses=usesDst,  ...} = dst
# Line 87  Line 93
95                        (case !color of                        (case !color of
96                           (SPILLED _ | PSEUDO) =>                       (SPILLED | MEMREG _ | SPILL_LOC _ | PSEUDO) =>
# Line 96  Line 102
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
"<->"^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;
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
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
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
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