[Soot-list] Cycle detection in pointer analysis

[Dimitrios Prountzos]

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.

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