[Soot-list] Cycle detection in pointer analysis

[Ondrej Lhotak]

On Mon, Nov 19, 2007 at 01:57:24PM -0600, Dimitrios Prountzos wrote:
> Hi Manu,
> 
> Thank you for your answer. I agree with you that there don't seem to be 
> many cycles in the beginning. I have a couple of questions, if you or 
> someone else could give some intuitive answer, it would be great.
> 
> In his thesis, Ondrej tries to collapse cycles that only contain 
> reference variables. I was wondering if it would make any sense to try to 
> collapse cycles that contain both variable nodes and field 
> reference nodes, thus trying to eliminate more cycles.
> Also, I was wondering if PAG could be constructed in another way (more 
> lazilly) in order to try and gain more benefits from a dynamic cycle 
> detection approach. In the current implementation all nodes are added
> in the PAG from the beginning and a single cycle detection pass is enough.

One disadvantage of collapsing cycles involving field reference nodes is
that it reduces precision of the analysis. Normally, a store to and load
from the field reference node will propagate only if the base variable
of the field reference has a non-empty points-to set. Collapsing the
cycle effectively treats this case as always propagating, even if
the points-to set of the base variable is empty.

Ondrej

> Regards,
> 
> Dimitris
> 
> One question I had while reading Ondrej's thesis
> is
> 
> On Mon, 19 Nov 2007, Manu Sridharan wrote:
> 
> >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
> >>>>
> >>>
> >>
> >
>