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
A supergraph as defined by Reps, Horwitz, and Sagiv POPL95
In 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
Modifier and TypeFieldDescriptionstatic final byte
static final byte
static final byte
static final byte
-
Method Summary
Modifier and TypeMethodDescriptionbyte
classifyEdge
(T src, T dest) getCalledNodes
(T call) getCallSites
(T ret, P callee) T[]
getEntriesForProcedure
(P procedure) T[]
getExitsForProcedure
(P procedure) getLocalBlock
(P procedure, int i) int
getNormalSuccessors
(T call) int
getNumberOfBlocks
(P procedure) getReturnSites
(T call, P callee) boolean
boolean
boolean
boolean
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, stream
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 Details
-
CALL_EDGE
static final byte CALL_EDGE- See Also:
-
RETURN_EDGE
static final byte RETURN_EDGE- See Also:
-
CALL_TO_RETURN_EDGE
static final byte CALL_TO_RETURN_EDGE- See Also:
-
OTHER
static final byte OTHER- See Also:
-
-
Method Details
-
getProcedureGraph
- Returns:
- the graph of procedures (e.g. a call graph) over which this supergraph is induced.
-
isCall
- Parameters:
n
- a node in this supergraph- Returns:
- true iff this node includes a call.
-
getCalledNodes
- Parameters:
call
- a "call" node in the supergraph- Returns:
- an Iterator of nodes that are targets of this call.
-
getNormalSuccessors
- 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
- 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
- Parameters:
ret
- 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
- Parameters:
n
- a node in the supergraph- Returns:
- true iff this node is an exit node
-
getProcOf
- Parameters:
n
- a node in the supergraph- Returns:
- an object which represents the procedure which contains n
-
getEntriesForProcedure
- Returns:
- the blocks in the supergraph that represents entry nodes for procedure p
-
getExitsForProcedure
- Returns:
- the blocks in the supergraph that represents exit nodes for procedure p
-
getNumberOfBlocks
- Parameters:
procedure
- an object that represents a procedure- Returns:
- the number of blocks from this procedure in this supergraph
-
getLocalBlockNumber
- Parameters:
n
- a node in the supergraph- Returns:
- the "logical" basic block number of n in its procedure
-
getLocalBlock
- 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
- Parameters:
n
- a node in this supergraph- Returns:
- true iff this node is a return site.
-
isEntry
- Returns:
- true iff this node is an entry node s_p for a procedure
-
classifyEdge
- 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
-