[Soot-list] LocalMustAliasAnalysis inaccuracy

[Arie Zilberstein]

Hi,

I like the new implementation :) I've integrated this approach into my
own analysis and it seems neat and correct.

In fact I think there is an advantage in having the merge point
statement as a parameter to the merge method. Other analyses can
probably benefit from this. I noticed that the merge statement is
passed around to the merge method in other static analyzers (e.g.
FindBugs), and I'm happy that soot now follows this practice.

Best,
Arie


On Wed, Oct 14, 2009 at 11:01 AM, Eric Bodden
<bodden at st.informatik.tu-darmstadt.de> wrote:
> Laurie Hendren just pointed out to me that my proposed solution seems
> to coincide with what she published years ago under the name of
> "Extended SSA Numbering":
>
> Lapkowski, C. and Hendren, L. J. 1996. Extended SSA numbering:
> introducing SSA properties to languages with multi-level pointers. In
> Proceedings of the 1996 Conference of the Centre For Advanced Studies
> on Collaborative Research (Toronto, Ontario, Canada, November 12 - 14,
> 1996). M. Bauer, K. Bennet, M. Gentleman, H. Johnson, K. Lyons, and J.
> Slonim, Eds. IBM Centre for Advanced Studies Conference. IBM Press,
> 23.  http://portal.acm.org/citation.cfm?id=782075#
>
> Having read the paper now, it seems that indeed the paper describes
> the same idea. The only major difference is that Laurie used secondary
> numbers that describe the value that a pointer points to. My current
> implementation only uses primary numbers.
>
> Eric
>
> 2009/10/13 Eric Bodden <bodden at st.informatik.tu-darmstadt.de>:
>> Hi all.
>>
>> I just committed another version of the LocalMustAliasAnalysis.
>> Hopefully it is correct now. To implement this attempt, I had to add
>> an overloaded version of the merge function, which gets passed not
>> only the two in sets and the out set but also the "merge point", i.e.,
>> the successor unit of the merge. This allows us to assign to each
>> variable a unique number for each merge point. Because there are only
>> finitely many merge points and variables, the number of generated
>> numbers is bounded.
>>
>> This approach is similar to generating "phi nodes" in SSA: there's one
>> phi node for each variable and merge point.
>>
>> Arie, the analysis now seems to report the correct results (and
>> terminate!) on all the examples you provided and on all examples I
>> have in my personal set of test cases. I would appreciate if you could
>> try out the analysis and maybe also give it a quick code review.
>> Please report back if you find any more issues.
>>
>> Eric
>> --
>> Eric Bodden
>> Software Technology Group, Technische Universität Darmstadt, Germany
>> Tel: +49 6151 16-5478    Fax: +49 6151 16-5410
>> Mailing Address: S2|02 A209, Hochschulstraße 10, 64289 Darmstadt
>>
>
>
>
> --
> Eric Bodden
> Software Technology Group, Technische Universität Darmstadt, Germany
> Tel: +49 6151 16-5478    Fax: +49 6151 16-5410
> Mailing Address: S2|02 A209, Hochschulstraße 10, 64289 Darmstadt
>