com.ibm.wala.dataflow.IFDS
Class PartiallyCollapsedSupergraph

java.lang.Object
  com.ibm.wala.util.graph.AbstractGraph<java.lang.Object>
      com.ibm.wala.dataflow.IFDS.PartiallyCollapsedSupergraph

All Implemented Interfaces:

ISupergraph<java.lang.Object,CGNode>, EdgeManager<java.lang.Object>, Graph<java.lang.Object>, NodeManager<java.lang.Object>, NumberedEdgeManager<java.lang.Object>, NumberedGraph<java.lang.Object>, NumberedNodeManager<java.lang.Object>, java.lang.Iterable<java.lang.Object>

public class PartiallyCollapsedSupergraph
extends AbstractGraph<java.lang.Object>
implements ISupergraph<java.lang.Object,CGNode>

A Supergraph customized for the case when some nodes are "collapsible", meaning the result for every basic block in a collapsible node is identical. This graph is an InterproceduralCFG for uncollapsable nodes, hooked up to collapsed nodes.

Field Summary

Fields inherited from interface com.ibm.wala.dataflow.IFDS.ISupergraph

CALL_EDGE, CALL_TO_RETURN_EDGE, OTHER, RETURN_EDGE

Constructor Summary

PartiallyCollapsedSupergraph(CallGraph cg, CFGCache cfgCache, java.util.Collection<CGNode> noCollapse, Filter relevant, WarningSet warnings)

PartiallyCollapsedSupergraph(CallGraph cg, CFGCache cfgCache, java.util.Collection<CGNode> noCollapse, WarningSet warnings)

PartiallyCollapsedSupergraph(CallGraph cg, java.util.Collection<CGNode> noCollapse, Filter relevant, WarningSet warnings)

PartiallyCollapsedSupergraph(CallGraph cg, java.util.Collection<CGNode> noCollapse, WarningSet warnings)

Method Summary

byte	classifyEdge(java.lang.Object src, java.lang.Object dest)
java.util.Iterator<java.lang.Object>	getCalledNodes(java.lang.Object n)
CallGraph	getCallGraph()
java.util.Iterator<? extends java.lang.Object>	getCallSites(java.lang.Object object)
protected EdgeManager<java.lang.Object>	getEdgeManager()
java.lang.Object[]	getEntries(java.lang.Object n)
java.lang.Object[]	getEntriesForProcedure(CGNode object)
java.lang.Object	getEntryForProcedure(java.lang.Object p)
java.lang.Object[]	getExitsForProcedure(CGNode node)
java.lang.Object	getLocalBlock(CGNode procedure, int i)
int	getLocalBlockNumber(java.lang.Object n)
CGNode	getMain()
java.lang.Object	getMainEntry()
java.lang.Object	getMainExit()
int	getMaxNumber()
java.lang.Object	getNode(int number)
protected NodeManager<java.lang.Object>	getNodeManager()
java.util.Iterator<java.lang.Object>	getNormalSuccessors(java.lang.Object call) In forward problems, a call node will have no normal successors.
int	getNumber(java.lang.Object N)
int	getNumberOfBlocks(CGNode procedure)
IntSet	getPredNodeNumbers(java.lang.Object node)
CGNode	getProcOf(java.lang.Object n)
java.util.Iterator<? extends java.lang.Object>	getReturnSites(java.lang.Object object)
IntSet	getSuccNodeNumbers(java.lang.Object node)
InterproceduralCFG	getUncollapsedGraph()
boolean	isCall(java.lang.Object object)
boolean	isEntry(java.lang.Object object)
boolean	isExit(java.lang.Object object)
boolean	isReturn(java.lang.Object object)
java.util.Iterator<java.lang.Object>	iterateNodes(IntSet s)

Methods inherited from class com.ibm.wala.util.graph.AbstractGraph

addEdge, addNode, containsNode, getNumberOfNodes, getPredNodeCount, getPredNodes, getSuccNodeCount, getSuccNodes, hasEdge, iterator, removeAllIncidentEdges, removeEdge, removeIncomingEdges, removeNode, removeNodeAndEdges, removeOutgoingEdges, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface com.ibm.wala.util.graph.Graph

removeNodeAndEdges

Methods inherited from interface com.ibm.wala.util.graph.NodeManager

addNode, containsNode, getNumberOfNodes, iterator, removeNode

Methods inherited from interface com.ibm.wala.util.graph.EdgeManager

