Package com.ibm.wala.dataflow.IFDS

Class ICFGSupergraph

java.lang.Object

com.ibm.wala.dataflow.IFDS.ICFGSupergraph

All Implemented Interfaces:

ISupergraph<BasicBlockInContext<IExplodedBasicBlock>,CGNode>, EdgeManager<BasicBlockInContext<IExplodedBasicBlock>>, Graph<BasicBlockInContext<IExplodedBasicBlock>>, NodeManager<BasicBlockInContext<IExplodedBasicBlock>>, NumberedEdgeManager<BasicBlockInContext<IExplodedBasicBlock>>, NumberedGraph<BasicBlockInContext<IExplodedBasicBlock>>, NumberedNodeManager<BasicBlockInContext<IExplodedBasicBlock>>, Iterable<BasicBlockInContext<IExplodedBasicBlock>>

public class ICFGSupergraph
extends Object
implements ISupergraph<BasicBlockInContext<IExplodedBasicBlock>,CGNode>

Forward supergraph induced over an ExplodedInterproceduralCFG

This should lazily build the supergraph as it is explored.

Author:

sjfink

Field Summary

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

CALL_EDGE, CALL_TO_RETURN_EDGE, OTHER, RETURN_EDGE

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	ICFGSupergraph(ExplodedInterproceduralCFG icfg)

Method Summary

Modifier and Type	Method	Description
void	addEdge(BasicBlockInContext<IExplodedBasicBlock> src, BasicBlockInContext<IExplodedBasicBlock> dst)
void	addNode(BasicBlockInContext<IExplodedBasicBlock> n)	add a node to this graph
byte	classifyEdge(BasicBlockInContext<IExplodedBasicBlock> src, BasicBlockInContext<IExplodedBasicBlock> dest)
boolean	containsNode(BasicBlockInContext<IExplodedBasicBlock> N)
Iterator<? extends BasicBlockInContext<IExplodedBasicBlock>>	getCalledNodes(BasicBlockInContext<IExplodedBasicBlock> call)
Iterator<BasicBlockInContext<IExplodedBasicBlock>>	getCallSites(BasicBlockInContext<IExplodedBasicBlock> r, CGNode callee)
ControlFlowGraph<SSAInstruction,IExplodedBasicBlock>	getCFG(BasicBlockInContext<IExplodedBasicBlock> node)
IClassHierarchy	getClassHierarchy()
BasicBlockInContext<IExplodedBasicBlock>[]	getEntriesForProcedure(CGNode procedure)
BasicBlockInContext<IExplodedBasicBlock>[]	getExitsForProcedure(CGNode procedure)
ExplodedInterproceduralCFG	getICFG()
BasicBlockInContext<IExplodedBasicBlock>	getLocalBlock(CGNode procedure, int i)
int	getLocalBlockNumber(BasicBlockInContext<IExplodedBasicBlock> n)
BasicBlockInContext<IExplodedBasicBlock>	getMainEntry()
int	getMaxNumber()
BasicBlockInContext<IExplodedBasicBlock>	getNode(int number)
Iterator<BasicBlockInContext<IExplodedBasicBlock>>	getNormalSuccessors(BasicBlockInContext<IExplodedBasicBlock> call)
int	getNumber(BasicBlockInContext<IExplodedBasicBlock> N)
int	getNumberOfBlocks(CGNode procedure)
int	getNumberOfNodes()
int	getPredNodeCount(BasicBlockInContext<IExplodedBasicBlock> N)	Return the number of immediate predecessor nodes of n
IntSet	getPredNodeNumbers(BasicBlockInContext<IExplodedBasicBlock> node)
Iterator<BasicBlockInContext<IExplodedBasicBlock>>	getPredNodes(BasicBlockInContext<IExplodedBasicBlock> N)	Return an Iterator over the immediate predecessor nodes of n
Graph<CGNode>	getProcedureGraph()
CGNode	getProcOf(BasicBlockInContext<IExplodedBasicBlock> n)
Iterator<? extends BasicBlockInContext<IExplodedBasicBlock>>	getReturnSites(BasicBlockInContext<IExplodedBasicBlock> call, CGNode callee)
int	getSuccNodeCount(BasicBlockInContext<IExplodedBasicBlock> N)	Return the number of immediate successor nodes of this Node in the Graph
IntSet	getSuccNodeNumbers(BasicBlockInContext<IExplodedBasicBlock> node)
Iterator<BasicBlockInContext<IExplodedBasicBlock>>	getSuccNodes(BasicBlockInContext<IExplodedBasicBlock> N)	Return an Iterator over the immediate successor nodes of n
boolean	hasEdge(BasicBlockInContext<IExplodedBasicBlock> src, BasicBlockInContext<IExplodedBasicBlock> dst)
boolean	isCall(BasicBlockInContext<IExplodedBasicBlock> n)
boolean	isEntry(BasicBlockInContext<IExplodedBasicBlock> n)
boolean	isExit(BasicBlockInContext<IExplodedBasicBlock> n)
boolean	isReturn(BasicBlockInContext<IExplodedBasicBlock> n)
Iterator<BasicBlockInContext<IExplodedBasicBlock>>	iterateNodes(IntSet s)
Iterator<BasicBlockInContext<IExplodedBasicBlock>>	iterator()
static ICFGSupergraph	make(CallGraph cg)
void	removeAllIncidentEdges(BasicBlockInContext<IExplodedBasicBlock> node)
void	removeEdge(BasicBlockInContext<IExplodedBasicBlock> src, BasicBlockInContext<IExplodedBasicBlock> dst)
void	removeIncomingEdges(BasicBlockInContext<IExplodedBasicBlock> node)
void	removeNode(BasicBlockInContext<IExplodedBasicBlock> n)	remove a node from this graph
void	removeNodeAndEdges(BasicBlockInContext<IExplodedBasicBlock> N)	remove a node and all its incident edges
void	removeOutgoingEdges(BasicBlockInContext<IExplodedBasicBlock> node)
Stream<BasicBlockInContext<IExplodedBasicBlock>>	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

