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 733, Fri Nov 17 05:13:45 2000 UTC revision 744, Fri Dec 8 04:11:42 2000 UTC
# Line 54  Line 54 
54   *   *
55   *)   *)
56    
57    local
58    
59       val debug = false
60       val tally = false
61    
62    in
63    
64  structure RACore : RA_CORE =  structure RACore : RA_CORE =
65  struct  struct
66    
# Line 62  Line 69 
69    structure W    = Word    structure W    = Word
70    structure W8A  = Word8Array    structure W8A  = Word8Array
71    structure W8   = Word8    structure W8   = Word8
72      structure C    = RAGraph.C
73    
74    (* For debugging, uncomment Unsafe. *)    (* For debugging, uncomment Unsafe. *)
75    structure UA   = Unsafe.Array    structure UA   = Unsafe.Array
# Line 69  Line 77 
77    
78    open G    open G
79    
   val debug = false  
 (*  val tally = false *)  
   
   
80    val verbose       = MLRiscControl.getFlag "ra-verbose"    val verbose       = MLRiscControl.getFlag "ra-verbose"
81    val ra_spill_coal = MLRiscControl.getCounter "ra-spill-coalescing"    val ra_spill_coal = MLRiscControl.getCounter "ra-spill-coalescing"
82    val ra_spill_prop = MLRiscControl.getCounter "ra-spill-propagation"    val ra_spill_prop = MLRiscControl.getCounter "ra-spill-propagation"
# Line 98  Line 102 
102    val MEMORY_COALESCING      =    val MEMORY_COALESCING      =
103        SPILL_COALESCING + SPILL_COLORING + SPILL_PROPAGATION        SPILL_COALESCING + SPILL_COLORING + SPILL_PROPAGATION
104    
105      val i2s = Int.toString
106    
107    local    local
108    
# Line 363  Line 368 
368    fun chase(NODE{color=ref(ALIASED r), ...}) = chase r    fun chase(NODE{color=ref(ALIASED r), ...}) = chase r
369      | chase x = x      | chase x = x
370    
371    fun colorOf(G.GRAPH{showReg,...}) (NODE{number, color, pri,...}) =    fun cellId(C.CELL{id, ...}) = id
372         showReg number^  
373             (case !color of    fun col2s col =
374           case col of
375                PSEUDO     => ""                PSEUDO     => ""
376              | REMOVED    => "r"              | REMOVED    => "r"
377              | ALIASED _  => "a"              | ALIASED _  => "a"
378              | COLORED c  => "["^showReg c^"]"         | COLORED c  => "["^i2s c^"]"
379              | MEMREG  m  => "m" ^ "{" ^ Int.toString m ^ "}"         | MEMREG (_,m)  => "m" ^ "{" ^ C.toString m ^ "}"
380              | SPILLED    => "s"              | SPILLED    => "s"
381              | SPILL_LOC c  => "s" ^ "{" ^ Int.toString c ^ "}"         | SPILL_LOC c  => "s" ^ "{" ^ i2s c ^ "}"
382             (*esac*))  
383      fun node2s (NODE{cell, color, pri,...}) = i2s(cellId cell)^col2s(!color)
384    
385    fun show G (node as NODE{pri,...}) =    fun show G (node as NODE{pri,...}) =
386        colorOf G node^(if !verbose then "("^Int.toString(!pri)^")" else "")        node2s node^(if !verbose then "("^i2s(!pri)^")" else "")
387    
388    (*    (*
389     * Dump the interference graph     * Dump the interference graph
# Line 384  Line 391 
391    fun dumpGraph(G as G.GRAPH{nodes, showReg, K,...}) stream =    fun dumpGraph(G as G.GRAPH{nodes, showReg, K,...}) stream =
392    let fun pr s = TextIO.output(stream, s)    let fun pr s = TextIO.output(stream, s)
393        val show = show G        val show = show G
       val colorOf = colorOf G  
394        fun prMove(MV{src, dst, status=ref(WORKLIST | BRIGGS_MOVE | GEORGE_MOVE),        fun prMove(MV{src, dst, status=ref(WORKLIST | BRIGGS_MOVE | GEORGE_MOVE),
395                      cost,...}) =                      cost,...}) =
396              pr(colorOf(chase dst)^" <- "^colorOf(chase src)^              pr(node2s(chase dst)^" <- "^node2s(chase src)^
397                 "("^Int.toString(cost)^") ")                 "("^i2s(cost)^") ")
398          | prMove _ = ()          | prMove _ = ()
399    
400        fun prAdj(n,n' as NODE{adj, degree, uses, defs,        fun prAdj(n,n' as NODE{adj, degree, uses, defs,
401                               color, pri, movecnt, movelist, ...}) =                               color, pri, movecnt, movelist, ...}) =
402            (pr(show n');            (pr(show n');
403             if !verbose then pr(" deg="^Int.toString(!degree)) else ();             if !verbose then pr(" deg="^i2s(!degree)) else ();
404             (case !color of             (case !color of
405                ALIASED n => (pr " => "; pr(show n); pr "\n")                ALIASED n => (pr " => "; pr(show n); pr "\n")
406              | _ =>              | _ =>
407                (pr(" <-->");                (pr(" <-->");
408                 app (fn n => (pr " "; pr(show n))) (!adj); pr "\n";                 app (fn n => (pr " "; pr(show n))) (!adj); pr "\n";
409                 if !verbose andalso !movecnt > 0 then                 if !verbose andalso !movecnt > 0 then
410                   (pr("\tmoves "^Int.toString(!movecnt)^": ");                   (pr("\tmoves "^i2s(!movecnt)^": ");
411                    app prMove (!movelist);                    app prMove (!movelist);
412                    pr "\n"                    pr "\n"
413                   )                   )
# Line 410  Line 416 
416             )             )
417           )           )
418    
419    in  pr("=========== K="^Int.toString K^" ===========\n");    in  pr("=========== K="^i2s K^" ===========\n");
420        app prAdj (ListMergeSort.sort (fn ((x, _),(y, _)) => x > y)        app prAdj (ListMergeSort.sort (fn ((x, _),(y, _)) => x > y)
421                      (IntHashTable.listItemsi nodes))                      (IntHashTable.listItemsi nodes))
422    end    end
# Line 424  Line 430 
430    let val getnode = IntHashTable.lookup nodes    let val getnode = IntHashTable.lookup nodes
431        val addnode = IntHashTable.insert nodes        val addnode = IntHashTable.insert nodes
432    
433          fun colorOf(C.CELL{col=ref(C.MACHINE r), ...}) = r
434            | colorOf(C.CELL{id, ...}) = id
435    
436        fun defUse{defs, uses, pt, cost} =        fun defUse{defs, uses, pt, cost} =
437        let  fun def reg =        let  fun def cell =
438             let val node as NODE{pri, defs,...} = getnode reg             let val reg = colorOf cell
439               in  let val node as NODE{pri, defs,...} = getnode reg
440             in  pri := !pri + cost;(* increment the priority by the cost *)             in  pri := !pri + cost;(* increment the priority by the cost *)
441                 defs := pt :: !defs;                 defs := pt :: !defs;
442                 node                 node
443             end             end
444             handle _ =>             handle _ =>
445             let val col = if reg < firstPseudoR then COLORED(reg) else PSEUDO                 let val C.CELL{col, ...} = cell
446                       val col = case !col of
447                                   C.MACHINE r => COLORED r
448                                 | C.PSEUDO    => PSEUDO
449                                 | C.ALIASED _ => error "newNodes.def ALIASED"
450                                 | C.SPILLED   => error "newNodes.def SPILLED"
451                 val node =                 val node =
452                     NODE{number=reg, color=ref col, degree=ref 0,                         NODE{number=reg,
453                                cell=cell, color=ref col, degree=ref 0,
454                          adj=ref [], movecnt=ref 0, movelist = ref [],                          adj=ref [], movecnt=ref 0, movelist = ref [],
455                          movecost=ref 0, (* pair=false, *) pri=ref cost,                          movecost=ref 0, (* pair=false, *) pri=ref cost,
456                          defs=ref [pt], uses=ref []}                          defs=ref [pt], uses=ref []}
457             in addnode(reg, node); node             in addnode(reg, node); node
458             end             end
459             fun use reg =             end
460             let val node as NODE{pri, uses,...} = getnode reg             fun use cell =
461               let val reg = colorOf cell
462               in  let val node as NODE{pri, uses,...} = getnode reg
463             in  pri := !pri + cost; (* increment the priority by the cost *)             in  pri := !pri + cost; (* increment the priority by the cost *)
464                 uses := pt :: !uses                 uses := pt :: !uses
465             end             end
466             handle _ =>             handle _ =>
467             let val col = if reg < firstPseudoR then COLORED(reg) else PSEUDO                 let val C.CELL{col, ...} = cell
468                       val col = case !col of
469                                   C.MACHINE r => COLORED r
470                                 | C.PSEUDO    => PSEUDO
471                                 | C.ALIASED _ => error "newNodes.use ALIASED"
472                                 | C.SPILLED   => error "newNodes.use SPILLED"
473                 val node =                 val node =
474                     NODE{number=reg, color=ref col, degree=ref 0,                     NODE{number=reg, color=ref col, degree=ref 0,
475                          adj=ref [], movecnt=ref 0, movelist = ref [],                          adj=ref [], movecnt=ref 0, movelist = ref [],
476                          movecost=ref 0, (* pair=false, *)                          movecost=ref 0, (* pair=false, *)
477                          pri=ref cost, defs=ref [], uses=ref[pt]                              pri=ref cost, defs=ref [], uses=ref[pt], cell=cell
478                         }                         }
479             in addnode(reg, node)             in addnode(reg, node)
480             end             end
481               end
482             fun defAll([],ds) = ds | defAll(r::rs,ds) = defAll(rs,def r::ds)             fun defAll([],ds) = ds | defAll(r::rs,ds) = defAll(rs,def r::ds)
483             fun useAll [] = () | useAll(r::rs) = (use r; useAll rs)             fun useAll [] = () | useAll(r::rs) = (use r; useAll rs)
484             val defs = defAll(defs,[])             val defs = defAll(defs,[])
# Line 473  Line 497 
497     * Now we allow spilled node to be added to the edge; these do not     * Now we allow spilled node to be added to the edge; these do not
498     * count toward the degree.     * count toward the degree.
499     *)     *)
500    fun addEdge(GRAPH{bitMatrix,...}) = let    fun addEdge(GRAPH{bitMatrix,...}) =
501      val addBitMatrix = BM.add(!bitMatrix)    let val addBitMatrix = BM.add(!bitMatrix)
   
     fun noEdges(COLORED _) = true  
       | noEdges(SPILLED) = true  
       | noEdges(SPILL_LOC _) = true  
       | noEdges(MEMREG _) = true  
       | noEdges _ = false  
   
