[Soot-list] LocalMustAliasAnalysis inaccuracy

[Arie Zilberstein]

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