cps & contification

[Matthew Fluet]

> Sure.  I'm also including call-graph.{sig, fun} which is a modified
> version of checkDominators which creates the call graph with nontail call
> edges labeled with the continuation.  This makes it a little easier to
> think about what the contification analysis is doing on particular
> functions.  Of course, it results in many more edges on the graph.
> 
> In all three passes, all of the functions which are contifiable by the new
> analysis want to be contified in x_49.  Probably the easiest example is to
> look at x_0, x_1, and x_49.  We have
> (x_49, x_0), (x_49, x1), (x_0, x_1), (x_1, x_0), (x_1, x_49) in T
> The problem is that x_0 and x_1 are mutually recursive, but there are
> outside calls from x_49 to each of them.

Also take a look at x_35 and x_40.  Both are found call contifiable (there
are single calls in x_26) and both are found new contifiable.  But, the
new analysis makes them contifiable in x_49 (along with everything else).
Since there is no way of nesting all of the functions in x_49, nothing
from that group is contified -- including x_35 and x_40.

> I was thinking about trying to prove that the analysis A is the least safe
> analysis under the RCont ordering extended pointwise to analyses.  But
> this won't work, because of nesting of functions:
...
> It seems like for tail calls (f, g) in T, we want to favor A(g) = A(f)
> over A(g) = f.

I wrote the following notes to myself after thinking about the above
"problem," which may have some bearing on the issue with x_35 and x_40.

On the other hand, does it make more sense to really contify h in g?
This would result in deeper lexical nesting, which may make other
values available and avoid repeated computation.  Does this correspond
to the following definition of B:
    B(f) = 
         if parent(f) = Root
           then A'(f)
           else parent(f)
Intuitively, this seems like a safe analysis, but it violates the
current definition of safety:

fun fm () = ... f () ...
fun f () = ... g () ... i () ...
fun g () = ... h () ...
fun h () = ... i () ...
fun i () = ...

Then A(fm) = Unknown
     A(f) = fm
     A(g) = fm
     A(h) = fm
     A(i) = fm

And  B(fm) = Unknown
     B(f) = fm
     B(g) = f
     B(h) = g
     B(i) = f
We have (h, i) in T, 
 but B(h) <> Uncalled and B(i) notin {h, B(h), Unknown}.

We would need something like
 *** For all tail calls (f, g) in T
     A(f) = Uncalled
     or A(g) in {f, A(f), A(A(f)), ..., Unknown}


Are these orthogonal issues?  The current definition of the analysis
"works" in the sense that we always get useful and correct information;
i.e., if A(f) = g in Fun, then every call to f always returns to g.  Then
there are the other two issues: 1) can mutual recursion be acheived by
nesting? and 2) is deeper lexical nesting desired?  As Steve pointed out,
the second of these issues could probably be dealt with by a separate
simplification pass (possibly yielding benefits for other passes which
don't produce the best local code).  The first issue is for the most part
independent of the analysis -- the analysis answers "what would we like to
do?" and the mutual recursion deals with the question "what can we
actually do given the constraints of the IL?"  But, logic seems to say
that sometimes all of these issues do come together.