ICFGSupergraph

protected ICFGSupergraph(ExplodedInterproceduralCFG icfg)

Method Details

make

public static ICFGSupergraph make(CallGraph cg)

getProcedureGraph

public Graph<CGNode> getProcedureGraph()

Specified by:

getProcedureGraph in interface ISupergraph<BasicBlockInContext<IExplodedBasicBlock>,CGNode>

Returns:

the graph of procedures (e.g. a call graph) over which this supergraph is induced.

getClassHierarchy

public IClassHierarchy getClassHierarchy()

classifyEdge

public byte classifyEdge(BasicBlockInContext<IExplodedBasicBlock> src,
 BasicBlockInContext<IExplodedBasicBlock> dest)

Specified by:

classifyEdge in interface ISupergraph<BasicBlockInContext<IExplodedBasicBlock>,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

getCallSites

public Iterator<BasicBlockInContext<IExplodedBasicBlock>> getCallSites(BasicBlockInContext<IExplodedBasicBlock> r,
 CGNode callee)

Specified by:

getCallSites in interface ISupergraph<BasicBlockInContext<IExplodedBasicBlock>,CGNode>

Parameters:

r - a "return" node in the supergraph

callee - a "called" "procedure" in the supergraph. if callee is null, answer return sites for which no callee was found.

Returns:

the corresponding call nodes. There may be many.

getCalledNodes

public Iterator<? extends BasicBlockInContext<IExplodedBasicBlock>> getCalledNodes(BasicBlockInContext<IExplodedBasicBlock> call)

Specified by:

getCalledNodes in interface ISupergraph<BasicBlockInContext<IExplodedBasicBlock>,CGNode>

Parameters:

call - a "call" node in the supergraph

Returns:

an Iterator of nodes that are targets of this call.

getEntriesForProcedure

public BasicBlockInContext<IExplodedBasicBlock>[] getEntriesForProcedure(CGNode procedure)

Specified by:

getEntriesForProcedure in interface ISupergraph<BasicBlockInContext<IExplodedBasicBlock>,CGNode>

Returns:

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

getExitsForProcedure

public BasicBlockInContext<IExplodedBasicBlock>[] getExitsForProcedure(CGNode procedure)

Specified by:

getExitsForProcedure in interface ISupergraph<BasicBlockInContext<IExplodedBasicBlock>,CGNode>

Returns:

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

getLocalBlock

public BasicBlockInContext<IExplodedBasicBlock> getLocalBlock(CGNode procedure,
 int i)

Specified by:

getLocalBlock in interface ISupergraph<BasicBlockInContext<IExplodedBasicBlock>,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

getLocalBlockNumber

