[Soot-list] Cycle detection in pointer analysis

[Dimitrios Prountzos]

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
>>
>