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

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

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

revision 469, Wed Nov 10 22:42:52 1999 UTC revision 475, Wed Nov 10 22:59:58 1999 UTC
# Line 70  Line 70 
70    open G    open G
71    
72    val verbose = MLRiscControl.getFlag "ra-verbose"    val verbose = MLRiscControl.getFlag "ra-verbose"
73      val ra_spill_coal = MLRiscControl.getCounter "ra-spill-coalescing"
74      val ra_spill_prop = MLRiscControl.getCounter "ra-spill-propagation"
75    
76    fun error msg = MLRiscErrorMsg.error("RACore", msg)    fun error msg = MLRiscErrorMsg.error("RACore", msg)
77    
# Line 77  Line 79 
79    fun x + y = W.toIntX(W.+(W.fromInt x, W.fromInt y))    fun x + y = W.toIntX(W.+(W.fromInt x, W.fromInt y))
80    fun x - y = W.toIntX(W.-(W.fromInt x, W.fromInt y))    fun x - y = W.toIntX(W.-(W.fromInt x, W.fromInt y))
81    
82      fun concat([], b) = b
83        | concat(x::a, b) = concat(a, x::b)
84    
85    (*    (*
86     * Bit Matrix routines     * Bit Matrix routines
87     *)     *)
# Line 340  Line 345 
345              | ALIASED _ => "a"              | ALIASED _ => "a"
346              | COLORED c => "["^showReg c^"]"              | COLORED c => "["^showReg c^"]"
347              | SPILLED _ => "s"              | SPILLED _ => "s"
             | ALIASED_SPILL _ => "as"  
348             )             )
349    
350    fun show G (node as NODE{pri,...}) =    fun show G (node as NODE{pri,...}) =
# Line 450  Line 454 
454             | ALIASED _     => error "addEdge: ALIASED"             | ALIASED _     => error "addEdge: ALIASED"
455             | REMOVED       => error "addEdge: REMOVED"             | REMOVED       => error "addEdge: REMOVED"
456             | SPILLED _     => error "addEdge: SPILLED"             | SPILLED _     => error "addEdge: SPILLED"
            | ALIASED_SPILL _ => error "addEdge: ALIASED_SPILL"  
457            )            )
458    in  fn (x as NODE{number=xn, ...}, y as NODE{number=yn, ...}) =>    in  fn (x as NODE{number=xn, ...}, y as NODE{number=yn, ...}) =>
459            if xn = yn then ()            if xn = yn then ()
# Line 479  Line 482 
482             | ALIASED _     => error "removeEdge: ALIASED"             | ALIASED _     => error "removeEdge: ALIASED"
483             | REMOVED       => error "removeEdge: REMOVED"             | REMOVED       => error "removeEdge: REMOVED"
484             | SPILLED _     => error "removeEdge: SPILLED"             | SPILLED _     => error "removeEdge: SPILLED"
            | ALIASED_SPILL _ => error "removeEdge: ALIASED_SPILL"  
485            )            )
486    in  fn (x as NODE{number=xn, ...}, y as NODE{number=yn, ...}) =>    in  fn (x as NODE{number=xn, ...}, y as NODE{number=yn, ...}) =>
487            if xn = yn then ()            if xn = yn then ()
# Line 611  Line 613 
613        fun num(NODE{color=ref(COLORED r),...}) = r        fun num(NODE{color=ref(COLORED r),...}) = r
614          | num(NODE{color=ref(ALIASED n),...}) = num n          | num(NODE{color=ref(ALIASED n),...}) = num n
615          | num(NODE{color=ref(SPILLED s),number,...}) = ~1          | num(NODE{color=ref(SPILLED s),number,...}) = ~1
         | num(NODE{color=ref(ALIASED_SPILL s), number, ...}) = ~1  
616          | num(NODE{number, color=ref PSEUDO,...}) = number          | num(NODE{number, color=ref PSEUDO,...}) = number
617          | num _ = error "regmap"          | num _ = error "regmap"
618        fun lookup r = num(getnode r) handle _ => r (* XXX *)        fun lookup r = num(getnode r) handle _ => r (* XXX *)
# Line 627  Line 628 
628        fun num(NODE{color=ref(COLORED r),...}) = r        fun num(NODE{color=ref(COLORED r),...}) = r
629          | num(NODE{color=ref(ALIASED n),...}) = num n          | num(NODE{color=ref(ALIASED n),...}) = num n
630          | num(NODE{color=ref(SPILLED _),number,...}) = number          | num(NODE{color=ref(SPILLED _),number,...}) = number
         | num(NODE{color=ref(ALIASED_SPILL _), number, ...}) = number  
