Re: Reverse control flow graph for control dependence

[Navindra Umanee <navindra@cs.mcgill.ca>]

Neil Walkinshaw <Neil.Walkinshaw@cis.strath.ac.uk> wrote:
> I'm trying to use Soot to compute intra-procedural control dependencies 
> using Cytron's algorithm. According to this, I need to compute the 
> dominator tree on a reverse control flow graph. I have found the 
> soot.shimple.internal.analysis.DominatorTree class which accepts a 

You should be able to get DominatorTree to work without too much
hassle, but please note that it's marked "internal and messy" because
the implementation and interface really isn't all that pretty and
might make certain undocumented assumptions.  One thing that's
immediately obvious is that some of the exposed public interfaces are
really meant for internal use only.

You can therefore expect the code to change significantly in the
future.  I will be cleaning up the code and moving it out of
shimple/internal into jimple/toolkits for public use especially since
I've been getting several enquiries about it.

> BlockGraph, but since the BlockGraph is not mutable, it seems impossible 
> to construct a MutableDirectedGraph which reverses the Blockgraph in 
> question. Are there any convenience methods in soot which I have 
> overlooked? Do you have any suggestions that might help?

I think it should be fairly easy to hack this at a lower level:

Basically iterate through all the Blocks and reverse the predecessors
with the successors for each block.  Look at the API documentation for
Block for how to do this.  

Okay, then you have to reverse the heads with the tails... you can
easily do this by modifying the (backed) lists you get from getHeads
and getTails.  Not at all ideal, I agree, but it should work.  :-)

Another gotcha: You will probably have to run
OneHeadBlockGraph.convert on the resulting graph before passing it to
DominatorTree.

Cheers,
Navin.