Package com.ibm.wala.dataflow.IFDS

Class BackwardsSupergraph<T,P>

java.lang.Object

com.ibm.wala.dataflow.IFDS.BackwardsSupergraph<T,P>

All Implemented Interfaces:

ISupergraph<T,P>, EdgeManager<T>, Graph<T>, NodeManager<T>, NumberedEdgeManager<T>, NumberedGraph<T>, NumberedNodeManager<T>, Iterable<T>

public class BackwardsSupergraph<T,P>
extends Object
implements ISupergraph<T,P>

A "reversed" supergraph for backwards analysis.

In this view, a return is treated like a call, and vice-versa. All normal edges are reversed.

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	BackwardsSupergraph(ISupergraph<T,P> forwardGraph)

Method Summary

Modifier and Type	Method	Description
void	addEdge(Object src, Object dst)
void	addNode(Object n)	add a node to this graph
byte	classifyEdge(T src, T dest)
boolean	containsNode(T N)
Iterator<T>	getCalledNodes(T ret)	get the "called" (sic) nodes for a return site; i.e., the exit nodes that flow directly to this return site.
Iterator<? extends T>	getCallSites(T r, P callee)
T[]	getEntriesForProcedure(P object)
T[]	getExitsForProcedure(P object)
T	getLocalBlock(P procedure, int i)
int	getLocalBlockNumber(T n)
int	getMaxNumber()
T	getNode(int number)
Iterator<T>	getNormalSuccessors(T ret)	get the "normal" successors (sic) for a return site; i.e., the "normal" CFG predecessors that are not call nodes.
int	getNumber(T N)
int	getNumberOfBlocks(P procedure)
int	getNumberOfNodes()
int	getPredNodeCount(T N)	Return the number of immediate predecessor nodes of n
IntSet	getPredNodeNumbers(Object node)
Iterator<T>	getPredNodes(T N)	Return an Iterator over the immediate predecessor nodes of n
Graph<P>	getProcedureGraph()	TODO: for now, this is not inverted.
P	getProcOf(T n)
Iterator<? extends T>	getReturnSites(T c, P callee)
int	getSuccNodeCount(T N)	Return the number of immediate successor nodes of this Node in the Graph
IntSet	getSuccNodeNumbers(T node)
Iterator<T>	getSuccNodes(T N)	Return an Iterator over the immediate successor nodes of n
boolean	hasEdge(T src, T dst)
boolean	isCall(T n)
boolean	isEntry(T n)
boolean	isExit(T n)
boolean	isReturn(T n)
Iterator<T>	iterateNodes(IntSet s)
Iterator<T>	iterator()
static <T, P> BackwardsSupergraph<T,P>	make(ISupergraph<T,P> forwardGraph)
void	removeAllIncidentEdges(Object node)
void	removeEdge(Object src, Object dst)
void	removeIncomingEdges(Object node)
void	removeNode(Object n)	remove a node from this graph
void	removeNodeAndEdges(Object N)	remove a node and all its incident edges
void	removeOutgoingEdges(T node)
Stream<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

BackwardsSupergraph

protected BackwardsSupergraph(ISupergraph<T,P> forwardGraph)

Parameters:

forwardGraph - the graph to ``reverse''

Method Details

make

public static <T,
P> BackwardsSupergraph<T,P> make(ISupergraph<T,P> forwardGraph)

getProcedureGraph

public Graph<P> getProcedureGraph()

TODO: for now, this is not inverted.

Specified by:

getProcedureGraph in interface ISupergraph<T,P>

Returns:

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

isCall

public boolean isCall(T n)

Specified by:

isCall in interface ISupergraph<T,P>

Parameters:

n - a node in this supergraph

Returns:

true iff this node includes a call.

getCalledNodes

public Iterator<T> getCalledNodes(T ret)

get the "called" (sic) nodes for a return site; i.e., the exit nodes that flow directly to this return site.

