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.)