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
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
addEdge(Object src, Object dst)
void
addNode(Object n)
add a node to this graphbyte
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 ofimmediate predecessor
nodes of nIntSet
getPredNodeNumbers(Object node)
Iterator<T>
getPredNodes(T N)
Return anIterator
over the immediate predecessor nodes of n This method never returnsnull
.Graph<? extends 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 ofimmediate successor
nodes of this Node in the GraphIntSet
getSuccNodeNumbers(T node)
Iterator<T>
getSuccNodes(T N)
Return an Iterator over the immediate successor nodes of nboolean
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 graphvoid
removeNodeAndEdges(Object N)
remove a node and all its incident edgesvoid
removeOutgoingEdges(T node)
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 Detail
-
BackwardsSupergraph
protected BackwardsSupergraph(ISupergraph<T,P> forwardGraph)
- Parameters:
forwardGraph
- the graph to ``reverse''
-
-
Method Detail
-
make
public static <T,P> BackwardsSupergraph<T,P> make(ISupergraph<T,P> forwardGraph)
-
getProcedureGraph
public Graph<? extends P> getProcedureGraph()
TODO: for now, this is not inverted.- Specified by:
getProcedureGraph
in interfaceISupergraph<T,P>
- Returns:
- the graph of procedures (e.g. a call graph) over which this supergraph is induced.
- See Also:
ISupergraph.getProcedureGraph()
-
isCall
public boolean isCall(T n)
- Specified by:
isCall
in interfaceISupergraph<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 interfaceISupergraph<T,P>
- Parameters:
ret
- a "call" node in the supergraph- Returns:
- an Iterator of nodes that are targets of this call.
- See Also:
ISupergraph.getCalledNodes(java.lang.Object)
-
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 interfaceISupergraph<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 interfaceISupergraph<T,P>
- Parameters:
c
- a "call" node in the supergraphcallee
- 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 interfaceISupergraph<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 interfaceISupergraph<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 interfaceGraph<T>
- Throws:
UnsupportedOperationException
- if the graph implementation does not allow removal
-
getNumberOfNodes
public int getNumberOfNodes()
- Specified by:
getNumberOfNodes
in interfaceNodeManager<T>
- Returns:
- the number of nodes in this graph
-
addNode
public void addNode(Object n) throws UnsupportedOperationException
Description copied from interface:NodeManager
add a node to this graph- Specified by:
addNode
in interfaceNodeManager<T>
- Throws:
UnsupportedOperationException
-
removeNode
public void removeNode(Object n) throws UnsupportedOperationException
Description copied from interface:NodeManager
remove a node from this graph- Specified by:
removeNode
in interfaceNodeManager<T>
- Throws:
UnsupportedOperationException
-
containsNode
public boolean containsNode(T N)
- Specified by:
containsNode
in interfaceNodeManager<T>
- Returns:
- true iff the graph contains the specified node
-
getPredNodes
public Iterator<T> getPredNodes(T N)
Description copied from interface:EdgeManager
Return anIterator
over the immediate predecessor nodes of n This method never returnsnull
.- Specified by:
getPredNodes
in interfaceEdgeManager<T>
- Returns:
- an
Iterator
over the immediate predecessor nodes of this Node.
-
getPredNodeCount
public int getPredNodeCount(T N)
Description copied from interface:EdgeManager
Return the number ofimmediate predecessor
nodes of n- Specified by:
getPredNodeCount
in interfaceEdgeManager<T>
- Returns:
- the number of immediate predecessors of n.
-
getSuccNodes
public Iterator<T> getSuccNodes(T N)
Description copied from interface:EdgeManager
Return an Iterator over the immediate successor nodes of nThis method never returns
null
.- Specified by:
getSuccNodes
in interfaceEdgeManager<T>
- Returns:
- an Iterator over the immediate successor nodes of n
-
hasEdge
public boolean hasEdge(T src, T dst)
- Specified by:
hasEdge
in interfaceEdgeManager<T>
-
getSuccNodeCount
public int getSuccNodeCount(T N)
Description copied from interface:EdgeManager
Return the number ofimmediate successor
nodes of this Node in the Graph- Specified by:
getSuccNodeCount
in interfaceEdgeManager<T>
- Returns:
- the number of immediate successor Nodes of this Node in the Graph.
-
addEdge
public void addEdge(Object src, Object dst) throws UnsupportedOperationException
- Specified by:
addEdge
in interfaceEdgeManager<T>
- Throws:
UnsupportedOperationException
-
removeEdge
public void removeEdge(Object src, Object dst) throws UnsupportedOperationException
- Specified by:
removeEdge
in interfaceEdgeManager<T>
- Throws:
UnsupportedOperationException
-
removeAllIncidentEdges
public void removeAllIncidentEdges(Object node) throws UnsupportedOperationException
- Specified by:
removeAllIncidentEdges
in interfaceEdgeManager<T>
- Throws:
UnsupportedOperationException
-
getEntriesForProcedure
public T[] getEntriesForProcedure(P object)
- Specified by:
getEntriesForProcedure
in interfaceISupergraph<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 interfaceISupergraph<T,P>
- Returns:
- the blocks in the supergraph that represents exit nodes for procedure p
-
isReturn
public boolean isReturn(T n) throws UnimplementedError
- Specified by:
isReturn
in interfaceISupergraph<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 interfaceISupergraph<T,P>
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 interfaceISupergraph<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 interfaceISupergraph<T,P>
- Parameters:
src
- node in the supergraphdest
- a successor of src in the supergraph- Returns:
- one of CALL_EDGE, RETURN_EDGE, CALL_TO_RETURN_EDGE, or OTHER
-
removeIncomingEdges
public void removeIncomingEdges(Object node) throws UnsupportedOperationException
- Specified by:
removeIncomingEdges
in interfaceEdgeManager<T>
- Throws:
UnsupportedOperationException
-
removeOutgoingEdges
public void removeOutgoingEdges(T node) throws UnsupportedOperationException
- Specified by:
removeOutgoingEdges
in interfaceEdgeManager<T>
- Throws:
UnsupportedOperationException
-
getNumberOfBlocks
public int getNumberOfBlocks(P procedure)
- Specified by:
getNumberOfBlocks
in interfaceISupergraph<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 interfaceISupergraph<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 interfaceISupergraph<T,P>
- Parameters:
procedure
- an object that represents a procedurei
- 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 interfaceNumberedNodeManager<T>
-
getNode
public T getNode(int number)
- Specified by:
getNode
in interfaceNumberedNodeManager<T>
-
getMaxNumber
public int getMaxNumber()
- Specified by:
getMaxNumber
in interfaceNumberedNodeManager<T>
-
iterateNodes
public Iterator<T> iterateNodes(IntSet s) throws UnimplementedError
- Specified by:
iterateNodes
in interfaceNumberedNodeManager<T>
- Returns:
- iterator of nodes with the numbers in set s
- Throws:
UnimplementedError
-
getSuccNodeNumbers
public IntSet getSuccNodeNumbers(T node)
- Specified by:
getSuccNodeNumbers
in interfaceNumberedEdgeManager<T>
- Returns:
- the numbers identifying the immediate successors of node
-
getPredNodeNumbers
public IntSet getPredNodeNumbers(Object node) throws UnimplementedError
- Specified by:
getPredNodeNumbers
in interfaceNumberedEdgeManager<T>
- Returns:
- the numbers identifying the immediate predecessors of node
- Throws:
UnimplementedError
-
-