Specified by:

getCalledNodes in interface ISupergraph<T,P>

Parameters:

ret - a "call" node in the supergraph

Returns:

an Iterator of nodes that are targets of this call.

getNormalSuccessors

public Iterator<T> getNormalSuccessors(T ret)

get the "normal" successors (sic) for a return site; i.e., the "normal" CFG predecessors that are not call nodes.

Specified by:

getNormalSuccessors in interface ISupergraph<T,P>

Parameters:

ret - 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.getCalledNodes(java.lang.Object)

getReturnSites

public Iterator<? extends T> getReturnSites(T c,
 P callee)

Specified by:

getReturnSites in interface ISupergraph<T,P>

Parameters:

c - 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.

isExit

public boolean isExit(T n)

Specified by:

isExit in interface ISupergraph<T,P>

Parameters:

n - a node in the supergraph

Returns:

true iff this node is an exit node

getProcOf

public P getProcOf(T n)

Specified by:

getProcOf in interface ISupergraph<T,P>

Parameters:

n - a node in the supergraph

Returns:

an object which represents the procedure which contains n

removeNodeAndEdges

public void removeNodeAndEdges(Object N)
                        throws UnsupportedOperationException

Description copied from interface: Graph

remove a node and all its incident edges

Specified by:

removeNodeAndEdges in interface Graph<T>

Throws:

UnsupportedOperationException - if the graph implementation does not allow removal

See Also:

• Graph.removeNodeAndEdges(java.lang.Object)

iterator

public Iterator<T> iterator()

Specified by:

iterator in interface Iterable<T>

Specified by:

iterator in interface NodeManager<T>

Returns:

an Iterator of the nodes in this graph

stream

public Stream<T> stream()

Specified by:

stream in interface NodeManager<T>

Returns:

a Stream of the nodes in this graph

getNumberOfNodes

public int getNumberOfNodes()

Specified by:

getNumberOfNodes in interface NodeManager<T>

Returns:

the number of nodes in this graph

See Also:

• NodeManager.getNumberOfNodes()

addNode

public void addNode(Object n)
             throws UnsupportedOperationException

Description copied from interface: NodeManager

add a node to this graph

Specified by:

addNode in interface NodeManager<T>

Throws:

UnsupportedOperationException

See Also:

• NodeManager.addNode(java.lang.Object)

removeNode

public void removeNode(Object n)
                throws UnsupportedOperationException

Description copied from interface: NodeManager

remove a node from this graph

Specified by:

removeNode in interface NodeManager<T>

Throws:

UnsupportedOperationException

See Also:

• NodeManager.removeNode(java.lang.Object)

containsNode

public boolean containsNode(T N)

Specified by:

containsNode in interface NodeManager<T>

Returns:

true iff the graph contains the specified node

See Also:

• NodeManager.containsNode(java.lang.Object)

getPredNodes

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

Returns:

an Iterator over the immediate predecessor nodes of this Node.

See Also:

• EdgeManager.getPredNodes(java.lang.Object)

getPredNodeCount

public int getPredNodeCount(T N)

Description copied from interface: EdgeManager

Return the number of immediate predecessor nodes of n

Specified by:

getPredNodeCount in interface EdgeManager<T>

Returns:

the number of immediate predecessors of n.

See Also:

• EdgeManager.getPredNodeCount(java.lang.Object)

getSuccNodes

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

Returns:

an Iterator over the immediate successor nodes of n

See Also:

• EdgeManager.getSuccNodes(java.lang.Object)

hasEdge

public boolean hasEdge(T src,
 T dst)

Specified by:

hasEdge in interface EdgeManager<T>

getSuccNodeCount

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

Returns:

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

See Also:

• EdgeManager.getSuccNodeCount(java.lang.Object)

addEdge

public void addEdge(Object src,
 Object dst)
             throws UnsupportedOperationException

Specified by:

