Re: Static Points-to Analysis Query

Thanks David for your feedback. Your comments and suggestions have
helped me to continue on with more realistic expectations. I'll have
to impose some analytical constraints, like avoiding cases that cause
recursion (because of the whole undecidability issue). Also thanks for
confirming that my approach is one of the right ways to go about
partially solving it. Looks like I've a long road ahead of me to
implement a half-way decent solution.... Thanks again...

Jon.

On Sat, Mar 6, 2010 at 3:28 AM, David Chase <[email protected]> wrote:
> It's really hard, I worked on this problem 20 (!) years ago.
> We used a semi-weird incremental SSA-framework (this requires
> that you do control-flow analysis before your data flow
> analysis, so you know the dominator tree and where all the
> join points are).  (If you track down our paper -- Chase, Wegman,
> Zadeck -- be warned that there is a renaming error at the top
> of loops, that causes the analysis to be non-monotonic, but
> you can fix it by (if I recall correctly) pushing values through
> back-edges last.)
>
> There's been better papers written since then, but they are all
> hard to understand.
>
> If I recall correctly, Landi (or one of Barbara Ryder's other students)
> proved some fundamental bounds on how hard this problem is, if
> you decide that you want to get "really good" results.  yes:
>
> http://portal.acm.org/citation.cfm?id=186041
>
> This doesn't mean that it's hopeless, but it does mean that you should
> set your expectations appropriately.  On a cheerier note, consider that
> humans figure this out in many cases, and we're actually kinda stupid,
> and we're certainly lazier and buggier than a well-implemented analysis
> algorithm.
>
> And to perhaps cheer you up some more, the way you are doing it, looks
> similar to the way that most people attack this.  One approximation that
> is not terrible, is to declare that you will give up when faced with
> recursive data structures (e.g., a list allocated in a loop), and then
> see how well you do working with stuff that is only tree-like.  Another
> thing that is interesting is to spot data structures that cannot be
> cyclic; that inevitably requires storing a pointer to "young" in something
> that is "old", so if pointer stores don't cross that age order, then the
> data is not cyclic.
>
> David
>
> On 2010-03-05, at 10:03 PM, Jonathan Byrne wrote:
>
>> Hi, I've used ASM to implement a very, very simple intra-procedural
>> points-to analysis that is based on an iterative forward-seeking,
>> fixed-point, data-flow analysis. For the moment I'm just interested in
>> detecting relationships (or points-to sets) for objects, so I'm
>> tracking for the moment: ALOAD for the right-hand side of an
>> assignment; and ASTORE for the left-hand side of an expression. My
>> analysis is very simple because it detects cases like:
>>
>> if (someBoolean) {
>>    // Exoression 1
>>    // ALOAD 1
>>    // ASTORE 0
>>    o = a;
>> } else {
>>    // Exoression 2
>>    // ALOAD 2
>>    // ASTORE 0
>>    o = b;
>> }
>>
>> My question is (and I must say, I'm very new to this area): how do I
>> -- in a general way -- detect an expression like 1 and 2 above where
>> the bytecode for the left and right-hand side of an expression can be
>> become very complicated:
>>
>> // ALOAD A
>> // ALOAD B
>> // GETFIELD B.f
>> // GETFIELD B.f.f'
>> // PUTFIELD A.f
>> A.f = B.f.f'
>>
>> Do I need to define a Deterministic Finite State Automata (DFA) for
>> all possible as a bunch switch, cases, which I think can get rather
>> large. Or is there a smarter way to do this, like modelling the
>> execution of the bytecode like in Analyzer.java, but I think this is
>> only useful for checking for type safety on opcode usage.
>>
>> The problem becomes more apparent when I want to see which objects are escaping:
>>
>> // ILOAD 0
>> // ALOAD 1
>> // INVOKESTATIC methodDispatch....
>> z = methodDispatch(int, Object);
>>
>> This is a rather simple case, and I could right a simple set of
>> switch, cases to detect this pattern in the bytecode, but integer
>> parameter might come from an object's field (ALOAD X, GETFIELD I) and
>> the same for the Object parameter; furthermore the number of
>> parameters could be N, and a method's signature can vary a lot: int,
>> double or double, float, Object, and so on...
>>
>> I fear the solution is going to be rather painful :-) and lengthly;
>> I'm kinda of thinking I'll need to define a DFA like:
>>
>> (s0) --ALOAD--> (s1) --GETFIELD--> (s2)  --ASTORE--> (s3)
>>
>> With a loop back from s2 to s1 and if I reach state s3 where s2 has
>> been visited twice then the bytecode sequence is:
>>
>> ALOAD
>> GETFIELD
>> GETFIELD
>> ASTORE
>>
>> And so on, but this can very easily get complex and out-of-hand with cases like:
>>
>> x = methodA(int, double, Object) + methodB(float, Array, Object.f.f')
>>
>> Any comments, suggestions would be GREATLY appreciate!!
>>
>> Many thanks,
>> Jon.
>>
>> --
>> You receive this message as a subscriber of the [email protected] mailing list.
>> To unsubscribe: mailto:[email protected]
>> For general help: mailto:[email protected]?subject=help
>> OW2 mailing lists service home page: http://www.ow2.org/wws
>
>

-- 
You receive this message as a subscriber of the [email protected] mailing list.
To unsubscribe: mailto:[email protected]
For general help: mailto:[email protected]?subject=help
OW2 mailing lists service home page: http://www.ow2.org/wws