[Soot-list] Creating an abstracted call graph

[Prof. Laurie HENDREN]

Eric,

I think you have to be very careful here because the call graph
is tightly bound with other analyses, most notably points-to
analysis.   As more call graph edges are found more points-to
relationships are implied.

Ondrej?

Cheers, Laurie




+-----------------------------------------------------------------
| Laurie Hendren --- laurie.hendren at mcgill.ca
| Associate Dean (Academic), Faculty of Science,
| Dawson Hall, McGill University, 853 Sherbrooke St W,
| Montreal QC H3A 2T6 Canada, 514-398-7179, fax 514-398-1774
+----------------------------------------------------------------
| For contact and home page info as Professor, Computer Science:
| http://www.sable.mcgill.ca/~hendren   ---  hendren at cs.mcgill.ca
| Research: http://www.sable.mcgill.ca  http://aspectbench.org
+----------------------------------------------------------------

On Wed, 15 Feb 2006, Eric Bodden wrote:

> Hello.
>
> In order to speed up analysis I want to create an abstracted call graph,
> i.e. this graph "A" should hold only certain nodes that satisfy a given
> predicate. An edge between two such nodes in "A" shall exist whenever
> there is a path between those nodes in the original call graph "G" and
> in between there is no other node satisfying this predicate. (So
> basically all nodes and edges not satisfying the predicate are collapsed
> in a conservative way.)
>
> Consider the following example, where [Mi] methods satisfy the
> predicate:
>
> [M1] -----> M2 ----> [M3]
>   |                   ^|
>   |                   ||
>   |                   |v
>   ------------------> M4 ---->[M5]
>
> This would be abstracted to:
>
> [M1] --------------> [M3]
>   |                   |
>   |                   |
>   |                   v
>   ------------------>[M5]
>
> Note that a marked node [Mi] is connected to a marked node [Mj] iff it
> is reachable over a path p in the original graph and no other marked
> node is on p.
>
> This could certainly be solved by first building the usual call graph
> and then using Filter and TransitiveTargets. However, this would
> probably be quite slow.
>
> So I was wondering if it would be a better idea to modify/subclass
> OnFlyCallGraphBuilder in such a way that it creates this abstracttion
> right away. Basically, it would have modified in such a way that it only
> adds edges between nodes that satisfy the predicate. If one was about to
> add an edge ([M1],M2), then one would not add this edge (since M2 is not
> marked) but rather store [M1] (hence deleting M2) and at the next time
> one encounters a marked method (here [M3]) would add the edge
> ([M1},[M3]). At this time one would also have to adjust all incoming
> edges which went to M2 to now point to M3.
>
> This of course all only works if the call graph builder builds the graph
> in a depth first order. Would it be safe to make such an assumption? Or
> does anyone have a better idea of how to achive this?
>
> Thanks a lot,
>
> Eric
>
> --
> Eric Bodden
> Sable Research Group, McGill University
> Montreal, Canada
> _______________________________________________
> Soot-list mailing list
> Soot-list at sable.mcgill.ca
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>