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

  val show : outstream * igraph -> unit
end
*)

structure Liveness = 
struct
  exception IllegalState
  structure Table = Graph.Table
  structure Set = IntListSet
  structure Map = IntBinaryMap

  fun calcLiveness(Flow.FGRAPH{def,use,control,...}) =
      let val emptySet = IntListSet.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 inSet = getInSet(outTable,fgNode)
                  val inTable' = Table.enter(inTable,fgNode,inSet)
                  val outSet = getOutSet(inTable',fgNode)
                  val outTable' = Table.enter(outTable,fgNode,outSet)
              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
end