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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 576 - (download) (annotate)
Fri Mar 10 07:27:16 2000 UTC (19 years, 4 months ago) by leunga
File size: 7056 byte(s)

More assembly output problems involving the indexed addressing mode
on the x86 have been found and corrected. Thanks to Fermin Reig for the
fix.

The interface and implementation of the register allocator have been changed
slightly to accommodate the possibility to skip the register allocation
phases completely and go directly to memory allocation.  This is needed
for C-- use.

This fix only affects the x86 assembly output.
(*
 * This is the new interference graph used by the new register allocator.
 * 
 * -- Allen
 *)

structure RAGraph : RA_GRAPH =
struct

  (* A new bit matrix datatype.
   * We use the small representation whenever possible to save space.
   *)
  datatype bitMatrix = BM of {table:hashTable,
                              elems:int ref,
                              edges:int}
  and hashTable = SMALL of word list Array.array ref * word
                | LARGE of bucket Array.array ref * word
             (* | BITMATRIX of Word8Array.array *)
  and bucket = NIL | B of int * int * bucket

  type priority = int

  type programPoint = int

  type cost = int

  type mode = word

  datatype interferenceGraph = 
   GRAPH of { bitMatrix    : bitMatrix ref,
              nodes        : node Intmap.intmap,
              regmap       : int Intmap.intmap,
              K            : int,
              firstPseudoR : int,
              dedicated    : bool Array.array,
              getreg       : 
                  {pref:int list, stamp:int, proh:int Array.array} -> int,
              getpair       : 
                  {pref:int list, stamp:int, proh:int Array.array} -> int,
              proh         : int Array.array,
              stamp        : int ref,

             (* Info to undo a spill when an optimistic spill has occurred *)
              spillFlag    : bool ref,
              spilledRegs  : bool Intmap.intmap,
              trail        : trailInfo ref,

              showReg      : int -> string,
              numRegs      : int,
              maxRegs      : unit -> int,
 
              deadCopies   : int list ref,
              copyTmps     : node list ref,
              memMoves     : move list ref,
              memRegs      : node list ref,

              spillLoc     : int ref,
              span         : int Intmap.intmap option ref,
              mode         : mode,
              pseudoCount  : int ref,
              blockedCount : int ref
            }

  and moveStatus = BRIGGS_MOVE | GEORGE_MOVE
                 | COALESCED | CONSTRAINED | LOST | WORKLIST

  and move = 
    MV of {src : node,			(* source register of move *)
	   dst : node,			(* destination register of move *)
           (* kind: moveKind, *)        (* what kind of move *)
           cost : cost,                 (* cost *)
	   status : moveStatus ref,	(* coalesced? *)
	   hicount : int ref	        (* neighbors of high degree *)
	  }

  and moveKind = REG_TO_REG      (* register to register *)
               | EVEN_TO_REG     (* even register in pair to register *)
               | ODD_TO_REG      (* odd register in pair to register *)
               | PAIR_TO_PAIR    (* register pair to register pair *)
               | REG_TO_EVEN     (* register to even register in pair *)
               | REG_TO_ODD      (* register to odd register in pair *)

  and nodeStatus =
        PSEUDO                (* pseudo register *)
      | REMOVED               (* removed from the interference graph *)
      | ALIASED of node       (* coalesced *)
      | COLORED of int        (* colored *)
      | SPILLED of int        (* spilled *)

  and node = 
    NODE of { number : int,		(* node number *)
	      movecnt: int ref,		(* #moves this node is involved in *)
	      movelist: move list ref,	(* moves associated with this node *)
	      degree : int ref,		(* current degree *)
	      color : nodeStatus ref,	(* status *)
	      adj : node list ref,      (* adjacency list *)
              pri : priority ref,       (* priority *)
              movecost : cost ref,      (* move cost *)
              (* pair : bool, *)        (* register pair? *)
              defs : programPoint list ref,
              uses : programPoint list ref
            }

  and trailInfo = END | UNDO of node * moveStatus ref * trailInfo

  exception Nodes

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

  val stampCounter = ref 0

  (* Create a new bitMatrix *)
  fun roundSize size = 
  let fun f(x, shift) =
        if x >= size then (x, Word.>>(shift, 0w1))
        else f(x+x, shift+0w1)
  in f(64, 0w6) end

  val max = Word.<<(0w1,Word.>>(Word.fromInt Word.wordSize,0w1)) 
  val _ = if max < Word.<<(0w1,0w15) 
          then error "word size too small" else ()

  fun newBitMatrix{edges, maxRegs} =
  let val table = 
        (* if maxRegs < 1024 then
          let val denseBytes  = (maxRegs * (maxRegs + 1) + 15) div 16
          in  BITMATRIX(Word8Array.array(denseBytes,0w0))
          end 
          else *)
          let val (tableSize, shift) = roundSize edges
          in  if Word.fromInt maxRegs < max then
                 SMALL(ref(Array.array(tableSize,[])),shift)
              else  
                 LARGE(ref(Array.array(tableSize,NIL)),shift)
          end
  in  BM{table=table, elems=ref 0, edges=edges}
  end

  (* Create a new interference graph *)
  fun newGraph{nodes,regmap,K,firstPseudoR,dedicated,spillLoc,
               getreg,getpair,showReg,maxRegs,numRegs,proh,
               memRegs,mode} =
  let (* lower triangular bitmatrix primitives *)
      (* NOTE: The average ratio of E/N is about 16 *)
      val bitMatrix = newBitMatrix{edges=numRegs * 16,maxRegs=maxRegs()}

      (* Make memory register nodes *)
      fun makeMemRegs [] = []
        | makeMemRegs(ranges) = 
          let val add = Intmap.add nodes
              fun loop(from, to, ns) = 
                  if from > to then ns 
                  else 
                  let val node = 
                      NODE{pri=ref 0,adj=ref [],degree=ref 0,movecnt=ref 0,
                           color=ref(SPILLED from), defs=ref [], uses=ref [],
                           movecost=ref 0,movelist=ref [], number=from}
                  in  add(from, node); loop(from+1, to, node::ns)
                  end
              fun loop2([], ns) = ns
                | loop2((from,to)::ranges, ns) = loop2(ranges, loop(from,to,ns))
          in  loop2(ranges, [])
          end 

      val memRegs = makeMemRegs memRegs

  in  if !stampCounter > 10000000 then stampCounter := 0 else ();
      GRAPH{ bitMatrix    = ref bitMatrix,
             nodes        = nodes,
             regmap       = regmap,
             K            = K,
             firstPseudoR = firstPseudoR,
             dedicated    = dedicated,
             getreg       = getreg,
             getpair      = getpair,
             proh         = proh,
             stamp        = stampCounter,
             spillFlag    = ref false,
             spilledRegs  = Intmap.new(2,Nodes),
             trail        = ref END,
             showReg      = Int.toString,
             numRegs      = numRegs,
             maxRegs      = maxRegs,
             deadCopies   = ref [],
             copyTmps     = ref [],
             memMoves     = ref [],
             memRegs      = ref memRegs,
             spillLoc     = spillLoc,
             span         = ref NONE,
             mode         = mode,
             pseudoCount  = ref 0,
             blockedCount = ref 0
           }
  end
  
end

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