[Soot-list] LocalMustAliasAnalysis inaccuracy

[Eric Bodden]

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