Re: Limiting whole-program analysis

[Ondrej Lhotak <olhotak@sable.mcgill.ca>]

On Thu, Jun 03, 2004 at 09:51:45AM +0200, Helge Jensen wrote:
> 
> 
> Ondrej Lhotak wrote:
> 
> > Yes, these are consistent with what I'm seeing.
> 
> Ouch...
> 
> Tracing the ResolveMethod.addMethod, I can see that more than 14000 
> methods are entered into the call-graph of the program:
> 
>    public class A { public static void main(String[] a) {} };
> 
> So that would explain why it takes so long.
> 
> > I tend to run Spark with the class library from the 1.3.1 JDK, which in
> > this case ends up running about 6 times faster. I'm not quite sure what
> > it is about the 1.4 class library that takes so long.
> 
> The 14000 methods are on the 1.4 class libs, i'll try out the 1.3.1 and 
> make a count again.
> 
> I'm aiming at analyzing the points-to sets and call-graphs for just a 
> few classes, and (at least in the edit/compile/debug/test cycle) 2 mins. 
> is a long time to wait for something seemingly that simple.

For debugging, I use an even smaller class library, from JDK 1.1.8. With
that one, your example runs in 11 seconds. That should be acceptable.
Other people working on points-to (not with Spark) use GNU Classpath,
which is even smaller. I haven't tried analyzing it with Spark.

In Java, there is no such thing as a small program with just a few
classes. If you run a Hello World program and use the JVM's profiler
interface to see what's going on, you will see that about 500 distinct
methods are actually executed. Of course, at least all of these must
appear in any conservative static call graph.

> Is there a way where i can reliably limit the visited graph, in a 
> consistent manner? So as to say "it's faster, but it may disregard 
> class-constructors and methods in the java.** packages".
> 
> For example by (ordered by expected simplicity):
> 
>    1. Reducing the precision of the analysis, by preventing it from 
> visiting method-calls, class-constructors, serialization, ...
>    2. Tranforming the CFG, replacing virtualinvoke for some places with 
> "NOOP"

If you want the analysis to still be conservative, simple things break
down. For example, consider a program with a GUI containing a button.
When the uesr clicks the button, the library button code calls some
method in the program. This method is otherwise not called anywhere in
the program, so if you ignore the library, you won't ever think that
this method is even reachable. Yet for programs with GUIs, it's not
uncommon to have most of their functionality in methods invoked as a
result of user actions, so you'll be ignoring most of the program.

There is some published work on analyzing programs and making
conservative assumptions about the library, particularly by Atanas
Rountev. I have some ideas about this as well, but none of them have
been implemented.

Ondrej

> 
> Note, that the "possible bug" i reported occurs only when i prevent 
> ReachableMethods.addMethod from invoking reachable.add(m) for ALL m. So 
> that solutions doesn't seem to work.
> 
> -- 
> Helge
>