Package com.ibm.wala.ssa
Class SSACFG
- java.lang.Object
-
- com.ibm.wala.ssa.SSACFG
-
- All Implemented Interfaces:
ControlFlowGraph<SSAInstruction,ISSABasicBlock>
,EdgeManager<ISSABasicBlock>
,Graph<ISSABasicBlock>
,NodeManager<ISSABasicBlock>
,NumberedEdgeManager<ISSABasicBlock>
,NumberedGraph<ISSABasicBlock>
,NumberedNodeManager<ISSABasicBlock>
,Iterable<ISSABasicBlock>
public class SSACFG extends Object implements ControlFlowGraph<SSAInstruction,ISSABasicBlock>
A control-flow graph for ssa form. This implementation is uglified in the name of performance. This implementation does not directly track the graph structure, but instead delegates to a prebuiltControlFlowGraph
which stores the structure. This decision from 2004 may have been premature optimization, left over from a world whereIR
s and related structures were long-lived. In today's system, they are cached and reconstituted bySSACache
. Perhaps we should just extendAbstractCFG
and not worry so much about space. As the current implementation stands, the delegate graph stores the graph structure, and this class additionally storesSSACFG.BasicBlock
s and theSSAInstruction
array.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description class
SSACFG.BasicBlock
A Basic Block in an SSA IRclass
SSACFG.ExceptionHandlerBasicBlock
-
Field Summary
Fields Modifier and Type Field Description protected AbstractCFG<IInstruction,IBasicBlock<IInstruction>>
delegate
A delegate CFG, pre-built, which stores the graph structure of this CFG.protected SSAInstruction[]
instructions
The "normal" instructions which constitute the SSA form.protected IMethod
method
TheIMethod
thisControlFlowGraph
represents
-
Constructor Summary
Constructors Constructor Description SSACFG(IMethod method, AbstractCFG cfg, SSAInstruction[] instructions)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
addEdge(ISSABasicBlock src, ISSABasicBlock dst)
void
addNode(ISSABasicBlock n)
add a node to this graphboolean
containsNode(ISSABasicBlock N)
SSACFG.BasicBlock
entry()
Return the entry basic block in the CFGboolean
equals(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()
Collection<ISSABasicBlock>
getExceptionalPredecessors(ISSABasicBlock b)
The order of blocks returned should be arbitrary but deterministic.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)
Collection<ISSABasicBlock>
getNormalPredecessors(ISSABasicBlock b)
The order of blocks returned should be arbitrary but deterministic.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 ofimmediate predecessor
nodes of nIntSet
getPredNodeNumbers(ISSABasicBlock node)
Iterator<ISSABasicBlock>
getPredNodes(ISSABasicBlock b)
Return anIterator
over the immediate predecessor nodes of n This method never returnsnull
.int
getProgramCounter(int index)
TODO: move this into IR?int
getSuccNodeCount(ISSABasicBlock b)
Return the number ofimmediate successor
nodes of this Node in the GraphIntSet
getSuccNodeNumbers(ISSABasicBlock b)
Iterator<ISSABasicBlock>
getSuccNodes(ISSABasicBlock b)
Return an Iterator over the immediate successor nodes of nboolean
hasEdge(ISSABasicBlock src, ISSABasicBlock dst)
boolean
hasExceptionalEdge(SSACFG.BasicBlock src, SSACFG.BasicBlock dest)
has exceptional edge src -> destint
hashCode()
boolean
hasNormalEdge(SSACFG.BasicBlock src, SSACFG.BasicBlock dest)
has normal edge src -> destboolean
isCatchBlock(int i)
is the given i a catch block?Iterator<ISSABasicBlock>
iterateNodes(IntSet s)
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 graphvoid
removeNodeAndEdges(ISSABasicBlock N)
remove a node and all its incident edgesvoid
removeOutgoingEdges(ISSABasicBlock node)
String
toString()
-
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
-
Methods inherited from interface java.lang.Iterable
forEach, spliterator
-
-
-
-
Field Detail
-
instructions
protected final SSAInstruction[] instructions
The "normal" instructions which constitute the SSA form. This does not includeSSAPhiInstruction
s, which dwell inSSACFG.BasicBlock
s instead.
-
method
protected final IMethod method
TheIMethod
thisControlFlowGraph
represents
-
delegate
protected final AbstractCFG<IInstruction,IBasicBlock<IInstruction>> delegate
A delegate CFG, pre-built, which stores the graph structure of this CFG.
-
-
Constructor Detail
-
SSACFG
public SSACFG(IMethod method, AbstractCFG cfg, SSAInstruction[] instructions)
- Throws:
IllegalArgumentException
- if method is null
-
-
Method Detail
-
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 interfaceControlFlowGraph<SSAInstruction,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 interfaceControlFlowGraph<SSAInstruction,ISSABasicBlock>
- Returns:
- an array containing the SSA instructions.
-
getCatchBlocks
public BitVector getCatchBlocks()
- Specified by:
getCatchBlocks
in interfaceControlFlowGraph<SSAInstruction,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 interfaceControlFlowGraph<SSAInstruction,ISSABasicBlock>
-
exit
public SSACFG.BasicBlock exit()
- Specified by:
exit
in interfaceControlFlowGraph<SSAInstruction,ISSABasicBlock>
- Returns:
- the synthetic exit block for the cfg
-
getNumber
public int getNumber(ISSABasicBlock b) throws IllegalArgumentException
- Specified by:
getNumber
in interfaceNumberedNodeManager<ISSABasicBlock>
- Throws:
IllegalArgumentException
-
getNode
public SSACFG.BasicBlock getNode(int number)
- Specified by:
getNode
in interfaceNumberedNodeManager<ISSABasicBlock>
-
getMaxNumber
public int getMaxNumber()
- Specified by:
getMaxNumber
in interfaceNumberedNodeManager<ISSABasicBlock>
-
iterator
public Iterator<ISSABasicBlock> iterator()
- Specified by:
iterator
in interfaceIterable<ISSABasicBlock>
- Specified by:
iterator
in interfaceNodeManager<ISSABasicBlock>
- Returns:
- an
Iterator
of the nodes in this graph
-
getNumberOfNodes
public int getNumberOfNodes()
- Specified by:
getNumberOfNodes
in interfaceNodeManager<ISSABasicBlock>
- Returns:
- the number of nodes in this graph
-
getPredNodes
public Iterator<ISSABasicBlock> getPredNodes(ISSABasicBlock b) throws IllegalArgumentException
Description copied from interface:EdgeManager
Return anIterator
over the immediate predecessor nodes of n This method never returnsnull
.- Specified by:
getPredNodes
in interfaceEdgeManager<ISSABasicBlock>
- Returns:
- an
Iterator
over the immediate predecessor nodes of this Node. - Throws:
IllegalArgumentException
-
getPredNodeCount
public int getPredNodeCount(ISSABasicBlock b) throws IllegalArgumentException
Description copied from interface:EdgeManager
Return the number ofimmediate predecessor
nodes of n- Specified by:
getPredNodeCount
in interfaceEdgeManager<ISSABasicBlock>
- Returns:
- the number of immediate predecessors of n.
- Throws:
IllegalArgumentException
-
getSuccNodes
public Iterator<ISSABasicBlock> getSuccNodes(ISSABasicBlock b) throws IllegalArgumentException
Description copied from interface:EdgeManager
Return an Iterator over the immediate successor nodes of nThis method never returns
null
.- Specified by:
getSuccNodes
in interfaceEdgeManager<ISSABasicBlock>
- Returns:
- an Iterator over the immediate successor nodes of n
- Throws:
IllegalArgumentException
-
getSuccNodeCount
public int getSuccNodeCount(ISSABasicBlock b) throws IllegalArgumentException
Description copied from interface:EdgeManager
Return the number ofimmediate successor
nodes of this Node in the Graph- Specified by:
getSuccNodeCount
in interfaceEdgeManager<ISSABasicBlock>
- Returns:
- the number of immediate successor Nodes of this Node in the Graph.
- Throws:
IllegalArgumentException
-
addNode
public void addNode(ISSABasicBlock n) throws UnsupportedOperationException
Description copied from interface:NodeManager
add a node to this graph- Specified by:
addNode
in interfaceNodeManager<ISSABasicBlock>
- Throws:
UnsupportedOperationException
-
addEdge
public void addEdge(ISSABasicBlock src, ISSABasicBlock dst) throws UnsupportedOperationException
- Specified by:
addEdge
in interfaceEdgeManager<ISSABasicBlock>
- Throws:
UnsupportedOperationException
-
removeEdge
public void removeEdge(ISSABasicBlock src, ISSABasicBlock dst) throws UnsupportedOperationException
- Specified by:
removeEdge
in interfaceEdgeManager<ISSABasicBlock>
- Throws:
UnsupportedOperationException
-
removeAllIncidentEdges
public void removeAllIncidentEdges(ISSABasicBlock node) throws UnsupportedOperationException
- Specified by:
removeAllIncidentEdges
in interfaceEdgeManager<ISSABasicBlock>
- Throws:
UnsupportedOperationException
-
removeNodeAndEdges
public void removeNodeAndEdges(ISSABasicBlock N) throws UnsupportedOperationException
Description copied from interface:Graph
remove a node and all its incident edges- Specified by:
removeNodeAndEdges
in interfaceGraph<ISSABasicBlock>
- Throws:
UnsupportedOperationException
- if the graph implementation does not allow removal
-
removeNode
public void removeNode(ISSABasicBlock n) throws UnsupportedOperationException
Description copied from interface:NodeManager
remove a node from this graph- Specified by:
removeNode
in interfaceNodeManager<ISSABasicBlock>
- Throws:
UnsupportedOperationException
-
getProgramCounter
public int getProgramCounter(int index)
Description copied from interface:ControlFlowGraph
TODO: move this into IR?- Specified by:
getProgramCounter
in interfaceControlFlowGraph<SSAInstruction,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 interfaceNodeManager<ISSABasicBlock>
- Returns:
- true iff the graph contains the specified node
-
getMethod
public IMethod getMethod()
- Specified by:
getMethod
in interfaceControlFlowGraph<SSAInstruction,ISSABasicBlock>
- Returns:
- the Method this CFG represents
-
getExceptionalSuccessors
public 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 interfaceControlFlowGraph<SSAInstruction,ISSABasicBlock>
- Returns:
- the basic blocks which may be reached from b via exceptional control flow
-
getExceptionalPredecessors
public Collection<ISSABasicBlock> getExceptionalPredecessors(ISSABasicBlock b)
Description copied from interface:ControlFlowGraph
The order of blocks returned should be arbitrary but deterministic.- Specified by:
getExceptionalPredecessors
in interfaceControlFlowGraph<SSAInstruction,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:
IllegalArgumentException
- if dest is null
-
hasNormalEdge
public boolean hasNormalEdge(SSACFG.BasicBlock src, SSACFG.BasicBlock dest)
has normal edge src -> dest- Throws:
IllegalArgumentException
- if dest is null
-
getNormalSuccessors
public Collection<ISSABasicBlock> getNormalSuccessors(ISSABasicBlock b)
Description copied from interface:ControlFlowGraph
The order of blocks returned should be arbitrary but deterministic.- Specified by:
getNormalSuccessors
in interfaceControlFlowGraph<SSAInstruction,ISSABasicBlock>
- Returns:
- the basic blocks which may be reached from b via normal control flow
-
getNormalPredecessors
public Collection<ISSABasicBlock> getNormalPredecessors(ISSABasicBlock b)
Description copied from interface:ControlFlowGraph
The order of blocks returned should be arbitrary but deterministic.- Specified by:
getNormalPredecessors
in interfaceControlFlowGraph<SSAInstruction,ISSABasicBlock>
- Returns:
- the basic blocks from which b may be reached via normal control flow
-
iterateNodes
public Iterator<ISSABasicBlock> iterateNodes(IntSet s)
- Specified by:
iterateNodes
in interfaceNumberedNodeManager<ISSABasicBlock>
- Returns:
- iterator of nodes with the numbers in set s
-
removeIncomingEdges
public void removeIncomingEdges(ISSABasicBlock node) throws UnsupportedOperationException
- Specified by:
removeIncomingEdges
in interfaceEdgeManager<ISSABasicBlock>
- Throws:
UnsupportedOperationException
-
removeOutgoingEdges
public void removeOutgoingEdges(ISSABasicBlock node) throws UnsupportedOperationException
- Specified by:
removeOutgoingEdges
in interfaceEdgeManager<ISSABasicBlock>
- Throws:
UnsupportedOperationException
-
hasEdge
public boolean hasEdge(ISSABasicBlock src, ISSABasicBlock dst) throws UnimplementedError
- Specified by:
hasEdge
in interfaceEdgeManager<ISSABasicBlock>
- Throws:
UnimplementedError
-
getSuccNodeNumbers
public IntSet getSuccNodeNumbers(ISSABasicBlock b) throws IllegalArgumentException
- Specified by:
getSuccNodeNumbers
in interfaceNumberedEdgeManager<ISSABasicBlock>
- Returns:
- the numbers identifying the immediate successors of node
- Throws:
IllegalArgumentException
-
getPredNodeNumbers
public IntSet getPredNodeNumbers(ISSABasicBlock node) throws UnimplementedError
- Specified by:
getPredNodeNumbers
in interfaceNumberedEdgeManager<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
-
-