contification transformation

[Matthew Fluet]

> I wrote up an alternate transformation routine to work with the alternate
> definition of safety using A*.  It's very similar to what I described
> yesterday, and does indeed allow contification of those two functions in
> logic.  The downside is that it's probably more expensive (time/space) 
> than the current implementation.  But I'm thinking about ways of
> "batching" all of the contifications at once, so maybe I can get that to
> go away. 

I cleaned this up, so it should be almost as efficient as the current
transformation.  The actual transformation is almost identical to the
current version; I just removed some of the cases on contification
strategy.  The "prep" is a little different.  Essentially, I build the
following graph: 

Node = Jump U Fun
Edge = {(f, g) | A(g) = f} U
       {(j, g) | A(g) = j}
       
and then process nodes of the tree in order of the finishing times of a
depth first traversal from the roots.  Actually, the graph will be a
forest assuming that the analysis A is acyclic (which is reasonable for
the interpretation of A). 

Processing of a node proceeds as follows: look at all successors of the
node which are elements of Fun.  These are the functions which the
analysis marked as contifiable in this node.  Construct the call-graph and
compute sccs.  If there is an scc with more than one outside caller, then
mark all elements of the scc as uncontifiable and return them as
scc-heads.  If there is an scc with one outside caller, then nest the
remaining elements of the scc in the function called from the outside and
return the function called from the outside as an scc-head.  Given a
complete set of scc-heads, some are marked uncontifiable and some are
marked contifiable.  Partition this set, and for each uncontifiable
function, mark all of it's callees as uncontifiable; also, mark the
callees of any function which will be contified in an uncontifiable
function (because we haven't actually performed the contification, just
added them to a list of prefixes).  Now recurse on the contifiable
functions (because some of these might have been marked uncontifiable by
the processing of uncontifiable functions).  Once there are no
uncontifiable functions, add these functions to the set of functions to be
contified in the node.  Safety of the analysis and this bottom-up approach
ensures that anything that gets added to the list of prefixes won't later
be marked as uncontifiable. 

Here's a quick example, using the parent version of the dominator
analysis: 

fun fm () = ... K (h ()) ...
fun a () = ... b () ... h () ...
fun b () = ... f () ... g () ...
fun f () = ... g () ... h () ...
fun g () = ... f () ...
fun h () = ...

A(fm) = Unknown
A(a) = K
A(b) = a
A(f) = b
A(g) = b
A(h) = a

The graph looks like:

 fm    K
       |
       a
       | \
       b  h
      / \
     f   g

Initially, everything is marked as contifiable, except those functions i
which have A(i) = Uncalled or Unknown (i.e., roots of the trees.) 

Processing of fm, f, g, and h is trivial, because they have no decendants.
Processing of b computes the sccs of {f, g}, which is the single set {f,
g}, which has outside calls to both f and g, so f and g are marked
uncontifiable.  Now, mark the callees of f and g as uncontifiable, which
marks h as uncontifiable.  The set of contifiable scc-heads is empty, so
nothing is contified in b.

Processing of a computes the sccs of {b, h} which are the two singleton
sets {b} and {h}.  No problem with outside callers, so process the set of
scc-heads {b, h}.  Partitioning this set finds that h is marked
uncontifiable (note: it was marked uncontifiable in another round). 
Nothing changes after marking the callees of h uncontifiable, so b is
added to the list of functions contified in a. 

Likewise, a gets added to the list of functions contified in K. 

Once we're done processing all the nodes, we have prefix and nested lists
for each function and jump, and the actual rewriting is the same as
before. 

Note also that this transformation would allow b to call a function i and
still have i contified in b although f and g would be not be contified.  I
think this pretty much pushes the limit on getting all the functions
contifiable given the IL constraints. 

I also wrote versions of the call and cont analyses to use the RCont.t
datatype.  This lets the transformation code be free of branches on
strategy, and to use the Both strategy, I just take the appropriate combo
of the results of the Call and Cont analyses.