latest contify.fun

Matthew Fluet fluet@CS.Cornell.EDU
Thu, 22 Feb 2001 13:41:38 -0500 (EST)



> I added some Control.traceCalls to get a breakdown of where time is being spent
> in the new contifier.  They show that most of the time (~ 90%) is spent in the
> dominator analysis, and most of that (~ 90%) is spent in the Vector.foreach that
> builds the graph that is the argument to Graph.dominators.  That seems very
> weird to be spending time there.  It should be a simple pass over the program
> (i.e. < 1 second).  If we can get rid of all that we should be back down close
> to the old time.  I am investigating.

If the build graph is the real bottleneck, then I suspect it's my
(re-)definition of addEdge:

structure JumpFuncGraph =
  struct
    ...
    fun newJumpFuncGraph {getJumpData: Jump.t -> JumpData.t,
			  getFuncData: Func.t -> FuncData.t}
      = let
	  val G = Graph.new ()

	  fun addEdge edge
	    = if Node.hasEdge edge
		then ()
		else (Graph.addEdge (G, edge); ())

I'm calling an addEdge at just about every call site and, looking at
directed-graph.sml, Node.hasEdge is essentially a List.exists.

I wanted to keep the graph small, with the thought that that would make
the dominator calculation faster.  Maybe it makes more sense to remove
duplicate edges after building the whole graph.  Or maybe the dominator
calculation won't be that bad with the larger graph.