Re: Scene rebuild

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

On Tue, Aug 19, 2003 at 08:07:10PM -0500, Manoj Plakal wrote:
> 
> Right, I can individually rebuild
> stuff that I know will be affected
> by my changes. Which is what
> I am doing now. But perhaps the
> "inter-stuff" dependencies could
> be made a bit more explicit.
> 
> So I have two questions:
>   - What stuff needs to be rebuilt?
>       - depends on what I'm changing. 
>         Fine, I can decide that and
>         manually call Soot phases
>         to rebuild their information.
> 
>   - Are there dependences between the
>     various kinds of stuff? Is there magic
>     inside Soot to invalidate information
>     when dependent objects are changed?
>     E.g., does the hierarchy get invalidated
>     when classes are added or removed?
> 
> The latter question is a bit harder for
> me to answer, it depends on what Soot
> does internally. This will also be an issue for 
> anyone who is writing a whole-program transformation
> phase, or composing multiple whole-program
> transformation phases. Each such phase
> will have to be preceded by code that
> ensures that the Scene structures are
> consistent.
> 
> As a concrete suggestion, I would suggest
> adding some sort of 'requirements' or
> dependence information in Soot phases
> that compute persistent information.
> Updates of dependent information should
> trigger an invalidation of objects
> that use that information. E.g., the
> hierarchy is automatically invalidated
> whenever classes are added or removed,
> or if the inherits relation is changed.
> And perhaps, objects can then automatically
> rebuild themselves when they are accessed
> in an invalid state.

This sounds like it would be nice, but might be very difficult to design
and implement (possibly a research topic?). All the method bodies depend
on the hierarchy (because of the typing algorithm). Do you want to
re-jimplify everything whenever you add a class or otherwise change the
hierarchy? The pointer analysis can be affected by adding or removing
just about any statement. Detecting whether a statement affects it
or not is non-trivial. Removing a single call would mean having to
recompute the set of reachable methods, and the call graph from scratch.
Depending on the settings, there may be a circular dependence between
the points-to analysis and the call graph.

So far, we've done the following: the analyses give you information
about the original code. If you only do semantics-preserving
transformations (for some loose deifinition of semantics-preserving),
the analyses should not have to change. If you do something that might
change them in a way that would affect other phases, it's up to you to
update them, either incrementally, or by rebuilding them. For example,
the method inliner has always incrementally updated the call graph.
If you're doing non-semantics-preserving transformations, such as using
Soot to add code for instrumenting, then do you really want the
information to reflect the code you've added so far, or the original
code?

Anyway, the dependences I know of are the following:

hierarchy depends on set of classes and subclass relationships, loaded
with loadClassAndSupport

bodies depend on hierarchy

call graph, reachable methods, and points-to analysis depend on bodies,
hierarchy, and interdepend on each other

side-effect analysis depends on call graph and points-to analysis

Ondrej

> 
> I've seen such a setup in another Java
> compiler I'm using (not publicly available),
> where they use a small array of requirements
> to tag each transformation and analysis
> phase. The requirements encode things like
> being in SSA form, having reaching definitions
> computed, etc. Each phase checks that
> the required information is available
> and recomputes it if necessary before
> executing its own code. Available information
> is invalidated if the underlying code is
> updated by any phase.
> 
> Manoj
> 
> 
> Ondrej Lhotak wrote (Tue, Aug 19, 2003 at 08:17:42PM -0400) :
> > On Tue, Aug 19, 2003 at 06:10:17PM -0500, Manoj Plakal wrote:
> > > 
> > > Hello Soot-ers,
> > > 
> > > What's the recommended way to rebuild a Scene's
> > > hierarchies and analyses after modifying a Scene? 
> > > 
> > > I'm adding classes and modifying
> > > methods and adding entry points, and right
> > > now I'm manually calling Scene methods to
> > > delete and rebuild certain analyses. But
> > > I'm not 100% sure if I'm missing an update
> > > somewhere.
> > > 
> > > Is there a canonical way to rebuild the 
> > > entire scene including the hierarchy, call graph, 
> > > and points-to analysis, ensuring everything
> > > is consistent and up-to-date?
> > > 
> > > Perhaps forceRebuildScene() could be added as 
> > > a method to the Scene class.
> > 
> > Unfortunately, that's easier said than done. The Scene is a container of
> > global data, not an active object that actually builds things. It's used
> > as a place where pieces of Soot store things for other pieces of Soot to
> > pick up. When classes are read in, they are stored in the Scene. When
> > a call graph is read in, it is stored in the Scene. If you wanted a way
> > to clear out "everything" from the Scene, you would first have to define
> > what you mean by "everything". Presumably, in your case, you don't want
> > it to clear out and rebuild all the classes, even though conceptually,
> > they are no different than the call graph, in that they're just
> > something that's built by some phase of Soot and stashed in the Scene.
> > 
> > As for rebuilding all the things once you clear them out, you need to
> > figure out where they get rebuilt. The hierarchy gets magically built
> > when you first ask for it, because it's used by the intraprocedural type
> > inference code. The call graph and points-to analysis get built by the
> > cg phase.
> > 
> > I agree that the Scene contains a lot of cruft that makes it difficult
> > to tell what everything is and what gets created where, and how it
> > should all be cleaned up. We cleaned up a lot of this in the transition
> > to Soot 2.0, by moving a lot of things out of the Scene. Concrete
> > suggestions for ways of cleaning it up further are welcome.
> > 
> > > 
> > > Thanks,
> > > Manoj
> > > 
> > > PS: I'd also like to know the recommended way
> > > to add entry points of my own and then rebuild
> > > the call graph and points-to analysis. Right now
> > > I'm imitating what I see in the Soot source.
> > 
> > The recommended way is to call Scene.v().setEntryPoints() before doing
> > anything else with Soot.
> > 
> > >