signature MAKEGRAPH =
sig
  val instrs2graph: Assem.instr list ->
                    Flow.flowgraph * Flow.Graph.node list
end

structure MakeGraph : MAKEGRAPH = 
struct
  fun instrs2graph(instrList) = 
      let val control = Graph.newGraph()
          val emptyTbl = Graph.Table.empty
          fun makeNodeAndAttr(instr) =
              let val node = Graph.newNode(control)
                  fun setAttr(Assem.OPER{dst,src,...}) = (dst,src,false)
                    | setAttr(Assem.MOVE{dst,src,...}) = ([dst],[src],true)
                    | setAttr(_) = (nil,nil,false)
              in (node,setAttr(instr))
              end
          val nodeAndAttrList = map makeNodeAndAttr instrList
          fun makeAttrTable(attrs,nil) = attrs
            | makeAttrTable((def,use,ismove),
                            (node,(dst,src,imVal))::xs) = 
              let val enter = Graph.Table.enter
              in makeAttrTable((enter(def,node,dst),
                                enter(use,node,src),
                                enter(ismove,node,imVal)),
                               xs)
              end
          val (def,use,ismove) = makeAttrTable((emptyTbl,emptyTbl,emptyTbl),
                                               nodeAndAttrList)
          val nodeList = map (fn (node,_) => node) nodeAndAttrList

          exception IllegalState
          fun makeLabelTable(tbl,nil,nil):Flow.Graph.node Symbol.table = tbl
            | makeLabelTable(_,nil,_) = raise IllegalState
            | makeLabelTable(_,_,nil) = raise IllegalState
            | makeLabelTable(tbl,Assem.LABEL{lab,...}::xs,node::ys) =
              let val tbl' = Symbol.enter(tbl,lab,node)
              in makeLabelTable(tbl',xs,ys)
              end
            | makeLabelTable(tbl,_::xs,_::ys) = makeLabelTable(tbl,xs,ys)
          val labelTable = makeLabelTable(Symbol.empty,instrList,nodeList)

          fun addEdge(0) = raise IllegalState
            | addEdge(1) = ()
            | addEdge(i) =
              let val n = length(instrList) - i
              in (case List.nth(instrList,n)
                   of Assem.OPER{jump=SOME lbls,...} => 
                      let val toNodes = 
                              map (fn x => Symbol.look(labelTable,x)) lbls
                      in app (fn NONE => raise IllegalState
                               | SOME toNode => 
                                 Graph.mk_edge {from=List.nth(nodeList,n), 
                                                to=toNode}) toNodes
                      end
                    | _ => Graph.mk_edge {from=List.nth(nodeList,n), 
                                          to=List.nth(nodeList,n+1)};
                  addEdge(i-1))
              end
          val _ = addEdge(length(instrList))

      in (Flow.FGRAPH{control=control,def=def,use=use,ismove=ismove}, 
          nodeList)
      end
end