signature LIVENESS =
sig
  datatype igraph =
           IGRAPH of {graph: Graph.graph,
                      tnode: Temp.temp -> Graph.node,
                      gtemp: Graph.node -> Temp.temp,
                      moves: (Graph.node list) Graph.Table.table}
  val interferenceGraph : 
      Flow.flowgraph ->
      igraph * (Flow.Graph.node -> Temp.temp list)
  val show : TextIO.outstream * igraph -> unit
end

structure Liveness(* :LIVENESS *) = 
struct
  exception IllegalState
  structure Table = Graph.Table
  structure Set = IntListSet
  structure Map = IntBinaryMap
  datatype igraph =
           IGRAPH of {graph: Graph.graph,
                      tnode: Temp.temp -> Graph.node,
                      gtemp: Graph.node -> Temp.temp,
                      moves: (Graph.node list) Graph.Table.table}

  fun calcLiveness(Flow.FGRAPH{def,use,control,...}) =
      let val emptySet = Set.empty
          fun getSetFromTbl(table,node) = 
              let val setOpt = Table.look(table,node)
              in case setOpt of
                     NONE => emptySet
                   | SOME setVal => setVal
              end
          fun getInSet(outTable,fgNode) =
              let fun makeSet(table,node) =
                      let val listOpt = Table.look(table,node)
                      in case listOpt of
                             NONE => raise IllegalState
                           | SOME listVal => Set.addList(emptySet,listVal)
                      end
                  val useSetN = makeSet(use,fgNode)
                  val defSetN = makeSet(def,fgNode)
                  fun outSetN() = getSetFromTbl(outTable,fgNode)
                  val odSetN = Set.difference(outSetN(),defSetN)
                  val inSet = Set.union(useSetN,odSetN)
              in inSet
              end
          fun getOutSet(inTable,fgNode) = 
              let val succN = Graph.succ(fgNode)
                  val succInSetList = 
                      map (fn node => getSetFromTbl(inTable, node)) succN
                  val outSet = foldl Set.union emptySet succInSetList
              in outSet
              end

          fun updateInOutTable(fgNode,(inTable,outTable)) =
              let val outSet = getOutSet(inTable,fgNode)
                  val outTable' = Table.enter(outTable,fgNode,outSet)
                  val inSet = getInSet(outTable',fgNode)
                  val inTable' = Table.enter(inTable,fgNode,inSet)
              in (inTable',outTable')
              end
          fun tablesAreEqual(table,table') = 
              if Map.numItems(table) <> Map.numItems(table') then false
              else let val items = Map.listItems(table)
                       val items' = Map.listItems(table')
                   in ListPair.foldl 
                          (fn (set,set',result) 
                              => Set.equal(set,set') andalso result)
                          true (items,items')
                   end
          fun calcInOutTable(fgNodes,(inTable,outTable)) =
              let val (inTable',outTable') = 
                      foldl updateInOutTable (inTable,outTable) fgNodes
              in if tablesAreEqual(inTable,inTable')
                    andalso 
                    tablesAreEqual(outTable,outTable')
                 then (inTable',outTable')
                 else calcInOutTable(fgNodes,(inTable',outTable'))
              end

          val fgNodes = rev(Graph.nodes(control))
          val inOutTable = calcInOutTable(fgNodes,(Table.empty,Table.empty))
      in inOutTable
      end


  fun getTempList(Flow.FGRAPH{def,use,...}) =
      let val defList = List.concat(Map.listItems(def))
          val useList = List.concat(Map.listItems(use))
          val tempSet = Set.addList(Set.addList(Set.empty,defList),
                                    useList)
          val tempList = Set.listItems(tempSet)
      in tempList
      end


  fun interferenceGraph(fGraph as Flow.FGRAPH{control,def,use,ismove}) =
      let val (_,outTable) = calcLiveness(fGraph)
          val tempList = getTempList(fGraph)
          val iGraph = Graph.newGraph()
          val tgPairList = map (fn temp => 
                                   (temp, Graph.newNode(iGraph)))
                               tempList
          val fgNodes = Graph.nodes(control)

          fun tnode(temp) = 
              let val igNodeOpt = 
                      List.find (fn (pTemp,_) => pTemp = temp)
                                tgPairList
              in case igNodeOpt
                  of SOME (_,igNode) => igNode
                   | _ => raise IllegalState
              end
          fun gtemp(igNode) = 
              let val tempOpt = 
                      List.find (fn (_,pIgNode) => Graph.eq(pIgNode,igNode))
                                tgPairList
              in case tempOpt
                  of SOME (temp,_) => temp
                   | _ => raise IllegalState
              end

          fun addInterferenceEdge(fgNode) =
              let val defList = valOf(Table.look(def,fgNode))
                  val useList = valOf(Table.look(use,fgNode))
                  val isMoveNode = valOf(Table.look(ismove,fgNode))
                  fun outList() = 
                      let val outSet = valOf(Table.look(outTable,fgNode))
                          val defSet = Set.addList(Set.empty,defList)
                          val useSet = Set.addList(Set.empty,useList)
                      in if isMoveNode = true 
                         then Set.listItems(Set.difference(outSet,useSet))
                         else Set.listItems(outSet)
                      end
                  val outList = outList()
                  val defNodes = map tnode defList
                  val outNodes = map tnode outList
                  fun addInterferenceEdge0(nil) = ()
                    | addInterferenceEdge0(def::rest) =
                      (app (fn out => 
                               if Graph.eq(def,out) then ()
                               else Graph.mk_edge{from=def,to=out}) outNodes;
                       addInterferenceEdge0(rest))
              in addInterferenceEdge0(defNodes)
              end
          val _ = app addInterferenceEdge fgNodes

          fun makeMovesTable(fgNode,movesTable) = 
              let val isMoveNode = valOf(Table.look(ismove,fgNode))
                  fun duList() = 
                      let val defList = valOf(Table.look(def,fgNode))
                          val useList = valOf(Table.look(use,fgNode))
                          val defNode = tnode(hd(defList))
                          val useNode = tnode(hd(useList))
                      in [defNode,useNode]
                      end 
                          (* _very_ crude exception handling;
                             should be revisited *)
                          handle _ => raise IllegalState
              in if isMoveNode = true
                 then Table.enter(movesTable,fgNode,duList())
                 else movesTable
              end
          val movesTable = foldl makeMovesTable Table.empty fgNodes

          fun getOutList(fgNode) = 
              Set.listItems(valOf(Table.look(outTable,fgNode)))


      in (IGRAPH{graph=iGraph,tnode=tnode,gtemp=gtemp,moves=movesTable},
          getOutList)
      end
end