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.