Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] View of /sml/trunk/src/MLRISC/ra/ra.sml
ViewVC logotype

View of /sml/trunk/src/MLRISC/ra/ra.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 545 - (download) (annotate)
Thu Feb 24 13:56:44 2000 UTC (19 years, 7 months ago) by george
File size: 16808 byte(s)
  Changes to MLTREE
(*
 * This is the new register allocator based on
 * the 'iterated register coalescing' scheme described 
 * in POPL'96, and TOPLAS v18 #3, pp 325-353. 
 *
 * Now with numerous extensions:
 *
 *   0. Dead copy elimination (optional)
 *   1. Priority based coalescing
 *   2. Priority based freezing
 *   3. Priority based spilling
 *   4. Biased selection (optional)
 *   5. Spill Coalescing (optional)
 *   6. Spill Propagation (optional)
 *   7. Spill Coloring (optional)
 *
 * For details, please see the paper from
 *
 *    http://cm.bell-labs.com/cm/cs/what/smlnj/compiler-notes/index.html
 *
 * The basic structure of this register allocator is as follows:
 *   1.  RAGraph.  This module enscapsulates the interference graph 
 *       datatype (adjacency list + interference graph + node table)
 *       and contains nothing architecture specific.
 *   2.  RACore.  This module implements the main part of the iterated
 *       coalescing algorithm, with frequency enhancements.
 *   3.  RA_FLOWGRAPH.  This register allocator is parameterized
 *       with respect to this signature.  This basically abstracts out
 *       the representation of the program flowgraph, and provide
 *       a few services to the main allocator, such as building the 
 *       interference graph, rewriting the flowgraph after spilling,
 *       and rebuilding the interference graph after spilling.  
 *       This module is responsible for caching any information necessary 
 *       to make spilling fast.
 *   4.  This functor.  This functor drives the entire process.
 *
 * -- Allen Leung (leunga@cs.nyu.edu)
 *)

functor RegisterAllocator
   (SpillHeuristics : RA_SPILL_HEURISTICS) 
   (Flowgraph : RA_FLOWGRAPH) : RA =
