|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object soot.toolkits.graph.MHGDominatorsFinder<N>
public class MHGDominatorsFinder<N>
Calculate dominators for basic blocks.
Uses the algorithm contained in Dragon book, pg. 670-1.
D(n0) := { n0 } for n in N - { n0 } do D(n) := N; while changes to any D(n) occur do for n in N - {n0} do D(n) := {n} U (intersect of D(p) over all predecessors p of n)2007/07/03 - updated to use
BitSet
s instead of HashSet
s, as the most expensive
operation in this algorithm used to be cloning of the fullSet, which is very cheap
for BitSet
s.
Field Summary | |
---|---|
protected BitSet |
fullSet
|
protected DirectedGraph<N> |
graph
|
protected List<N> |
heads
|
protected Map<Integer,N> |
indexToNode
|
protected int |
lastIndex
|
protected Map<N,BitSet> |
nodeToFlowSet
|
protected Map<N,Integer> |
nodeToIndex
|
Constructor Summary | |
---|---|
MHGDominatorsFinder(DirectedGraph<N> graph)
|
Method Summary | |
---|---|
protected void |
doAnalysis()
|
List<N> |
getDominators(Object node)
Returns a list of dominators for the given node in the graph. |
DirectedGraph<N> |
getGraph()
Returns the graph to which the analysis pertains. |
N |
getImmediateDominator(Object node)
Returns the immediate dominator of node or null if the node has no immediate dominator. |
protected int |
indexOf(N o)
|
boolean |
isDominatedBy(N node,
N dominator)
True if "node" is dominated by "dominator" in the graph. |
boolean |
isDominatedByAll(N node,
Collection<N> dominators)
True if "node" is dominated by all nodes in "dominators" in the graph. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
protected DirectedGraph<N> graph
protected BitSet fullSet
protected List<N> heads
protected Map<N,BitSet> nodeToFlowSet
protected Map<N,Integer> nodeToIndex
protected Map<Integer,N> indexToNode
protected int lastIndex
Constructor Detail |
---|
public MHGDominatorsFinder(DirectedGraph<N> graph)
Method Detail |
---|
protected void doAnalysis()
protected int indexOf(N o)
public DirectedGraph<N> getGraph()
DominatorsFinder
getGraph
in interface DominatorsFinder<N>
public List<N> getDominators(Object node)
DominatorsFinder
getDominators
in interface DominatorsFinder<N>
public N getImmediateDominator(Object node)
DominatorsFinder
getImmediateDominator
in interface DominatorsFinder<N>
public boolean isDominatedBy(N node, N dominator)
DominatorsFinder
isDominatedBy
in interface DominatorsFinder<N>
public boolean isDominatedByAll(N node, Collection<N> dominators)
DominatorsFinder
isDominatedByAll
in interface DominatorsFinder<N>
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |