[Soot-list] LocalMustAliasAnalysis inaccuracy
bodden at st.informatik.tu-darmstadt.de
Tue Oct 20 02:49:10 EDT 2009
Excellent. Thanks for the update.
2009/10/19 Arie Zilberstein <arie.zilberstein at gmail.com>:
> 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.
> 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.
>> 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 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
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
More information about the Soot-list