[Soot-list] Cycle detection in pointer analysis

[Manu Sridharan]

Hi Dimitris,

I don't know of any publications that analyze "type filters vs. cycle
detection" per-se.  If you look at Section 5.3.3 of Ondrej's Master's thesis
(http://plg.uwaterloo.ca/~olhotak/pubs/thesis-olhotak-msc.ps), you'll see
some analysis of the interaction between types and cycles when the call
graph is computed ahead-of-time.  The data there show that types don't
greatly reduce the number of cycles, but there don't seem to be that many
cycles in the first place.  I know through personal communication
that Heintze-Tardieu-style cycle detection didn't provide a big performance
benefit for another points-to analysis implementation.  I would be
interested to see a study that analyzed the interactions between types and
cycle detection, also comparing Java and C.
-Manu
On Nov 17, 2007 9:51 AM, Dimitrios Prountzos <dprountz at cs.utexas.edu> wrote:

> Thank you both for your answers,
>
> I am trying to familiarize myself with the pointer analysis framework of
> Soot and since the code was there, I had a look at it. So, do you think,
> that online cycle detection, in general, does not offer any real benefit
> in the case of Java? Could you recommend any publications that further
> analyze the "type filters vs. cycle detection" issue that you mentioned
> in your email?
>
> Thank you,
>
> Dimitris
>
> On Fri, 16 Nov 2007, Manu Sridharan wrote:
>
> > 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/20071119/56b73085/attachment.htm