struct

   structure F      = Flowgraph
   structure I      = F.I
   structure C      = I.C
   structure Core   = RACore
   structure G      = Core.G

   type getreg = { pref  : C.cell list,
                   stamp : int,
                   proh  : int Array.array
                 } -> C.cell

   type mode = word

   type raClient =
   { cellkind     : C.cellkind,             (* kind of register *)
     spillProh    : (C.cell * C.cell) list, (* don't spill these *)
     K            : int,                    (* number of colors *)
     dedicated    : bool Array.array,       (* dedicated registers *)
     getreg       : getreg,                 (* how to find a color *)
     copyInstr    : F.Spill.copyInstr,      (* how to make a copy *)
     spill        : F.Spill.spill,          (* spill callback *)
     spillSrc     : F.Spill.spillSrc,       (* spill callback *)
     spillCopyTmp : F.Spill.spillCopyTmp,   (* spill callback *)
     reload       : F.Spill.reload,         (* reload callback *)
     reloadDst    : F.Spill.reloadDst,      (* reload callback *)
     renameSrc    : F.Spill.renameSrc,      (* rename callback *)
     firstMemReg  : C.cell,
     numMemRegs   : int,
     mode         : mode                    (* mode *)
   } 

   val debug = false

   val NO_OPTIMIZATION      = 0wx0
   val DEAD_COPY_ELIM       = Core.DEAD_COPY_ELIM
   val BIASED_SELECTION     = Core.BIASED_SELECTION
   val HAS_PARALLEL_COPIES  = Core.HAS_PARALLEL_COPIES
   val SPILL_COALESCING     = 0wx100
   val SPILL_COLORING       = 0wx200
   val SPILL_PROPAGATION    = 0wx400
   val COPY_PROPAGATION     = 0wx800

   fun isOn(flag, mask) = Word.andb(flag,mask) <> 0w0

   open G

   fun error msg = MLRiscErrorMsg.error("RegisterAllocator",msg)

   (*
    * Debugging flags + counters
    *)
   val cfg_before_ra     = MLRiscControl.getFlag "dump-cfg-before-ra"
   val cfg_after_ra      = MLRiscControl.getFlag "dump-cfg-after-ra"
   val cfg_after_spill   = MLRiscControl.getFlag "dump-cfg-after-spilling"
   val cfg_before_ras    = MLRiscControl.getFlag "dump-cfg-before-all-ra"
   val cfg_after_ras     = MLRiscControl.getFlag "dump-cfg-after-all-ra"
   val dump_graph        = MLRiscControl.getFlag "dump-interference-graph"
   val debug_spill       = MLRiscControl.getFlag "ra-debug-spilling"
   val ra_count          = MLRiscControl.getCounter "ra-count"
   val rebuild_count     = MLRiscControl.getCounter "ra-rebuild"

(*
   val count_dead        = MLRiscControl.getFlag "ra-count-dead-code"
   val dead              = MLRiscControl.getCounter "ra-dead-code"
 *)
   val debug_stream      = MLRiscControl.debug_stream

   (*
    * Optimization flags
    *)
(*
   val rematerialization = MLRiscControl.getFlag "ra-rematerialization"
 *)

   exception NodeTable

   (* This array is used for getreg.
    * We allocate it once. 
    *) 
   val proh = Array.array(C.firstPseudo, ~1)

   (*
    * Register allocator.  
    *    spillProh is a list of registers that are not candidates for spills.
    *)
   fun ra params flowgraph =
   let 
       (* Flowgraph methods *)
       val {build=buildMethod, spill=spillMethod, ...} = F.services flowgraph 

       (* global spill location counter *)
       val spillLoc=ref ~256

       (* How to dump the flowgraph *)
       fun dumpFlowgraph(flag, title) =
           if !flag then F.dumpFlowgraph(title, flowgraph,!debug_stream) else ()

       (* Main function *)
       fun regalloc{getreg, K, dedicated, copyInstr,
                    spill, spillSrc, spillCopyTmp, renameSrc,
                    reload, reloadDst, spillProh, cellkind, mode, 
                    firstMemReg, numMemRegs} =
       let val numCell = C.numCell cellkind () 
       in  if numCell = 0
       then ()
       else
       let (* extract the regmap and blocks from the flowgraph *)
           val regmap = F.regmap flowgraph (* the register map *)
    
           (* the nodes table *)
           val nodes  = Intmap.new(numCell,NodeTable) 
           val mode   = if isOn(HAS_PARALLEL_COPIES, mode) then
                           Word.orb(Core.SAVE_COPY_TEMPS, mode) 
                        else mode
           (* create an empty interference graph *)
           val G      = G.newGraph{nodes=nodes, 
                                   K=K,
                                   dedicated=dedicated,
                                   numRegs=numCell,
                                   maxRegs=C.maxCell,
                                   regmap=regmap,
                                   showReg=C.toString cellkind,
                                   getreg=getreg,
                                   getpair=fn _ => error "getpair",
                                   firstPseudoR=C.firstPseudo,
                                   proh=proh,
                                   mode=Word.orb(Flowgraph.mode,
                                         Word.orb(mode,SpillHeuristics.mode)),
                                   spillLoc=spillLoc,
                                   firstMemReg=firstMemReg,
                                   numMemRegs=numMemRegs
                                  }
           val G.GRAPH{spilledRegs, pseudoCount, spillFlag, ...} = G
    
           val hasBeenSpilled = Intmap.mapWithDefault (spilledRegs,false)
    
           fun logGraph(header,G) = 
               if !dump_graph then
                   (TextIO.output(!debug_stream,
                        "-------------"^header^"-----------\n");
                    Core.dumpGraph G (!debug_stream) 
                   )
               else ()
    
           (*
            * Build the interference graph 
            *) 
           fun buildGraph(G) = 
           let val _ = if debug then print "build..." else ()
               val moves = buildMethod(G,cellkind)
               val worklists = 
                   (Core.initWorkLists G) {moves=moves} 
           in  (* if !count_dead then
                  Intmap.app (fn (_,NODE{uses=ref [],...}) => dead := !dead + 1
                               | _ => ()) nodes
               else (); *)
               logGraph("build",G);
               if debug then
               let val G.GRAPH{bitMatrix=ref(G.BM{elems, ...}), ...} = G
               in  print ("done: nodes="^Int.toString(Intmap.elems nodes)^ 
                          " edges="^Int.toString(!elems)^
                          " moves="^Int.toString(length moves)^
                          "\n")
               end else (); 
               worklists
           end
    
           (*
            * Potential spill phase
            *) 
           fun chooseVictim{spillWkl} =
           let fun dumpSpillCandidates(spillWkl) =
                   (print "Spill candidates:\n";
                    app (fn n => print(Core.show G n^" ")) spillWkl;
                    print "\n"
                   )
               (* Initialize if it is the first time we spill *)
               val _ = if !spillFlag then () else SpillHeuristics.init()
               (* Choose a node *)
               val {node,cost,spillWkl} =
                   SpillHeuristics.chooseSpillNode
                       {graph=G, hasBeenSpilled=hasBeenSpilled,
                        spillWkl=spillWkl}
                    handle SpillHeuristics.NoCandidate =>
                      (Core.dumpGraph G (!debug_stream);
                       dumpSpillCandidates(spillWkl);
                       error ("chooseVictim")
                      )
           in  if !debug_spill then
                  (case node of
                     NONE => ()
                   | SOME(best as NODE{defs,uses,...}) =>
                        print("Spilling node "^Core.show G best^
                              " cost="^Real.toString cost^
                              " defs="^Int.toString(length(!defs))^
                              " uses="^Int.toString(length(!uses))^"\n"
                             )
                  ) else ();
               {node=node,cost=cost,spillWkl=spillWkl}
           end 
              
           (*
            * Mark spill nodes
            *)
           fun markSpillNodes nodesToSpill =
           let val marker = SPILLED(~1)
               fun loop [] = ()
                 | loop(NODE{color, ...}::ns) = (color := marker; loop ns)
           in  loop nodesToSpill end

           (* Mark nodes that are immediately aliased to mem regs;
            * These are nodes that need also to be spilled
            *)
           fun markMemRegs [] = ()
             | markMemRegs(NODE{number=r, color as ref(ALIASED
                          (NODE{color=ref(col as SPILLED c), ...})), ...}::ns) =
                (if c >= 0 then color := col else ();
                 markMemRegs ns)
             | markMemRegs(_::ns) = markMemRegs ns
      
           (*
            * Actual spill phase.  
            *   Insert spill node and incrementally 
            *   update the interference graph. 
            *)
           fun actualSpills{spills} = 
           let val _ = if debug then print "spill..." else (); 
               val _ = if isOn(mode, 
                               SPILL_COALESCING+
                               SPILL_PROPAGATION+
                               SPILL_COLORING) then
                           markSpillNodes spills
                       else ()
               val _ = if isOn(mode,SPILL_PROPAGATION+SPILL_COALESCING) then   
                          Core.initMemMoves G 
                       else ()
               (*
               val spills = if isOn(mode,SPILL_PROPAGATION) then   
                               Core.spillPropagation G spills else spills
               val _ = if isOn(mode,SPILL_COALESCING) then 
                          Core.spillCoalescing G spills else ()
               val _ = if isOn(mode,SPILL_COLORING) then 
                          Core.spillColoring G spills else ()
               val _ = if isOn(mode,SPILL_COALESCING+SPILL_PROPAGATION) then 
                          markMemRegs spills else ()
                *)
               val _ = logGraph("actual spill",G);
               val {simplifyWkl,freezeWkl,moveWkl,spillWkl} =  
                    Core.initWorkLists G
                       {moves=spillMethod{graph=G, cellkind=cellkind,
                                          spill=spill, spillSrc=spillSrc,
                                          spillCopyTmp=spillCopyTmp,
                                          renameSrc=renameSrc,
                                          reload=reload, reloadDst=reloadDst,
                                          copyInstr=copyInstr, nodes=spills
                                         }
                       }
               val _ = dumpFlowgraph(cfg_after_spill,"after spilling")
           in  logGraph("rebuild",G);
               if debug then print "done\n" else ();
               rebuild_count := !rebuild_count + 1;
               (simplifyWkl, moveWkl, freezeWkl, spillWkl, [])
           end
           
           (*
            * Main loop of the algorithm
            *)
           fun main(G) =
           let 
                   
               (* Main loop *) 
               fun loop(simplifyWkl,moveWkl,freezeWkl,spillWkl,stack) =
               let val iteratedCoal = Core.iteratedCoalescing G
                   val potentialSpill = Core.potentialSpillNode G
                   (* simplify/coalesce/freeze/potential spill phases 
                    *    simplifyWkl -- non-move related nodes with low degree 
                    *    moveWkl     -- moves to be considered for coalescing
                    *    freezeWkl   -- move related nodes (with low degree)
                    *    spillWkl    -- potential spill nodes
                    *    stack       -- simplified nodes
                    *)
                   fun iterate(simplifyWkl,moveWkl,freezeWkl,spillWkl,stack) =
                   let (* perform iterated coalescing *)
                       val {stack} = iteratedCoal{simplifyWkl=simplifyWkl,
                                                  moveWkl=moveWkl,
                                                  freezeWkl=freezeWkl,
                                                  stack=stack}
                   in  case spillWkl of
                         [] => stack (* nothing to spill *)
                       |  _ => 
                         if !pseudoCount = 0 (* all nodes simplified *)
                         then stack 
                         else
                         let val {node,cost,spillWkl} = 
                                    chooseVictim{spillWkl=spillWkl}
                         in  case node of  
                               SOME node => (* spill node and continue *)
                               let val _ = if debug then print "-" else () 
                                   val {moveWkl,freezeWkl,stack} = 
                                       potentialSpill{node=node,
                                                      cost=cost,
                                                      stack=stack}
                               in  iterate([],moveWkl,freezeWkl,spillWkl,stack)
                               end 
                             | NONE => stack (* nothing to spill *)
                         end
                   end

                   (* simplify the nodes *)
                   val stack = iterate
                          (simplifyWkl,moveWkl,freezeWkl,spillWkl,stack)
                   (* color the nodes *)
                   val {spills} = (Core.select G) {stack=stack} 
               in  (* check for actual spills *)
                   case spills of
                     [] => ()
                   | spills => 
                     (if isOn(mode,COPY_PROPAGATION) then ()
                      else loop(actualSpills{spills=spills})
                     )
               end
    
               val {simplifyWkl, moveWkl, freezeWkl, spillWkl} = buildGraph G
    
           in  loop(simplifyWkl, moveWkl, freezeWkl, spillWkl, [])
           end
    
           fun initSpillProh(from,to) = 
           let val markAsSpilled = Intmap.add spilledRegs
               fun loop r = 
                   if r <= to then (markAsSpilled(r,true); loop(r+1)) else ()
           in  loop from end
    
       in  dumpFlowgraph(cfg_before_ra,"before register allocation");
           app initSpillProh spillProh;
           main(G); (* main loop *)
           (* update the regmap *)
           logGraph("done",G);
           if isOn(mode,COPY_PROPAGATION) 
           then Core.finishCP G 
           else Core.finishRA G
           ;
           ra_count := !ra_count + 1;
           dumpFlowgraph(cfg_after_ra,"after register allocation");
           (* Clean up spilling *)
           SpillHeuristics.init() 
       end
       end

       fun regallocs [] = ()
         | regallocs(p::ps) = (regalloc p; regallocs ps)

   in  dumpFlowgraph(cfg_before_ras,"before register allocation");
       regallocs params;
       dumpFlowgraph(cfg_after_ras,"after register allocation");
       flowgraph
   end

end

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