Class ICFGSupergraph
java.lang.Object
com.ibm.wala.dataflow.IFDS.ICFGSupergraph
- All Implemented Interfaces:
ISupergraph<BasicBlockInContext<IExplodedBasicBlock>,
,CGNode> EdgeManager<BasicBlockInContext<IExplodedBasicBlock>>
,Graph<BasicBlockInContext<IExplodedBasicBlock>>
,NodeManager<BasicBlockInContext<IExplodedBasicBlock>>
,NumberedEdgeManager<BasicBlockInContext<IExplodedBasicBlock>>
,NumberedGraph<BasicBlockInContext<IExplodedBasicBlock>>
,NumberedNodeManager<BasicBlockInContext<IExplodedBasicBlock>>
,Iterable<BasicBlockInContext<IExplodedBasicBlock>>
public class ICFGSupergraph
extends Object
implements ISupergraph<BasicBlockInContext<IExplodedBasicBlock>,CGNode>
Forward supergraph induced over an
ExplodedInterproceduralCFG
This should lazily build the supergraph as it is explored.
- Author:
- sjfink
-
Field Summary
Fields inherited from interface com.ibm.wala.dataflow.IFDS.ISupergraph
CALL_EDGE, CALL_TO_RETURN_EDGE, OTHER, RETURN_EDGE
-
Constructor Summary
-
Method Summary
Modifier and TypeMethodDescriptionvoid
void
add a node to this graphbyte
classifyEdge
(BasicBlockInContext<IExplodedBasicBlock> src, BasicBlockInContext<IExplodedBasicBlock> dest) boolean
Iterator
<? extends BasicBlockInContext<IExplodedBasicBlock>> getCallSites
(BasicBlockInContext<IExplodedBasicBlock> r, CGNode callee) getEntriesForProcedure
(CGNode procedure) getExitsForProcedure
(CGNode procedure) getICFG()
getLocalBlock
(CGNode procedure, int i) int
int
getNode
(int number) int
int
getNumberOfBlocks
(CGNode procedure) int
int
Return the number ofimmediate predecessor
nodes of nReturn anIterator
over the immediate predecessor nodes of nIterator
<? extends BasicBlockInContext<IExplodedBasicBlock>> getReturnSites
(BasicBlockInContext<IExplodedBasicBlock> call, CGNode callee) int
Return the number ofimmediate successor
nodes of this Node in the GraphReturn an Iterator over the immediate successor nodes of nboolean
boolean
boolean
boolean
boolean
iterator()
static ICFGSupergraph
void
void
removeEdge
(BasicBlockInContext<IExplodedBasicBlock> src, BasicBlockInContext<IExplodedBasicBlock> 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, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.lang.Iterable
forEach, spliterator
-
Constructor Details
-
ICFGSupergraph
-
-
Method Details
-
make
-
getProcedureGraph
- Specified by:
getProcedureGraph
in interfaceISupergraph<BasicBlockInContext<IExplodedBasicBlock>,
CGNode> - Returns:
- the graph of procedures (e.g. a call graph) over which this supergraph is induced.
-
getClassHierarchy
-
classifyEdge
public byte classifyEdge(BasicBlockInContext<IExplodedBasicBlock> src, BasicBlockInContext<IExplodedBasicBlock> dest) - Specified by:
classifyEdge
in interfaceISupergraph<BasicBlockInContext<IExplodedBasicBlock>,
CGNode> - Parameters:
src
- node in the supergraphdest
- a successor of src in the supergraph- Returns:
- one of CALL_EDGE, RETURN_EDGE, CALL_TO_RETURN_EDGE, or OTHER
-
getCallSites
public Iterator<BasicBlockInContext<IExplodedBasicBlock>> getCallSites(BasicBlockInContext<IExplodedBasicBlock> r, CGNode callee) - Specified by:
getCallSites
in interfaceISupergraph<BasicBlockInContext<IExplodedBasicBlock>,
CGNode> - Parameters:
r
- a "return" node in the supergraphcallee
- a "called" "procedure" in the supergraph. if callee is null, answer return sites for which no callee was found.- Returns:
- the corresponding call nodes. There may be many.
-
getCalledNodes
public Iterator<? extends BasicBlockInContext<IExplodedBasicBlock>> getCalledNodes(BasicBlockInContext<IExplodedBasicBlock> call) - Specified by:
getCalledNodes
in interfaceISupergraph<BasicBlockInContext<IExplodedBasicBlock>,
CGNode> - Parameters:
call
- a "call" node in the supergraph- Returns:
- an Iterator of nodes that are targets of this call.
-
getEntriesForProcedure
- Specified by:
getEntriesForProcedure
in interfaceISupergraph<BasicBlockInContext<IExplodedBasicBlock>,
CGNode> - Returns:
- the blocks in the supergraph that represents entry nodes for procedure p
-
getExitsForProcedure
- Specified by:
getExitsForProcedure
in interfaceISupergraph<BasicBlockInContext<IExplodedBasicBlock>,
CGNode> - Returns:
- the blocks in the supergraph that represents exit nodes for procedure p
-
getLocalBlock
- Specified by:
getLocalBlock
in interfaceISupergraph<BasicBlockInContext<IExplodedBasicBlock>,
CGNode> - Parameters:
procedure
- an object that represents a procedurei
- the "logical" basic block number of a node in the procedure- Returns:
- the corresponding node in the supergraph
-
getLocalBlockNumber
- Specified by:
getLocalBlockNumber
in interfaceISupergraph<BasicBlockInContext<IExplodedBasicBlock>,
CGNode> - Parameters:
n
- a node in the supergraph- Returns:
- the "logical" basic block number of n in its procedure
-
getMainEntry
-
getNormalSuccessors
public Iterator<BasicBlockInContext<IExplodedBasicBlock>> getNormalSuccessors(BasicBlockInContext<IExplodedBasicBlock> call) - Specified by:
getNormalSuccessors
in interfaceISupergraph<BasicBlockInContext<IExplodedBasicBlock>,
CGNode> - Parameters:
call
- a "call" node in the supergraph- Returns:
- an Iterator of nodes that are normal (non-call) successors of this call. This should only apply to backwards problems, where we might have, say, a call and a goto flow into a return site.
-
getNumberOfBlocks
- Specified by:
getNumberOfBlocks
in interfaceISupergraph<BasicBlockInContext<IExplodedBasicBlock>,
CGNode> - Parameters:
procedure
- an object that represents a procedure- Returns:
- the number of blocks from this procedure in this supergraph
-
getProcOf
- Specified by:
getProcOf
in interfaceISupergraph<BasicBlockInContext<IExplodedBasicBlock>,
CGNode> - Parameters:
n
- a node in the supergraph- Returns:
- an object which represents the procedure which contains n
-
getReturnSites
public Iterator<? extends BasicBlockInContext<IExplodedBasicBlock>> getReturnSites(BasicBlockInContext<IExplodedBasicBlock> call, CGNode callee) - Specified by:
getReturnSites
in interfaceISupergraph<BasicBlockInContext<IExplodedBasicBlock>,
CGNode> - Parameters:
call
- a "call" node in the supergraphcallee
- a "called" "procedure" in the supergraph. if callee is null, answer return sites for which no callee was found.- Returns:
- the corresponding return nodes. There may be many, because of exceptional control flow.
-
isCall
- Specified by:
isCall
in interfaceISupergraph<BasicBlockInContext<IExplodedBasicBlock>,
CGNode> - Parameters:
n
- a node in this supergraph- Returns:
- true iff this node includes a call.
-
isEntry
- Specified by:
isEntry
in interfaceISupergraph<BasicBlockInContext<IExplodedBasicBlock>,
CGNode> - Returns:
- true iff this node is an entry node s_p for a procedure
-
isExit
- Specified by:
isExit
in interfaceISupergraph<BasicBlockInContext<IExplodedBasicBlock>,
CGNode> - Parameters:
n
- a node in the supergraph- Returns:
- true iff this node is an exit node
-
isReturn
- Specified by:
isReturn
in interfaceISupergraph<BasicBlockInContext<IExplodedBasicBlock>,
CGNode> - Parameters:
n
- a node in this supergraph- Returns:
- true iff this node is a return site.
-
removeNodeAndEdges
public void removeNodeAndEdges(BasicBlockInContext<IExplodedBasicBlock> N) throws UnsupportedOperationException Description copied from interface:Graph
remove a node and all its incident edges- Specified by:
removeNodeAndEdges
in interfaceGraph<BasicBlockInContext<IExplodedBasicBlock>>
- Throws:
UnsupportedOperationException
- if the graph implementation does not allow removal
-
addNode
Description copied from interface:NodeManager
add a node to this graph- Specified by:
addNode
in interfaceNodeManager<BasicBlockInContext<IExplodedBasicBlock>>
-
containsNode
- Specified by:
containsNode
in interfaceNodeManager<BasicBlockInContext<IExplodedBasicBlock>>
- Returns:
- true iff the graph contains the specified node
-
getNumberOfNodes
public int getNumberOfNodes()- Specified by:
getNumberOfNodes
in interfaceNodeManager<BasicBlockInContext<IExplodedBasicBlock>>
- Returns:
- the number of nodes in this graph
-
iterator
- Specified by:
iterator
in interfaceIterable<BasicBlockInContext<IExplodedBasicBlock>>
- Specified by:
iterator
in interfaceNodeManager<BasicBlockInContext<IExplodedBasicBlock>>
- Returns:
- an
Iterator
of the nodes in this graph
-
stream
- Specified by:
stream
in interfaceNodeManager<BasicBlockInContext<IExplodedBasicBlock>>
- Returns:
- a
Stream
of the nodes in this graph
-
removeNode
Description copied from interface:NodeManager
remove a node from this graph- Specified by:
removeNode
in interfaceNodeManager<BasicBlockInContext<IExplodedBasicBlock>>
-
addEdge
public void addEdge(BasicBlockInContext<IExplodedBasicBlock> src, BasicBlockInContext<IExplodedBasicBlock> dst) - Specified by:
addEdge
in interfaceEdgeManager<BasicBlockInContext<IExplodedBasicBlock>>
-
getPredNodeCount
Description copied from interface:EdgeManager
Return the number ofimmediate predecessor
nodes of n- Specified by:
getPredNodeCount
in interfaceEdgeManager<BasicBlockInContext<IExplodedBasicBlock>>
- Returns:
- the number of immediate predecessors of n.
-
getPredNodes
public Iterator<BasicBlockInContext<IExplodedBasicBlock>> getPredNodes(BasicBlockInContext<IExplodedBasicBlock> N) Description copied from interface:EdgeManager
Return anIterator
over the immediate predecessor nodes of nThis method never returns
null
.- Specified by:
getPredNodes
in interfaceEdgeManager<BasicBlockInContext<IExplodedBasicBlock>>
- Returns:
- an
Iterator
over the immediate predecessor nodes of this Node.
-
getSuccNodeCount
Description copied from interface:EdgeManager
Return the number ofimmediate successor
nodes of this Node in the Graph- Specified by:
getSuccNodeCount
in interfaceEdgeManager<BasicBlockInContext<IExplodedBasicBlock>>
- Returns:
- the number of immediate successor Nodes of this Node in the Graph.
-
getSuccNodes
public Iterator<BasicBlockInContext<IExplodedBasicBlock>> getSuccNodes(BasicBlockInContext<IExplodedBasicBlock> N) Description copied from interface:EdgeManager
Return an Iterator over the immediate successor nodes of nThis method never returns
null
.- Specified by:
getSuccNodes
in interfaceEdgeManager<BasicBlockInContext<IExplodedBasicBlock>>
- Returns:
- an Iterator over the immediate successor nodes of n
-
hasEdge
public boolean hasEdge(BasicBlockInContext<IExplodedBasicBlock> src, BasicBlockInContext<IExplodedBasicBlock> dst) - Specified by:
hasEdge
in interfaceEdgeManager<BasicBlockInContext<IExplodedBasicBlock>>
-
removeAllIncidentEdges
public void removeAllIncidentEdges(BasicBlockInContext<IExplodedBasicBlock> node) throws UnsupportedOperationException - Specified by:
removeAllIncidentEdges
in interfaceEdgeManager<BasicBlockInContext<IExplodedBasicBlock>>
- Throws:
UnsupportedOperationException
-
removeEdge
public void removeEdge(BasicBlockInContext<IExplodedBasicBlock> src, BasicBlockInContext<IExplodedBasicBlock> dst) throws UnsupportedOperationException - Specified by:
removeEdge
in interfaceEdgeManager<BasicBlockInContext<IExplodedBasicBlock>>
- Throws:
UnsupportedOperationException
-
removeIncomingEdges
public void removeIncomingEdges(BasicBlockInContext<IExplodedBasicBlock> node) throws UnsupportedOperationException - Specified by:
removeIncomingEdges
in interfaceEdgeManager<BasicBlockInContext<IExplodedBasicBlock>>
- Throws:
UnsupportedOperationException
-
removeOutgoingEdges
public void removeOutgoingEdges(BasicBlockInContext<IExplodedBasicBlock> node) throws UnsupportedOperationException - Specified by:
removeOutgoingEdges
in interfaceEdgeManager<BasicBlockInContext<IExplodedBasicBlock>>
- Throws:
UnsupportedOperationException
-
getMaxNumber
public int getMaxNumber()- Specified by:
getMaxNumber
in interfaceNumberedNodeManager<BasicBlockInContext<IExplodedBasicBlock>>
-
getNode
- Specified by:
getNode
in interfaceNumberedNodeManager<BasicBlockInContext<IExplodedBasicBlock>>
-
getNumber
- Specified by:
getNumber
in interfaceNumberedNodeManager<BasicBlockInContext<IExplodedBasicBlock>>
-
iterateNodes
- Specified by:
iterateNodes
in interfaceNumberedNodeManager<BasicBlockInContext<IExplodedBasicBlock>>
- Returns:
- iterator of nodes with the numbers in set s
-
getPredNodeNumbers
- Specified by:
getPredNodeNumbers
in interfaceNumberedEdgeManager<BasicBlockInContext<IExplodedBasicBlock>>
- Returns:
- the numbers identifying the immediate predecessors of node
-
getSuccNodeNumbers
- Specified by:
getSuccNodeNumbers
in interfaceNumberedEdgeManager<BasicBlockInContext<IExplodedBasicBlock>>
- Returns:
- the numbers identifying the immediate successors of node
-
getCFG
public ControlFlowGraph<SSAInstruction,IExplodedBasicBlock> getCFG(BasicBlockInContext<IExplodedBasicBlock> node) -
getICFG
-
toString
-