502    in  fn (x as NODE{number=xn, color=colx, adj=adjx, degree=degx, ...},    in  fn (x as NODE{number=xn, color=colx, adj=adjx, degree=degx, ...},
503            y as NODE{number=yn, color=coly, adj=adjy, degree=degy, ...}) =>            y as NODE{number=yn, color=coly, adj=adjy, degree=degy, ...}) =>
504            if xn = yn then ()            if xn = yn then ()
# Line 490  Line 507 
507                  (PSEUDO,      PSEUDO) => (adjx := y :: !adjx; degx := !degx + 1;                  (PSEUDO,      PSEUDO) => (adjx := y :: !adjx; degx := !degx + 1;
508                                            adjy := x :: !adjy; degy := !degy + 1)                                            adjy := x :: !adjy; degy := !degy + 1)
509                | (PSEUDO,   COLORED _) => (adjx := y :: !adjx; degx := !degx + 1)                | (PSEUDO,   COLORED _) => (adjx := y :: !adjx; degx := !degx + 1)
               | (COLORED _,   PSEUDO) => (adjy := x :: !adjy; degy := !degy + 1)  
   
510                | (PSEUDO,    MEMREG _) => (adjx := y :: !adjx; adjy := x :: !adjy)                | (PSEUDO,    MEMREG _) => (adjx := y :: !adjx; adjy := x :: !adjy)
               | (PSEUDO,     SPILLED) => (adjx := y :: !adjx; adjy := x :: !adjy)  
