Class PDG<T extends InstanceKey>
java.lang.Object
com.ibm.wala.ipa.slicer.PDG<T>
- All Implemented Interfaces:
EdgeManager<Statement>
,Graph<Statement>
,LabeledEdgeManager<Statement,
,Dependency> NumberedLabeledEdgeManager<Statement,
,Dependency> NumberedLabeledGraph<Statement,
,Dependency> NodeManager<Statement>
,NumberedEdgeManager<Statement>
,NumberedGraph<Statement>
,NumberedNodeManager<Statement>
,Iterable<Statement>
public class PDG<T extends InstanceKey>
extends Object
implements NumberedLabeledGraph<Statement,Dependency>
Program dependence graph for a single call graph node
-
Constructor Summary
ConstructorDescriptionPDG
(CGNode node, PointerAnalysis<T> pa, Map<CGNode, OrdinalSet<PointerKey>> mod, Map<CGNode, OrdinalSet<PointerKey>> ref, Slicer.DataDependenceOptions dOptions, Slicer.ControlDependenceOptions cOptions, HeapExclusions exclusions, CallGraph cg, ModRef<T> modRef) PDG
(CGNode node, PointerAnalysis<T> pa, Map<CGNode, OrdinalSet<PointerKey>> mod, Map<CGNode, OrdinalSet<PointerKey>> ref, Slicer.DataDependenceOptions dOptions, Slicer.ControlDependenceOptions cOptions, HeapExclusions exclusions, CallGraph cg, ModRef<T> modRef, boolean ignoreAllocHeapDefs) -
Method Summary
Modifier and TypeMethodDescriptionvoid
void
addEdge
(Statement src, Statement dst, Dependency label) adds an edge with some labelvoid
add a node to this graphstatic Map
<SSAInstruction, Integer> boolean
boolean
return the set of all PARAM_CALLER and HEAP_PARAM_CALLER statements associated with a given callreturn the set of all NORMAL_RETURN_CALLER and HEAP_RETURN_CALLER statements associated with a given call.return the set of all PARAM_CALLER, HEAP_PARAM_CALLER, and NORMAL statements (i.e., the actual call statement) associated with a given callSets the default object used as label for operations where no specific edge label is provided.Set
<? extends Dependency> getEdgeLabels
(Statement src, Statement dst) Returns a set of all labeled edges between node src and node dstint
getNode
(int number) int
int
Iterator
<? extends Dependency> int
Return the number ofimmediate predecessor
nodes of nint
getPredNodeCount
(Statement N, Dependency label) Return the number ofimmediate predecessor
nodes of this Node in the Graph on edges with some label.getPredNodeNumbers
(Statement node) getPredNodeNumbers
(Statement node, Dependency label) Return anIterator
over the immediate predecessor nodes of ngetPredNodes
(Statement N, Dependency label) Return an Iterator over the immediate predecessor nodes of this Node in the Graph on edges with some label.Iterator
<? extends Dependency> int
Return the number ofimmediate successor
nodes of this Node in the Graphint
getSuccNodeCount
(Statement N, Dependency label) Return the number ofimmediate successor
nodes of this Node in the GraphgetSuccNodeNumbers
(Statement node) getSuccNodeNumbers
(Statement node, Dependency label) Return an Iterator over the immediate successor nodes of ngetSuccNodes
(Statement N, Dependency label) Return an Iterator over the immediate successor nodes of this Node in the Graph on edges with some label.boolean
boolean
hasEdge
(Statement src, Statement dst, Dependency label) int
hashCode()
iterator()
void
void
removeEdge
(Statement src, Statement dst) void
removeEdge
(Statement src, Statement dst, Dependency label) void
removeIncomingEdges
(Statement node) void
remove a node from this graphvoid
remove a node and all its incident edgesvoid
removeOutgoingEdges
(Statement node) static Statement
ssaInstruction2Statement
(CGNode node, SSAInstruction s, Map<SSAInstruction, Integer> instructionIndices, IR ir) stream()
toString()
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.lang.Iterable
forEach, spliterator
Methods inherited from interface com.ibm.wala.util.graph.labeled.LabeledEdgeManager
getPredNodes
-
Constructor Details
-
PDG
public PDG(CGNode node, PointerAnalysis<T> pa, Map<CGNode, OrdinalSet<PointerKey>> mod, Map<CGNode, OrdinalSet<PointerKey>> ref, Slicer.DataDependenceOptions dOptions, Slicer.ControlDependenceOptions cOptions, HeapExclusions exclusions, CallGraph cg, ModRef<T> modRef) - Parameters:
mod
- the set of heap locations which may be written (transitively) by this node. These are logically return values in the SDG.ref
- the set of heap locations which may be read (transitively) by this node. These are logically parameters in the SDG.- Throws:
IllegalArgumentException
- if node is null
-
PDG
public PDG(CGNode node, PointerAnalysis<T> pa, Map<CGNode, OrdinalSet<PointerKey>> mod, Map<CGNode, OrdinalSet<PointerKey>> ref, Slicer.DataDependenceOptions dOptions, Slicer.ControlDependenceOptions cOptions, HeapExclusions exclusions, CallGraph cg, ModRef<T> modRef, boolean ignoreAllocHeapDefs) - Parameters:
mod
- the set of heap locations which may be written (transitively) by this node. These are logically return values in the SDG.ref
- the set of heap locations which may be read (transitively) by this node. These are logically parameters in the SDG.- Throws:
IllegalArgumentException
- if node is null
-
-
Method Details
-
getCallerParamStatements
public Set<Statement> getCallerParamStatements(SSAAbstractInvokeInstruction call) throws IllegalArgumentException return the set of all PARAM_CALLER and HEAP_PARAM_CALLER statements associated with a given call- Throws:
IllegalArgumentException
-
getCallStatements
public Set<Statement> getCallStatements(SSAAbstractInvokeInstruction call) throws IllegalArgumentException return the set of all PARAM_CALLER, HEAP_PARAM_CALLER, and NORMAL statements (i.e., the actual call statement) associated with a given call- Throws:
IllegalArgumentException
-
getCallerReturnStatements
public Set<Statement> getCallerReturnStatements(SSAAbstractInvokeInstruction call) throws IllegalArgumentException return the set of all NORMAL_RETURN_CALLER and HEAP_RETURN_CALLER statements associated with a given call.- Throws:
IllegalArgumentException
-
ssaInstruction2Statement
public static Statement ssaInstruction2Statement(CGNode node, SSAInstruction s, Map<SSAInstruction, Integer> instructionIndices, IR ir) -
computeInstructionIndices
- Returns:
- for each SSAInstruction, its instruction index in the ir instruction array
-
toString
-
getParamCalleeStatements
-
getReturnStatements
-
getCallGraphNode
-
equals
-
hashCode
-
getPredNodeCount
Description copied from interface:EdgeManager
Return the number ofimmediate predecessor
nodes of n- Specified by:
getPredNodeCount
in interfaceEdgeManager<T extends InstanceKey>
- Returns:
- the number of immediate predecessors of n.
- Throws:
UnimplementedError
-
getPredNodes
Description copied from interface:EdgeManager
Return anIterator
over the immediate predecessor nodes of nThis method never returns
null
.- Specified by:
getPredNodes
in interfaceEdgeManager<T extends InstanceKey>
- Returns:
- an
Iterator
over the immediate predecessor nodes of this Node.
-
getSuccNodeCount
Description copied from interface:EdgeManager
Return the number ofimmediate successor
nodes of this Node in the Graph- Specified by:
getSuccNodeCount
in interfaceEdgeManager<T extends InstanceKey>
- Returns:
- the number of immediate successor Nodes of this Node in the Graph.
- Throws:
UnimplementedError
-
getSuccNodes
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 extends InstanceKey>
- Returns:
- an Iterator over the immediate successor nodes of n
-
hasEdge
- Specified by:
hasEdge
in interfaceEdgeManager<T extends InstanceKey>
- Throws:
UnimplementedError
-
removeNodeAndEdges
Description copied from interface:Graph
remove a node and all its incident edges- Specified by:
removeNodeAndEdges
in interfaceGraph<T extends InstanceKey>
- Throws:
UnsupportedOperationException
- if the graph implementation does not allow removal
-
addNode
Description copied from interface:NodeManager
add a node to this graph- Specified by:
addNode
in interfaceNodeManager<T extends InstanceKey>
-
containsNode
- Specified by:
containsNode
in interfaceNodeManager<T extends InstanceKey>
- Returns:
- true iff the graph contains the specified node
-
getNumberOfNodes
public int getNumberOfNodes()- Specified by:
getNumberOfNodes
in interfaceNodeManager<T extends InstanceKey>
- Returns:
- the number of nodes in this graph
-
iterator
- Specified by:
iterator
in interfaceIterable<T extends InstanceKey>
- Specified by:
iterator
in interfaceNodeManager<T extends InstanceKey>
- Returns:
- an
Iterator
of the nodes in this graph
-
stream
- Specified by:
stream
in interfaceNodeManager<T extends InstanceKey>
- Returns:
- a
Stream
of the nodes in this graph
-
removeNode
Description copied from interface:NodeManager
remove a node from this graph- Specified by:
removeNode
in interfaceNodeManager<T extends InstanceKey>
-
addEdge
- Specified by:
addEdge
in interfaceEdgeManager<T extends InstanceKey>
-
removeAllIncidentEdges
- Specified by:
removeAllIncidentEdges
in interfaceEdgeManager<T extends InstanceKey>
- Throws:
UnsupportedOperationException
-
removeEdge
- Specified by:
removeEdge
in interfaceEdgeManager<T extends InstanceKey>
- Throws:
UnsupportedOperationException
-
removeIncomingEdges
- Specified by:
removeIncomingEdges
in interfaceEdgeManager<T extends InstanceKey>
- Throws:
UnsupportedOperationException
-
removeOutgoingEdges
- Specified by:
removeOutgoingEdges
in interfaceEdgeManager<T extends InstanceKey>
- Throws:
UnsupportedOperationException
-
getMaxNumber
public int getMaxNumber()- Specified by:
getMaxNumber
in interfaceNumberedNodeManager<T extends InstanceKey>
-
getNode
- Specified by:
getNode
in interfaceNumberedNodeManager<T extends InstanceKey>
-
getNumber
- Specified by:
getNumber
in interfaceNumberedNodeManager<T extends InstanceKey>
-
iterateNodes
- Specified by:
iterateNodes
in interfaceNumberedNodeManager<T extends InstanceKey>
- Returns:
- iterator of nodes with the numbers in set s
-
getPredNodeNumbers
- Specified by:
getPredNodeNumbers
in interfaceNumberedEdgeManager<T extends InstanceKey>
- Returns:
- the numbers identifying the immediate predecessors of node
-
getSuccNodeNumbers
- Specified by:
getSuccNodeNumbers
in interfaceNumberedEdgeManager<T extends InstanceKey>
- Returns:
- the numbers identifying the immediate successors of node
-
getPredNodeNumbers
- Specified by:
getPredNodeNumbers
in interfaceNumberedLabeledEdgeManager<Statement,
Dependency> - Throws:
IllegalArgumentException
-
getSuccNodeNumbers
- Specified by:
getSuccNodeNumbers
in interfaceNumberedLabeledEdgeManager<Statement,
Dependency> - Throws:
IllegalArgumentException
-
getDefaultLabel
Description copied from interface:LabeledEdgeManager
Sets the default object used as label for operations where no specific edge label is provided. This is due to compatibility with the EdgeManager interface- Specified by:
getDefaultLabel
in interfaceLabeledEdgeManager<Statement,
Dependency>
-
getPredNodes
Description copied from interface:LabeledEdgeManager
Return an Iterator over the immediate predecessor nodes of this Node in the Graph on edges with some label.This method never returns
null
.- Specified by:
getPredNodes
in interfaceLabeledEdgeManager<Statement,
Dependency> - Returns:
- an Iterator over the immediate predecessor nodes of this Node.
-
getPredLabels
- Specified by:
getPredLabels
in interfaceLabeledEdgeManager<Statement,
Dependency> - Returns:
- the labels on edges whose destination is N
-
getPredNodeCount
Description copied from interface:LabeledEdgeManager
Return the number ofimmediate predecessor
nodes of this Node in the Graph on edges with some label.- Specified by:
getPredNodeCount
in interfaceLabeledEdgeManager<Statement,
Dependency> - Returns:
- the number of immediate predecessor Nodes of this Node in the Graph.
-
getSuccNodes
Description copied from interface:LabeledEdgeManager
Return an Iterator over the immediate successor nodes of this Node in the Graph on edges with some label.This method never returns
null
.- Specified by:
getSuccNodes
in interfaceLabeledEdgeManager<Statement,
Dependency> - Returns:
- an Iterator over the immediate successor Nodes of this Node.
-
getSuccLabels
- Specified by:
getSuccLabels
in interfaceLabeledEdgeManager<Statement,
Dependency> - Returns:
- the labels on edges whose source is N
-
getSuccNodeCount
Description copied from interface:LabeledEdgeManager
Return the number ofimmediate successor
nodes of this Node in the Graph- Specified by:
getSuccNodeCount
in interfaceLabeledEdgeManager<Statement,
Dependency> - Returns:
- the number of immediate successor Nodes of this Node in the Graph.
-
addEdge
Description copied from interface:LabeledEdgeManager
adds an edge with some label- Specified by:
addEdge
in interfaceLabeledEdgeManager<Statement,
Dependency>
-
removeEdge
public void removeEdge(Statement src, Statement dst, Dependency label) throws UnsupportedOperationException - Specified by:
removeEdge
in interfaceLabeledEdgeManager<Statement,
Dependency> - Throws:
UnsupportedOperationException
-
hasEdge
- Specified by:
hasEdge
in interfaceLabeledEdgeManager<Statement,
Dependency>
-
getEdgeLabels
Description copied from interface:LabeledEdgeManager
Returns a set of all labeled edges between node src and node dst- Specified by:
getEdgeLabels
in interfaceLabeledEdgeManager<Statement,
Dependency> - Parameters:
src
- source node of the edgedst
- target node of the edge- Returns:
- Set of edge labels
-