Re: Static Points-to Analysis Query

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