Re: Soot 2.1.0 released

["'Ondrej Lhotak'" <olhotak@sable.mcgill.ca>]

On Thu, Dec 18, 2003 at 11:32:59AM -0600, Venkatesh Prasad Ranganath wrote:
> 'Ondrej Lhotak' wrote:
> > On Thu, Dec 18, 2003 at 05:00:05PM +0100, Eric Bodden wrote:
> > 
> >>Nice!
> >>
> >>
> >>>5. initial support for 
> >>>context-sensitive call graph and points-to analysis
> >>
> >>In what sense is it context sensitive? Where can I find further information?
> > 
> > 
> > The Edge class that is inserted into the CallGraph now contains a
> > MethodOrMethodContext rather than just SootMethod as source and target.
> > A MethodOrMethodContext can either be just a SootMethod, or it can
> > be a MethodContext, which is a pair of a SootMethod and an arbitrary
> > Object as context (though in future versions, it will need to implement
> > an empty Context interface, just to keep track of things which can
> > be contexts). Currently, the call graph builder supports building a
> > context-insensitive call graph, a call graph with the call site as
> > context, and (in combination with Spark) a call graph with the receiver
> > as context. For more information, see:
> 
> Out of curiousity, do you have an empirical data to compare running time/memory and precision of receiver-insensitive 
> call-graph v/s receiver-sensitive call-graph?  (The time and memory are inclusive of all the analyses that lead to or are 
> required for call-graph construction.)

Not yet. I'm planning to do such measurements, which is why I've
implemented it in Soot. Roughly speaking, it appears to be quite
expensive.

BTW The idea is from a paper by Milanova, Rountev, and Ryder at ISSTA
2002. They have some empirical data showing it to not be very expensive.
However, they suggest a range of variations on the idea, and the
variation that they measured is different from the one currently in
Soot. In Soot, all local variables are split between contexts. I can't
remember the details of the paper, but I believe that they only split
parameters and return values between contexts.

> Also, by context, do you mean call-string/call-stack?  If so, do you do some sort of limiting on the length/size of the 
> context?  Do you have any empirical data about cost and precision?

Currently the call "string" is limited to one call site. However,
extending it to an arbitrary length would be trivial. The only reason I
didn't do it is that I'd like to understand the performance with a
single call site first.

Anyway, in the call graph, the context can be arbitrary. In particular,
it can be a receiver, or a call site, or a string of call sites. Of
these three, the first two are implemented.

Ondrej

> 
> waiting for reply,
> 
> -- 
> 
> Venkatesh Prasad Ranganath,
> Dept. Computing and Information Science,
> Kansas State University, US.
> web: http://www.cis.ksu.edu/~rvprasad
>