[Soot-list] <To sum up> my StrongLocalMustAliasAnalysis gives unexpected results
Laurie Hendren
hendren at cs.mcgill.ca
Sun Oct 21 15:26:47 EDT 2012
I think the confusion is about the fact that when we say "represents a
single run-time object", it means, "at any point in the execution it
represents a single run-time object".
Indeed, that is what is assumed everywhere, for example, in the following:
main()
{ foo();
foo();
}
foo()
{ A a = new A(); // S
A b = a;
}
At any point in the execution of the program statement S a points to
only one object, and so obeys our "represents a single run-time
object". However, over the life of the whole program it will
represent two different objects, one for the first call of foo() and
the other for the second call of foo(). However, we are not
reasoning about the life of the whole program.
Note that knowing that a "represents a single run-time object" also
allows one to say that "a" and "b" must point to the same object.
Now, if you understand that example, the loop example is effectively
the same thing, except instead of two calls to foo() you have several
executions of the loop body.
Cheers, Laurie
+--------------------------------------------------------------
| Laurie Hendren --- http://www.sable.mcgill.ca/~hendren
| Associate Dean (Academic), Faculty of Science
| Professor, School of Computer Science, McGill University
| *** New McLAB Release ***
| *** http://www.sable.mcgill.ca/mclab/Software.html ***
| Other Proj: www.sable.mcgill.ca/soot www.sable.mcgill.ca/abc
+--------------------------------------------------------------
On 21/10/2012 11:50 AM, Patrick Lam wrote:
> It's not an extra condition. x can only represent a single run-time
> object at a time at line 5. You know exactly what x points to.
>
> On 10/21/2012 11:46 AM, Zhoulai wrote:
>> To sum up after this long discussion,
>>
>> -- The 2008 Object Representative paper gives me the impression that
>> Strong Must Alias Analysis associate UNKNOWN with variables that can be
>> assigned more than one values.
>>
>> Quoted from the 2008 paper on object representative:
>> "A strong representative only must-alias itself at the same program
>> location if it is guaranteed that this representative represents a
>> single run-time object."
>>
>> I thought, the StrongAliasAnalysis should associate UNKNOWN with x and y
>> before line 5.
>> > > ****************
>> > > 1: static void test5(int i){
>> > > 2: while (i>0){
>> > > 3: A x = new A();
>> > > 4: A y = x;
>> > > 5: String s = "hello";
>> > > }
>> > > }
>> > > **************
>> because both x and y are bound to more than objects during their lifetime.
>>
>> -- However, Patrick gave me an extra condition:
>> " variable redefinition only gives UNKNOWN if the
>> redefinition is not mandatory. ",
>> and argued that x and y should not be associated with UNKNOWN, because
>> the redefinition is not mandatory.
>>
>> The problem is still extremely confusing to me. I don't see how to
>> formalize and verify this last condition. Anyway, thanks again for the
>> patience of Patrick and Eric and others!
>>
>> Zell.
>>
>>
>>
>>
>> On Sun, Oct 21, 2012 at 2:39 PM, Patrick Lam <plam at sable.mcgill.ca
>> <mailto:plam at sable.mcgill.ca>> wrote:
>>
>> No. If line 5 executes, line 3 has definitely executed. There is no
>> other option.
>>
>>
>> On 10/21/2012 07:39 AM, Zhoulai wrote:
>>
>> We were talking about an example where thredefinition of
>> variable 'x' is
>> not mandatory (see below the program) , but your
>> StrongMustAliasAnalysis
>> associates with 'x' an integer , rather than UNKNOWN.
>>
>> > > ****************
>> > > 1: static void test5(int i){
>> > > 2: while */(i>0)/*{
>> > > 3: A x = new A(); _// The re-assignment is NOT
>> mandatory here._
>> > > 4: A y = x; //_but 'x' is
>> bound
>> to an integer value. This is not sound!_
>>
>> > > 5: String s = "hello";
>> > > }
>> > > }
>> > > **************
>>
>> 'x' is /potentially/ re-assigned in the loop
>>
>> ==> 'x' is expected to be bound to "UNKNOWN" by your
>> StrongMustAliasAnalysis (**)
>>
>> But, at line (5) your analyzer infers that x is bound to some
>> integer
>> value (*)
>>
>> So the expected (**) and the implemented (*) contradict.
>>
>> Zell.
>>
>>
>> On Sun, Oct 21, 2012 at 1:04 PM, Patrick Lam
>> <plam at sable.mcgill.ca <mailto:plam at sable.mcgill.ca>
>> <mailto:plam at sable.mcgill.ca <mailto:plam at sable.mcgill.ca>>> wrote:
>>
>> As I said, variable redefinition only gives UNKNOWN if the
>> redefinition is not mandatory.
>>
>> pat
>>
>>
>> On 10/21/2012 01:26 AM, Zhoulai wrote:
>>
>> Thanks Patrick. I see your point. Don't forget that your
>> StrongMustAliasAnalysis, as described by your 2008's
>> paper, is
>> supposed
>> to consider variable redefinition in loops!
>>
>> For the k-th iteration of the loop, a new object o_k is
>> created and
>> bound to x (which overwrites its earlier state) , so
>> the "*states
>> history* " related to x will be
>>
>> x->o_0, x -> o_2, x->o_k....
>> which mean that ***Over time*** x is bound to
>> {o_0,o_1,o_2 ...}. I
>>
>> believe this is the way your StrongMustAliasAnalysis in
>> your paper
>> reasons, right?
>>
>> My apologies for any misunderstandings.
>> Zell.
>>
>> On Sun, Oct 21, 2012 at 6:33 AM, Patrick Lam
>> <plam at sable.mcgill.ca <mailto:plam at sable.mcgill.ca>
>> <mailto:plam at sable.mcgill.ca <mailto:plam at sable.mcgill.ca>>
>> <mailto:plam at sable.mcgill.ca <mailto:plam at sable.mcgill.ca>
>> <mailto:plam at sable.mcgill.ca <mailto:plam at sable.mcgill.ca>>>__>
>> wrote:
>>
>> On 10/21/2012 12:25 AM, Zhoulai wrote:
>> > > ****************
>> > > 1: static void test5(int i){
>> > > 2: while (i>0){
>> > > 3: A x = new A();
>> > > 4: A y = x;
>> > > 5: String s = "hello";
>> > > }
>> > > }
>> > > **************
>>
>> > By your specification in your paper, the strong
>> representative only
>> > must-alias itself at the same program location if it is not
>> guaranteed
>> > that this representative represents a single run-time object.
>> >
>> > Here variable 'x'' is associated with more than 1 run-time
>> objects. It
>> > is therefore expected to be bound to UNKNOWN.
>>
>> x only points to one object at a time in this
>> case. The
>> only way that x
>> might point to more than one object is if there
>> are two
>> different
>> definitions that reach x (perhaps from different
>> iterations
>> of the
>> loop), like if you had this program instead:
>>
>> A x = null;
>> if (...) x = new A();
>> A y = x;
>>
>> Then you should not get UNKNOWN. But in the
>> program you
>> wrote, there's
>> only one object that x could possibly contain.
>>
>> pat
>>
>> ___________________________________________________
>>
>> Soot-list mailing list
>> Soot-list at sable.mcgill.ca <mailto:Soot-list at sable.mcgill.ca>
>> <mailto:Soot-list at sable.__mcgill.ca
>> <mailto:Soot-list at sable.mcgill.ca>>
>> <mailto:Soot-list at sable. <mailto:Soot-list at sable.>__mcgi__ll.ca
>> <http://mcgill.ca>
>> <mailto:Soot-list at sable.__mcgill.ca
>> <mailto:Soot-list at sable.mcgill.ca>>>
>> http://mailman.cs.mcgill.ca/____mailman/listinfo/soot-list
>> <http://mailman.cs.mcgill.ca/__mailman/listinfo/soot-list>
>> <http://mailman.cs.mcgill.ca/__mailman/listinfo/soot-list
>> <http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list>>
>>
>>
>>
>>
>>
>>
>>
>>
>> _______________________________________________
>> Soot-list mailing list
>> Soot-list at sable.mcgill.ca
>> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
> _______________________________________________
> Soot-list mailing list
> Soot-list at sable.mcgill.ca
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
More information about the Soot-list
mailing list