public int getLocalBlockNumber(BasicBlockInContext<IExplodedBasicBlock> n)

Specified by:

getLocalBlockNumber in interface ISupergraph<BasicBlockInContext<IExplodedBasicBlock>,CGNode>

Parameters:

n - a node in the supergraph

Returns:

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

getMainEntry

public BasicBlockInContext<IExplodedBasicBlock> getMainEntry()

getNormalSuccessors

public Iterator<BasicBlockInContext<IExplodedBasicBlock>> getNormalSuccessors(BasicBlockInContext<IExplodedBasicBlock> call)

Specified by:

getNormalSuccessors in interface ISupergraph<BasicBlockInContext<IExplodedBasicBlock>,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.

getNumberOfBlocks

public int getNumberOfBlocks(CGNode procedure)

Specified by:

getNumberOfBlocks in interface ISupergraph<BasicBlockInContext<IExplodedBasicBlock>,CGNode>

Parameters:

procedure - an object that represents a procedure

Returns:

the number of blocks from this procedure in this supergraph

getProcOf

public CGNode getProcOf(BasicBlockInContext<IExplodedBasicBlock> n)

Specified by:

getProcOf in interface ISupergraph<BasicBlockInContext<IExplodedBasicBlock>,CGNode>

Parameters:

n - a node in the supergraph

Returns:

an object which represents the procedure which contains n

getReturnSites

public Iterator<? extends BasicBlockInContext<IExplodedBasicBlock>> getReturnSites(BasicBlockInContext<IExplodedBasicBlock> call,
 CGNode callee)

Specified by:

getReturnSites in interface ISupergraph<BasicBlockInContext<IExplodedBasicBlock>,CGNode>

Parameters:

call - a "call" node in the supergraph

callee - a "called" "procedure" in the supergraph. if callee is null, answer return sites for which no callee was found.

Returns:

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

isCall

public boolean isCall(BasicBlockInContext<IExplodedBasicBlock> n)

Specified by:

isCall in interface ISupergraph<BasicBlockInContext<IExplodedBasicBlock>,CGNode>

Parameters:

n - a node in this supergraph

Returns:

true iff this node includes a call.

isEntry

public boolean isEntry(BasicBlockInContext<IExplodedBasicBlock> n)

Specified by:

isEntry in interface ISupergraph<BasicBlockInContext<IExplodedBasicBlock>,CGNode>

Returns:

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

isExit

public boolean isExit(BasicBlockInContext<IExplodedBasicBlock> n)

Specified by:

isExit in interface ISupergraph<BasicBlockInContext<IExplodedBasicBlock>,CGNode>

Parameters:

n - a node in the supergraph

Returns:

true iff this node is an exit node

isReturn

public boolean isReturn(BasicBlockInContext<IExplodedBasicBlock> n)

Specified by:

isReturn in interface ISupergraph<BasicBlockInContext<IExplodedBasicBlock>,CGNode>

Parameters:

n - a node in this supergraph

Returns:

true iff this node is a return site.

removeNodeAndEdges

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

Description copied from interface: Graph

remove a node and all its incident edges

Specified by:

removeNodeAndEdges in interface Graph<BasicBlockInContext<IExplodedBasicBlock>>

Throws:

UnsupportedOperationException - if the graph implementation does not allow removal

addNode

public void addNode(BasicBlockInContext<IExplodedBasicBlock> n)

Description copied from interface: NodeManager

add a node to this graph

Specified by:

addNode in interface NodeManager<BasicBlockInContext<IExplodedBasicBlock>>

containsNode

public boolean containsNode(BasicBlockInContext<IExplodedBasicBlock> N)

Specified by:

containsNode in interface NodeManager<BasicBlockInContext<IExplodedBasicBlock>>

Returns:

true iff the graph contains the specified node

getNumberOfNodes

public int getNumberOfNodes()

Specified by:

getNumberOfNodes in interface NodeManager<BasicBlockInContext<IExplodedBasicBlock>>

Returns:

the number of nodes in this graph

iterator

public Iterator<BasicBlockInContext<IExplodedBasicBlock>> iterator()

Specified by:

iterator in interface Iterable<BasicBlockInContext<IExplodedBasicBlock>>

Specified by:

iterator in interface NodeManager<BasicBlockInContext<IExplodedBasicBlock>>

Returns:

an Iterator of the nodes in this graph

stream

public Stream<BasicBlockInContext<IExplodedBasicBlock>> stream()

