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 499, Tue Dec 7 15:44:50 1999 UTC revision 545, Thu Feb 24 13:56:44 2000 UTC
# Line 86  Line 86 
86    val bad_freeze    = MLRiscControl.getCounter "bad-freeze"    val bad_freeze    = MLRiscControl.getCounter "bad-freeze"
87   *)   *)
88    
89    val NO_OPTIMIZATION  = 0w0    val NO_OPTIMIZATION     = 0wx0
90    val BIASED_SELECTION = 0w1    val BIASED_SELECTION    = 0wx1
91    val DEAD_COPY_ELIM   = 0w2    val DEAD_COPY_ELIM      = 0wx2
92    val COMPUTE_SPAN     = 0w4    val COMPUTE_SPAN        = 0wx4
93    val SAVE_COPY_TEMPS  = 0w8    val SAVE_COPY_TEMPS     = 0wx8
94      val HAS_PARALLEL_COPIES = 0wx10
95    
96    local    local
97    
# Line 213  Line 214 
214                   val tab = !table                   val tab = !table
215                   val len = A.length tab                   val len = A.length tab
216               in  if !elems < len then               in  if !elems < len then
217                   let fun hashFun(i, j, shift, size) =                   let val index = hashFun(i, j, shift, len)
                      let val i    = W.fromInt i  
                          val j    = W.fromInt j  
                          val h    = W.+(W.<<(i, shift), W.+(i, j))  
                          val mask = W.-(W.fromInt size, 0w1)  
                      in  W.toIntX(W.andb(h, mask)) end  
                      val index = hashFun(i, j, shift, len)  
218                       fun find NIL = false                       fun find NIL = false
219                         | find(B(i',j',b)) = i = i' andalso j = j' orelse find b                         | find(B(i',j',b)) = i = i' andalso j = j' orelse find b
220                       val b = UA.sub(tab, index)                       val b = UA.sub(tab, index)
# Line 404  Line 399 
399                    app prMove (!movelist);                    app prMove (!movelist);
400                    pr "\n"                    pr "\n"
401                   )                   )
402                 else ();                 else ()
                if n = 10 then  
                (pr "defs="; app (fn p => pr(Int.toString p^" ")) (!defs);pr"\n";  
                 pr "uses="; app (fn p => pr(Int.toString p^" ")) (!uses);pr"\n"  
                ) else ()  
