Package com.ibm.wala.dataflow.IFDS
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 anExplodedInterproceduralCFG
This should lazily build the supergraph as it is explored.
-
-
Field Summary
-
Fields inherited from interface com.ibm.wala.dataflow.IFDS.ISupergraph
CALL_EDGE, CALL_TO_RETURN_EDGE, OTHER, RETURN_EDGE
-
-
Constructor Summary
Constructors Modifier Constructor Description protected
ICFGSupergraph(ExplodedInterproceduralCFG icfg, AnalysisCache cache)
-
Method Summary
-
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 Detail
-
ICFGSupergraph
protected ICFGSupergraph(ExplodedInterproceduralCFG icfg, AnalysisCache cache)
-
-
Method Detail
-
make
public static ICFGSupergraph make(CallGraph cg, AnalysisCache cache)
-
getProcedureGraph
public Graph<? extends CGNode> 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
public IClassHierarchy 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>
callee
- 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
public BasicBlockInContext<IExplodedBasicBlock>[] getEntriesForProcedure(CGNode procedure)
- Specified by:
getEntriesForProcedure
in interfaceISupergraph<BasicBlockInContext<IExplodedBasicBlock>,CGNode>
- Returns:
- the blocks in the supergraph that represents entry nodes for procedure p
-
getExitsForProcedure
public BasicBlockInContext<IExplodedBasicBlock>[] getExitsForProcedure(CGNode procedure)
- Specified by:
getExitsForProcedure
in interfaceISupergraph<BasicBlockInContext<IExplodedBasicBlock>,CGNode>
- Returns:
- the blocks in the supergraph that represents exit nodes for procedure p
-
getLocalBlock
public BasicBlockInContext<IExplodedBasicBlock> getLocalBlock(CGNode procedure, int i)
- 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
public int getLocalBlockNumber(BasicBlockInContext<IExplodedBasicBlock> n)
- 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
public BasicBlockInContext<IExplodedBasicBlock> 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
public int getNumberOfBlocks(CGNode procedure)
- 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
public CGNode getProcOf(BasicBlockInContext<IExplodedBasicBlock> n)
- 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
public boolean isCall(BasicBlockInContext<IExplodedBasicBlock> n)
- Specified by:
isCall
in interfaceISupergraph<BasicBlockInContext<IExplodedBasicBlock>,CGNode>
- Parameters:
n
- a node in this supergraph- Returns:
- true iff this node includes a call.
-
isEntry
public boolean isEntry(BasicBlockInContext<IExplodedBasicBlock> n)
- Specified by:
isEntry
in interfaceISupergraph<BasicBlockInContext<IExplodedBasicBlock>,CGNode>
- Returns:
- true iff this node is an entry node s_p for a procedure
-
isExit
public boolean isExit(BasicBlockInContext<IExplodedBasicBlock> n)
- 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
public boolean isReturn(BasicBlockInContext<IExplodedBasicBlock> n)
- 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
public void addNode(BasicBlockInContext<IExplodedBasicBlock> n)
Description copied from interface:NodeManager
add a node to this graph- Specified by:
addNode
in interfaceNodeManager<BasicBlockInContext<IExplodedBasicBlock>>
-
containsNode
public boolean containsNode(BasicBlockInContext<IExplodedBasicBlock> N)
- 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
public Iterator<BasicBlockInContext<IExplodedBasicBlock>> iterator()
- Specified by:
iterator
in interfaceIterable<BasicBlockInContext<IExplodedBasicBlock>>
- Specified by:
iterator
in interfaceNodeManager<BasicBlockInContext<IExplodedBasicBlock>>
- Returns:
- an
Iterator
of the nodes in this graph
-
removeNode
public void removeNode(BasicBlockInContext<IExplodedBasicBlock> n)
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
public int getPredNodeCount(BasicBlockInContext<IExplodedBasicBlock> N)
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 n This method never returnsnull
.- Specified by:
getPredNodes
in interfaceEdgeManager<BasicBlockInContext<IExplodedBasicBlock>>
- Returns:
- an
Iterator
over the immediate predecessor nodes of this Node.
-
getSuccNodeCount
public int getSuccNodeCount(BasicBlockInContext<IExplodedBasicBlock> N)
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
public BasicBlockInContext<IExplodedBasicBlock> getNode(int number)
- Specified by:
getNode
in interfaceNumberedNodeManager<BasicBlockInContext<IExplodedBasicBlock>>
-
getNumber
public int getNumber(BasicBlockInContext<IExplodedBasicBlock> N)
- Specified by:
getNumber
in interfaceNumberedNodeManager<BasicBlockInContext<IExplodedBasicBlock>>
-
iterateNodes
public Iterator<BasicBlockInContext<IExplodedBasicBlock>> iterateNodes(IntSet s)
- Specified by:
iterateNodes
in interfaceNumberedNodeManager<BasicBlockInContext<IExplodedBasicBlock>>
- Returns:
- iterator of nodes with the numbers in set s
-
getPredNodeNumbers
public IntSet getPredNodeNumbers(BasicBlockInContext<IExplodedBasicBlock> node)
- Specified by:
getPredNodeNumbers
in interfaceNumberedEdgeManager<BasicBlockInContext<IExplodedBasicBlock>>
- Returns:
- the numbers identifying the immediate predecessors of node
-
getSuccNodeNumbers
public IntSet getSuccNodeNumbers(BasicBlockInContext<IExplodedBasicBlock> node)
- 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
public ExplodedInterproceduralCFG getICFG()
-
-