631          | num(NODE{number, color=ref PSEUDO,...}) = number          | num(NODE{number, color=ref PSEUDO,...}) = number
632          | num _ = error "spillRegmap"          | num _ = error "spillRegmap"
633        fun lookup r = num(getnode r) handle _ => r (* XXX *)        fun lookup r = num(getnode r) handle _ => r (* XXX *)
# Line 643  Line 643 
643        fun num(NODE{color=ref(ALIASED n), ...}) = num n        fun num(NODE{color=ref(ALIASED n), ...}) = num n
644          | num(NODE{color=ref(SPILLED ~1), number, ...}) = number          | num(NODE{color=ref(SPILLED ~1), number, ...}) = number
645          | num(NODE{color=ref(SPILLED c), ...}) = c          | num(NODE{color=ref(SPILLED c), ...}) = c
         | num(NODE{color=ref(ALIASED_SPILL n), ...}) = num n  
646          | num(NODE{number, ...}) = number          | num(NODE{number, ...}) = number
647        fun lookup r = num(getnode r) handle _ => r (* XXX *)        fun lookup r = num(getnode r) handle _ => r (* XXX *)
648    in  lookup    in  lookup
# Line 828  Line 827 
827                 NODE{color=ref(COLORED _),...} => loop adj (* can't be r! *)                 NODE{color=ref(COLORED _),...} => loop adj (* can't be r! *)
828               | NODE{color=ref(ALIASED _),...} => loop adj (* not real *)               | NODE{color=ref(ALIASED _),...} => loop adj (* not real *)
829               | NODE{color=ref(SPILLED _),...} => loop adj (* gone! *)               | NODE{color=ref(SPILLED _),...} => loop adj (* gone! *)
              | NODE{color=ref(ALIASED_SPILL _),...} => loop adj (* gone! *)  
830               | NODE{degree,...} => (* PSEUDO or REMOVED *)               | NODE{degree,...} => (* PSEUDO or REMOVED *)
831                  (!degree < K orelse member(n, r)) andalso loop adj                  (!degree < K orelse member(n, r)) andalso loop adj
832               )               )
# Line 905  Line 903 
903                     * Strictly speaking, the def/use points of the move                     * Strictly speaking, the def/use points of the move
904                     * should also be removed.  But since we never spill                     * should also be removed.  But since we never spill
905                     * a coalesced node and only spilling makes use of these                     * a coalesced node and only spilling makes use of these
906                     * def/use points, we are safe for now.  (NOTE to SELF:                     * def/use points, we are safe for now.
907                     * I think it is not necessary to maintain these.                     *
908                       * New comment: with spill propagation, it is necessary
909                       * to keep track of the spilled program points.
910                     *)                     *)
911           (* defsu := !defsu @ !defsv;           defsu := concat(!defsu, !defsv);
912           usesu := !usesu @ !usesv; *)           usesu := concat(!usesu, !usesv);
913           case !ucol of           case !ucol of
914             PSEUDO =>             PSEUDO =>
915               (if !cntv > 0 then moveu := mergeMoveList(!movev, !moveu) else ();               (if !cntv > 0 then moveu := mergeMoveList(!movev, !moveu) else ();
# Line 1245  Line 1245 
1245     * in non-increasing order of move cost.     * in non-increasing order of move cost.
1246     *)     *)
1247    fun spillCoalescing(GRAPH{bitMatrix, ...}) nodesToSpill =    fun spillCoalescing(GRAPH{bitMatrix, ...}) nodesToSpill =
1248    let val marker = SPILLED(~1)    let fun chase(NODE{color=ref(ALIASED n), ...}) = chase n
       fun mark [] = ()  
         | mark(NODE{color, ...}::ns) = (color := marker; mark ns)  
       val _ = mark nodesToSpill  
       fun chase(NODE{color=ref(ALIASED_SPILL n), ...}) = chase n  
         | chase(NODE{color=ref(ALIASED n), ...}) = chase n  
