Package com.ibm.wala.dataflow.IFDS
Interface ISupergraph<T,P>
-
- All Superinterfaces:
EdgeManager<T>
,Graph<T>
,Iterable<T>
,NodeManager<T>
,NumberedEdgeManager<T>
,NumberedGraph<T>
,NumberedNodeManager<T>
- All Known Implementing Classes:
BackwardsSupergraph
,ICFGSupergraph
public interface ISupergraph<T,P> extends NumberedGraph<T>
A supergraph as defined by Reps, Horwitz, and Sagiv POPL95In our implementation we don't require explicit entry and exit nodes. So, the first basic block in a method is implicitly the entry node, but might also be a call node too. Similarly for exit nodes. The solver is coded to deal with this appropriately.
Additionally, due to exceptional control flow, each method might have multiple exits or multiple entries. T type of node in the supergraph P type of a procedure (like a box in an RSM)
-
-
Field Summary
Fields Modifier and Type Field Description static byte
CALL_EDGE
static byte
CALL_TO_RETURN_EDGE
static byte
OTHER
static byte
RETURN_EDGE
-
Method Summary
All Methods Instance Methods Abstract Methods Modifier and Type Method Description byte
classifyEdge(T src, T dest)
Iterator<? extends T>
getCalledNodes(T call)
Iterator<? extends T>
getCallSites(T ret, P callee)
T[]
getEntriesForProcedure(P procedure)
T[]
getExitsForProcedure(P procedure)
T
getLocalBlock(P procedure, int i)
int
getLocalBlockNumber(T n)
Iterator<T>
getNormalSuccessors(T call)
int
getNumberOfBlocks(P procedure)
Graph<? extends P>
getProcedureGraph()
P
getProcOf(T n)
Iterator<? extends T>
getReturnSites(T call, P callee)
boolean
isCall(T n)
boolean
isEntry(T n)
boolean
isExit(T n)
boolean
isReturn(T n)
-
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.Graph
removeNodeAndEdges
-
Methods inherited from interface java.lang.Iterable
forEach, spliterator
-
Methods inherited from interface com.ibm.wala.util.graph.NodeManager
addNode, containsNode, getNumberOfNodes, iterator, removeNode
-
Methods inherited from interface com.ibm.wala.util.graph.NumberedEdgeManager
getPredNodeNumbers, getSuccNodeNumbers
-
Methods inherited from interface com.ibm.wala.util.graph.NumberedNodeManager
getMaxNumber, getNode, getNumber, iterateNodes
-
-
-
-
Field Detail
-
CALL_EDGE
static final byte CALL_EDGE
- See Also:
- Constant Field Values
-
RETURN_EDGE
static final byte RETURN_EDGE
- See Also:
- Constant Field Values
-
CALL_TO_RETURN_EDGE
static final byte CALL_TO_RETURN_EDGE
- See Also:
- Constant Field Values
-
OTHER
static final byte OTHER
- See Also:
- Constant Field Values
-
-
Method Detail
-
getProcedureGraph
Graph<? extends P> getProcedureGraph()
- Returns:
- the graph of procedures (e.g. a call graph) over which this supergraph is induced.
-
isCall
boolean isCall(T n)
- Parameters:
n
- a node in this supergraph- Returns:
- true iff this node includes a call.
-
getCalledNodes
Iterator<? extends T> getCalledNodes(T call)
- Parameters:
call
- a "call" node in the supergraph- Returns:
- an Iterator of nodes that are targets of this call.
-
getNormalSuccessors
Iterator<T> getNormalSuccessors(T call)
- 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.
-
getReturnSites
Iterator<? extends T> getReturnSites(T call, P callee)
- Parameters:
call
- 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.
-
getCallSites
Iterator<? extends T> getCallSites(T ret, P callee)
- Parameters:
r
- a "return" 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 call nodes. There may be many.
-
isExit
boolean isExit(T n)
- Parameters:
n
- a node in the supergraph- Returns:
- true iff this node is an exit node
-
getProcOf
P getProcOf(T n)
- Parameters:
n
- a node in the supergraph- Returns:
- an object which represents the procedure which contains n
-
getEntriesForProcedure
T[] getEntriesForProcedure(P procedure)
- Returns:
- the blocks in the supergraph that represents entry nodes for procedure p
-
getExitsForProcedure
T[] getExitsForProcedure(P procedure)
- Returns:
- the blocks in the supergraph that represents exit nodes for procedure p
-
getNumberOfBlocks
int getNumberOfBlocks(P procedure)
- Parameters:
procedure
- an object that represents a procedure- Returns:
- the number of blocks from this procedure in this supergraph
-
getLocalBlockNumber
int getLocalBlockNumber(T n)
- Parameters:
n
- a node in the supergraph- Returns:
- the "logical" basic block number of n in its procedure
-
getLocalBlock
T getLocalBlock(P procedure, int i)
- 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
-
isReturn
boolean isReturn(T n)
- Parameters:
n
- a node in this supergraph- Returns:
- true iff this node is a return site.
-
isEntry
boolean isEntry(T n)
- Returns:
- true iff this node is an entry node s_p for a procedure
-
-