[Soot-list] LocalMustAliasAnalysis inaccuracy

[Eric Bodden]

Hi Arie.

I am just writing to confirm the problem. I am still working on a
solution. It's a little tricky. I think I may have to reconsider the
abstraction. It seems that associating a variable with a single number
at a time retains too little information at merge points. I am
currently contemplating whether it would work to instead associate
each variable with a *set* of value numbers (and a merge would simply
join those sets). After finishing the fixed point iteration one could
then probably still flatten those sets into numbers again.

Eric

2009/9/27 Arie Zilberstein <arie.zilberstein at gmail.com>:
> Hi Eric,
>
> I regret to say that there is still a problem with the algorithm. Please
> look at the following method:
>
> public void run() {
>        while (true) {
>
>                Object localLock = new Object();
>                synchronized (localLock) {
>
>                        try {
>                                localLock.wait();
>                        } catch (InterruptedException x) {
>                        }
>                        continue;
>                }
>        }
> }
>
> Now, if you invoke the following lines, the algorithm will run forever and
> not converge!
>
> ExceptionalUnitGraph graph = new ExceptionalUnitGraph(activeBody);
> LocalMustAliasAnalysis alias = new LocalMustAliasAnalysis(graph);
>
>
> This is my initial analysis of the problem: it seems, that new merged values
> are generated all over again. This happens when a statement, for example,
> $r2 := @caughtexception;, has multiple predecessors, each of which has a
> different value of the same variable. The merge process treats only pairs,
> so if the same variable is merged from 3 or more locations, a problem arises
> and too many merge numbers are created.
>
> I now understand why the previous algorithm tried to take into account the
> merge location, and I realize that in order to fix the algorithm, we must
> take into account both the variable itself that is being merged, together
> with the merge location. I guess one possible fix would be to make use of
> the merge location, but this seems impossible without receiving the stmt as
> a parameter to the merge() method.
>
> Please let me know what you think.
>
>
> Best,
> Arie
>
>
> -----Original Message-----
> From: eric.bodden at googlemail.com [mailto:eric.bodden at googlemail.com] On
> Behalf Of Eric Bodden
> Sent: Saturday, September 26, 2009 8:34 PM
> To: Arie Zilberstein
> Cc: soot-list at sable.mcgill.ca
> Subject: Re: [Soot-list] LocalMustAliasAnalysis inaccuracy
>
>> My problem with my analysis right now is that there is an endless loop
> when
>> analyzing <java.lang.ref.Reference$ReferenceHandler: void run()>. I keep
>> getting new merged value numbers again and again. I wonder if the problem
>> also happens with LocalMustAliasAnalysis on that method?
>
> I don't think so. If you look at the analysis you can see that I use a
> map to cache value numbers. When re-visiting an expression then the
> analysis models this expression using the same value number that was
> used before. The same holds for value numbers that originate from a
> merge. Without that "trick" the analysis would not converge either.
>
> 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