com.ibm.wala.ssa
Class SSACFG

java.lang.Object
  com.ibm.wala.ssa.SSACFG

All Implemented Interfaces:

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

public class SSACFG
extends java.lang.Object
implements ControlFlowGraph<ISSABasicBlock>

A control-flow graph for ssa form.

Nested Class Summary

class	SSACFG.BasicBlock A Basic Block in an SSA IR
class	SSACFG.ExceptionHandlerBasicBlock

Field Summary

protected AbstractCFG<IBasicBlock>	cfg
protected SSAInstruction[]	instructions
protected IMethod	method

Constructor Summary

	SSACFG(IMethod method, AbstractCFG cfg, SSAInstruction[] instructions)
protected	SSACFG(SSACFG aCFG)

Method Summary

void	addEdge(ISSABasicBlock src, ISSABasicBlock dst)
void	addNode(ISSABasicBlock n) add a node to this graph
boolean	containsNode(ISSABasicBlock N)
SSACFG.BasicBlock	entry() Return the entry basic block in the CFG
boolean	equals(java.lang.Object o)
SSACFG.BasicBlock	exit()
SSACFG.BasicBlock	getBasicBlock(int bb)
SSACFG.BasicBlock	getBlockForInstruction(int instructionIndex) Get the basic block an instruction belongs to.
BitVector	getCatchBlocks()
java.util.Collection<ISSABasicBlock>	getExceptionalPredecessors(ISSABasicBlock b) The order of blocks returned should be arbitrary but deterministic.
java.util.List<ISSABasicBlock>	getExceptionalSuccessors(ISSABasicBlock b) The order of blocks returned must indicate the exception-handling scope.
SSAInstruction[]	getInstructions() NB: Use iterators such as IR.iterateAllInstructions() instead of this method.
int	getMaxNumber()
IMethod	getMethod()
SSACFG.BasicBlock	getNode(int number)
java.util.Collection<ISSABasicBlock>	getNormalPredecessors(ISSABasicBlock b) The order of blocks returned should be arbitrary but deterministic.
java.util.Collection<ISSABasicBlock>	getNormalSuccessors(ISSABasicBlock b) The order of blocks returned should be arbitrary but deterministic.
int	getNumber(ISSABasicBlock b)
int	getNumberOfNodes()
int	getPredNodeCount(ISSABasicBlock b) Return the number of immediate predecessor nodes of this Node in the Graph.
IntSet	getPredNodeNumbers(ISSABasicBlock node)
java.util.Iterator<ISSABasicBlock>	getPredNodes(ISSABasicBlock b) Return an Iterator over the immediate predecessor nodes of this Node in the Graph.
int	getProgramCounter(int index) TODO: move this into IR?
int	getSuccNodeCount(ISSABasicBlock b) Return the number of immediate successor nodes of this Node in the Graph
IntSet	getSuccNodeNumbers(ISSABasicBlock b)
java.util.Iterator<ISSABasicBlock>	getSuccNodes(ISSABasicBlock b) Return an Iterator over the immediate successor nodes of this Node in the Graph
boolean	hasEdge(ISSABasicBlock src, ISSABasicBlock dst)
boolean	hasExceptionalEdge(SSACFG.BasicBlock src, SSACFG.BasicBlock dest) has exceptional edge src -> dest
int	hashCode()
boolean	hasNormalEdge(SSACFG.BasicBlock src, SSACFG.BasicBlock dest) has normal edge src -> dest
boolean	isCatchBlock(int i) is the given i a catch block?
java.util.Iterator<ISSABasicBlock>	iterateNodes(IntSet s)
java.util.Iterator<ISSABasicBlock>	iterator()
void	removeAllIncidentEdges(ISSABasicBlock node)
void	removeEdge(ISSABasicBlock src, ISSABasicBlock dst)
void	removeIncomingEdges(ISSABasicBlock node)
void	removeNode(ISSABasicBlock n) remove a node from this graph
void	removeNodeAndEdges(ISSABasicBlock N) remove a node and all its incident edges
void	removeOutgoingEdges(ISSABasicBlock node)
java.lang.String	toString()

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

instructions

protected final SSAInstruction[] instructions

method

protected final IMethod method

cfg

protected final AbstractCFG<IBasicBlock> cfg

Constructor Detail

SSACFG

protected SSACFG(SSACFG aCFG)

SSACFG

public SSACFG(IMethod method,
              AbstractCFG cfg,
              SSAInstruction[] instructions)

Throws:

java.lang.IllegalArgumentException - if method is null

Method Detail

hashCode

public int hashCode()

Overrides:

hashCode in class java.lang.Object

equals

public boolean equals(java.lang.Object o)

