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_ALLOC *) =
struct
  structure Frame = Frame
  structure Table = Graph.Table
  (* attributes for interference graph node *)

  type allocation = Frame.register Temp.Table.table

  fun initMoveAttrBase isMoveTable (fgNode,moveAttrTbl) =
      if valOf(Table.look(isMoveTable,fgNode)) = true
      then Table.enter(moveAttrTbl,fgNode,Color.WORKLIST_MOVE)
      else moveAttrTbl

  fun makeMovesTableBase isMoveTable def use tnode (fgNode,movesTbl) = 
      let val isMoveNode = valOf(Table.look(isMoveTable,fgNode))
              handle e => raise e
          fun takeDefUseNode(duTable,fgNode) =
              let val duList = valOf(Table.look(duTable,fgNode))
              in tnode(hd(duList))
              end
          fun addFgNode(movesTbl,duTable,fgNode) = 
              let val duNode = takeDefUseNode(duTable,fgNode)
                  val nodeListOpt = Table.look(movesTbl,duNode)
              in case nodeListOpt
                  of NONE 
                     => Table.enter(movesTbl,duNode,[fgNode])
                   | SOME nodeList 
                     => Table.enter(movesTbl,duNode,fgNode::nodeList)
              end
      in if isMoveNode = true
         then let val movesTblD = addFgNode(movesTbl,def,fgNode)
                  val movesTblDU = addFgNode(movesTblD,use,fgNode)
              in movesTblDU
              end
         else movesTbl
      end

  fun alloc(instrs, frame) = 
      let val (fGraph, fgNodes) = MakeGraph.instrs2graph(instrs)
          val (interference, gtMap) = Liveness.interferenceGraph(fGraph)
          fun spillCost(node) = 1
          val registers = Frame.registers
          val initial = foldl (fn (tmp,tbl) => Temp.Table.enter(tbl,tmp,tmp))
                              Temp.Table.empty registers

          (* Making moveAttrTbl: Table for Move instr attributes *)
          val Flow.FGRAPH{control=fControl,ismove=isMoveTable,def,use} = fGraph
          val initMoveAttr = initMoveAttrBase isMoveTable
          val fgNodeList = Graph.nodes(fControl)
          val moveAttrTbl = foldl initMoveAttr Table.empty fgNodeList

          val Liveness.IGRAPH {tnode,...} = interference
          val makeMovesTable = makeMovesTableBase isMoveTable def use tnode
          val movesTbl = foldl makeMovesTable Table.empty fgNodes

          val (allocationTable, spillList) = 
              Color.color {interference=interference,
                           initial=initial,
                           spillCost=spillCost,
                           registers=registers,
                           moveAttrTbl=moveAttrTbl,
                           movesTbl=movesTbl}

      in if spillList = nil then (instrs, allocationTable)
         else (print "Executing handleSpills\n";
               alloc(Frame.rewriteProgram(frame,instrs,spillList), frame))
      end
end