signature REG_ALLOC =
sig
  structure Frame : FRAME
  type allocation = Frame.register Temp.Table.table
  val alloc : Assem.instr list * Frame.frame ->
              Assem.instr list * allocation
end

structure RegAlloc (* :REG_ALLOG *) =
struct
  structure Frame = Frame
  structure Table = Graph.Table
  (* attributes for interference graph node *)
  datatype iNodeAttr = 
           PRECOLORED | INITIAL | SIMPLIFYWORK 
         | FREEZEWORK | SPILLWORK | SPILLED | COALESCED 
         | COLORED | SELECTED
  datatype moveAttr = COALESCED | CONSTRAINED | FROZEN
                    | WORKLIST | ACTIVE

  type allocation = Frame.register Temp.Table.table

  fun buildMoveList(FGRAPH) = ()

  fun alloc(instrs, frame) = 
      let val allocTable = Temp.Table.empty
          val (fGraph, fgNodes) = MakeGraph.instrs2graph(instrs)
          val (interference, gtMap) = 
              Liveness.interferenceGraph(fGraph)
          val initial = Frame.tempMap
          fun spillCost(node) = 1
          val registers = Frame.registers

          val Liveness.IGRAPH{graph=igraph, gtemp=gtemp,...} = interference

          fun initINodeAttr(iNode,iNodeAttrTbl) =
              let val isPrecolored = Option.isSome(Table.look(initial,iNode))
              in if isPrecolored = true 
                 then Table.enter(iNodeAttrTbl,iNode,PRECOLORED)
                 else Table.enter(iNodeAttrTbl,iNode,INITIAL)
              end
          val iNodeList = Graph.nodes(igraph)
          val iNodeAttrTbl = foldl initINodeAttr Table.empty iNodeList

          (* Table for Move sets *)
          val fNodeAttrTbl = Table.empty

          val (cAlloc,aList) = Color.color {interference=interference,
                                            initial=initial,
                                            spillCost=spillCost,
                                            registers=registers}
      in (instrs, allocTable)
      end
end