Overrides:

equals in class java.lang.Object

getBlockForInstruction

public SSACFG.BasicBlock getBlockForInstruction(int instructionIndex)

Get the basic block an instruction belongs to. Note: the instruction2Block array is filled in lazily. During initialization, the mapping is set up only for the first instruction of each basic block.

Specified by:

getBlockForInstruction in interface ControlFlowGraph<ISSABasicBlock>

Parameters:

instructionIndex - an instruction index

Returns:

the basic block which contains this instruction.

getInstructions

public SSAInstruction[] getInstructions()

NB: Use iterators such as IR.iterateAllInstructions() instead of this method. This will probably be deprecated someday. Return the instructions. Note that the CFG is created from the Shrike CFG prior to creating the SSA instructions.

Specified by:

getInstructions in interface ControlFlowGraph<ISSABasicBlock>

Returns:

an array containing the SSA instructions.

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

getCatchBlocks

public BitVector getCatchBlocks()

Specified by:

getCatchBlocks in interface ControlFlowGraph<ISSABasicBlock>

Returns:

the indices of the catch blocks, as a bit vector

isCatchBlock

public boolean isCatchBlock(int i)

is the given i a catch block?

Returns:

true if catch block, false otherwise

entry

public SSACFG.BasicBlock entry()

Description copied from interface: ControlFlowGraph

Return the entry basic block in the CFG

Specified by:

entry in interface ControlFlowGraph<ISSABasicBlock>

exit

public SSACFG.BasicBlock exit()

Specified by:

exit in interface ControlFlowGraph<ISSABasicBlock>

Returns:

the synthetic exit block for the cfg

getNumber

public int getNumber(ISSABasicBlock b)
              throws java.lang.IllegalArgumentException

Specified by:

getNumber in interface NumberedNodeManager<ISSABasicBlock>

Throws:

java.lang.IllegalArgumentException

getNode

public SSACFG.BasicBlock getNode(int number)

Specified by:

getNode in interface NumberedNodeManager<ISSABasicBlock>

getMaxNumber

public int getMaxNumber()

Specified by:

getMaxNumber in interface NumberedNodeManager<ISSABasicBlock>

iterator

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

Specified by:

iterator in interface NodeManager<ISSABasicBlock>

Specified by:

iterator in interface java.lang.Iterable<ISSABasicBlock>

Returns:

an Iterator of the nodes in this graph

getNumberOfNodes

public int getNumberOfNodes()

Specified by:

getNumberOfNodes in interface NodeManager<ISSABasicBlock>

Returns:

the number of nodes in this graph

getPredNodes

public java.util.Iterator<ISSABasicBlock> getPredNodes(ISSABasicBlock b)
                                                throws java.lang.IllegalArgumentException

Description copied from interface: EdgeManager

Return an Iterator over the immediate predecessor nodes of this Node in the Graph. This method never returns null.

Specified by:

getPredNodes in interface EdgeManager<ISSABasicBlock>

Returns:

an Iterator over the immediate predecessor nodes of this Node.

Throws:

java.lang.IllegalArgumentException

getPredNodeCount

public int getPredNodeCount(ISSABasicBlock b)
                     throws java.lang.IllegalArgumentException

Description copied from interface: EdgeManager

Return the number of immediate predecessor nodes of this Node in the Graph.

Specified by:

getPredNodeCount in interface EdgeManager<ISSABasicBlock>

Returns:

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

Throws:

java.lang.IllegalArgumentException

getSuccNodes

public java.util.Iterator<ISSABasicBlock> getSuccNodes(ISSABasicBlock b)
                                                throws java.lang.IllegalArgumentException

Description copied from interface: EdgeManager

Return an Iterator over the immediate successor nodes of this Node in the Graph

This method never returns null.

Specified by:

getSuccNodes in interface EdgeManager<ISSABasicBlock>

Returns:

an Iterator over the immediate successor Nodes of this Node.

Throws:

java.lang.IllegalArgumentException

getSuccNodeCount

public int getSuccNodeCount(ISSABasicBlock b)
                     throws java.lang.IllegalArgumentException

Description copied from interface: EdgeManager

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

Specified by:

getSuccNodeCount in interface EdgeManager<ISSABasicBlock>

Returns:

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

Throws:

java.lang.IllegalArgumentException

addNode

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

Description copied from interface: NodeManager

add a node to this graph

Specified by:

addNode in interface NodeManager<ISSABasicBlock>

Throws:

java.lang.UnsupportedOperationException

addEdge

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

Specified by:

addEdge in interface EdgeManager<ISSABasicBlock>

Throws:

java.lang.UnsupportedOperationException

removeEdge

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

Specified by:

