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

Diff of /MLRISC/releases/release-110.79/ra/ra-core.sml

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

revision 579, Wed Mar 22 06:33:08 2000 UTC revision 585, Wed Mar 29 23:55:35 2000 UTC
# Line 529  Line 529 
529    fun initWorkLists    fun initWorkLists
530          (GRAPH{nodes, K, bitMatrix, regmap, pseudoCount, blockedCount,          (GRAPH{nodes, K, bitMatrix, regmap, pseudoCount, blockedCount,
531                 firstPseudoR, deadCopies, memMoves, mode, ...}) {moves} =                 firstPseudoR, deadCopies, memMoves, mode, ...}) {moves} =
532    let (* Filter moves that already have an interference    let
533          (* Remove duplicates from the moves *)
534          (*
535          local
536             fun idOf(mv as MV{src=NODE{number=x, ...},
537                               dst=NODE{number=y, ...}, ...}) =
538               if x < y then (x,y,mv) else (y,x,mv)
539             fun order((a,b,mv1), (c,d,mv2)) = a < c orelse a = c andalso b < d
540             fun elimDup((a,b,mv)::mvs, mvs') = elimDup'(a,b,mv,mvs,mvs')
541               | elimDup([], mvs') = mvs'
542             and elimDup'(a,b,mv,[],mvs') = mv::mvs'
543               | elimDup'(a:int,b:int,mv1 as MV{cost=c1,status,src,dst,hicount,...},
544                          (c,d,mv2 as MV{cost=c2,...})::rest,mvs') =
545                 if a=c andalso b=d then
546                     elimDup'(a,b,MV{cost=c1+c2,status=status,
547                                     src=src,dst=dst,hicount=hicount},
548                              rest, mvs')
549                 else
550                     elimDup'(c,d,mv2,rest,mv1::mvs')
551              val moves = ListMergeSort.sort order (map idOf moves)
552          in
553              val moves = elimDup(moves, [])
554          end
555          *)
556    
557    
558          (* Filter moves that already have an interference
559         * Also initialize the movelist and movecnt fields at this time.         * Also initialize the movelist and movecnt fields at this time.
560         *)         *)
561        val member = BM.member(!bitMatrix)        val member = BM.member(!bitMatrix)
# Line 934  Line 960 
960            * to prune the lists            * to prune the lists
961            *)            *)
962           fun mergeMoveList([], mv) = mv           fun mergeMoveList([], mv) = mv
963             | mergeMoveList((m as MV{status,hicount,...})::rest, mv) =             | mergeMoveList((m as MV{status,hicount,src,dst,...})::rest, mv) =
964                (case !status of                (case !status of
965                  BRIGGS_MOVE =>                  BRIGGS_MOVE =>
966                    (* if we are changing a copy from v <-> w to uv <-> w                    (* if we are changing a copy from v <-> w to uv <-> w
967                     * makes sure we reset its trigger count, so that it                     * makes sure we reset its trigger count, so that it
968                     * will be tested next.                     * will be tested next.
969                     *)                     *)
970                    (if coloringv then (status := GEORGE_MOVE; hicount := 0)                    (if coloringv then
971                          (status := GEORGE_MOVE;
972                           hicount := 0;
973                           if debug then
974                              print ("New george "^show src^"<->"^show dst^"\n")
975                           else ()
976                          )
977                     else ();                     else ();
978                     mergeMoveList(rest, m::mv)                     mergeMoveList(rest, m::mv)
979                    )                    )
# Line 1438  Line 1470 
1470    end    end
1471    
1472    (*    (*
    * Spill coalescing.  
    * Coalesce non-interfering moves between spilled nodes,  
    * in non-increasing order of move cost.  
    *)  
   fun spillCoalescing(GRAPH{bitMatrix, ...}) =  
   let val member = BM.member(!bitMatrix)  
       val addEdge = BM.add(!bitMatrix)  
   in  fn nodesToSpill =>  
       let  
           (* Find moves between two spilled nodes *)  
           fun collectMoves([], mv') = mv'  
             | collectMoves(NODE{movelist, color=ref(SPILLED _), ...}::ns, mv') =  
               let fun ins([], mv') = collectMoves(ns, mv')  
                     | ins(MV{status=ref(COALESCED | CONSTRAINED), ...}::mvs,  
                           mv') = ins(mvs, mv')  
                     | ins((mv as MV{dst, src, ...})::mvs, mv') =  
                        (case (chase dst, chase src) of  
                           (NODE{color=ref(SPILLED x), number=d, ...},  
                            NODE{color=ref(SPILLED y), number=s, ...}) =>  
                               if d = s orelse            (* trival move *)  
                                  (x >= 0 andalso y >= 0) (* both are fixed *)  
                               then ins(mvs, mv')  
                               else ins(mvs, MV.add(mv, mv'))  
                         | _ => ins(mvs, mv')  
                        )  
               in  ins(!movelist, mv') end  
             | collectMoves(_::ns, mv') = collectMoves(ns, mv')  
   
           val mvs = collectMoves(nodesToSpill, MV.EMPTY)  
   
           (* Coalesce moves between two spilled nodes *)  
           fun coalesceMoves(MV.EMPTY) = ()  
             | coalesceMoves(MV.TREE(MV{dst, src, cost, ...}, _, l, r)) =  
               let val dst as NODE{color=colorDst, ...} = chase dst  
                   val src = chase src  
   
                   (* Make sure that dst is the non-mem reg node *)  
                   val (dst, src) =  
                        case !colorDst of  
                          SPILLED ~1 => (dst, src)  
                        | _ => (src, dst)  
   
                   val dst as NODE{number=d, color=colorDst, adj=adjDst,  
                                   defs=defsDst, uses=usesDst,  ...} = dst  
                   val src as NODE{number=s, color=colorSrc, adj=adjSrc,  
                                   defs=defsSrc, uses=usesSrc, ...} = src  
   
                   (* combine adjacency lists *)  
                   fun union([], adjSrc) = adjSrc  
                     | union((n as NODE{color, adj=adjT,  
                                        number=t, ...})::adjDst, adjSrc) =  
                       (case !color of  
                          (SPILLED _ | PSEUDO) =>  
                            if addEdge(s, t) then  
                               (adjT := src :: !adjT; union(adjDst, n::adjSrc))  
                            else union(adjDst, adjSrc)  
                        | COLORED _ =>  
                            if addEdge(s, t) then union(adjDst, n::adjSrc)  
                            else union(adjDst, adjSrc)  
                        | _ => union(adjDst, adjSrc)  
                       )  
                   val mvs = MV.merge(l,r)  
               in  if d = s then          (* trivial *)  
                      coalesceMoves mvs  
                   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  
                          ((* print(Int.toString d ^"<->"^Int.toString s^"\n");*)  
                           ra_spill_coal := !ra_spill_coal + 1;  
                            (* unify *)  
                           colorDst := ALIASED src;  
                           adjSrc := union(!adjDst, !adjSrc);  
                           if x >= 0 then ()  
                           else  
                             (defsSrc := concat(!defsDst, !defsSrc);  
                              usesSrc := concat(!usesDst, !usesSrc))  
                          )  
                    | _ => error "coalesceMoves";  
                    coalesceMoves mvs  
                   )  
               end  
      in  coalesceMoves mvs  
      end  
   end  
   
   (*  
   (*  
    * Spill propagation.  
    *)  
   fun spillPropagation(G as GRAPH{bitMatrix, memRegs, ...}) nodesToSpill =  
   let val spillCoalescing = spillCoalescing G  
       exception SpillProp  
       val visited = Intmap.new(32, SpillProp) : bool Intmap.intmap  
       val hasBeenVisited = Intmap.mapWithDefault (visited, false)  
       val markAsVisited = Intmap.add visited  
       val member = BM.member(!bitMatrix)  
   
       (* compute savings due to spill coalescing.  
        * The move list must be associated with a colorable node.  
        * The pinned flag is to prevent the spill node from coalescing  
        * two different fixed memory registers.  
        *)  
       fun coalescingSavings([], pinned, sc) = (pinned, sc+sc)  
         | coalescingSavings(MV{status=ref(CONSTRAINED | COALESCED), ...}::mvs,  
                             pinned, sc) = coalescingSavings(mvs, pinned, sc)  
         | coalescingSavings(MV{dst, src, cost, ...}::mvs, pinned, sc) =  
           let val NODE{number=d, color=dstCol, ...} = chase dst  
               val NODE{number=s, color=srcCol, ...} = chase src  
               fun savings(x) =  
                   if member(d, s) then coalescingSavings(mvs, pinned, sc)  
                   else if x = ~1 then coalescingSavings(mvs, pinned, sc+cost)  
                   else if pinned >= 0 andalso pinned <> x then  
                      (* already coalesced with another mem reg *)  
                      coalescingSavings(mvs, pinned, sc)  
                   else  
                      (* coalescingSavings(mvs, x, sc+cost) *) (* XXX *)  
                      coalescingSavings(mvs, x, sc+cost)  
           in  if d = s then  
                  coalescingSavings(mvs, pinned, sc)  
               else  
                  case (!dstCol, !srcCol) of  
                    (SPILLED x, PSEUDO) => savings(x)  
                  | (PSEUDO, SPILLED x) => savings(x)  
                  | _ => coalescingSavings(mvs, pinned, sc)  
           end  
   
       (* Insert all spillable neighbors onto the worklist *)  
       fun insert([], worklist) = worklist  
         | insert((node as NODE{color=ref PSEUDO, number, ...})::adj, worklist) =  
           if hasBeenVisited number  
           then insert(adj, worklist)  
           else (markAsVisited (number, true);  
                 insert(adj, node::worklist))  
         | insert(_::adj, worklist) = insert(adj, worklist)  
   
       val marker = SPILLED(~1)  
   
       (* Process all nodes from the worklist *)  
       fun propagate([], spilled) = spilled  
         | propagate((node as NODE{color as ref PSEUDO,  
                                   pri=ref spillcost, number,  
                                   adj, movelist, ...})::worklist,  
                     spilled) =  
           let val (pinned, savings) = coalescingSavings(!movelist, ~1, 0)  
           in  (* if (if pinned >= 0 then savings > spillcost  
                  else savings >= spillcost) *) (* XXX *)  
               if savings >= spillcost  
               then  (* propagate spill *)  
                  (ra_spill_prop := !ra_spill_prop + 1;  
                   color := marker; (* spill the node *)  
                   (* print("Propagating "^Int.toString number^" "^  
                         "savings="^Int.toString(savings)^  
                        " cost="^Int.toString spillcost^"\n"); *)  
                   (* run spill coalescing *)  
                   spillCoalescing [node];  
                   propagate(insert(!adj, worklist), node::spilled)  
                  )  
               else  
                  propagate(worklist, spilled)  
           end  
         | propagate(_::worklist, spilled) =  
             propagate(worklist, spilled)  
   
       (* Initialize worklist *)  
       fun init([], worklist) = worklist  
         | init(NODE{adj, color=ref(SPILLED _), ...}::rest, worklist) =  
             init(rest, insert(!adj, worklist))  
         | init(_::rest, worklist) = init(rest, worklist)  
   
       (*  
        * Iterate between spill coalescing and propagation  
        *)  
       fun iterate(spillWorkList, spilled) =  
       let (* run one round of coalescing first *)  
           val _ = spillCoalescing spillWorkList  
           val propagationWorkList = init(spillWorkList, [])  
           (* iterate on our own spill nodes *)  
           val spilled = propagate(propagationWorkList, spilled)  
           (* try the memory registers too *)  
           val spilled = propagate(!memRegs, spilled)  
       in  spilled  
       end  
   
   in  iterate(nodesToSpill, nodesToSpill)  
   end  
   
   (*  
    * Spill coloring.  
    * Assign logical spill locations to all the spill nodes.  
    *  
    * IMPORTANT BUG FIX:  
    *    Spilled copy temporaries are assigned its own set of colors and  
    * cannot share with another other nodes.   They can share colors with  
    * themselves however.  
    *)  
   fun spillColoring(GRAPH{spillLoc, copyTmps, mode, ...}) nodesToSpill =  
   let val proh     = A.array(length nodesToSpill, ~1)  
       val firstLoc = !spillLoc  
       val _ = spillLoc := firstLoc - 1 (* allocate one location first *)  
   
       fun colorCopyTmps(tmps) =  
       let fun loop([], found) = found  
             | loop(NODE{color as ref(SPILLED ~1), ...}::tmps, found) =  
                 (color := SPILLED firstLoc; loop(tmps, true))  
             | loop(_::tmps, found) = loop(tmps, found)  
       in  if loop(tmps, false) then  
              (spillLoc := !spillLoc - 1; firstLoc - 1)  
           else firstLoc  
       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)  
           end  
         | selectColor(_::nodes, firstColor, currLoc) =  
               selectColor(nodes, firstColor, currLoc)  
   
       (* color the copy temporaries first *)  
        val firstColor = if isOn(mode, HAS_PARALLEL_COPIES)  
                         then colorCopyTmps(!copyTmps) else firstLoc  
       (* color the rest of the spilled nodes *)  
   in  selectColor(nodesToSpill, firstColor, !spillLoc)  
   end  
   *)  
   
   (*  
1473     * Update the regmap, after finishing register allocation.     * Update the regmap, after finishing register allocation.
1474     * All nodes must have been colored.     * All nodes must have been colored.
1475     *)     *)

Legend:
Removed from v.579  
changed lines
  Added in v.585

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