com.ibm.wala.ssa.analysis
Class ExplodedControlFlowGraph

java.lang.Object
  com.ibm.wala.ssa.analysis.ExplodedControlFlowGraph

All Implemented Interfaces:

ControlFlowGraph<SSAInstruction,IExplodedBasicBlock>, EdgeManager<IExplodedBasicBlock>, Graph<IExplodedBasicBlock>, NodeManager<IExplodedBasicBlock>, NumberedEdgeManager<IExplodedBasicBlock>, NumberedGraph<IExplodedBasicBlock>, NumberedNodeManager<IExplodedBasicBlock>, java.lang.Iterable<IExplodedBasicBlock>

public class ExplodedControlFlowGraph
extends java.lang.Object
implements ControlFlowGraph<SSAInstruction,IExplodedBasicBlock>

A view of a control flow graph where each basic block corresponds to exactly one SSA instruction index. Prototype: Not terribly efficient.

Method Summary

void	addEdge(IExplodedBasicBlock src, IExplodedBasicBlock dst)
void	addNode(IExplodedBasicBlock n) add a node to this graph
boolean	containsNode(IExplodedBasicBlock N)
IExplodedBasicBlock	entry() Return the entry basic block in the CFG
IExplodedBasicBlock	exit()
IExplodedBasicBlock	getBlockForInstruction(int index)
BitVector	getCatchBlocks()
java.util.Collection<IExplodedBasicBlock>	getExceptionalPredecessors(IExplodedBasicBlock bb) The order of blocks returned should be arbitrary but deterministic.
java.util.List<IExplodedBasicBlock>	getExceptionalSuccessors(IExplodedBasicBlock bb) The order of blocks returned must indicate the exception-handling scope.
SSAInstruction[]	getInstructions()
IR	getIR()
int	getMaxNumber()
IMethod	getMethod()
IExplodedBasicBlock	getNode(int number)
java.util.Collection<IExplodedBasicBlock>	getNormalPredecessors(IExplodedBasicBlock bb) The order of blocks returned should be arbitrary but deterministic.
java.util.Collection<IExplodedBasicBlock>	getNormalSuccessors(IExplodedBasicBlock bb) The order of blocks returned should be arbitrary but deterministic.
int	getNumber(IExplodedBasicBlock n)
int	getNumberOfNodes()
int	getPredNodeCount(IExplodedBasicBlock bb) Return the number of immediate predecessor nodes of n
IntSet	getPredNodeNumbers(IExplodedBasicBlock node)
java.util.Iterator<IExplodedBasicBlock>	getPredNodes(IExplodedBasicBlock bb) Return an Iterator over the immediate predecessor nodes of n This method never returns null.
int	getProgramCounter(int index) TODO: move this into IR?
int	getSuccNodeCount(IExplodedBasicBlock N) Return the number of immediate successor nodes of this Node in the Graph
IntSet	getSuccNodeNumbers(IExplodedBasicBlock node)
java.util.Iterator<IExplodedBasicBlock>	getSuccNodes(IExplodedBasicBlock bb) Return an Iterator over the immediate successor nodes of n
boolean	hasEdge(IExplodedBasicBlock src, IExplodedBasicBlock dst)
java.util.Iterator<IExplodedBasicBlock>	iterateNodes(IntSet s)
java.util.Iterator<IExplodedBasicBlock>	iterator()
static ExplodedControlFlowGraph	make(IR ir)
void	removeAllIncidentEdges(IExplodedBasicBlock node)
void	removeEdge(IExplodedBasicBlock src, IExplodedBasicBlock dst)
void	removeIncomingEdges(IExplodedBasicBlock node)
void	removeNode(IExplodedBasicBlock n) remove a node from this graph
void	removeNodeAndEdges(IExplodedBasicBlock N) remove a node and all its incident edges
void	removeOutgoingEdges(IExplodedBasicBlock node)
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Method Detail

make

public static ExplodedControlFlowGraph make(IR ir)

entry

public IExplodedBasicBlock entry()

Description copied from interface: ControlFlowGraph

Return the entry basic block in the CFG

Specified by:

entry in interface ControlFlowGraph<SSAInstruction,IExplodedBasicBlock>

exit

public IExplodedBasicBlock exit()

Specified by:

exit in interface ControlFlowGraph<SSAInstruction,IExplodedBasicBlock>

Returns:

the synthetic exit block for the cfg

getBlockForInstruction

public IExplodedBasicBlock getBlockForInstruction(int index)

Specified by:

getBlockForInstruction in interface ControlFlowGraph<SSAInstruction,IExplodedBasicBlock>

Parameters:

index - an instruction index

Returns:

the basic block which contains this instruction.

getCatchBlocks

public BitVector getCatchBlocks()

Specified by:

