[Soot-list] Cycle detection in pointer analysis

[Manu Sridharan]

Just curious, why do you need cycle collection?  AFAIK, there's no evidence
that Heintze-Tardieu style cycle collection provides a performance benefit
for Java points-to analysis over the highly-tuned propagation algorithms
already present in Spark.  In fact, I think the Heintze-Tardieu algorithm
was implemented in WALA (another analysis framework), and no performance
benefit was seen.  A difference between C and Java that could account for
this is the use of type filters in Java points-to analysis: they provide a
large performance benefit in the absence of cycle collection, and it's not
entirely clear how to keep that benefit while incorporating cycle
collection.

-Manu
On Nov 16, 2007 11:05 AM, Ondrej Lhotak <olhotak at uwaterloo.ca> wrote:

> On Thu, Nov 15, 2007 at 01:44:57PM -0600, Dimitrios Prountzos wrote:
> > Hi,
> >
> > I was looking at the code that propagates points-to sets
> > using on-line cycle detection, based on the Heintze and
> > Tardieu algorithm (spark/solver/PropCycle.java) and I
> > got the impression that in the current implementation
> > there is no attempt to collapse cycles. In particular,
> > in the computeP2Set() method, the only statement that
> > tries to merge nodes is in comments.
> > If this is indeed the case, would it be enough to just
> > remove the comment from the specific statement, or does
> > it require more work to support cycle elimination?
>
> That file contains only a partial, unfinished implementation of Heintze
> and Tardieu's algorithm. I started implementing it at one point, but got
> sidetracked by other things before finishing it. I don't remember how
> far it is from being finished, but there is probably still substantial
> work left to be done.
>
> Ondrej
>
> > Thank you,
> >
> > Dimitris
> > _______________________________________________
> > Soot-list mailing list
> > Soot-list at sable.mcgill.ca
> > http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
> >
> _______________________________________________
> Soot-list mailing list
> Soot-list at sable.mcgill.ca
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.CS.McGill.CA/pipermail/soot-list/attachments/20071116/302ce7ea/attachment.htm