511                | (PSEUDO, SPILL_LOC _) => (adjx := y :: !adjx; adjy := x :: !adjy)                | (PSEUDO, SPILL_LOC _) => (adjx := y :: !adjx; adjy := x :: !adjy)
512               | (PSEUDO,     SPILLED) => ()
513               | (COLORED _,   PSEUDO) => (adjy := x:: !adjy; degy := !degy+1)
514               | (COLORED _, COLORED _) => () (* x<>y, can't alias *)
515               | (COLORED _, MEMREG _) => () (* x<>y, can't alias *)
516               | (COLORED _, SPILL_LOC _) => () (* x<>y, can't alias *)
517               | (COLORED _,   SPILLED) => ()
518                | (MEMREG _,    PSEUDO) => (adjx := y :: !adjx; adjy := x :: !adjy)                | (MEMREG _,    PSEUDO) => (adjx := y :: !adjx; adjy := x :: !adjy)
519                | (SPILLED,     PSEUDO) => (adjx := y :: !adjx; adjy := x :: !adjy)             | (MEMREG _, COLORED _) => ()   (* x<>y, can't alias *)
520               | (MEMREG _,  MEMREG _) => ()   (* x<>y, can't alias *)
521               | (MEMREG _, SPILL_LOC _) => () (* x<>y, can't alias *)
522               | (MEMREG _,   SPILLED) => ()
523                | (SPILL_LOC _, PSEUDO) => (adjx := y :: !adjx; adjy := x :: !adjy)                | (SPILL_LOC _, PSEUDO) => (adjx := y :: !adjx; adjy := x :: !adjy)
524                | _ =>             | (SPILL_LOC _, COLORED _) => ()     (* x<>y, can't alias *)
525                    if (noEdges (!colx) andalso noEdges(!coly)) then ()             | (SPILL_LOC _, MEMREG _) => ()    (* x<>y, can't alias *)
526                    else error "addEge"             | (SPILL_LOC _, SPILL_LOC _) => () (* x<>y, can't alias *)
527               | (SPILL_LOC _, SPILLED) => () (* x<>y, can't alias *)
528               | (SPILLED,  _) => ()
529               | (colx, coly) =>
530                   error("addEdge x="^i2s xn^col2s colx^" y="^i2s yn^col2s coly)
531                )                )
532            else () (* edge already there *)            else () (* edge already there *)
533    end    end
# Line 517  Line 544 
544     * Initialize a list of worklists     * Initialize a list of worklists
545     *)     *)
546    fun initWorkLists    fun initWorkLists
547          (GRAPH{nodes, K, bitMatrix, regmap, pseudoCount, blockedCount,          (GRAPH{nodes, K, bitMatrix, pseudoCount, blockedCount,
548                 firstPseudoR, deadCopies, memMoves, mode, ...}) {moves} =                 firstPseudoR, deadCopies, memMoves, mode, ...}) {moves} =
549    let    let
550        (* Filter moves that already have an interference        (* Filter moves that already have an interference
# Line 556  Line 583 
583          | filterDead((mv as          | filterDead((mv as
584                    MV{src as NODE{number=x, color as ref colSrc,                    MV{src as NODE{number=x, color as ref colSrc,
585                                   pri, adj, uses,...},                                   pri, adj, uses,...},
586                       dst as NODE{number=y, color=ref colDst,                       dst as NODE{number=y, cell=celly, color=ref colDst,
587                                   defs=dstDefs, uses=dstUses,...},                                   defs=dstDefs, uses=dstUses,...},
588                       cost, ...})::mvs,                       cost, ...})::mvs,
589                   mvs', mem, dead) =                   mvs', mem, dead) =
# Line 580  Line 607 
607                     uses := uses';                     uses := uses';
608                     color := ALIASED src;                     color := ALIASED src;
609                     decDegree(!adj);                     decDegree(!adj);
610                     filterDead(mvs, mvs', mem, y::dead)                     filterDead(mvs, mvs', mem, celly::dead)
611                 end                 end
612               | _ =>  (* normal moves *)               | _ =>  (* normal moves *)
613                 if member(x, y)     (* moves that interfere *)                 if member(x, y)     (* moves that interfere *)
# Line 632  Line 659 
659    end    end
660    
661    (*    (*
    * Return a regmap that reflects the current interference graph.  
    * Spilled registers are given the special value ~1  
    *)  
   fun regmap(G.GRAPH{nodes,...}) =  
   let val getnode = IntHashTable.lookup nodes  
       fun num(NODE{color=ref(COLORED r),...}) = r  
         | num(NODE{color=ref(ALIASED n),...}) = num n  
         | num(NODE{color=ref(SPILL_LOC _), ...}) = ~1  
         | num(NODE{color=ref(SPILLED), ...}) = ~1  
         | num(NODE{color=ref(MEMREG m), ...}) = m  
         | num(NODE{number, color=ref PSEUDO,...}) = number  
         | num _ = error "regmap"  
       fun lookup r = num(getnode r) handle e => r  
   in lookup  
   end  
   
   (*  
    * Return a regmap that reflects the current interference graph,  
    * during spilling.  
    *)  
   fun spillRegmap(G.GRAPH{nodes,...}) =  
   let val getnode = IntHashTable.lookup nodes  
       fun num(NODE{color=ref(COLORED r),...}) = r  
         | num(NODE{color=ref(ALIASED n),...}) = num n  
         | num(NODE{color=ref(SPILL_LOC _), number, ...}) = number  
         | num(NODE{color=ref(SPILLED), number, ...}) = number  
         | num(NODE{color=ref(MEMREG _), number, ...}) = number  
         | num(NODE{number, color=ref PSEUDO,...}) = number  
         | num _ = error "spillRegmap"  
       fun lookup r = num(getnode r) handle e => r  
   in  lookup  
   end  
   
   (*  
662     * Return a regmap that returns the current spill location     * Return a regmap that returns the current spill location
663     * during spilling.     * during spilling.
664     *)     *)
# Line 674  Line 667 
667        fun num(NODE{color=ref(ALIASED n), ...}) = num n        fun num(NODE{color=ref(ALIASED n), ...}) = num n
668          | num(NODE{color=ref(SPILLED), number, ...}) = number          | num(NODE{color=ref(SPILLED), number, ...}) = number
669          | num(NODE{color=ref(SPILL_LOC s), number, ...}) = ~s          | num(NODE{color=ref(SPILL_LOC s), number, ...}) = ~s
670          | num(NODE{color=ref(MEMREG m), number, ...}) = m          | num(NODE{color=ref(MEMREG(m, _)), number, ...}) = m
671          | num(NODE{number, ...}) = number          | num(NODE{number, ...}) = number
672        fun lookup r = num(getnode r) handle e => r        fun lookup r = num(getnode r) handle _ => r
673      in  lookup
674      end
675    
676      fun spillLocToString(G.GRAPH{nodes,...}) =
677      let val getnode = IntHashTable.lookup nodes
678          fun num(NODE{color=ref(ALIASED n), ...}) = num n
679            | num(NODE{color=ref(SPILLED), cell, ...}) = "spilled "^C.toString cell
680            | num(NODE{color=ref(SPILL_LOC s), number, ...}) = "frame "^i2s s
681            | num(NODE{color=ref(MEMREG(_,m)), ...}) = "memreg "^C.toString m
682            | num(NODE{number, ...}) = "error "^i2s number
683          fun lookup r = num(getnode r)
684    in  lookup    in  lookup
685    end    end
686    
# Line 741  Line 745 
745                      (* false, *) mv, fz, stack) =                      (* false, *) mv, fz, stack) =
746             (* normal edge *)             (* normal edge *)
747            (if debug then            (if debug then
748             print("DecDegree "^show node^" d="^Int.toString(d-1)^"\n") else ();             print("DecDegree "^show node^" d="^i2s(d-1)^"\n") else ();
749             degree := K - 1;             degree := K - 1;
750             (* node is now low degree!!! *)             (* node is now low degree!!! *)
751             let val mv = enableMoves(!adj, mv)             let val mv = enableMoves(!adj, mv)
# Line 1029  Line 1033 
1033                         COLORED _ => (v, u)                         COLORED _ => (v, u)
1034                       | _         => (u, v)                       | _         => (u, v)
1035               val _ = if debug then print ("Coalescing "^show u^"<->"^show v               val _ = if debug then print ("Coalescing "^show u^"<->"^show v
1036                           ^" ("^Int.toString cost^")") else ()                           ^" ("^i2s cost^")") else ()
1037               val mv = MV.merge(l, r)               val mv = MV.merge(l, r)
1038               fun coalesceIt(status, v) =               fun coalesceIt(status, v) =
1039                  (status := COALESCED;                  (status := COALESCED;
# Line 1100  Line 1104 
1104              node as NODE{number=me, degree,              node as NODE{number=me, degree,
1105                           adj, movelist, movecnt as ref mc,...},                           adj, movelist, movecnt as ref mc,...},
1106              fz, stack) =              fz, stack) =
1107        let val _ = if debug then print("Mark as frozen "^Int.toString me^"\n")        let val _ = if debug then print("Mark as frozen "^i2s me^"\n")
1108                    else ()                    else ()
1109            (* eliminate all moves, return a list of nodes that            (* eliminate all moves, return a list of nodes that
1110             * can be simplified             * can be simplified
# Line 1178  Line 1182 
1182                       in  if !blocked = 0                       in  if !blocked = 0
1183                           then ((* print "[no freezing again]"; *) stack)                           then ((* print "[no freezing again]"; *) stack)
1184                           else ((* print("[freezing again "^                           else ((* print("[freezing again "^
1185                                 Int.toString(!blocked)^"]"); *)                                 i2s(!blocked)^"]"); *)
1186                                 loop(FZ.merge(fz, newFz), FZ.EMPTY, stack))                                 loop(FZ.merge(fz, newFz), FZ.EMPTY, stack))
1187                       end                       end
1188                    | _ =>                    | _ =>
# Line 1186  Line 1190 
1190                       loop(fz, newFz, stack))                       loop(fz, newFz, stack))
1191                end                end
1192        in  if !blocked = 0 then ((* print "[no freezing]"; *) stack)        in  if !blocked = 0 then ((* print "[no freezing]"; *) stack)
1193            else ((* print("[freezing "^Int.toString(!blocked)^"]"); *)            else ((* print("[freezing "^i2s(!blocked)^"]"); *)
1194                  loop(fz, FZ.EMPTY, stack))                  loop(fz, FZ.EMPTY, stack))
1195        end        end
1196    
# Line 1422  Line 1426 
1426    let exception Savings    let exception Savings
1427        val savingsMap = IntHashTable.mkTable(32, Savings)        val savingsMap = IntHashTable.mkTable(32, Savings)
1428                 : {pinned:int,cost:int} IntHashTable.hash_table                 : {pinned:int,cost:int} IntHashTable.hash_table
1429        fun savings i = getOpt (IntHashTable.find savingsMap i,        val savings = IntHashTable.find savingsMap
1430                                { pinned = ~1, cost = 0 })        val savings = fn r => case savings r of NONE => {pinned= ~1, cost=0}
1431                                                | SOME s => s
1432        val addSavings = IntHashTable.insert savingsMap        val addSavings = IntHashTable.insert savingsMap
1433        val member     = BM.member(!bitMatrix)        val member     = BM.member(!bitMatrix)
1434        fun incSavings(u, v, c) =        fun incSavings(u, v, c) =
# Line 1449  Line 1454 
1454    end    end
1455    
1456    (*    (*
1457     * Update the regmap, after finishing register allocation.     * Update the color of cells
    * All nodes must have been colored.  
1458     *)     *)
1459    fun finishRA(GRAPH{regmap, nodes, deadCopies, ...}) =    fun updateCellColors(GRAPH{nodes, deadCopies, ...}) =
1460    let val enter = IntHashTable.insert regmap    let fun enter(C.CELL{col, ...},c) = col := c
1461        fun set(r, NODE{color=ref(COLORED c),...}) = enter(r, c)        fun cellOf(NODE{cell, ...}) = cell
1462          | set(r, NODE{color=ref(ALIASED n),...}) = set(r, n)        fun set(NODE{cell, color=ref(COLORED c),...}) =
1463          | set(r, NODE{color=ref(SPILLED),...}) =  enter(r, ~1)              enter(cell, C.MACHINE c)
1464          | set(r, NODE{color=ref(SPILL_LOC s),...}) =  enter(r, ~1)          | set(NODE{cell, color=ref(ALIASED alias),...}) =
1465          | set(r, NODE{color=ref(MEMREG m),...}) =  enter(r, m)              enter(cell, C.ALIASED(cellOf alias))
1466          | set(r, _) = error("finishRA "^Int.toString r)          | set(NODE{cell, color=ref(SPILLED),...}) =
1467    in  IntHashTable.appi set nodes;              enter(cell, C.SPILLED)
1468        case !deadCopies of          | set(NODE{cell, color=ref(SPILL_LOC s),...}) =
1469          [] => ()              enter(cell, C.SPILLED)
1470        | dead => app (fn r => enter(r, ~1)) dead          | set(NODE{cell, color=ref(MEMREG(m, _)),...})=
1471                enter(cell, C.MACHINE m)
1472            | set(NODE{cell, color=ref PSEUDO, ...}) = ()
1473            | set(_) = error("updateCellColors")
1474      in  IntHashTable.app set nodes
1475    end    end
1476    
1477    (*    (*
1478     * Update the regmap, after copy propagation     * Update aliases before spill rewriting.
1479     *)     *)
1480    fun finishCP(GRAPH{regmap, nodes,...}) =    fun updateCellAliases(GRAPH{nodes, deadCopies, ...}) =
1481    let val enter = IntHashTable.insert regmap    let fun enter(C.CELL{col, ...},c) = col := c
1482    in  IntHashTable.appi        fun cellOf(NODE{cell, ...}) = cell
1483          (fn (r, node as NODE{color as ref(ALIASED _),...}) =>        fun set(NODE{cell, color=ref(COLORED c),...}) = ()
1484              (case chase node of          | set(NODE{cell, color=ref(ALIASED alias),...}) =
1485                 NODE{color=ref(COLORED c),...} => enter(r, c)              enter(cell, C.ALIASED(cellOf alias))
1486               | NODE{color=ref PSEUDO, number,...} => enter(r, number)          | set(NODE{cell, color=ref(SPILLED),...}) = ()
1487               | NODE{color=ref REMOVED, number,...} => enter(r, number)          | set(NODE{cell, color=ref(SPILL_LOC s),...}) = ()
1488               | _ => error "finishCP"          | set(NODE{cell, color=ref(MEMREG _),...})= ()
1489              )          | set(NODE{cell, color=ref PSEUDO, ...}) = ()
1490            | _ => ()          | set(_) = error("updateCellAliases")
1491          ) nodes    in  IntHashTable.app set nodes
1492      end
1493    
1494      fun markDeadCopiesAsSpilled(GRAPH{deadCopies, ...}) =
1495      let fun enter(C.CELL{col, ...},c) = col := c
1496      in  case !deadCopies of
1497            [] => ()
1498          | dead => app (fn r => enter(r, C.SPILLED)) dead
1499    end    end
1500    
1501    (*    (*
# Line 1509  Line 1524 
1524    end (* local *)    end (* local *)
1525    
1526  end  end
1527    
1528    end (* local *)

Legend:
Removed from v.733  
changed lines
  Added in v.744

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