addEdge, getPredNodeCount, getPredNodes, getSuccNodeCount, getSuccNodes, hasEdge, removeAllIncidentEdges, removeEdge, removeIncomingEdges, removeOutgoingEdges

Methods inherited from interface com.ibm.wala.util.graph.NodeManager

addNode, containsNode, getNumberOfNodes, iterator, removeNode

Methods inherited from interface com.ibm.wala.util.graph.EdgeManager

addEdge, getPredNodeCount, getPredNodes, getSuccNodeCount, getSuccNodes, hasEdge, removeAllIncidentEdges, removeEdge, removeIncomingEdges, removeOutgoingEdges

Constructor Detail

PartiallyCollapsedSupergraph

public PartiallyCollapsedSupergraph(CallGraph cg,
                                    CFGCache cfgCache,
                                    java.util.Collection<CGNode> noCollapse,
                                    WarningSet warnings)

Parameters:

cg - Governing call graph

noCollapse - set of nodes in the call graph which cannot be collapsed

warnings - object to track analysis warnings

PartiallyCollapsedSupergraph

public PartiallyCollapsedSupergraph(CallGraph cg,
                                    CFGCache cfgCache,
                                    java.util.Collection<CGNode> noCollapse,
                                    Filter relevant,
                                    WarningSet warnings)

Parameters:

cg - Governing call graph

noCollapse - set of nodes in the call graph which cannot be collapsed

relevant - set of nodes which are relevant and should be included in the supergraph

warnings - object to track analysis warnings

PartiallyCollapsedSupergraph

public PartiallyCollapsedSupergraph(CallGraph cg,
                                    java.util.Collection<CGNode> noCollapse,
                                    WarningSet warnings)

Parameters:

cg - Governing call graph

noCollapse - set of nodes in the call graph which cannot be collapsed

warnings - object to track analysis warnings

PartiallyCollapsedSupergraph

public PartiallyCollapsedSupergraph(CallGraph cg,
                                    java.util.Collection<CGNode> noCollapse,
                                    Filter relevant,
                                    WarningSet warnings)

Parameters:

cg - Governing call graph

noCollapse - set of nodes in the call graph which cannot be collapsed

relevant - set of nodes which are relevant and should be included in the supergraph

warnings - object to track analysis warnings

Method Detail

getNodeManager

protected NodeManager<java.lang.Object> getNodeManager()

Specified by:

getNodeManager in class AbstractGraph<java.lang.Object>

Returns:

the object which manages nodes in the graph

getEdgeManager

protected EdgeManager<java.lang.Object> getEdgeManager()

Specified by:

getEdgeManager in class AbstractGraph<java.lang.Object>

Returns:

the object which manages edges in the graph

getMain

public CGNode getMain()

Specified by:

getMain in interface ISupergraph<java.lang.Object,CGNode>

Returns:

an identifier for the main procedure for this supergraph

getEntryForProcedure

public java.lang.Object getEntryForProcedure(java.lang.Object p)

getEntries

public java.lang.Object[] getEntries(java.lang.Object n)

getExitsForProcedure

public java.lang.Object[] getExitsForProcedure(CGNode node)

Specified by:

getExitsForProcedure in interface ISupergraph<java.lang.Object,CGNode>

Returns:

the blocks in the supergraph that represents exit nodes for procedure p

isCall

public boolean isCall(java.lang.Object object)

Specified by:

isCall in interface ISupergraph<java.lang.Object,CGNode>

Parameters:

object - a node in this supergraph

Returns:

true iff this node includes a call.

isEntry

public boolean isEntry(java.lang.Object object)

Specified by:

isEntry in interface ISupergraph<java.lang.Object,CGNode>

Returns:

true iff this node is an entry node s_p for a procedure

isExit

public boolean isExit(java.lang.Object object)

Specified by:

isExit in interface ISupergraph<java.lang.Object,CGNode>

Parameters:

object - a node in the supergraph

Returns:

true iff this node is an exit node

getCalledNodes

public java.util.Iterator<java.lang.Object> getCalledNodes(java.lang.Object n)

Specified by:

getCalledNodes in interface ISupergraph<java.lang.Object,CGNode>

Parameters:

n - a "call" node in the supergraph

Returns:

an Iterator of nodes that are targets of this call.

getReturnSites

public java.util.Iterator<? extends java.lang.Object> getReturnSites(java.lang.Object object)

Specified by:

getReturnSites in interface ISupergraph<java.lang.Object,CGNode>

Parameters:

