expressing the call analysis

Matthew Fluet fluet@CS.Cornell.EDU
Mon, 19 Feb 2001 13:48:26 -0500 (EST)


I ran into a small "problem" trying to express the call analysis in the
new framework.  I want to express all of the analyses relative to the
abstraction P = (fm, N, T).  The problem is thinking about N and T as sets
pushes us away from the implementation. E.g.

fun f () = ... g () ... g () ...
fun g () = ...

If T = {(f,g)}, then we've lost the fact that g is called twice by f.  My
first attempt was to define

OuterT(f) = { g | (g, f) in T and g <> f and Reach(g) }
OuterN(f) = { j | (g, f, j) in T and g <> f and Reach(g) }
InnerN(f) = { j | (f, f, j) in T }

Acall(f) = Uncalled   if not Reach(f)
           Unknown    if f = fm
              l       if InnerN(f) = empty and OuterT(f) U OuterN(f) = {l}
           Unknown    otherwise

Under this definition, Acall(g) = f.

The most reasonable solution seems to be to note that N and T are
multisets, corresponding to the way one would likely process nontail and
tail calls in an implementation.