Re: Incremental Points-to Analysis?

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

On Thu, Jan 15, 2004 at 04:48:18PM -0600, Joel Jones wrote:
> First, I would like to thank everyone who makes soot possible.  I 
> appreciate the great amount of effort that goes into a project like 
> this.
> 
> Fall semester, I had students in my graduate compiler class use soot 
> to develop an analysis for detecting problems with the use of 
> hashCode and equals.  One of
> the problems we encountered were the long run times.  Perhaps we were 
> doing something wrong, but it seemed that even the most trivial of 
> programs would require 8-10 minutes to analyze.  As the overall goal 
> of my research is to have an IDE that can detect design problems, 
> some sort of incremental analysis seems necessary.  I have examined 
> the web site carefully, but have been unable to find any work on 
> incremental points-to analysis.  Have I missed something?

To start off by answering your question, no, we don't have any sort of
incremental points-to analysis in Soot, nor any sort of incremental
anything, for that matter. The reason that Soot takes a long time
even on "trivial" programs is that it is doing a whole-program analysis,
which requires reading in all of the standard libraries, which are
anything but trivial. After this initial processing, the points-to
analysis itself is actually quite fast. Implementing some sort of
on-demand points-to analysis would do little to improve things, because
these analyses still need to start with a complete conservative call
graph, which is what would take the bulk of the time.

Of course, since the library rarely changes, it would be nice to be able
to avoid reprocessing them all the time. Incremental compilation is a
difficult problem, however. Even tools like javac and IDEs that I am
aware of do not handle all dependencies correctly, and often one must do
a "complete rebuild". Many people (including people here in the Sable
group) are now integrating their compiler work into IDE's and asking
similar kinds of questions, so perhaps this is a good time to start on a
new framework for exploring these incremental compilation issues and IDE
integration. Such a framework could reuse many of the ideas that have
been developed in Soot over there years; however, I'm pessimistic about
simply trying to shoehorn incremental compilation into a big hunk of code
that was never designed with it in mind.

To get back to the problem at hand, if what you need is fast local
points-to analysis, perhaps your best bet would be to only do some
intra-procedural pointer propagation, and make conservative assumptions
about things that flow in from outside the analyzed code. I'm not sure
whether the reduction in precision would be acceptable for your
application, however.

Ondrej


> 
> -- 
> Joel Jones                                         jones@cs.ua.edu
> Department of Computer Science             http://cs.ua.edu/~jones
> University of Alabama                               (205) 348-1618
>