getCatchBlocks in interface ControlFlowGraph<SSAInstruction,IExplodedBasicBlock>

Returns:

the indices of the catch blocks, as a bit vector

getExceptionalPredecessors

public java.util.Collection<IExplodedBasicBlock> getExceptionalPredecessors(IExplodedBasicBlock bb)

Description copied from interface: ControlFlowGraph

The order of blocks returned should be arbitrary but deterministic.

Specified by:

getExceptionalPredecessors in interface ControlFlowGraph<SSAInstruction,IExplodedBasicBlock>

Returns:

the basic blocks from which b may be reached via exceptional control flow

getExceptionalSuccessors

public java.util.List<IExplodedBasicBlock> getExceptionalSuccessors(IExplodedBasicBlock bb)

Description copied from interface: ControlFlowGraph

The order of blocks returned must indicate the exception-handling scope. So the first block is the first candidate catch block, and so on. With this invariant one can compute the exceptional control flow for a given exception type.

Specified by:

getExceptionalSuccessors in interface ControlFlowGraph<SSAInstruction,IExplodedBasicBlock>

Returns:

the basic blocks which may be reached from b via exceptional control flow

getInstructions

public SSAInstruction[] getInstructions()

Specified by:

getInstructions in interface ControlFlowGraph<SSAInstruction,IExplodedBasicBlock>

Returns:

the instructions of this CFG, as an array.

getMethod

public IMethod getMethod()
                  throws UnimplementedError

Specified by:

getMethod in interface ControlFlowGraph<SSAInstruction,IExplodedBasicBlock>

Returns:

the Method this CFG represents

Throws:

UnimplementedError

getNormalPredecessors

public java.util.Collection<IExplodedBasicBlock> getNormalPredecessors(IExplodedBasicBlock bb)

Description copied from interface: ControlFlowGraph

The order of blocks returned should be arbitrary but deterministic.

Specified by:

getNormalPredecessors in interface ControlFlowGraph<SSAInstruction,IExplodedBasicBlock>

Returns:

the basic blocks from which b may be reached via normal control flow

getNormalSuccessors

public java.util.Collection<IExplodedBasicBlock> getNormalSuccessors(IExplodedBasicBlock bb)

Description copied from interface: ControlFlowGraph

The order of blocks returned should be arbitrary but deterministic.

Specified by:

getNormalSuccessors in interface ControlFlowGraph<SSAInstruction,IExplodedBasicBlock>

Returns:

the basic blocks which may be reached from b via normal control flow

getProgramCounter

public int getProgramCounter(int index)
                      throws UnimplementedError

Description copied from interface: ControlFlowGraph

TODO: move this into IR?

Specified by:

getProgramCounter in interface ControlFlowGraph<SSAInstruction,IExplodedBasicBlock>

Parameters:

index - an instruction index

Returns:

the program counter (bytecode index) corresponding to that instruction

Throws:

UnimplementedError

removeNodeAndEdges

public void removeNodeAndEdges(IExplodedBasicBlock N)
                        throws java.lang.UnsupportedOperationException

Description copied from interface: Graph

remove a node and all its incident edges

Specified by:

removeNodeAndEdges in interface Graph<IExplodedBasicBlock>

Throws:

java.lang.UnsupportedOperationException - if the graph implementation does not allow removal

addNode

public void addNode(IExplodedBasicBlock n)
             throws java.lang.UnsupportedOperationException

Description copied from interface: NodeManager

add a node to this graph

Specified by:

addNode in interface NodeManager<IExplodedBasicBlock>

Throws:

java.lang.UnsupportedOperationException

containsNode

public boolean containsNode(IExplodedBasicBlock N)

Specified by:

containsNode in interface NodeManager<IExplodedBasicBlock>

Returns:

true iff the graph contains the specified node

getNumberOfNodes

public int getNumberOfNodes()

Specified by:

getNumberOfNodes in interface NodeManager<IExplodedBasicBlock>

Returns:

the number of nodes in this graph

iterator

public java.util.Iterator<IExplodedBasicBlock> iterator()

Specified by:

iterator in interface NodeManager<IExplodedBasicBlock>

Specified by:

iterator in interface java.lang.Iterable<IExplodedBasicBlock>

Returns:

an Iterator of the nodes in this graph

removeNode

public void removeNode(IExplodedBasicBlock n)
                throws java.lang.UnsupportedOperationException

Description copied from interface: NodeManager

remove a node from this graph

Specified by:

removeNode in interface NodeManager<IExplodedBasicBlock>

Throws:

java.lang.UnsupportedOperationException

addEdge

public void addEdge(IExplodedBasicBlock src,
                    IExplodedBasicBlock dst)
             throws java.lang.UnsupportedOperationException

Specified by:

addEdge in interface EdgeManager<IExplodedBasicBlock>

