Re: Incremental Callgraph built

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

I would expect the difficult part to be detecting which parts of the
call graph need to be recomputed based on the changes to the changed
classes. I would expect there to be lots of related work dealing with
partial compilation (ie. which classes need to be recompiled when you
change a class).

Once you know what changed, re-processing the changed classes for the
purpose of adding call graph edges should be trivial, since you should
be able to reuse most of the existing call graph building code. It was
designed for adding edges on-the-fly, because that's needed when you're
doing a points-to analysis with on-the-fly call graph.

To remove call graph edges based on the changes, I don't think there is
any easy way to do it without traversing the whole call graph to see
what is still reachable. Also, note that the ReachableMethods currently
ignores edge removals, so you'd have to implement that.

As I believe I've said before, it's not the call graph building that is
slow, it's the fact that to build a call graph, you need to read in and
jimplify lots of code.

Now, you say that you don't want a complete call graph, but only the
part of the call graph starting at some specific method. If you just
tell the call graph building code to use only that method as an entry
point, it will build only that portion of the call graph, and I don't
see how that could be any slower than trying to incrementally change
an already built call graph. 

Anyway, to answer your question, I'm not aware of anyone incrementally
changing call graphs in Soot in particular.

Ondrej

On Tue, Nov 25, 2003 at 09:12:00AM +0100, Eric Bodden wrote:
> Hi!
> 
> I am currently investigating the possibility of developing a static
> approximation that helps to optimize weaving of a cflow statement in
> AspectJ. For this purpose one would need a partial call graph giving the
> transitive closure of all outgoing calls of a certain method. So far no
> problem - apart from efficiency. As I know the call graph analysis is
> typically very slow, especially when it comes to VTA or even more. So is
> there anybody who ever considered or even tried to implement kind of an
> incremental approach for building call graphs, meaning that e.g. if only one
> class is changed, only the edges touching this very class are recalculated?
> Or are there even problems that I did not think about which might make that
> impossible?
> 
> Thanks,
> Eric
> 
> ------------------------------------------------------------
> Eric Bodden
> Aachen University of Technology (RWTH)
> ICQ UIN: 12656220
> Website: http://www.bodden.de
> PGP key: http://www.bodden.de/pub_key.asc
> 
> 
>