addEdge in interface EdgeManager<T>

Throws:

UnsupportedOperationException

See Also:

• EdgeManager.addEdge(java.lang.Object, java.lang.Object)

removeEdge

public void removeEdge(Object src,
 Object dst)
                throws UnsupportedOperationException

Specified by:

removeEdge in interface EdgeManager<T>

Throws:

UnsupportedOperationException

removeAllIncidentEdges

public void removeAllIncidentEdges(Object node)
                            throws UnsupportedOperationException

Specified by:

removeAllIncidentEdges in interface EdgeManager<T>

Throws:

UnsupportedOperationException

See Also:

• EdgeManager.removeAllIncidentEdges(Object)

getEntriesForProcedure

public T[] getEntriesForProcedure(P object)

Specified by:

getEntriesForProcedure in interface ISupergraph<T,P>

Returns:

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

getExitsForProcedure

public T[] getExitsForProcedure(P object)

Specified by:

getExitsForProcedure in interface ISupergraph<T,P>

Returns:

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

See Also:

• ISupergraph.getEntriesForProcedure(java.lang.Object)

isReturn

public boolean isReturn(T n)
                 throws UnimplementedError

Specified by:

isReturn in interface ISupergraph<T,P>

Parameters:

n - a node in this supergraph

Returns:

true iff this node is a return site.

Throws:

UnimplementedError

getCallSites

public Iterator<? extends T> getCallSites(T r,
 P callee)

Specified by:

getCallSites in interface ISupergraph<T,P>

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.

isEntry

public boolean isEntry(T n)

Specified by:

isEntry in interface ISupergraph<T,P>

Returns:

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

classifyEdge

public byte classifyEdge(T src,
 T dest)

Specified by:

classifyEdge in interface ISupergraph<T,P>

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

toString

public String toString()

Overrides:

toString in class Object

removeIncomingEdges

public void removeIncomingEdges(Object node)
                         throws UnsupportedOperationException

Specified by:

removeIncomingEdges in interface EdgeManager<T>

Throws:

UnsupportedOperationException

removeOutgoingEdges

public void removeOutgoingEdges(T node)
                         throws UnsupportedOperationException

Specified by:

removeOutgoingEdges in interface EdgeManager<T>

Throws:

UnsupportedOperationException

getNumberOfBlocks

public int getNumberOfBlocks(P procedure)

Specified by:

getNumberOfBlocks in interface ISupergraph<T,P>

Parameters:

procedure - an object that represents a procedure

Returns:

the number of blocks from this procedure in this supergraph

getLocalBlockNumber

public int getLocalBlockNumber(T n)

Specified by:

getLocalBlockNumber in interface ISupergraph<T,P>

Parameters:

n - a node in the supergraph

Returns:

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

getLocalBlock

public T getLocalBlock(P procedure,
 int i)

Specified by:

getLocalBlock in interface ISupergraph<T,P>

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(T N)

Specified by:

getNumber in interface NumberedNodeManager<T>

getNode

public T getNode(int number)

Specified by:

getNode in interface NumberedNodeManager<T>

getMaxNumber

public int getMaxNumber()

Specified by:

getMaxNumber in interface NumberedNodeManager<T>

iterateNodes

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

Specified by:

iterateNodes in interface NumberedNodeManager<T>

Returns:

iterator of nodes with the numbers in set s

Throws:

UnimplementedError

getSuccNodeNumbers

public IntSet getSuccNodeNumbers(T node)

Specified by:

getSuccNodeNumbers in interface NumberedEdgeManager<T>

Returns:

the numbers identifying the immediate successors of node

getPredNodeNumbers

public IntSet getPredNodeNumbers(Object node)
                          throws UnimplementedError

Specified by:

getPredNodeNumbers in interface NumberedEdgeManager<T>

Returns:

the numbers identifying the immediate predecessors of node

Throws:

UnimplementedError