Throws:

java.lang.UnsupportedOperationException

getPredNodeCount

public int getPredNodeCount(IExplodedBasicBlock bb)
                     throws java.lang.IllegalArgumentException

Description copied from interface: EdgeManager

Return the number of immediate predecessor nodes of n

Specified by:

getPredNodeCount in interface EdgeManager<IExplodedBasicBlock>

Returns:

the number of immediate predecessors of n.

Throws:

java.lang.IllegalArgumentException

getPredNodes

public java.util.Iterator<IExplodedBasicBlock> getPredNodes(IExplodedBasicBlock bb)
                                                     throws java.lang.IllegalArgumentException

Description copied from interface: EdgeManager

Return an Iterator over the immediate predecessor nodes of n This method never returns null.

Specified by:

getPredNodes in interface EdgeManager<IExplodedBasicBlock>

Returns:

an Iterator over the immediate predecessor nodes of this Node.

Throws:

java.lang.IllegalArgumentException

getSuccNodeCount

public int getSuccNodeCount(IExplodedBasicBlock N)
                     throws UnimplementedError

Description copied from interface: EdgeManager

Return the number of immediate successor nodes of this Node in the Graph

Specified by:

getSuccNodeCount in interface EdgeManager<IExplodedBasicBlock>

Returns:

the number of immediate successor Nodes of this Node in the Graph.

Throws:

UnimplementedError

getSuccNodes

public java.util.Iterator<IExplodedBasicBlock> getSuccNodes(IExplodedBasicBlock bb)

Description copied from interface: EdgeManager

Return an Iterator over the immediate successor nodes of n

This method never returns null.

Specified by:

getSuccNodes in interface EdgeManager<IExplodedBasicBlock>

Returns:

an Iterator over the immediate successor nodes of n

hasEdge

public boolean hasEdge(IExplodedBasicBlock src,
                       IExplodedBasicBlock dst)
                throws UnimplementedError

Specified by:

hasEdge in interface EdgeManager<IExplodedBasicBlock>

Throws:

UnimplementedError

removeAllIncidentEdges

public void removeAllIncidentEdges(IExplodedBasicBlock node)
                            throws java.lang.UnsupportedOperationException

Specified by:

removeAllIncidentEdges in interface EdgeManager<IExplodedBasicBlock>

Throws:

java.lang.UnsupportedOperationException

removeEdge

public void removeEdge(IExplodedBasicBlock src,
                       IExplodedBasicBlock dst)
                throws java.lang.UnsupportedOperationException

Specified by:

removeEdge in interface EdgeManager<IExplodedBasicBlock>

Throws:

java.lang.UnsupportedOperationException

removeIncomingEdges

public void removeIncomingEdges(IExplodedBasicBlock node)
                         throws java.lang.UnsupportedOperationException

Specified by:

removeIncomingEdges in interface EdgeManager<IExplodedBasicBlock>

Throws:

java.lang.UnsupportedOperationException

removeOutgoingEdges

public void removeOutgoingEdges(IExplodedBasicBlock node)
                         throws java.lang.UnsupportedOperationException

Specified by:

removeOutgoingEdges in interface EdgeManager<IExplodedBasicBlock>

Throws:

java.lang.UnsupportedOperationException

getMaxNumber

public int getMaxNumber()

Specified by:

getMaxNumber in interface NumberedNodeManager<IExplodedBasicBlock>

getNode

public IExplodedBasicBlock getNode(int number)

Specified by:

getNode in interface NumberedNodeManager<IExplodedBasicBlock>

getNumber

public int getNumber(IExplodedBasicBlock n)
              throws java.lang.IllegalArgumentException

Specified by:

getNumber in interface NumberedNodeManager<IExplodedBasicBlock>

Throws:

java.lang.IllegalArgumentException

iterateNodes

public java.util.Iterator<IExplodedBasicBlock> iterateNodes(IntSet s)
                                                     throws UnimplementedError

Specified by:

iterateNodes in interface NumberedNodeManager<IExplodedBasicBlock>

Returns:

iterator of nodes with the numbers in set s

Throws:

UnimplementedError

getPredNodeNumbers

public IntSet getPredNodeNumbers(IExplodedBasicBlock node)

Specified by:

getPredNodeNumbers in interface NumberedEdgeManager<IExplodedBasicBlock>

Returns:

the numbers identifying the immediate predecessors of node

getSuccNodeNumbers

public IntSet getSuccNodeNumbers(IExplodedBasicBlock node)
                          throws UnimplementedError

Specified by:

getSuccNodeNumbers in interface NumberedEdgeManager<IExplodedBasicBlock>

Returns:

the numbers identifying the immediate successors of node

Throws:

UnimplementedError

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

getIR

public IR getIR()