1249          | chase n = n          | chase n = n
1250        fun collectMoves([], mv') = mv'        fun collectMoves([], mv') = mv'
1251          | collectMoves(NODE{movelist, number, ...}::ns, mv') =          | collectMoves(NODE{movelist, color=ref(SPILLED ~1), ...}::ns, mv') =
1252            let fun addMoves([], mv') = collectMoves(ns, mv')            let fun addMoves([], mv') = collectMoves(ns, mv')
1253                  | addMoves((mv as MV{dst,src,status=ref LOST, ...})::mvs, mv') =                  | addMoves((mv as MV{dst,src,status=ref LOST, ...})::mvs, mv') =
1254                     (case (chase dst, chase src) of                     (case (chase dst, chase src) of
# Line 1265  Line 1260 
1260                     )                     )
1261                  | addMoves(_::mvs, mv') = addMoves(mvs, mv')                  | addMoves(_::mvs, mv') = addMoves(mvs, mv')
1262            in  addMoves(!movelist, mv') end            in  addMoves(!movelist, mv') end
1263            | collectMoves(_::ns, mv') = collectMoves(ns, mv')
1264    
1265        val mvs = collectMoves(nodesToSpill, MV.EMPTY)        val mvs = collectMoves(nodesToSpill, MV.EMPTY)
1266    
1267        val member = BM.member(!bitMatrix)        val member = BM.member(!bitMatrix)
1268        val addEdge = BM.add(!bitMatrix)        val addEdge = BM.add(!bitMatrix)
1269    
1270        fun coalesceMoves(MV.EMPTY) = ()        fun coalesceMoves(MV.EMPTY) = ()
1271          | coalesceMoves(MV.TREE(MV{dst, src, ...}, _, l, r)) =          | coalesceMoves(MV.TREE(MV{dst, src, ...}, _, l, r)) =
1272            let val dst as NODE{number=d, uses=u1, defs=d1,            let val dst as NODE{number=d, color, adj=adjDst,
1273                                color, adj=adj1, ...} = chase dst                                defs=defsDst, uses=usesDst, ...} = chase dst
1274                val src as NODE{number=s, uses=u2, defs=d2, adj=adj2, ...} =                val src as NODE{number=s, adj=adjSrc,
1275                                chase src                                defs=defsSrc, uses=usesSrc, ...} = chase src
1276                fun addEdges [] = ()                fun union([], adjSrc) = adjSrc
1277                  | addEdges(n::adj) =                  | union((n as NODE{color, adj=adjT,
1278                    (case chase n of                                     number=t, ...})::adjDst, adjSrc) =
1279                       n as NODE{color=ref(SPILLED ~1), number=t, ...} =>                    (case !color of
1280                       (if addEdge(s,t) then adj2 := n :: !adj2 else ();                       (SPILLED _ | PSEUDO) =>
1281                        addEdges adj)                         if addEdge(s, t) then
1282                     | _ => addEdges adj                            (adjT := src :: !adjT; union(adjDst, n::adjSrc))
1283                           else union(adjDst, adjSrc)
1284                       | COLORED _ =>
1285                           if addEdge(s, t) then union(adjDst, n::adjSrc)
1286                           else union(adjDst, adjSrc)
1287                       | _ => union(adjDst, adjSrc)
1288                    )                    )
1289            in  if d = s orelse member(dst, src) then ()            in  if d = s orelse member(dst, src) then ()
1290                else ((* print(Int.toString d ^"<->"^Int.toString s^"\n"); *)                else ((* print(Int.toString d ^"<->"^Int.toString s^"\n"); *)
1291                      color := ALIASED_SPILL src; addEdges(!adj1)                      ra_spill_coal := !ra_spill_coal + 1;
1292                        color := ALIASED src;
1293                        adjSrc := union(!adjDst, !adjSrc);
1294                        defsSrc := concat(!defsDst, !defsSrc);
1295                        usesSrc := concat(!usesDst, !usesSrc)
1296                     );                     );
1297                coalesceMoves(MV.merge(l,r))                coalesceMoves(MV.merge(l,r))
1298            end            end
# Line 1292  Line 1300 
1300    end    end
1301    
1302    (*    (*
1303       * Spill propagation.
1304       *)
1305      fun spillPropagation(G as GRAPH{bitMatrix, ...}) nodesToSpill =
1306      let val spillCoalescing = spillCoalescing G
1307          exception SpillProp
1308          val visited = Intmap.new(32, SpillProp) : bool Intmap.intmap
1309          val hasBeenVisited = Intmap.mapWithDefault (visited, false)
1310          val markAsVisited = Intmap.add visited
1311          val member = BM.member(!bitMatrix)
1312    
1313          fun chase(NODE{color=ref(ALIASED n), ...}) = chase n
1314            | chase n = n
1315    
1316          (* compute savings due to spill coalescing.
1317           * The move list must be associated with a colorable node.
1318           *)
1319          fun coalescingSavings([], sc) = sc+sc
1320            | coalescingSavings(MV{dst, src, status=ref LOST, cost, ...}::mvs, sc) =
1321              (case (chase dst, chase src) of
1322                 (dst as NODE{number=d, color=ref(SPILLED ~1), ...},
1323                  src as NODE{number=s, ...}) =>
1324                   if d = s orelse member(dst, src) then coalescingSavings(mvs, sc)
1325                   else coalescingSavings(mvs, sc+cost)
1326               | (dst as NODE{number=d, ...},
1327                  src as NODE{number=s, color=ref(SPILLED ~1),...}) =>
1328                   if d = s orelse member(dst, src) then coalescingSavings(mvs, sc)
1329                   else coalescingSavings(mvs, sc+cost)
1330               | _ => coalescingSavings(mvs, sc)
1331              )
1332            | coalescingSavings(_::mvs, sc) = coalescingSavings(mvs, sc)
1333    
1334          (* Insert all colorable neighbors into worklist *)
1335          fun insert([], worklist) = worklist
1336            | insert((node as NODE{color=ref PSEUDO, number, ...})::adj, worklist) =
1337              if hasBeenVisited number then insert(adj, worklist)
1338              else (markAsVisited (number, true);
1339                    insert(adj, node::worklist))
1340            | insert(_::adj, worklist) = insert(adj, worklist)
1341    
1342          val marker = SPILLED(~1)
1343    
1344          (* Process all nodes from the worklist *)
1345          fun propagate([], new, spilled) = (new, spilled)
1346            | propagate(node::worklist, new, spilled) =
1347              let val NODE{pri=ref spillcost, color, number,
1348                           adj, movelist, ...} = node
1349                  val savings = coalescingSavings(!movelist, 0)
1350              in  if savings >= spillcost then  (* propagate spill *)
1351                     (ra_spill_prop := !ra_spill_prop + 1;
1352                      color := marker; (* spill the node *)
1353                      (* print("Propagating "^Int.toString number^"\n"); *)
1354                      propagate(insert(!adj, worklist), node::new, node::spilled)
1355                     )
1356                  else
1357                     propagate(worklist, new, spilled)
1358              end
1359    
1360          (* Initialize worklist *)
1361          fun init([], worklist) = worklist
1362            | init(NODE{adj, color=ref(SPILLED ~1), ...}::rest, worklist) =
1363                init(rest, insert(!adj, worklist))
1364            | init(_::rest, worklist) = init(rest, worklist)
1365    
1366          (*
1367           * Iterate between spill coalescing and propagation
1368           *)
1369          fun iterate(spillWorkList, spilled) =
1370          let val _ = spillCoalescing spillWorkList
1371              val propagationWorkList = init(spillWorkList, [])
1372              val (newNodes, spilled) = propagate(propagationWorkList, [], spilled)
1373          in  case newNodes of
1374                [] => spilled
1375              | _  => iterate(newNodes, spilled)
1376          end
1377      in  iterate(nodesToSpill, nodesToSpill)
1378      end
1379    
1380      (*
1381     * Spill coloring.     * Spill coloring.
1382     * Assign logical spill locations to all the spill nodes.     * Assign logical spill locations to all the spill nodes.
1383     *)     *)
# Line 1302  Line 1388 
1388        fun selectColor([], currLoc) = ()        fun selectColor([], currLoc) = ()
1389          | selectColor(NODE{color as ref(SPILLED _), number, adj, ...}::nodes,          | selectColor(NODE{color as ref(SPILLED _), number, adj, ...}::nodes,
1390                        currLoc) =                        currLoc) =
1391            let fun chase(NODE{color=ref(ALIASED_SPILL n), ...}) = chase n            let fun chase(NODE{color=ref(ALIASED n), ...}) = chase n
                 | chase(NODE{color=ref(ALIASED n), ...}) = chase n  
1392                  | chase n = n                  | chase n = n
1393                fun neighbors [] = ()                fun neighbors [] = ()
1394                  | neighbors(n::ns) =                  | neighbors(n::ns) =
# Line 1342  Line 1427 
1427        fun set(r, NODE{color=ref(COLORED c),...}) = enter(r, c)        fun set(r, NODE{color=ref(COLORED c),...}) = enter(r, c)
1428          | set(r, NODE{color=ref(ALIASED n),...}) = set(r, n)          | set(r, NODE{color=ref(ALIASED n),...}) = set(r, n)
1429          | set(r, NODE{color=ref(SPILLED _),...}) = enter(r,~1) (* XXX *)          | set(r, NODE{color=ref(SPILLED _),...}) = enter(r,~1) (* XXX *)
         | set(r, NODE{color=ref(ALIASED_SPILL _),...}) = enter(r,~1) (* XXX *)  
1430          | set _ = error "finishRA"          | set _ = error "finishRA"
1431    in  Intmap.app set nodes;    in  Intmap.app set nodes;
1432        case !deadCopies of        case !deadCopies of

Legend:
Removed from v.469  
changed lines
  Added in v.475

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