object - a "call" node in the supergraph

Returns:

the corresponding return nodes. There may be many, because of exceptional control flow.

getCallSites

public java.util.Iterator<? extends java.lang.Object> getCallSites(java.lang.Object object)

Specified by:

getCallSites in interface ISupergraph<java.lang.Object,CGNode>

Parameters:

object - a "return" node in the supergraph

Returns:

the corresponding call nodes. There may be many.

getProcOf

public CGNode getProcOf(java.lang.Object n)

Specified by:

getProcOf in interface ISupergraph<java.lang.Object,CGNode>

Parameters:

n - a node in the supergraph

Returns:

an object which represents the procedure which contains n

getEntriesForProcedure

public java.lang.Object[] getEntriesForProcedure(CGNode object)

Specified by:

getEntriesForProcedure in interface ISupergraph<java.lang.Object,CGNode>

Returns:

the blocks in the supergraph that represents entry nodes for procedure p

getMainEntry

public java.lang.Object getMainEntry()

Specified by:

getMainEntry in interface ISupergraph<java.lang.Object,CGNode>

Returns:

the unique entry node s_main for the main procedure

getMainExit

public java.lang.Object getMainExit()

Specified by:

getMainExit in interface ISupergraph<java.lang.Object,CGNode>

Returns:

the unique entry node e_main for the main procedure

isReturn

public boolean isReturn(java.lang.Object object)

Specified by:

isReturn in interface ISupergraph<java.lang.Object,CGNode>

Parameters:

object - a node in this supergraph

Returns:

true iff this node is a return site.

getUncollapsedGraph

public InterproceduralCFG getUncollapsedGraph()

Returns:

the portion of this graph that is a normal, uncollapsed, ICFG

classifyEdge

public byte classifyEdge(java.lang.Object src,
                         java.lang.Object dest)

Specified by:

classifyEdge in interface ISupergraph<java.lang.Object,CGNode>

Parameters:

src - node in the supergraph

dest - a successor of src in the supergraph

Returns:

one of CALL_EDGE, RETURN_EDGE, CALL_TO_RETURN_EDGE, or OTHER

getNormalSuccessors

public java.util.Iterator<java.lang.Object> getNormalSuccessors(java.lang.Object call)

In forward problems, a call node will have no normal successors.

Specified by:

getNormalSuccessors in interface ISupergraph<java.lang.Object,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.

See Also:

ISupergraph.getNormalSuccessors(java.lang.Object)

getNumberOfBlocks

public int getNumberOfBlocks(CGNode procedure)

Specified by:

getNumberOfBlocks in interface ISupergraph<java.lang.Object,CGNode>

Parameters:

procedure - an object that represents a procedure

Returns:

the number of blocks from this procedure in this supergraph

getLocalBlockNumber

public int getLocalBlockNumber(java.lang.Object n)

Specified by:

getLocalBlockNumber in interface ISupergraph<java.lang.Object,CGNode>

Parameters:

n - a node in the supergraph

Returns:

the "logical" basic block number of n in its procedure

getLocalBlock

public java.lang.Object getLocalBlock(CGNode procedure,
                                      int i)

Specified by:

getLocalBlock in interface ISupergraph<java.lang.Object,CGNode>

Parameters:

procedure - an object that represents a procedure

i - the "logical" basic block number of a node in the procedure

Returns:

the corresponding node in the supergraph

getNumber

public int getNumber(java.lang.Object N)

Specified by:

getNumber in interface NumberedNodeManager<java.lang.Object>

getNode

public java.lang.Object getNode(int number)

Specified by:

getNode in interface NumberedNodeManager<java.lang.Object>

getMaxNumber

public int getMaxNumber()

Specified by:

getMaxNumber in interface NumberedNodeManager<java.lang.Object>

iterateNodes

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

Specified by:

iterateNodes in interface NumberedNodeManager<java.lang.Object>

Returns:

iterator of nodes with the numbers in set s

getSuccNodeNumbers

public IntSet getSuccNodeNumbers(java.lang.Object node)

Specified by:

getSuccNodeNumbers in interface NumberedEdgeManager<java.lang.Object>

Returns:

the numbers identifying the immediate successors of node

getPredNodeNumbers

public IntSet getPredNodeNumbers(java.lang.Object node)

Specified by:

getPredNodeNumbers in interface NumberedEdgeManager<java.lang.Object>

Returns:

the numbers identifying the immediate predecessors of node

getCallGraph

public CallGraph getCallGraph()