Re: Soot bugs when first Unit is a target

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

On Fri, Jul 16, 2004 at 11:15:51AM -0500, Archie Cobbs wrote:
> > > For one thing, it's not clear to me what the definition of "head" is
> > > in the context of a directed graph. Is a head equivalent to a node with
> > > in-degree zero? (I don't think so, but..) If so, then BlockGraph.java is
> > > broken, because the first statement is always marked as a head.
> > 
> > This has come up before. I don't think the definition is clear to
> > anybody. It's not defined in DirectedGraph what a "head"/"tail" is.
> > In a DirectedGraph, the only definition that makes sense is nodes with
> > in/out-degree zero, respectively. Therefore, I believe UnitGraph and
> > BlockGraph should not redefine head/tail to mean entry/exit point, but
> > instead should define new methods for entry/exit points. This wasn't
> > done because nobody commented on it and it would break lots of existing
> > code, but IMHO it's more of a fix than a break, so I suggest it be done
> > anyway. I'd like to hear other opinions, however. BTW UnitGraph and
> > BlockGraph should get a common super-interface ControlFlowGraph with
> > these methods (which would be a sub-interface of DirectedGraph).
> 
> This sounds better to me. A directed graph (by traditional definition)
> has no such thing as a "head" or a "tail". So instead a subclass should
> add those concepts, where they should be clearly defined & documented.
> I also agree "entry" and "exit" are better terms than "head" and "tail".
> Changing the names will also help in quickly finding other code that
> needs to be updated :-)

I've been looking at this some more, and I've changed my mind about the
fix. There seem to be other subtypes of directed graph in Soot, which
are quite happy with the definition of heads/tails as nodes with
in/out-degree zero. Moreover, within DirectedGraph, we need some way
to get these nodes, because there is no way to get all the nodes; if a
node has no edges into it, how would we ever find it. So, I think we
should keep the getHeads()/getTails() methods, but change the incorrect
specification to say that they return the nodes with in/our-degree zero,
which is what various other classes assume anyway.

Then, in UnitGraph, these methods must respect the specification and
indeed return nodes with in/out-degree zero. This means that we need
to somehow identify entry/exit points. I've been thinking about your
example, where the entry point has an edge into it. I think this is very
strange, and is not usually the case in the example graphs that people
look at when they think about flow analysis. Since the entry/exit points
have to be treated specially (in many analyses, they are initialized to
different things), allowing them to have edges into them will lead to
confusing analyses at best, and possibly incorrect ones as well. The
standard thing in textbooks seems to be to have dummy entry/exit nodes.
Why can't we have those in UnitGraphs, and add methods to return them?
(Note that we couldn't just reuse getHeads/getTails, since although the
entry/exit nodes would have in/out-degree zero, there may be other nodes
that do, but are not heads/tails.)

What does everyone think?

Ondrej