removeEdge in interface EdgeManager<ISSABasicBlock>

Throws:

java.lang.UnsupportedOperationException

removeAllIncidentEdges

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

Specified by:

removeAllIncidentEdges in interface EdgeManager<ISSABasicBlock>

Throws:

java.lang.UnsupportedOperationException

removeNodeAndEdges

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

Description copied from interface: Graph

remove a node and all its incident edges

Specified by:

removeNodeAndEdges in interface Graph<ISSABasicBlock>

Throws:

java.lang.UnsupportedOperationException

removeNode

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

Description copied from interface: NodeManager

remove a node from this graph

Specified by:

removeNode in interface NodeManager<ISSABasicBlock>

Throws:

java.lang.UnsupportedOperationException

getProgramCounter

public int getProgramCounter(int index)

Description copied from interface: ControlFlowGraph

TODO: move this into IR?

Specified by:

getProgramCounter in interface ControlFlowGraph<ISSABasicBlock>

Parameters:

index - an instruction index

Returns:

the program counter (bytecode index) corresponding to that instruction

containsNode

public boolean containsNode(ISSABasicBlock N)

Specified by:

containsNode in interface NodeManager<ISSABasicBlock>

Returns:

true iff the graph contains the specified node

getMethod

public IMethod getMethod()

Specified by:

getMethod in interface ControlFlowGraph<ISSABasicBlock>

Returns:

the Method this CFG represents

getExceptionalSuccessors

public java.util.List<ISSABasicBlock> getExceptionalSuccessors(ISSABasicBlock b)

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<ISSABasicBlock>

Returns:

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

getExceptionalPredecessors

public java.util.Collection<ISSABasicBlock> getExceptionalPredecessors(ISSABasicBlock b)

Description copied from interface: ControlFlowGraph

The order of blocks returned should be arbitrary but deterministic.

Specified by:

getExceptionalPredecessors in interface ControlFlowGraph<ISSABasicBlock>

Returns:

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

hasExceptionalEdge

public boolean hasExceptionalEdge(SSACFG.BasicBlock src,
                                  SSACFG.BasicBlock dest)

has exceptional edge src -> dest

Throws:

java.lang.IllegalArgumentException - if dest is null

hasNormalEdge

public boolean hasNormalEdge(SSACFG.BasicBlock src,
                             SSACFG.BasicBlock dest)

has normal edge src -> dest

Throws:

java.lang.IllegalArgumentException - if dest is null

getNormalSuccessors

public java.util.Collection<ISSABasicBlock> getNormalSuccessors(ISSABasicBlock b)

Description copied from interface: ControlFlowGraph

The order of blocks returned should be arbitrary but deterministic.

Specified by:

getNormalSuccessors in interface ControlFlowGraph<ISSABasicBlock>

Returns:

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

getNormalPredecessors

public java.util.Collection<ISSABasicBlock> getNormalPredecessors(ISSABasicBlock b)

Description copied from interface: ControlFlowGraph

The order of blocks returned should be arbitrary but deterministic.

Specified by:

getNormalPredecessors in interface ControlFlowGraph<ISSABasicBlock>

Returns:

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

iterateNodes

public java.util.Iterator<ISSABasicBlock> iterateNodes(IntSet s)

Specified by:

iterateNodes in interface NumberedNodeManager<ISSABasicBlock>

Returns:

iterator of nodes with the numbers in set s

removeIncomingEdges

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

Specified by:

removeIncomingEdges in interface EdgeManager<ISSABasicBlock>

Throws:

java.lang.UnsupportedOperationException

removeOutgoingEdges

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

Specified by:

removeOutgoingEdges in interface EdgeManager<ISSABasicBlock>

Throws:

java.lang.UnsupportedOperationException

hasEdge

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

Specified by:

hasEdge in interface EdgeManager<ISSABasicBlock>

Throws:

UnimplementedError

getSuccNodeNumbers

public IntSet getSuccNodeNumbers(ISSABasicBlock b)
                          throws java.lang.IllegalArgumentException

Specified by:

getSuccNodeNumbers in interface NumberedEdgeManager<ISSABasicBlock>

Returns:

the numbers identifying the immediate successors of node

Throws:

java.lang.IllegalArgumentException

getPredNodeNumbers

public IntSet getPredNodeNumbers(ISSABasicBlock node)
                          throws UnimplementedError

Specified by:

getPredNodeNumbers in interface NumberedEdgeManager<ISSABasicBlock>

Returns:

the numbers identifying the immediate predecessors of node

Throws:

UnimplementedError

getBasicBlock

public SSACFG.BasicBlock getBasicBlock(int bb)

Returns:

the basic block with a particular number