[Soot-list] LocalMustAliasAnalysis inaccuracy

[Arie Zilberstein]

Hi Eric,

This sounds like it would work. I think associating a variable with a
set is natural if you compare this analysis to a points-to analysis.
The latter assigns to each variable a set of possible nodes to which
it may point to. Some special care should be taken handling the
"unknown" and "nothing" sets.

By the way, here is a simpler example that exhibits the problem, but
this time without synchronization and without continue statements:

	private static void hang1() {
		while (true) {
			Integer x;
			try {
				x = 1;
				x = 2;
			} catch (Exception e) {

			}
		}
	}

I hope you find the time to work on it -- I tried doing it myself but
it was close to a complete rewrite of the analysis and I were not sure
that I would preserve its correctness in all cases.

Best,
Arie

On Tue, Sep 29, 2009 at 9:57 AM, Eric Bodden
<bodden at st.informatik.tu-darmstadt.de> wrote:
> 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
>