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

Modifier and Type	Method	Description
void	addEdge(BasicBlockInContext<T> src, BasicBlockInContext<T> 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<T> 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)
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.
Set<CGNode>	getCallTargets(BasicBlockInContext<T> B)
abstract ControlFlowGraph<SSAInstruction,T>	getCFG(CGNode n)
ControlFlowGraph<SSAInstruction,T>	getCFG(BasicBlockInContext<T> B)
CGNode	getCGNode(BasicBlockInContext<T> 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)
Iterator<BasicBlockInContext<T>>	getPredNodes(BasicBlockInContext<T> N)	Return an Iterator over the immediate predecessor nodes of n
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)
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)
Iterator<BasicBlockInContext<T>>	iterateNodes(IntSet s)
Iterator<BasicBlockInContext<T>>	iterator()
void	removeAllIncidentEdges(BasicBlockInContext<T> node)
void	removeEdge(BasicBlockInContext<T> src, BasicBlockInContext<T> dst)
void	removeIncomingEdges(BasicBlockInContext<T> node)
void	removeNode(BasicBlockInContext<T> n)	remove a node from this graph
void	removeNodeAndEdges(BasicBlockInContext<T> N)	remove a node and all its incident edges
void	removeOutgoingEdges(BasicBlockInContext<T> node)
Stream<BasicBlockInContext<T>>	stream()
String	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

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 graph

relevant - a filter which accepts those call graph nodes which should be included in the I-CFG. Other nodes are ignored.

Method Details

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<T> B)
                                          throws IllegalArgumentException

Returns:

the original CFG from whence B came

Throws:

IllegalArgumentException - if B == null

getCGNode

public CGNode getCGNode(BasicBlockInContext<T> B)
                 throws IllegalArgumentException

Returns:

the original CGNode from whence B came

Throws:

IllegalArgumentException - if B == null

removeNodeAndEdges

public void removeNodeAndEdges(BasicBlockInContext<T> N)
                        throws UnsupportedOperationException

Description copied from interface: Graph

remove a node and all its incident edges

Specified by:

removeNodeAndEdges in interface Graph<T extends ISSABasicBlock>

Throws:

UnsupportedOperationException - if the graph implementation does not allow removal

See Also:

• Graph.removeNodeAndEdges(Object)

iterator

public Iterator<BasicBlockInContext<T>> iterator()

Specified by:

iterator in interface Iterable<T extends ISSABasicBlock>

Specified by:

iterator in interface NodeManager<T extends ISSABasicBlock>

Returns:

an Iterator of the nodes in this graph

See Also:

• NodeManager.iterator()

stream

public Stream<BasicBlockInContext<T>> stream()

Specified by:

stream in interface NodeManager<T extends ISSABasicBlock>

Returns:

a Stream of the nodes in this graph

See Also:

• NodeManager.iterator()

getNumberOfNodes

public int getNumberOfNodes()

Specified by:

getNumberOfNodes in interface NodeManager<T extends ISSABasicBlock>

Returns:

the number of nodes in this graph

See Also:

• NodeManager.getNumberOfNodes()

addNode

public void addNode(BasicBlockInContext<T> n)
             throws UnsupportedOperationException

Description copied from interface: NodeManager

add a node to this graph

Specified by:

addNode in interface NodeManager<T extends ISSABasicBlock>

Throws:

UnsupportedOperationException

See Also:

• NodeManager.addNode(Object)

removeNode

public void removeNode(BasicBlockInContext<T> n)
                throws UnsupportedOperationException

Description copied from interface: NodeManager

remove a node from this graph

Specified by:

removeNode in interface NodeManager<T extends ISSABasicBlock>

Throws:

UnsupportedOperationException

See Also:

• NodeManager.removeNode(Object)

getPredNodes

public 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<T extends ISSABasicBlock>

Returns:

an Iterator over the immediate predecessor nodes of this Node.

See Also:

• EdgeManager.getPredNodes(Object)

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<T extends ISSABasicBlock>

Returns:

the number of immediate predecessors of n.

See Also:

• EdgeManager.getPredNodeCount(Object)

getSuccNodes

public 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<T extends ISSABasicBlock>

Returns:

an Iterator over the immediate successor nodes of n

See Also:

• EdgeManager.getSuccNodes(Object)

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<T extends ISSABasicBlock>

Returns:

the number of immediate successor Nodes of this Node in the Graph.

See Also:

• EdgeManager.getSuccNodeCount(Object)

addEdge

public void addEdge(BasicBlockInContext<T> src,
 BasicBlockInContext<T> dst)
             throws UnsupportedOperationException

Specified by:

addEdge in interface EdgeManager<T extends ISSABasicBlock>

Throws:

UnsupportedOperationException

See Also:

• EdgeManager.addEdge(Object, Object)

removeEdge

public void removeEdge(BasicBlockInContext<T> src,
 BasicBlockInContext<T> dst)
                throws UnsupportedOperationException

Specified by:

removeEdge in interface EdgeManager<T extends ISSABasicBlock>

Throws:

UnsupportedOperationException

removeAllIncidentEdges

public void removeAllIncidentEdges(BasicBlockInContext<T> node)
                            throws UnsupportedOperationException

Specified by:

removeAllIncidentEdges in interface EdgeManager<T extends ISSABasicBlock>

Throws:

UnsupportedOperationException

See Also:

• EdgeManager.removeAllIncidentEdges(Object)

toString

public String toString()

Overrides:

toString in class Object

containsNode

public boolean containsNode(BasicBlockInContext<T> N)

Specified by:

containsNode in interface NodeManager<T extends ISSABasicBlock>

Returns:

true iff the graph contains the specified node

See Also:

• NodeManager.containsNode(Object)

hasCall

public boolean hasCall(BasicBlockInContext<T> 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)

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 the CallSiteReference corresponding to the last instruction in B (assumed to be a call)

removeIncomingEdges

public void removeIncomingEdges(BasicBlockInContext<T> node)
                         throws UnsupportedOperationException

Specified by:

removeIncomingEdges in interface EdgeManager<T extends ISSABasicBlock>

Throws:

UnsupportedOperationException

removeOutgoingEdges

public void removeOutgoingEdges(BasicBlockInContext<T> node)
                         throws UnsupportedOperationException

Specified by:

removeOutgoingEdges in interface EdgeManager<T extends ISSABasicBlock>

Throws:

UnsupportedOperationException

hasEdge

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

Specified by:

hasEdge in interface EdgeManager<T extends ISSABasicBlock>

getNumber

public int getNumber(BasicBlockInContext<T> N)

Specified by:

getNumber in interface NumberedNodeManager<T extends ISSABasicBlock>

getNode

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

Specified by:

getNode in interface NumberedNodeManager<T extends ISSABasicBlock>

Throws:

UnimplementedError

getMaxNumber

public int getMaxNumber()

Specified by:

getMaxNumber in interface NumberedNodeManager<T extends ISSABasicBlock>

iterateNodes

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

Specified by:

iterateNodes in interface NumberedNodeManager<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<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<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

getCallGraph

public CallGraph getCallGraph()

Returns:

the governing CallGraph used to build this ICFG