soot.toolkits.graph
Class DominatorTree

java.lang.Object
  soot.toolkits.graph.DominatorTree

Direct Known Subclasses:

MHGDominatorTree

public class DominatorTree
extends Object

Constructs a dominator tree structure from the given DominatorsFinder. The nodes in DominatorTree are of type DominatorNode.

Note: DominatorTree does not currently implement DirectedGraph since it provides 4 methods of navigating the nodes where the meaning of getPredsOf and getSuccsOf diverge from the usual meaning in a DirectedGraph implementation.

If you need a DirectedGraph implementation, see DominatorTreeAdapter.

Author:

Navindra Umanee

Field Summary

protected DominatorsFinder	dominators
protected HashMap	godeToDode "gode" is a node in the original graph, "dode" is a node in the dominator tree.
protected DirectedGraph	graph
protected DominatorNode	head
protected ArrayList	tails

Constructor Summary

DominatorTree(DominatorsFinder dominators)

Method Summary

protected void	buildTree() Add all the necessary links between nodes to form a meaningful tree structure.
protected DominatorNode	fetchDode(Object gode) Convenience method, ensures we don't create more than one DominatorNode for a given block.
protected DominatorNode	fetchParent(Object gode)
List	getChildrenOf(DominatorNode node) Returns the children of node in the tree.
DominatorNode	getDode(Object gode) Returns the DominatorNode for a given node in the original DirectedGraph.
DirectedGraph	getGraph() Returns the original graph to which the Dominator tree pertains.
DominatorNode	getHead() Returns the root of the dominator tree.
DominatorNode	getParentOf(DominatorNode node) Returns the parent of node in the tree, null if the node is at the root.
List<DominatorNode>	getPredsOf(DominatorNode node) Finds all the predecessors of node in the original DirectedGraph and returns a list of the corresponding DominatorNodes.
List<DominatorNode>	getSuccsOf(DominatorNode node) Finds all the successors of node in the original DirectedGraph and returns a list of the corresponding DominatorNodes.
List	getTails() Returns a list of the tails of the dominator tree.
boolean	isDominatorOf(DominatorNode dom, DominatorNode node) Returns true if dom dominates node.
boolean	isImmediateDominatorOf(DominatorNode idom, DominatorNode node) Returns true if idom immediately dominates node.
Iterator	iterator() Returns an iterator over the nodes in the tree.
int	size() Returns the number of nodes in the tree.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

dominators

protected DominatorsFinder dominators

graph

protected DirectedGraph graph

head

protected DominatorNode head

tails

protected ArrayList tails

godeToDode

protected HashMap godeToDode

"gode" is a node in the original graph, "dode" is a node in the dominator tree.

Constructor Detail

DominatorTree

public DominatorTree(DominatorsFinder dominators)

Method Detail

getGraph

public DirectedGraph getGraph()

Returns the original graph to which the Dominator tree pertains.

getHead

public DominatorNode getHead()

Returns the root of the dominator tree.

getTails

public List getTails()

Returns a list of the tails of the dominator tree.

getParentOf

public DominatorNode getParentOf(DominatorNode node)

Returns the parent of node in the tree, null if the node is at the root.

getChildrenOf

public List getChildrenOf(DominatorNode node)

Returns the children of node in the tree.

getPredsOf

public List<DominatorNode> getPredsOf(DominatorNode node)

Finds all the predecessors of node in the original DirectedGraph and returns a list of the corresponding DominatorNodes.

getSuccsOf

public List<DominatorNode> getSuccsOf(DominatorNode node)

Finds all the successors of node in the original DirectedGraph and returns a list of the corresponding DominatorNodes.

isImmediateDominatorOf

public boolean isImmediateDominatorOf(DominatorNode idom,
                                      DominatorNode node)

Returns true if idom immediately dominates node.

isDominatorOf

public boolean isDominatorOf(DominatorNode dom,
                             DominatorNode node)

Returns true if dom dominates node.

getDode

public DominatorNode getDode(Object gode)

Returns the DominatorNode for a given node in the original DirectedGraph.

iterator

public Iterator iterator()

Returns an iterator over the nodes in the tree. No ordering is implied.

size

public int size()

Returns the number of nodes in the tree.

buildTree

protected void buildTree()

Add all the necessary links between nodes to form a meaningful tree structure.

fetchDode

protected DominatorNode fetchDode(Object gode)

Convenience method, ensures we don't create more than one DominatorNode for a given block.

fetchParent

protected DominatorNode fetchParent(Object gode)