com.ibm.wala.ipa.cfg
Class InterproceduralCFG

java.lang.Object
  com.ibm.wala.ipa.cfg.InterproceduralCFG

All Implemented Interfaces:

EdgeManager<BasicBlockInContext>, Graph<BasicBlockInContext>, NodeManager<BasicBlockInContext>, NumberedEdgeManager<BasicBlockInContext>, NumberedGraph<BasicBlockInContext>, NumberedNodeManager<BasicBlockInContext>, java.lang.Iterable<BasicBlockInContext>

public class InterproceduralCFG
extends java.lang.Object
implements NumberedGraph<BasicBlockInContext>

Interprocedural control-flow graph. TODO: think about a better implementation; perhaps a lazy view of the constituent CFGs Lots of ways this can be optimized?

Constructor Summary

InterproceduralCFG(CallGraph CG, CFGCache cfgCache, WarningSet warnings)
Build an Interprocedural CFG from a call graph.

InterproceduralCFG(CallGraph CG, CFGProvider P, Filter relevant, boolean partitionExits, WarningSet warnings)
Build an Interprocedural CFG from a call graph.

Method Summary

void	addEdge(BasicBlockInContext src, BasicBlockInContext dst)
void	addNode(BasicBlockInContext n) add a node to this graph
boolean	containsNode(BasicBlockInContext N)
java.util.Iterator<BasicBlockInContext>	getCallSites(BasicBlockInContext bb)
java.util.Set<CGNode>	getCallTargets(IBasicBlock B)
ControlFlowGraph	getCFG(CGNode n)
ControlFlowGraph	getCFG(IBasicBlock B)
CGNode	getCGNode(IBasicBlock B)
java.lang.Object	getEntry(CGNode n)
int	getMaxNumber()
BasicBlockInContext	getNode(int number)
int	getNumber(BasicBlockInContext N)
int	getNumberOfNodes()
int	getPredNodeCount(BasicBlockInContext N) Return the number of immediate predecessor nodes of this Node in the Graph.
IntSet	getPredNodeNumbers(BasicBlockInContext node)
java.util.Iterator<? extends BasicBlockInContext>	getPredNodes(BasicBlockInContext N) Return an Iterator over the immediate predecessor nodes of this Node in the Graph.
java.util.Iterator<BasicBlockInContext>	getReturnSites(BasicBlockInContext bb)
int	getSuccNodeCount(BasicBlockInContext N) Return the number of immediate successor nodes of this Node in the Graph
IntSet	getSuccNodeNumbers(BasicBlockInContext node)
java.util.Iterator<? extends BasicBlockInContext>	getSuccNodes(BasicBlockInContext N) Return an Iterator over the immediate successor nodes of this Node in the Graph
boolean	hasCall(BasicBlockInContext B)
boolean	hasEdge(BasicBlockInContext src, BasicBlockInContext dst)
boolean	isReturn(java.lang.Object object)
java.util.Iterator<BasicBlockInContext>	iterateNodes(IntSet s)
java.util.Iterator<BasicBlockInContext>	iterator()
static CallSiteReference	makeCallSiteReference(ClassLoaderReference loader, int pc, IInvokeInstruction call)
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

InterproceduralCFG

public InterproceduralCFG(CallGraph CG,
                          CFGCache cfgCache,
                          WarningSet warnings)

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

warnings - an object to track analysis warnings

InterproceduralCFG

public InterproceduralCFG(CallGraph CG,
                          CFGProvider P,
                          Filter relevant,
                          boolean partitionExits,
                          WarningSet warnings)

Build an Interprocedural CFG from a call graph.

Parameters:

CG - the call graph

P - an object that provides CFGs for call graph nodes.

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

Method Detail

getCFG

public ControlFlowGraph getCFG(CGNode n)

Parameters:

n -

Returns:

the cfg for n, or null if none found

makeCallSiteReference

public static CallSiteReference makeCallSiteReference(ClassLoaderReference loader,
                                                      int pc,
                                                      IInvokeInstruction call)

getCFG

public ControlFlowGraph getCFG(IBasicBlock B)

Parameters:

B -

Returns:

the original CFG from whence B came

getCGNode

public CGNode getCGNode(IBasicBlock B)

Parameters:

B -

Returns:

the original CGNode from whence B came

removeNodeAndEdges

public void removeNodeAndEdges(BasicBlockInContext N)

Description copied from interface: Graph

remove a node and all its incident edges

Specified by:

removeNodeAndEdges in interface Graph<BasicBlockInContext>

iterator

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

Specified by:

iterator in interface NodeManager<BasicBlockInContext>

Specified by:

