[Soot-list] LocalMustAliasAnalysis inaccuracy
bodden at st.informatik.tu-darmstadt.de
Wed Oct 14 05:01:21 EDT 2009
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,
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
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