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>>, java.lang.Iterable<BasicBlockInContext<T>>

Direct Known Subclasses:

ExplodedInterproceduralCFG, InterproceduralCFG

public abstract class AbstractInterproceduralCFG<T extends ISSABasicBlock>
extends java.lang.Object
implements NumberedGraph<BasicBlockInContext<T>>

Interprocedural control-flow graph, constructed lazily.

Constructor Summary

AbstractInterproceduralCFG(CallGraph cg)
Build an Interprocedural CFG from a call graph.

AbstractInterproceduralCFG(CallGraph CG, Filter<CGNode> relevant)
Build an Interprocedural CFG from a call graph.

Method Summary

void	addEdge(BasicBlockInContext src, BasicBlockInContext dst)
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.
void	addNode(BasicBlockInContext n) add a node to this graph
void	callGraphUpdated() Should be invoked when the underlying call graph has changed.
boolean	containsNode(BasicBlockInContext<T> N)
CallGraph	getCallGraph()
protected CallSiteReference	getCallSiteForCallBlock(IBasicBlock<SSAInstruction> B, ControlFlowGraph<SSAInstruction,T> cfg) get the CallSiteReference corresponding to the last instruction in B (assumed to be a call)
java.util.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.
java.util.Set<CGNode>	getCallTargets(BasicBlockInContext<T> B)
ControlFlowGraph<SSAInstruction,T>	getCFG(BasicBlockInContext B)
abstract ControlFlowGraph<SSAInstruction,T>	getCFG(CGNode n)
CGNode	getCGNode(BasicBlockInContext B)
BasicBlockInContext<T>	getEntry(CGNode n)
BasicBlockInContext<T>	getExit(CGNode n)
protected SSAInstruction	getLastInstructionForBlock(T pb, SSAInstruction[] instrs)
int	getMaxNumber()
BasicBlockInContext<T>	getNode(int number)
int	getNumber(BasicBlockInContext<T> N)
int	getNumberOfNodes()
int	getPredNodeCount(BasicBlockInContext<T> N) Return the number of immediate predecessor nodes of n
IntSet	getPredNodeNumbers(BasicBlockInContext<T> node)
java.util.Iterator<BasicBlockInContext<T>>	getPredNodes(BasicBlockInContext<T> N) Return an Iterator over the immediate predecessor nodes of n This method never returns null.
java.util.Iterator<BasicBlockInContext<T>>	getReturnSites(BasicBlockInContext<T> callBlock)
int	getSuccNodeCount(BasicBlockInContext<T> N) Return the number of immediate successor nodes of this Node in the Graph
IntSet	getSuccNodeNumbers(BasicBlockInContext<T> node)
java.util.Iterator<BasicBlockInContext<T>>	getSuccNodes(BasicBlockInContext<T> N) Return an Iterator over the immediate successor nodes of n
boolean	hasCall(BasicBlockInContext<T> B)
protected boolean	hasCall(BasicBlockInContext<T> B, ControlFlowGraph<SSAInstruction,T> cfg)
boolean	hasEdge(BasicBlockInContext<T> src, BasicBlockInContext<T> dst)
boolean	isReturn(BasicBlockInContext<T> bb)
java.util.Iterator<BasicBlockInContext<T>>	iterateNodes(IntSet s)
java.util.Iterator<BasicBlockInContext<T>>	iterator()
void	removeAllIncidentEdges(BasicBlockInContext node)
void	removeEdge(BasicBlockInContext src, BasicBlockInContext dst)
void	removeIncomingEdges(BasicBlockInContext node)
void	removeNode(BasicBlockInContext n) remove a node from this graph
void	removeNodeAndEdges(BasicBlockInContext N) remove a node and all its incident edges
void	removeOutgoingEdges(BasicBlockInContext node)
java.lang.String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

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,
                                  Filter<CGNode> relevant)

Build an Interprocedural CFG from a call graph.

Parameters:

CG - the call graph

relevant - 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 node

cfg - the CFG for n

instrs - the instructions for node n

bb - a basic block in the CFG

getLastInstructionForBlock

protected SSAInstruction getLastInstructionForBlock(T pb,
                                                    SSAInstruction[] instrs)

getCFG

public ControlFlowGraph<SSAInstruction,T> getCFG(BasicBlockInContext B)
                                                                 throws java.lang.IllegalArgumentException

Returns:

the original CFG from whence B came

Throws:

java.lang.IllegalArgumentException - if B == null

getCGNode

public CGNode getCGNode(BasicBlockInContext B)
                 throws java.lang.IllegalArgumentException

Returns:

the original CGNode from whence B came

Throws:

java.lang.IllegalArgumentException - if B == null

removeNodeAndEdges

public void removeNodeAndEdges(BasicBlockInContext N)
                        throws java.lang.UnsupportedOperationException

Description copied from interface: Graph

remove a node and all its incident edges

Specified by:

removeNodeAndEdges in interface Graph<BasicBlockInContext<T extends ISSABasicBlock>>

Throws:

java.lang.UnsupportedOperationException - if the graph implementation does not allow removal

iterator

public java.util.Iterator<BasicBlockInContext<T>> iterator()

Specified by:

iterator in interface NodeManager<BasicBlockInContext<T extends ISSABasicBlock>>

Specified by:

iterator in interface java.lang.Iterable<BasicBlockInContext<T extends ISSABasicBlock>>

Returns:

an Iterator of the nodes in this graph

getNumberOfNodes

public int getNumberOfNodes()

Specified by:

getNumberOfNodes in interface NodeManager<BasicBlockInContext<T extends ISSABasicBlock>>

