latest contify.fun

[Matthew Fluet]

> There are ~50,000 jumps.  Doing lots of linear lookups in a 50,000 element list
> is not a very good idea :-).  I bet that removing this will solve the problem.
> The easiest thing to do would be to keep a bool flag associated with the jump
> that lets you tell in constant time if the edge has been added.  You should
> probably do the same for funcs as well.

It won't matter for funcs.  The edge (Root, f) can only be added once, if
f is unreachable (or if f is main). 

I had previously considered adding the edge (Root, j) at each jump
declaration, but that would add an edge for reach local function, whether
or not it was used as a continuation.  The alternative is to only add the
edge when we first encounter a jump used as a continuation.  The bool flag
will be easy enough to add. 

We'll still end up with multiple edges of the form (j, f) and (f, g),
corresponding to things like: 

fun f () = ... K (g ()) ... K ( g()) ...   :: will have (K, g) twice
fun f () = ... g () ... g () ...           :: will have (f, g) twice

Intuition on whether or not to do the lookup on these?  They both seem
like they could get expensive, although nothing approaching the number of
(Root, j) edges. 

> It wouldn't hurt to go through all uses of addEdge with an eye towards this
> problem, and avoid the linear lookup if possible.

There are only a three outside of analyzeDom.  

1. There is one to compute the call graph to calculate reach.  I don't
think skiping the linear lookup is a problem here.  I only perform one dfs
on the resulting graph; so, there will be at most one traversal of each
edge, which will be less expensive than the comparisons in addEdge.

2. There is one to compute the "analysis forest."  Since all of our
analysis are safe (hence acyclic), no duplicate edge will ever be added. 
So, we can skip the lookup. 

3. There's also one to compute the mini-call graph when computing sccs. 
Probably not an issue to elimate the lookup here.  But it's probably not
that expensive anyways. 


I'll report back when I've made these changes.