Re: Options for replacing use of UnitGraph() constructor (continued)

[John Jorgensen <jorgnsn@lcd.uregina.ca>]

(I'm going to respond to your question with two separate
messages, because I would like input from any "specification
lawyers" on the list (hello Etienne!) to the second part, and I
suspect few people are going to have the interest to read very
far into this first part of my response.)

    vranganath> I am bit concerned about how you are merging
    vranganath> edges relevant for data flow analyses and mere
    vranganath> CFG rather than distinguishing the edges based on
    vranganath> cause criteria.

I may be misunderstand what you are saying here, since I am not
sure how to interpret "mere CFG" and "cause criteria".

As I lament in section 2.4 of the technical report
(http://www.sable.mcgill.ca/publications/techreports/#report2003-3) 
the fact that exceptions interrupt an instruction
makes it difficult to have a "mere CFG", if by that you mean a
graph where each edge has a clear, rigorous meaning.

In the absence of exceptions, a CFG edge from node 'a' to node
'b' means that 'b' executes after 'a' has executed to
completion: when you get to 'b', all of the work at 'a' has been
done. 

To preserve the same interpretation of CFG edges in the presence
of exceptions, when 'a' might throw an exception to 'b', you
should draw edges to 'b' from each of the predecessors of 'a',
not 'a' itself, since those predecessors are the last
instructions to complete before 'b'.  But if 'a' might have side
effects that occur before the exception is thrown, there is no
way to preserve the simple interpretation of the CFG edge; you
need edges to the handler 'b' from 'a' itself---to indicate that
some state changes may have occurred at 'a' before 'b'
executes---as well as from all 'a's predecessors, to indicate
that not all of 'a's work has been completed.

I'm guessing that your idea of a "mere CFG" would always have an
edge from the excepting unit 'a' to the handler unit 'b', and no
edges from 'a's predecessors.  That would be consistent with an
interpretation of CFG edges that says there is an edge from 'a'
to 'b' if 'b' may be the next instruction to start execution
after 'a' has started execution. That may well be the appropriate
interpretation when the graph is being used to aid program
understanding by humans. It is not the appropriate interpretation
when the graph is being used for dataflow analyses by a compiler;
for dataflow analyses, what counts is whether the state of the
computation has actually changed.

The CFG classes provided with soot are used for dataflow analyses
within it (Soot started life as a compiler framework, after all),
so they need an interpretation of CFG edges that comes as close as
we can get to "all work at 'a' has been completed before the
transfer of control to 'b'". 

I'm guessing that by "cause criteria", you are suggesting that
the CFG could distinguish between unexceptional control flow
edges and exceptional control flow edges --- with the latter
drawn from excepting units to their handlers --- and that
analyses could then interpret the two two sorts of edges
differently. ExceptionalUnitGraph's interface can be used that
way now, albeit clumsily.  Use getUnexceptionalSuccsOf() and
getUnexceptionalPredsOf() to get the regular CFG edges, and use
getExceptionDests() to get edges from excepting units to their
handlers.

(getPredsOf() and getSuccsOf() continue to provide the
combination of exceptional and unexceptional edges to ensure
backward compatibility to clients of ComputeUnitGraph and
TrapUnitGraph. Perhaps getExceptionalSuccsOf() and
getExceptionalPredsOf(), which return what amounts to

  get{Succs,Preds}Of() - getUnexceptional{Preds,Succs()}Of

should be omitted or named differently.)

If your need a different interpretation of CFG edges, you can
override ExceptionalUnitGraph.buildExceptionalEdges() with a
method that doesn't add any edges from the predecessors of
excepting units, and which always adds edges to handlers from the
excepting units themselves.