cps & contification

[Stephen Weeks]

> So, the best we can say is
> If B(f) = h in Fun, then A'(f) in {Uncalled, Unknown} U Jump
>                      and A(f) in {Uncalled} U Jump U Fun
> 
> Combined with the two other implications which are true, we still have the
> result that if some safe analysis says a function is contifiable
> somewhere, then our analysis also determines that the function is
> contifiable (or uncalled).

That's good enough for me.

> After I found the error above, I started thinking about the possibility of
> doing the entire analysis using the dominator approach. Here's a sketch of
> what I was thinking:
...

> Define a directed graph G = (Node, Edge) where
> 	Node = Jump U Fun U {Root}
> 	Edge = {(Root, fm)} 
>                U {(Root, j) | j in Jump}
>                U {(f, g) | (f, g) in T and A'(f) <> Uncalled
>                                        and A'(g) = Unknown}
>                U {(j, g) | (f, g, j) in N and A'(f) <> Uncalled
>                                           and A'(g) = Unknown}
> 
> Let D be the dominator tree of G rooted at Root.
> For f in Fun, let parent(f) be the parent of f in D.
> 
> Define an analysis, A, based on A' and D as follows:
>     A(f) = 
>          if parent(f) = Root
>            then A'(f)
>          else the ancestor l of f in D such that parent(l) = Root

I like this better than the previous approach.  I have one minor correction.
If A'(f) = Uncalled, then there is no path in G from Root to f.  So, either
redefine A so that if A'(f) = Uncalled then A(f) = Uncalled or add some bogus
edges from Root to f whenever A'(f) = Uncalled.  I prefer the former.  Other
than that, I think this is equivalent to what we had.  It also makes it even
clearer to me why dominators is the right notion.

Are you working through the proofs of safety and minimality?