Specified by:

stream in interface NodeManager<BasicBlockInContext<IExplodedBasicBlock>>

Returns:

a Stream of the nodes in this graph

removeNode

public void removeNode(BasicBlockInContext<IExplodedBasicBlock> n)

Description copied from interface: NodeManager

remove a node from this graph

Specified by:

removeNode in interface NodeManager<BasicBlockInContext<IExplodedBasicBlock>>

addEdge

public void addEdge(BasicBlockInContext<IExplodedBasicBlock> src,
 BasicBlockInContext<IExplodedBasicBlock> dst)

Specified by:

addEdge in interface EdgeManager<BasicBlockInContext<IExplodedBasicBlock>>

getPredNodeCount

public int getPredNodeCount(BasicBlockInContext<IExplodedBasicBlock> N)

Description copied from interface: EdgeManager

Return the number of immediate predecessor nodes of n

Specified by:

getPredNodeCount in interface EdgeManager<BasicBlockInContext<IExplodedBasicBlock>>

Returns:

the number of immediate predecessors of n.

getPredNodes

public Iterator<BasicBlockInContext<IExplodedBasicBlock>> getPredNodes(BasicBlockInContext<IExplodedBasicBlock> 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<IExplodedBasicBlock>>

Returns:

an Iterator over the immediate predecessor nodes of this Node.

getSuccNodeCount

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

Returns:

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

getSuccNodes

public Iterator<BasicBlockInContext<IExplodedBasicBlock>> getSuccNodes(BasicBlockInContext<IExplodedBasicBlock> 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<IExplodedBasicBlock>>

Returns:

an Iterator over the immediate successor nodes of n

hasEdge

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

Specified by:

hasEdge in interface EdgeManager<BasicBlockInContext<IExplodedBasicBlock>>

removeAllIncidentEdges

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

Specified by:

removeAllIncidentEdges in interface EdgeManager<BasicBlockInContext<IExplodedBasicBlock>>

Throws:

UnsupportedOperationException

removeEdge

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

Specified by:

removeEdge in interface EdgeManager<BasicBlockInContext<IExplodedBasicBlock>>

Throws:

UnsupportedOperationException

removeIncomingEdges

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

Specified by:

removeIncomingEdges in interface EdgeManager<BasicBlockInContext<IExplodedBasicBlock>>

Throws:

UnsupportedOperationException

removeOutgoingEdges

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

Specified by:

removeOutgoingEdges in interface EdgeManager<BasicBlockInContext<IExplodedBasicBlock>>

Throws:

UnsupportedOperationException

getMaxNumber

public int getMaxNumber()

Specified by:

getMaxNumber in interface NumberedNodeManager<BasicBlockInContext<IExplodedBasicBlock>>

getNode

public BasicBlockInContext<IExplodedBasicBlock> getNode(int number)

Specified by:

getNode in interface NumberedNodeManager<BasicBlockInContext<IExplodedBasicBlock>>

getNumber

public int getNumber(BasicBlockInContext<IExplodedBasicBlock> N)

Specified by:

getNumber in interface NumberedNodeManager<BasicBlockInContext<IExplodedBasicBlock>>

iterateNodes

public Iterator<BasicBlockInContext<IExplodedBasicBlock>> iterateNodes(IntSet s)

Specified by:

iterateNodes in interface NumberedNodeManager<BasicBlockInContext<IExplodedBasicBlock>>

Returns:

iterator of nodes with the numbers in set s

getPredNodeNumbers

public IntSet getPredNodeNumbers(BasicBlockInContext<IExplodedBasicBlock> node)

Specified by:

getPredNodeNumbers in interface NumberedEdgeManager<BasicBlockInContext<IExplodedBasicBlock>>

Returns:

the numbers identifying the immediate predecessors of node

getSuccNodeNumbers

public IntSet getSuccNodeNumbers(BasicBlockInContext<IExplodedBasicBlock> node)

Specified by:

getSuccNodeNumbers in interface NumberedEdgeManager<BasicBlockInContext<IExplodedBasicBlock>>

Returns:

the numbers identifying the immediate successors of node

getCFG

public ControlFlowGraph<SSAInstruction,IExplodedBasicBlock> getCFG(BasicBlockInContext<IExplodedBasicBlock> node)

getICFG

public ExplodedInterproceduralCFG getICFG()

toString

public String toString()

Overrides:

toString in class Object