403                )                )
404             )             )
405           )           )
# Line 1248  Line 1239 
1239     *)     *)
1240    fun potentialSpillNode (G as G.GRAPH{spillFlag,...}) =    fun potentialSpillNode (G as G.GRAPH{spillFlag,...}) =
1241    let val {markAsFrozen,...} = iteratedCoalescingPhases G    let val {markAsFrozen,...} = iteratedCoalescingPhases G
1242    in  fn {node, stack} =>        val spilled = SPILLED ~1
1243      in  fn {node, cost, stack} =>
1244        let val _ = spillFlag := true (* potential spill found *)        let val _ = spillFlag := true (* potential spill found *)
1245            val (mv, fz, stack) = markAsFrozen(node, FZ.EMPTY, stack)            val (mv, fz, stack) = markAsFrozen(node, FZ.EMPTY, stack)
1246        in  {moveWkl=mv, freezeWkl=fz, stack=stack}        in  if cost < 0.0 then
1247                 let val NODE{color, ...} = node in color := spilled end
1248              else ();
1249              {moveWkl=mv, freezeWkl=fz, stack=stack}
1250        end        end
1251    end    end
1252    
# Line 1290  Line 1285 
1285    
1286        (* Briggs' optimistic spilling heuristic *)        (* Briggs' optimistic spilling heuristic *)
1287        fun optimistic([], spills, stamp) = (spills, stamp)        fun optimistic([], spills, stamp) = (spills, stamp)
1288            | optimistic((node as NODE{color=ref(SPILLED _), ...})::stack,
1289                         spills, stamp) =
1290                 optimistic(stack, node::spills, stamp)
1291          | optimistic((node as NODE{color, (* pair, *) adj, ...})::stack,          | optimistic((node as NODE{color, (* pair, *) adj, ...})::stack,
1292                       spills, stamp) =                       spills, stamp) =
1293            let (* set up the proh array *)            let (* set up the proh array *)
# Line 1309  Line 1307 
1307    
1308        (* Briggs' optimistic spilling heuristic, with biased coloring *)        (* Briggs' optimistic spilling heuristic, with biased coloring *)
1309        fun biasedColoring([], spills, stamp) = (spills, stamp)        fun biasedColoring([], spills, stamp) = (spills, stamp)
1310            | biasedColoring((node as NODE{color=ref(SPILLED _), ...})::stack,
1311                             spills, stamp) =
1312                 biasedColoring(stack, node::spills, stamp)
1313          | biasedColoring(          | biasedColoring(
1314               (node as NODE{number, color, adj,               (node as NODE{number, color, adj,
1315                             (* pair, *) movecnt, movelist,...})::stack,                             (* pair, *) movecnt, movelist,...})::stack,
# Line 1390  Line 1391 
1391        init moves        init moves
1392    end    end
1393    
1394    
1395      (*
1396       * Compute savings due to memory<->register moves
1397       *)
1398      fun moveSavings(GRAPH{memMoves=ref [], ...}) = (fn node => 0)
1399        | moveSavings(GRAPH{memMoves, bitMatrix, ...}) =
1400      let exception Savings
1401          val savingsMap = Intmap.new(32, Savings)
1402                   : {pinned:int,cost:int} Intmap.intmap
1403          val savings = Intmap.mapWithDefault(savingsMap, {pinned= ~1, cost=0})
1404          val addSavings = Intmap.add savingsMap
1405          val member     = BM.member(!bitMatrix)
1406          fun incSavings(u, v, c) =
1407          let val {pinned, cost} = savings u
1408          in  if pinned <> ~1 andalso v <> pinned orelse member(u, v)
1409              then ()
1410              else addSavings(u, {pinned=v, cost=cost + c + c})
1411          end
1412          fun computeSavings(MV{dst, src, cost, ...}) =
1413          let val src as NODE{number=u, color=cu, ...} = chase src
1414              val dst as NODE{number=v, color=cv, ...} = chase dst
1415          in  case (!cu, !cv) of
1416                (SPILLED _, PSEUDO) => incSavings(v, u, cost)
1417              | (PSEUDO, SPILLED _) => incSavings(u, v, cost)
1418              | _ => ()
1419          end
1420      in  app computeSavings (!memMoves);
1421          fn node => #cost(savings node)
1422      end
1423    
1424    (*    (*
1425     * Spill coalescing.     * Spill coalescing.
1426     * Coalesce non-interfering moves between spilled nodes,     * Coalesce non-interfering moves between spilled nodes,
# Line 1483  Line 1514 
1514    end    end
1515    
1516    (*    (*
1517      (*
1518     * Spill propagation.     * Spill propagation.
1519     *)     *)
1520    fun spillPropagation(G as GRAPH{bitMatrix, memRegs, ...}) nodesToSpill =    fun spillPropagation(G as GRAPH{bitMatrix, memRegs, ...}) nodesToSpill =
# Line 1540  Line 1572 
1572                                    adj, movelist, ...})::worklist,                                    adj, movelist, ...})::worklist,
1573                      spilled) =                      spilled) =
1574            let val (pinned, savings) = coalescingSavings(!movelist, ~1, 0)            let val (pinned, savings) = coalescingSavings(!movelist, ~1, 0)
1575            in  if (if pinned >= 0 then savings > spillcost            in  (* if (if pinned >= 0 then savings > spillcost
1576                   else savings >= spillcost) (* XXX *)                   else savings >= spillcost) *) (* XXX *)
1577                  if savings >= spillcost
1578                then  (* propagate spill *)                then  (* propagate spill *)
1579                   (ra_spill_prop := !ra_spill_prop + 1;                   (ra_spill_prop := !ra_spill_prop + 1;
1580                    color := marker; (* spill the node *)                    color := marker; (* spill the node *)
# Line 1584  Line 1617 
1617    (*    (*
1618     * Spill coloring.     * Spill coloring.
1619     * Assign logical spill locations to all the spill nodes.     * Assign logical spill locations to all the spill nodes.
1620       *
1621       * IMPORTANT BUG FIX:
1622       *    Spilled copy temporaries are assigned its own set of colors and
1623       * cannot share with another other nodes.   They can share colors with
1624       * themselves however.
1625     *)     *)
1626    fun spillColoring(GRAPH{spillLoc, ...}) nodesToSpill =    fun spillColoring(GRAPH{spillLoc, copyTmps, mode, ...}) nodesToSpill =
1627    let val proh     = A.array(length nodesToSpill, ~1)    let val proh     = A.array(length nodesToSpill, ~1)
1628        val firstLoc = !spillLoc        val firstLoc = !spillLoc
1629        val _ = spillLoc := firstLoc - 1 (* allocate one location *)        val _ = spillLoc := firstLoc - 1 (* allocate one location first *)
1630        fun selectColor([], currLoc) = ()  
1631          fun colorCopyTmps(tmps) =
1632          let fun loop([], found) = found
1633                | loop(NODE{color as ref(SPILLED ~1), ...}::tmps, found) =
1634                    (color := SPILLED firstLoc; loop(tmps, true))
1635                | loop(_::tmps, found) = loop(tmps, found)
1636          in  if loop(tmps, false) then
1637                 (spillLoc := !spillLoc - 1; firstLoc - 1)
1638              else firstLoc
1639          end
1640    
1641          fun selectColor([], firstColor, currLoc) = ()
1642          | selectColor(NODE{color as ref(SPILLED ~1), number, adj, ...}::nodes,          | selectColor(NODE{color as ref(SPILLED ~1), number, adj, ...}::nodes,
1643                        currLoc) =                        firstColor, currLoc) =
1644            let fun neighbors [] = ()            let fun neighbors [] = ()
1645                  | neighbors(n::ns) =                  | neighbors(n::ns) =
1646                    let fun mark(NODE{color=ref(SPILLED loc), ...}) =                    let fun mark(NODE{color=ref(SPILLED loc), ...}) =
# Line 1604  Line 1653 
1653                    in  mark n end                    in  mark n end
1654                val _ = neighbors(!adj)                val _ = neighbors(!adj)
1655                fun findColor(loc, startingPoint) =                fun findColor(loc, startingPoint) =
1656                    let val loc = if loc < firstLoc then !spillLoc + 1 else loc                    let val loc = if loc < firstColor then !spillLoc + 1 else loc
1657                    in  if A.sub(proh, firstLoc - loc) <> number then loc (* ok *)                    in  if A.sub(proh, firstLoc - loc) <> number then loc (* ok *)
1658                        else if loc = startingPoint then (* new location *)                        else if loc = startingPoint then (* new location *)
1659                        let val loc = !spillLoc                        let val loc = !spillLoc
1660                        in  spillLoc := loc - 1; loc end                        in  spillLoc := loc - 1; loc end
1661                        else findColor(loc - 1, startingPoint)                        else findColor(loc - 1, startingPoint)
1662                    end                    end
1663                val currLoc = if currLoc < firstLoc then !spillLoc + 1                val currLoc = if currLoc < firstColor then !spillLoc + 1
1664                              else currLoc                              else currLoc
1665                val loc = findColor(currLoc, currLoc)                val loc = findColor(currLoc, currLoc)
1666                (* val _ = print("Spill("^Int.toString number^")="^                (* val _ = print("Spill("^Int.toString number^")="^
1667                              Int.toString loc^"\n") *)                              Int.toString loc^"\n") *)
1668            in  color := SPILLED loc;            in  color := SPILLED loc; (* mark with color *)
1669                selectColor(nodes, loc - 1)                selectColor(nodes, firstColor, loc - 1)
1670            end            end
1671          | selectColor(_::nodes, currLoc) = selectColor(nodes, currLoc)          | selectColor(_::nodes, firstColor, currLoc) =
1672    in  selectColor(nodesToSpill, firstLoc)                selectColor(nodes, firstColor, currLoc)
1673    
1674          (* color the copy temporaries first *)
1675           val firstColor = if isOn(mode, HAS_PARALLEL_COPIES)
1676                            then colorCopyTmps(!copyTmps) else firstLoc
1677          (* color the rest of the spilled nodes *)
1678      in  selectColor(nodesToSpill, firstColor, !spillLoc)
1679    end    end
1680      *)
1681    
1682    (*    (*
1683     * Update the regmap, after finishing register allocation.     * Update the regmap, after finishing register allocation.
# Line 1661  Line 1717 
1717     * Clear the interference graph, but keep the nodes     * Clear the interference graph, but keep the nodes
1718     *)     *)
1719    fun clearGraph(GRAPH{bitMatrix, maxRegs, trail, spillFlag,    fun clearGraph(GRAPH{bitMatrix, maxRegs, trail, spillFlag,
1720                         deadCopies, memMoves, ...}) =                         deadCopies, memMoves, copyTmps, ...}) =
1721    let val edges = BM.edges(!bitMatrix)    let val edges = BM.edges(!bitMatrix)
1722    in  trail      := END;    in  trail      := END;
1723        spillFlag  := false;        spillFlag  := false;
       bitMatrix  := BM.empty;  
1724        deadCopies := [];        deadCopies := [];
1725        memMoves   := [];        memMoves   := [];
1726          copyTmps   := [];
1727          bitMatrix  := BM.empty;
1728        bitMatrix  := G.newBitMatrix{edges=edges, maxRegs=maxRegs()}        bitMatrix  := G.newBitMatrix{edges=edges, maxRegs=maxRegs()}
1729    end    end
1730    

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