[Soot-list] Control Flow Graph representation

[John Jorgensen]

>>>>> "bruno" == Bruno Harbulot <bruno.harbulot at cs.man.ac.uk> writes:

    bruno> The javadoc for
    bruno> soot.toolkits.graph.ExceptionalUnitGraph says: "For
    bruno> every Unit which may implicitly throw an exception
    bruno> that could be caught by a Trap in the Body, there will
    bruno> be an edge from each of the excepting Unit's
    bruno> predecessors to the Trap handler's first Unit (since
    bruno> any of those predecessors may have been the last Unit
    bruno> to complete execution before the handler starts
    bruno> execution)."

    bruno> Our FOAL2005 paper [1], in Section 7, talked briefly
    bruno> about an example from [2]. I was suggesting a
    bruno> work-around to make the corresponding CFG reducible by
    bruno> introducing a pseudo-node just before a node
    bruno> representing an excepting Unit: the exceptional edge
    bruno> would come from that pseudo-node instead of the
    bruno> previous non-excepting node.

    bruno> How feasible would it be to extend
    bruno> ExceptionalUnitGraph to have this kind of
    bruno> structure? Is it possible to have "empty"
    bruno> nodes in a UnitGraph?  

Despite being the person who wrote the sentence you quote from
ExceptionalUnitGraph's javadoc, I don't have an answer to your
question. All I can offer is a vague memory of a discussion 
involving some of the same issues that confront you.

There's a nasty variant of the need to include edges from all the
predecessors of a potentially excepting Unit to the catching
handler: what if the excepting Unit is the method's entry point,
and thus has no predecessors?

What I chose to do was to include the catching handler Unit in the
set of Units reported by ExceptionalUnitGraph.getHeads(), since
any of those Units might be the first Unit to execute to
completion (if the handlers are themselves protected by handlers,
you even need to do a transitive closure; there's some discussion
of this in sections 2.4 and 3.3.3 of the technical report
http://www.sable.mcgill.ca/publications/techreports/#report2003-3,
but it's probably of limited relevance to you).

Having getHeads() return multiple Units like this is nasty, so we
considered the possibility of adding a special Begin node to the
CFG which would not correspond to any instruction in the original
code, but would have the regular entry point as well as the
relevant handlers as its successors.  This Begin node would work
like your pseudo-node for making loops reducible.

Had we been designing ExceptionalUnitGraph from scratch, the
Begin node would certainly have been the way to go.  But Soot had
already existed for a couple years and ExceptionalUnitGraph needed
to work with client analyses written for its predecessor,
CompleteUnitGraph. Every node in CompleteUnitGraph corresponds
to an instruction in the intermediate representation of the
method: i.e. a Unit that would be found by iterating through the
method's UnitChain (in fact, UnitGraph.iterator() still returns
the underlying method's UnitChain iterator).  I wasn't confident
of my ability to determine which, if any, client analyses actually
depend on that one-to-one correspondence between CFG nodes and
Units, so I left well enough alone.

So if your pseudo-node were to remain in the graph seen by
existing Soot analyses, you'd need to worry about whether those
analyses could deal with nodes that don't correspond to
instructions. 

The workaround of adding nop's corresponding to your new nodes
faces two complications:  

  you need to ensure that none of Soot's optimization passes
  remove the nops before you're finished with them;

  even nops can throw exceptions. Asynchronous exceptions are
  always possible, so if your nop is in the scope of a handler
  which catches Throwable (e.g. one implementing a synchronized
  block), then there will be exceptional edges from the nop's
  predecessors to the handler.  If your loop is in the middle of
  a try block, then, you might have to split the exception range
  to keep the nop out of all handlers' scopes.

A conceivable variant would be to add your pseudo-node to the
graph without adding anything to the method's UnitChain,
reimplementing ExceptionalUnitGraph's iterator to iterate over
the graph nodes, rather than the UnitChain's nodes. Maybe this
iterator's next() would return a Nop for the pseudo-nodes.  Or
maybe the regular iterator, for use by the ignorant, could skip
over the pseudo-nodes completely, while a new special iterator
was made available for analyses that know about pseudo-nodes and
how to deal with them.

Sorry to provide only questions, rather than answers.
It could be that none of these issues present serious
difficulties at all.

-- 
John Jorgensen	LCD System Administrator  jorgnsn at lcd.uregina.ca
                                          306.337.2344