Returns:

the number of nodes in this graph

addNode

public void addNode(BasicBlockInContext n)
             throws java.lang.UnsupportedOperationException

Description copied from interface: NodeManager

add a node to this graph

Specified by:

addNode in interface NodeManager<BasicBlockInContext<T extends ISSABasicBlock>>

Throws:

java.lang.UnsupportedOperationException

removeNode

public void removeNode(BasicBlockInContext n)
                throws java.lang.UnsupportedOperationException

Description copied from interface: NodeManager

remove a node from this graph

Specified by:

removeNode in interface NodeManager<BasicBlockInContext<T extends ISSABasicBlock>>

Throws:

java.lang.UnsupportedOperationException

getPredNodes

public java.util.Iterator<BasicBlockInContext<T>> getPredNodes(BasicBlockInContext<T> N)

Description copied from interface: EdgeManager

Return an Iterator over the immediate predecessor nodes of n This method never returns null.

Specified by:

getPredNodes in interface EdgeManager<BasicBlockInContext<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 of immediate predecessor nodes of n

Specified by:

getPredNodeCount in interface EdgeManager<BasicBlockInContext<T extends ISSABasicBlock>>

Returns:

the number of immediate predecessors of n.

getSuccNodes

public java.util.Iterator<BasicBlockInContext<T>> getSuccNodes(BasicBlockInContext<T> N)

Description copied from interface: EdgeManager

Return an Iterator over the immediate successor nodes of n

This method never returns null.

Specified by:

getSuccNodes in interface EdgeManager<BasicBlockInContext<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 of immediate successor nodes of this Node in the Graph

Specified by:

getSuccNodeCount in interface EdgeManager<BasicBlockInContext<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 java.lang.UnsupportedOperationException

Specified by:

addEdge in interface EdgeManager<BasicBlockInContext<T extends ISSABasicBlock>>

Throws:

java.lang.UnsupportedOperationException

removeEdge

public void removeEdge(BasicBlockInContext src,
                       BasicBlockInContext dst)
                throws java.lang.UnsupportedOperationException

Specified by:

removeEdge in interface EdgeManager<BasicBlockInContext<T extends ISSABasicBlock>>

Throws:

java.lang.UnsupportedOperationException

removeAllIncidentEdges

public void removeAllIncidentEdges(BasicBlockInContext node)
                            throws java.lang.UnsupportedOperationException

Specified by:

removeAllIncidentEdges in interface EdgeManager<BasicBlockInContext<T extends ISSABasicBlock>>

Throws:

java.lang.UnsupportedOperationException

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

containsNode

public boolean containsNode(BasicBlockInContext<T> N)

Specified by:

containsNode in interface NodeManager<BasicBlockInContext<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 java.util.Set<CGNode> getCallTargets(BasicBlockInContext<T> B)

Parameters:

B -

Returns:

the set of CGNodes that B may call, according to the governing call graph.

Throws:

java.lang.IllegalArgumentException - if B is null

getCallSiteForCallBlock

protected CallSiteReference getCallSiteForCallBlock(IBasicBlock<SSAInstruction> B,
                                                    ControlFlowGraph<SSAInstruction,T> cfg)

get the CallSiteReference corresponding to the last instruction in B (assumed to be a call)

removeIncomingEdges

public void removeIncomingEdges(BasicBlockInContext node)
                         throws java.lang.UnsupportedOperationException

Specified by:

removeIncomingEdges in interface EdgeManager<BasicBlockInContext<T extends ISSABasicBlock>>

Throws:

java.lang.UnsupportedOperationException

removeOutgoingEdges

public void removeOutgoingEdges(BasicBlockInContext node)
                         throws java.lang.UnsupportedOperationException

Specified by:

removeOutgoingEdges in interface EdgeManager<BasicBlockInContext<T extends ISSABasicBlock>>

Throws:

java.lang.UnsupportedOperationException

hasEdge

public boolean hasEdge(BasicBlockInContext<T> src,
                       BasicBlockInContext<T> dst)

Specified by:

hasEdge in interface EdgeManager<BasicBlockInContext<T extends ISSABasicBlock>>

getNumber

public int getNumber(BasicBlockInContext<T> N)

Specified by:

getNumber in interface NumberedNodeManager<BasicBlockInContext<T extends ISSABasicBlock>>

getNode

public BasicBlockInContext<T> getNode(int number)
                                                      throws UnimplementedError

Specified by:

getNode in interface NumberedNodeManager<BasicBlockInContext<T extends ISSABasicBlock>>

Throws:

UnimplementedError

getMaxNumber

public int getMaxNumber()

Specified by:

getMaxNumber in interface NumberedNodeManager<BasicBlockInContext<T extends ISSABasicBlock>>

iterateNodes

public java.util.Iterator<BasicBlockInContext<T>> iterateNodes(IntSet s)
                                                                               throws UnimplementedError

Specified by:

iterateNodes in interface NumberedNodeManager<BasicBlockInContext<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 interface NumberedEdgeManager<BasicBlockInContext<T extends ISSABasicBlock>>

Returns:

the numbers identifying the immediate successors of node

getPredNodeNumbers

public IntSet getPredNodeNumbers(BasicBlockInContext<T> node)

Specified by:

getPredNodeNumbers in interface NumberedEdgeManager<BasicBlockInContext<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 java.util.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:

java.lang.IllegalArgumentException - if bb is null

getCallSites

public java.util.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 java.lang.IllegalArgumentException

Throws:

java.lang.IllegalArgumentException

getCallGraph

public CallGraph getCallGraph()

Returns:

the governing CallGraph used to build this ICFG