Package com.ibm.wala.ipa.slicer
Class PDG<T extends InstanceKey>
- java.lang.Object
-
- com.ibm.wala.ipa.slicer.PDG<T>
-
- All Implemented Interfaces:
EdgeManager<Statement>
,Graph<Statement>
,NodeManager<Statement>
,NumberedEdgeManager<Statement>
,NumberedGraph<Statement>
,NumberedNodeManager<Statement>
,Iterable<Statement>
public class PDG<T extends InstanceKey> extends Object implements NumberedGraph<Statement>
Program dependence graph for a single call graph node
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
PDG.Dependency
BEGIN Custom change: control deps
-
Constructor Summary
Constructors Constructor Description 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 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 modRef, boolean ignoreAllocHeapDefs)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
addEdge(Statement src, Statement dst)
void
addNode(Statement n)
add a node to this graphstatic Map<SSAInstruction,Integer>
computeInstructionIndices(IR ir)
boolean
containsNode(Statement N)
boolean
equals(Object obj)
Set<Statement>
getCallerParamStatements(SSAAbstractInvokeInstruction call)
return the set of all PARAM_CALLER and HEAP_PARAM_CALLER statements associated with a given callSet<Statement>
getCallerReturnStatements(SSAAbstractInvokeInstruction call)
return the set of all NORMAL_RETURN_CALLER and HEAP_RETURN_CALLER statements associated with a given call.CGNode
getCallGraphNode()
Set<Statement>
getCallStatements(SSAAbstractInvokeInstruction call)
return the set of all PARAM_CALLER, HEAP_PARAM_CALLER, and NORMAL statements (i.e., the actual call statement) associated with a given callint
getMaxNumber()
Statement
getNode(int number)
int
getNumber(Statement N)
int
getNumberOfNodes()
Statement[]
getParamCalleeStatements()
int
getPredNodeCount(Statement N)
Return the number ofimmediate predecessor
nodes of nIntSet
getPredNodeNumbers(Statement node)
Iterator<Statement>
getPredNodes(Statement N)
Return anIterator
over the immediate predecessor nodes of n This method never returnsnull
.Statement[]
getReturnStatements()
int
getSuccNodeCount(Statement N)
Return the number ofimmediate successor
nodes of this Node in the GraphIntSet
getSuccNodeNumbers(Statement node)
Iterator<Statement>
getSuccNodes(Statement N)
Return an Iterator over the immediate successor nodes of nboolean
hasEdge(Statement src, Statement dst)
int
hashCode()
boolean
isControlDependend(Statement from, Statement to)
BEGIN Custom change: control depsIterator<Statement>
iterateNodes(IntSet s)
Iterator<Statement>
iterator()
void
removeAllIncidentEdges(Statement node)
void
removeEdge(Statement src, Statement dst)
void
removeIncomingEdges(Statement node)
void
removeNode(Statement n)
remove a node from this graphvoid
removeNodeAndEdges(Statement N)
remove a node and all its incident edgesvoid
removeOutgoingEdges(Statement node)
static Statement
ssaInstruction2Statement(CGNode node, SSAInstruction s, Map<SSAInstruction,Integer> instructionIndices, IR ir)
String
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
-
-
-
-
Constructor Detail
-
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 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 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 Detail
-
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
public static Map<SSAInstruction,Integer> computeInstructionIndices(IR ir)
- Returns:
- for each SSAInstruction, its instruction index in the ir instruction array
-
getParamCalleeStatements
public Statement[] getParamCalleeStatements()
-
getReturnStatements
public Statement[] getReturnStatements()
-
getCallGraphNode
public CGNode getCallGraphNode()
-
getPredNodeCount
public int getPredNodeCount(Statement N) throws UnimplementedError
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
public Iterator<Statement> getPredNodes(Statement 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 extends InstanceKey>
- Returns:
- an
Iterator
over the immediate predecessor nodes of this Node.
-
getSuccNodeCount
public int getSuccNodeCount(Statement N) throws UnimplementedError
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
public Iterator<Statement> getSuccNodes(Statement 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 extends InstanceKey>
- Returns:
- an Iterator over the immediate successor nodes of n
-
hasEdge
public boolean hasEdge(Statement src, Statement dst) throws UnimplementedError
- Specified by:
hasEdge
in interfaceEdgeManager<T extends InstanceKey>
- Throws:
UnimplementedError
-
removeNodeAndEdges
public void removeNodeAndEdges(Statement N) throws UnsupportedOperationException
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
public void addNode(Statement n)
Description copied from interface:NodeManager
add a node to this graph- Specified by:
addNode
in interfaceNodeManager<T extends InstanceKey>
-
containsNode
public boolean containsNode(Statement N)
- 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
public Iterator<Statement> 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
-
removeNode
public void removeNode(Statement n)
Description copied from interface:NodeManager
remove a node from this graph- Specified by:
removeNode
in interfaceNodeManager<T extends InstanceKey>
-
addEdge
public void addEdge(Statement src, Statement dst)
- Specified by:
addEdge
in interfaceEdgeManager<T extends InstanceKey>
-
removeAllIncidentEdges
public void removeAllIncidentEdges(Statement node) throws UnsupportedOperationException
- Specified by:
removeAllIncidentEdges
in interfaceEdgeManager<T extends InstanceKey>
- Throws:
UnsupportedOperationException
-
removeEdge
public void removeEdge(Statement src, Statement dst) throws UnsupportedOperationException
- Specified by:
removeEdge
in interfaceEdgeManager<T extends InstanceKey>
- Throws:
UnsupportedOperationException
-
removeIncomingEdges
public void removeIncomingEdges(Statement node) throws UnsupportedOperationException
- Specified by:
removeIncomingEdges
in interfaceEdgeManager<T extends InstanceKey>
- Throws:
UnsupportedOperationException
-
removeOutgoingEdges
public void removeOutgoingEdges(Statement node) throws UnsupportedOperationException
- Specified by:
removeOutgoingEdges
in interfaceEdgeManager<T extends InstanceKey>
- Throws:
UnsupportedOperationException
-
getMaxNumber
public int getMaxNumber()
- Specified by:
getMaxNumber
in interfaceNumberedNodeManager<T extends InstanceKey>
-
getNode
public Statement getNode(int number)
- Specified by:
getNode
in interfaceNumberedNodeManager<T extends InstanceKey>
-
getNumber
public int getNumber(Statement N)
- Specified by:
getNumber
in interfaceNumberedNodeManager<T extends InstanceKey>
-
iterateNodes
public Iterator<Statement> iterateNodes(IntSet s)
- Specified by:
iterateNodes
in interfaceNumberedNodeManager<T extends InstanceKey>
- Returns:
- iterator of nodes with the numbers in set s
-
getPredNodeNumbers
public IntSet getPredNodeNumbers(Statement node)
- Specified by:
getPredNodeNumbers
in interfaceNumberedEdgeManager<T extends InstanceKey>
- Returns:
- the numbers identifying the immediate predecessors of node
-
getSuccNodeNumbers
public IntSet getSuccNodeNumbers(Statement node)
- Specified by:
getSuccNodeNumbers
in interfaceNumberedEdgeManager<T extends InstanceKey>
- Returns:
- the numbers identifying the immediate successors of node
-
-