Class SSACFG
- All Implemented Interfaces:
ControlFlowGraph<SSAInstruction,
,ISSABasicBlock> MinimalCFG<ISSABasicBlock>
,EdgeManager<ISSABasicBlock>
,Graph<ISSABasicBlock>
,NodeManager<ISSABasicBlock>
,NumberedEdgeManager<ISSABasicBlock>
,NumberedGraph<ISSABasicBlock>
,NumberedNodeManager<ISSABasicBlock>
,Iterable<ISSABasicBlock>
This implementation is uglified in the name of performance. This implementation does not
directly track the graph structure, but instead delegates to a prebuilt ControlFlowGraph
which stores the structure. This decision from 2004 may have been premature optimization, left
over from a world where IR
s and related structures were long-lived. In today's system,
they are cached and reconstituted by SSACache
. Perhaps we should just extend AbstractCFG
and not worry so much about space.
As the current implementation stands, the delegate graph stores the graph structure, and this
class additionally stores SSACFG.BasicBlock
s and the SSAInstruction
array.
-
Nested Class Summary
Modifier and TypeClassDescriptionclass
A Basic Block in an SSA IRclass
-
Field Summary
Modifier and TypeFieldDescriptionprotected final AbstractCFG
<IInstruction, IBasicBlock<IInstruction>> A delegate CFG, pre-built, which stores the graph structure of this CFG.protected final SSAInstruction[]
The "normal" instructions which constitute the SSA form.protected final IMethod
TheIMethod
thisControlFlowGraph
represents -
Constructor Summary
-
Method Summary
Modifier and TypeMethodDescriptionvoid
addEdge
(ISSABasicBlock src, ISSABasicBlock dst) void
add a node to this graphboolean
entry()
Return the entry basic block in the CFGboolean
exit()
getBasicBlock
(int bb) getBlockForInstruction
(int instructionIndex) Get the basic block an instruction belongs to.The order of blocks returned should be arbitrary but deterministic.The order of blocks returned must indicate the exception-handling scope.NB: Use iterators such as IR.iterateAllInstructions() instead of this method.int
getNode
(int number) The order of blocks returned should be arbitrary but deterministic.The order of blocks returned should be arbitrary but deterministic.int
int
int
Return the number ofimmediate predecessor
nodes of nReturn anIterator
over the immediate predecessor nodes of nint
getProgramCounter
(int index) TODO: move this into IR?int
Return the number ofimmediate successor
nodes of this Node in the GraphReturn 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()
void
void
removeEdge
(ISSABasicBlock src, ISSABasicBlock dst) void
void
remove a node from this graphvoid
remove a node and all its incident edgesvoid
stream()
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 Details
-
instructions
The "normal" instructions which constitute the SSA form. This does not includeSSAPhiInstruction
s, which dwell inSSACFG.BasicBlock
s instead. -
method
TheIMethod
thisControlFlowGraph
represents -
delegate
A delegate CFG, pre-built, which stores the graph structure of this CFG.
-
-
Constructor Details
-
SSACFG
- Throws:
IllegalArgumentException
- if method is null
-
-
Method Details
-
hashCode
-
equals
-
getBlockForInstruction
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
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.
-
toString
-
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
Description copied from interface:MinimalCFG
Return the entry basic block in the CFG- Specified by:
entry
in interfaceMinimalCFG<ISSABasicBlock>
-
exit
- Specified by:
exit
in interfaceMinimalCFG<ISSABasicBlock>
- Returns:
- the synthetic exit block for the cfg
-
getNumber
- Specified by:
getNumber
in interfaceNumberedNodeManager<ISSABasicBlock>
- Throws:
IllegalArgumentException
-
getNode
- Specified by:
getNode
in interfaceNumberedNodeManager<ISSABasicBlock>
- See Also:
-
getMaxNumber
public int getMaxNumber()- Specified by:
getMaxNumber
in interfaceNumberedNodeManager<ISSABasicBlock>
- See Also:
-
iterator
- Specified by:
iterator
in interfaceIterable<ISSABasicBlock>
- Specified by:
iterator
in interfaceNodeManager<ISSABasicBlock>
- Returns:
- an
Iterator
of the nodes in this graph - See Also:
-
stream
- Specified by:
stream
in interfaceNodeManager<ISSABasicBlock>
- Returns:
- a
Stream
of the nodes in this graph
-
getNumberOfNodes
public int getNumberOfNodes()- Specified by:
getNumberOfNodes
in interfaceNodeManager<ISSABasicBlock>
- Returns:
- the number of nodes in this graph
- See Also:
-
getPredNodes
Description copied from interface:EdgeManager
Return anIterator
over the immediate predecessor nodes of nThis method never returns
null
.- Specified by:
getPredNodes
in interfaceEdgeManager<ISSABasicBlock>
- Returns:
- an
Iterator
over the immediate predecessor nodes of this Node. - Throws:
IllegalArgumentException
- See Also:
-
getPredNodeCount
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
- See Also:
-
getSuccNodes
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
- See Also:
-
getSuccNodeCount
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
- See Also:
-
addNode
Description copied from interface:NodeManager
add a node to this graph- Specified by:
addNode
in interfaceNodeManager<ISSABasicBlock>
- Throws:
UnsupportedOperationException
- See Also:
-
addEdge
- Specified by:
addEdge
in interfaceEdgeManager<ISSABasicBlock>
- Throws:
UnsupportedOperationException
-
removeEdge
- Specified by:
removeEdge
in interfaceEdgeManager<ISSABasicBlock>
- Throws:
UnsupportedOperationException
-
removeAllIncidentEdges
- Specified by:
removeAllIncidentEdges
in interfaceEdgeManager<ISSABasicBlock>
- Throws:
UnsupportedOperationException
- See Also:
-
removeNodeAndEdges
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- See Also:
-
removeNode
Description copied from interface:NodeManager
remove a node from this graph- Specified by:
removeNode
in interfaceNodeManager<ISSABasicBlock>
- Throws:
UnsupportedOperationException
- See Also:
-
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
- Specified by:
containsNode
in interfaceNodeManager<ISSABasicBlock>
- Returns:
- true iff the graph contains the specified node
- See Also:
-
getMethod
- Specified by:
getMethod
in interfaceControlFlowGraph<SSAInstruction,
ISSABasicBlock> - Returns:
- the Method this CFG represents
-
getExceptionalSuccessors
Description copied from interface:MinimalCFG
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 interfaceMinimalCFG<ISSABasicBlock>
- Returns:
- the basic blocks which may be reached from b via exceptional control flow
-
getExceptionalPredecessors
Description copied from interface:MinimalCFG
The order of blocks returned should be arbitrary but deterministic.- Specified by:
getExceptionalPredecessors
in interfaceMinimalCFG<ISSABasicBlock>
- Returns:
- the basic blocks from which b may be reached via exceptional control flow
- See Also:
-
hasExceptionalEdge
has exceptional edge src -> dest- Throws:
IllegalArgumentException
- if dest is null
-
hasNormalEdge
has normal edge src -> dest- Throws:
IllegalArgumentException
- if dest is null
-
getNormalSuccessors
Description copied from interface:MinimalCFG
The order of blocks returned should be arbitrary but deterministic.- Specified by:
getNormalSuccessors
in interfaceMinimalCFG<ISSABasicBlock>
- Returns:
- the basic blocks which may be reached from b via normal control flow
-
getNormalPredecessors
Description copied from interface:MinimalCFG
The order of blocks returned should be arbitrary but deterministic.- Specified by:
getNormalPredecessors
in interfaceMinimalCFG<ISSABasicBlock>
- Returns:
- the basic blocks from which b may be reached via normal control flow
- See Also:
-
iterateNodes
- Specified by:
iterateNodes
in interfaceNumberedNodeManager<ISSABasicBlock>
- Returns:
- iterator of nodes with the numbers in set s
- See Also:
-
removeIncomingEdges
- Specified by:
removeIncomingEdges
in interfaceEdgeManager<ISSABasicBlock>
- Throws:
UnsupportedOperationException
-
removeOutgoingEdges
- Specified by:
removeOutgoingEdges
in interfaceEdgeManager<ISSABasicBlock>
- Throws:
UnsupportedOperationException
-
hasEdge
- Specified by:
hasEdge
in interfaceEdgeManager<ISSABasicBlock>
- Throws:
UnimplementedError
-
getSuccNodeNumbers
- Specified by:
getSuccNodeNumbers
in interfaceNumberedEdgeManager<ISSABasicBlock>
- Returns:
- the numbers identifying the immediate successors of node
- Throws:
IllegalArgumentException
-
getPredNodeNumbers
- Specified by:
getPredNodeNumbers
in interfaceNumberedEdgeManager<ISSABasicBlock>
- Returns:
- the numbers identifying the immediate predecessors of node
- Throws:
UnimplementedError
-
getBasicBlock
- Returns:
- the basic block with a particular number
-