iterator in interface java.lang.Iterable<BasicBlockInContext>

Returns:

an Iterator of the nodes in this graph

getNumberOfNodes

public int getNumberOfNodes()

Specified by:

getNumberOfNodes in interface NodeManager<BasicBlockInContext>

Returns:

the number of nodes in this graph

addNode

public void addNode(BasicBlockInContext n)

Description copied from interface: NodeManager

add a node to this graph

Specified by:

addNode in interface NodeManager<BasicBlockInContext>

removeNode

public void removeNode(BasicBlockInContext n)

Description copied from interface: NodeManager

remove a node from this graph

Specified by:

removeNode in interface NodeManager<BasicBlockInContext>

getPredNodes

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

Description copied from interface: EdgeManager

Return an Iterator over the immediate predecessor nodes of this Node in the Graph. This method never returns null.

Specified by:

getPredNodes in interface EdgeManager<BasicBlockInContext>

Returns:

an Iterator over the immediate predecessor nodes of this Node.

getPredNodeCount

public int getPredNodeCount(BasicBlockInContext N)

Description copied from interface: EdgeManager

Return the number of immediate predecessor nodes of this Node in the Graph.

Specified by:

getPredNodeCount in interface EdgeManager<BasicBlockInContext>

Returns:

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

getSuccNodes

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

Description copied from interface: EdgeManager

Return an Iterator over the immediate successor nodes of this Node in the Graph

This method never returns null.

Specified by:

getSuccNodes in interface EdgeManager<BasicBlockInContext>

Returns:

an Iterator over the immediate successor Nodes of this Node.

getSuccNodeCount

public int getSuccNodeCount(BasicBlockInContext 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>

Returns:

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

addEdge

public void addEdge(BasicBlockInContext src,
                    BasicBlockInContext dst)

Specified by:

addEdge in interface EdgeManager<BasicBlockInContext>

removeEdge

public void removeEdge(BasicBlockInContext src,
                       BasicBlockInContext dst)

Specified by:

removeEdge in interface EdgeManager<BasicBlockInContext>

removeAllIncidentEdges

public void removeAllIncidentEdges(BasicBlockInContext node)

Specified by:

removeAllIncidentEdges in interface EdgeManager<BasicBlockInContext>

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

containsNode

public boolean containsNode(BasicBlockInContext N)

Specified by:

containsNode in interface NodeManager<BasicBlockInContext>

Returns:

true iff the graph contains the specified node

hasCall

public boolean hasCall(BasicBlockInContext B)

Parameters:

B -

Returns:

true iff basic block B ends in a call instuction

getCallTargets

public java.util.Set<CGNode> getCallTargets(IBasicBlock 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

removeIncomingEdges

public void removeIncomingEdges(BasicBlockInContext node)

Specified by:

removeIncomingEdges in interface EdgeManager<BasicBlockInContext>

removeOutgoingEdges

public void removeOutgoingEdges(BasicBlockInContext node)

Specified by:

removeOutgoingEdges in interface EdgeManager<BasicBlockInContext>

hasEdge

public boolean hasEdge(BasicBlockInContext src,
                       BasicBlockInContext dst)

Specified by:

hasEdge in interface EdgeManager<BasicBlockInContext>

getNumber

public int getNumber(BasicBlockInContext N)

Specified by:

getNumber in interface NumberedNodeManager<BasicBlockInContext>

getNode

public BasicBlockInContext getNode(int number)

Specified by:

getNode in interface NumberedNodeManager<BasicBlockInContext>

getMaxNumber

public int getMaxNumber()

Specified by:

getMaxNumber in interface NumberedNodeManager<BasicBlockInContext>

iterateNodes

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

Specified by:

iterateNodes in interface NumberedNodeManager<BasicBlockInContext>

Returns:

iterator of nodes with the numbers in set s

getSuccNodeNumbers

public IntSet getSuccNodeNumbers(BasicBlockInContext node)

Specified by:

getSuccNodeNumbers in interface NumberedEdgeManager<BasicBlockInContext>

Returns:

the numbers identifying the immediate successors of node

getPredNodeNumbers

public IntSet getPredNodeNumbers(BasicBlockInContext node)

Specified by:

getPredNodeNumbers in interface NumberedEdgeManager<BasicBlockInContext>

Returns:

the numbers identifying the immediate predecessors of node

getEntry

public java.lang.Object getEntry(CGNode n)

getReturnSites

public java.util.Iterator<BasicBlockInContext> getReturnSites(BasicBlockInContext bb)

Parameters:

object - 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> getCallSites(BasicBlockInContext bb)

isReturn

public boolean isReturn(java.lang.Object object)