Package com.ibm.wala.ipa.cfg
Class AbstractInterproceduralCFG<T extends ISSABasicBlock>
- java.lang.Object
-
- com.ibm.wala.ipa.cfg.AbstractInterproceduralCFG<T>
-
- All Implemented Interfaces:
EdgeManager<BasicBlockInContext<T>>
,Graph<BasicBlockInContext<T>>
,NodeManager<BasicBlockInContext<T>>
,NumberedEdgeManager<BasicBlockInContext<T>>
,NumberedGraph<BasicBlockInContext<T>>
,NumberedNodeManager<BasicBlockInContext<T>>
,Iterable<BasicBlockInContext<T>>
- Direct Known Subclasses:
ExplodedInterproceduralCFG
,InterproceduralCFG
public abstract class AbstractInterproceduralCFG<T extends ISSABasicBlock> extends Object implements NumberedGraph<BasicBlockInContext<T>>
Interprocedural control-flow graph, constructed lazily.
-
-
Constructor Summary
Constructors Constructor Description AbstractInterproceduralCFG(CallGraph cg)
Build an Interprocedural CFG from a call graph.AbstractInterproceduralCFG(CallGraph CG, Predicate<CGNode> relevant)
Build an Interprocedural CFG from a call graph.
-
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
-
AbstractInterproceduralCFG
public AbstractInterproceduralCFG(CallGraph cg)
Build an Interprocedural CFG from a call graph. This version defaults to using whatever CFGs the call graph provides by default, and includes all nodes in the call graph.- Parameters:
cg
- the call graph
-
AbstractInterproceduralCFG
public AbstractInterproceduralCFG(CallGraph CG, Predicate<CGNode> relevant)
Build an Interprocedural CFG from a call graph.- Parameters:
CG
- the call graphrelevant
- a filter which accepts those call graph nodes which should be included in the I-CFG. Other nodes are ignored.
-
-
Method Detail
-
callGraphUpdated
public void callGraphUpdated()
Should be invoked when the underlying call graph has changed. This will cause certain successor and predecessor edges to be recomputed. USE WITH EXTREME CARE.
-
getCFG
public abstract ControlFlowGraph<SSAInstruction,T> getCFG(CGNode n)
-
addEdgesToNonEntryBlock
protected void addEdgesToNonEntryBlock(CGNode n, ControlFlowGraph<?,T> cfg, SSAInstruction[] instrs, T bb)
Add edges to the IPCFG for the incoming edges incident on a basic block bb.- Parameters:
n
- a call graph nodecfg
- the CFG for ninstrs
- the instructions for node nbb
- a basic block in the CFG
-
getLastInstructionForBlock
protected SSAInstruction getLastInstructionForBlock(T pb, SSAInstruction[] instrs)
-
getCFG
public ControlFlowGraph<SSAInstruction,T> getCFG(BasicBlockInContext B) throws IllegalArgumentException
- Returns:
- the original CFG from whence B came
- Throws:
IllegalArgumentException
- if B == null
-
getCGNode
public CGNode getCGNode(BasicBlockInContext B) throws IllegalArgumentException
- Returns:
- the original CGNode from whence B came
- Throws:
IllegalArgumentException
- if B == null
-
removeNodeAndEdges
public void removeNodeAndEdges(BasicBlockInContext N) throws UnsupportedOperationException
Description copied from interface:Graph
remove a node and all its incident edges- Specified by:
removeNodeAndEdges
in interfaceGraph<T extends ISSABasicBlock>
- Throws:
UnsupportedOperationException
- if the graph implementation does not allow removal
-
iterator
public Iterator<BasicBlockInContext<T>> iterator()
- Specified by:
iterator
in interfaceIterable<T extends ISSABasicBlock>
- Specified by:
iterator
in interfaceNodeManager<T extends ISSABasicBlock>
- Returns:
- an
Iterator
of the nodes in this graph
-
getNumberOfNodes
public int getNumberOfNodes()
- Specified by:
getNumberOfNodes
in interfaceNodeManager<T extends ISSABasicBlock>
- Returns:
- the number of nodes in this graph
-
addNode
public void addNode(BasicBlockInContext n) throws UnsupportedOperationException
Description copied from interface:NodeManager
add a node to this graph- Specified by:
addNode
in interfaceNodeManager<T extends ISSABasicBlock>
- Throws:
UnsupportedOperationException
-
removeNode
public void removeNode(BasicBlockInContext n) throws UnsupportedOperationException
Description copied from interface:NodeManager
remove a node from this graph- Specified by:
removeNode
in interfaceNodeManager<T extends ISSABasicBlock>
- Throws:
UnsupportedOperationException
-
getPredNodes
public Iterator<BasicBlockInContext<T>> getPredNodes(BasicBlockInContext<T> N)
Description copied from interface:EdgeManager
Return anIterator
over the immediate predecessor nodes of n This method never returnsnull
.- Specified by:
getPredNodes
in interfaceEdgeManager<T extends ISSABasicBlock>
- Returns:
- an
Iterator
over the immediate predecessor nodes of this Node.
-
getPredNodeCount
public int getPredNodeCount(BasicBlockInContext<T> N)
Description copied from interface:EdgeManager
Return the number ofimmediate predecessor
nodes of n- Specified by:
getPredNodeCount
in interfaceEdgeManager<T extends ISSABasicBlock>
- Returns:
- the number of immediate predecessors of n.
-
getSuccNodes
public Iterator<BasicBlockInContext<T>> getSuccNodes(BasicBlockInContext<T> 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<T extends ISSABasicBlock>
- Returns:
- an Iterator over the immediate successor nodes of n
-
getSuccNodeCount
public int getSuccNodeCount(BasicBlockInContext<T> N)
Description copied from interface:EdgeManager
Return the number ofimmediate successor
nodes of this Node in the Graph- Specified by:
getSuccNodeCount
in interfaceEdgeManager<T extends ISSABasicBlock>
- Returns:
- the number of immediate successor Nodes of this Node in the Graph.
-
addEdge
public void addEdge(BasicBlockInContext src, BasicBlockInContext dst) throws UnsupportedOperationException
- Specified by:
addEdge
in interfaceEdgeManager<T extends ISSABasicBlock>
- Throws:
UnsupportedOperationException
-
removeEdge
public void removeEdge(BasicBlockInContext src, BasicBlockInContext dst) throws UnsupportedOperationException
- Specified by:
removeEdge
in interfaceEdgeManager<T extends ISSABasicBlock>
- Throws:
UnsupportedOperationException
-
removeAllIncidentEdges
public void removeAllIncidentEdges(BasicBlockInContext node) throws UnsupportedOperationException
- Specified by:
removeAllIncidentEdges
in interfaceEdgeManager<T extends ISSABasicBlock>
- Throws:
UnsupportedOperationException
-
containsNode
public boolean containsNode(BasicBlockInContext<T> N)
- Specified by:
containsNode
in interfaceNodeManager<T extends ISSABasicBlock>
- Returns:
- true iff the graph contains the specified node
-
hasCall
public boolean hasCall(BasicBlockInContext<T> B)
- Parameters:
B
-- Returns:
- true iff basic block B ends in a call instuction
-
hasCall
protected boolean hasCall(BasicBlockInContext<T> B, ControlFlowGraph<SSAInstruction,T> cfg)
- Returns:
- true iff basic block B ends in a call instuction
-
getCallTargets
public Set<CGNode> getCallTargets(BasicBlockInContext<T> B)
- Parameters:
B
-- Returns:
- the set of CGNodes that B may call, according to the governing call graph.
- Throws:
IllegalArgumentException
- if B is null
-
getCallSiteForCallBlock
protected CallSiteReference getCallSiteForCallBlock(IBasicBlock<SSAInstruction> B, ControlFlowGraph<SSAInstruction,T> cfg)
get theCallSiteReference
corresponding to the last instruction in B (assumed to be a call)
-
removeIncomingEdges
public void removeIncomingEdges(BasicBlockInContext node) throws UnsupportedOperationException
- Specified by:
removeIncomingEdges
in interfaceEdgeManager<T extends ISSABasicBlock>
- Throws:
UnsupportedOperationException
-
removeOutgoingEdges
public void removeOutgoingEdges(BasicBlockInContext node) throws UnsupportedOperationException
- Specified by:
removeOutgoingEdges
in interfaceEdgeManager<T extends ISSABasicBlock>
- Throws:
UnsupportedOperationException
-
hasEdge
public boolean hasEdge(BasicBlockInContext<T> src, BasicBlockInContext<T> dst)
- Specified by:
hasEdge
in interfaceEdgeManager<T extends ISSABasicBlock>
-
getNumber
public int getNumber(BasicBlockInContext<T> N)
- Specified by:
getNumber
in interfaceNumberedNodeManager<T extends ISSABasicBlock>
-
getNode
public BasicBlockInContext<T> getNode(int number) throws UnimplementedError
- Specified by:
getNode
in interfaceNumberedNodeManager<T extends ISSABasicBlock>
- Throws:
UnimplementedError
-
getMaxNumber
public int getMaxNumber()
- Specified by:
getMaxNumber
in interfaceNumberedNodeManager<T extends ISSABasicBlock>
-
iterateNodes
public Iterator<BasicBlockInContext<T>> iterateNodes(IntSet s) throws UnimplementedError
- Specified by:
iterateNodes
in interfaceNumberedNodeManager<T extends ISSABasicBlock>
- Returns:
- iterator of nodes with the numbers in set s
- Throws:
UnimplementedError
-
getSuccNodeNumbers
public IntSet getSuccNodeNumbers(BasicBlockInContext<T> node)
- Specified by:
getSuccNodeNumbers
in interfaceNumberedEdgeManager<T extends ISSABasicBlock>
- Returns:
- the numbers identifying the immediate successors of node
-
getPredNodeNumbers
public IntSet getPredNodeNumbers(BasicBlockInContext<T> node)
- Specified by:
getPredNodeNumbers
in interfaceNumberedEdgeManager<T extends ISSABasicBlock>
- Returns:
- the numbers identifying the immediate predecessors of node
-
getEntry
public BasicBlockInContext<T> getEntry(CGNode n)
-
getExit
public BasicBlockInContext<T> getExit(CGNode n)
-
getReturnSites
public Iterator<BasicBlockInContext<T>> getReturnSites(BasicBlockInContext<T> callBlock)
- Parameters:
callBlock
- node in the IPCFG that ends in a call- Returns:
- the nodes that are return sites for this call.
- Throws:
IllegalArgumentException
- if bb is null
-
getCallSites
public Iterator<BasicBlockInContext<T>> getCallSites(BasicBlockInContext<T> returnBlock, CGNode callee)
get the basic blocks which are call sites that may call callee and return to returnBlock if callee is null, answer return sites for which no callee was found.
-
isReturn
public boolean isReturn(BasicBlockInContext<T> bb) throws IllegalArgumentException
- Throws:
IllegalArgumentException
-
-