cps & contification

[Stephen Weeks]

> Here it is.  I did it as a replacement of the existing new analysis, but
> if we really wanted to do comparisons with the two-phase analysis, it
> should be simple enough.  

I don't see any point in comparing with the two-phase analysis.  

> One more simplification: Reach(g) in the fourth and fifth clauses are
> implied by Reach(f) and the definition of Reach.  This is nice for the
> implementation, because we only check reach once for each function.  If
> true, then we do a Exp.foreachCall and don't need to check reach of the
> callee.  If false, we add the edge via the third clause.  This is already
> done in the file I sent out, but I forgot to mention it in the email.

Cool.

I'll play around with the new contify you sent and see if it triggers the same
space problems, which I am still tracking down.

> Given an analysis A, define A* : Fun -> 2^RCont as follows:
>     A*(f) = 
>          {f} U (if A(f) in Fun
>                   then A*(A(f))
>                   else {A(f)})

By this defn I assume you mean the least such A* under the obvious ordering on
Fun -> P(RCont).

> Lexical scoping will still be possible (although maybe harder to compute).
...

I didn't really follow this argument.  I got confused by the fact that you were
imposing constraints on where a function could be placed by looking at a single
call, but it wasn't easy for me to see why the constraints from different calls
couldn't be mutually incompatible.  I'm quite willing to wait and just read the
implementation, though.

> But, the upshot of this is that we can use the same G but define A as
>     A(f) = 
>          if parent(f) = Root
>            then if Reach(f) then Unknown else Uncalled
>          else parent(f)
> 
> and get an analysis that is safe, provably minimal (in the same way as
> before), and contifies those two annoying functions in logic.

It does this because it doesn't introduce as many sccs, right?