latest contify.fun

[Stephen Weeks]

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

It might matter, since you are doing a lookup on root's edge list, which could
be long. Even 50 traversals of a 50k element list is noticeable.

> 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. 

My intuition is no lookup.  The reason is that the dominator algorithm is
(almost) linear, and the graph you build will be linear in program size, even
without lookups.

> 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.

Agreed.  Drop the lookup.

> 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. 

Agreed.

> 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. 

Probably makes sense to drop it here as well.  Same argument as above.  SCC is
linear time.