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>, 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

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<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 Type	Method	Description
void	addEdge(Statement src, Statement dst)
void	addEdge(Statement src, Statement dst, Dependency label)	adds an edge with some label
void	addNode(Statement n)	add a node to this graph
static 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 call
Set<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 call
Dependency	getDefaultLabel()	Sets 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 dst
int	getMaxNumber()
Statement	getNode(int number)
int	getNumber(Statement N)
int	getNumberOfNodes()
Statement[]	getParamCalleeStatements()
Iterator<? extends Dependency>	getPredLabels(Statement N)
int	getPredNodeCount(Statement N)	Return the number of immediate predecessor nodes of n
int	getPredNodeCount(Statement N, Dependency label)	Return the number of immediate predecessor nodes of this Node in the Graph on edges with some label.
IntSet	getPredNodeNumbers(Statement node)
IntSet	getPredNodeNumbers(Statement node, Dependency label)
Iterator<Statement>	getPredNodes(Statement N)	Return an Iterator over the immediate predecessor nodes of n
Iterator<Statement>	getPredNodes(Statement N, Dependency label)	Return an Iterator over the immediate predecessor nodes of this Node in the Graph on edges with some label.
Statement[]	getReturnStatements()
Iterator<? extends Dependency>	getSuccLabels(Statement N)
int	getSuccNodeCount(Statement N)	Return the number of immediate successor nodes of this Node in the Graph
int	getSuccNodeCount(Statement N, Dependency label)	Return the number of immediate successor nodes of this Node in the Graph
IntSet	getSuccNodeNumbers(Statement node)
IntSet	getSuccNodeNumbers(Statement node, Dependency label)
Iterator<Statement>	getSuccNodes(Statement N)	Return an Iterator over the immediate successor nodes of n
Iterator<? extends Statement>	getSuccNodes(Statement N, Dependency label)	Return an Iterator over the immediate successor nodes of this Node in the Graph on edges with some label.
boolean	hasEdge(Statement src, Statement dst)
boolean	hasEdge(Statement src, Statement dst, Dependency label)
int	hashCode()
Iterator<Statement>	iterateNodes(IntSet s)
Iterator<Statement>	iterator()
void	removeAllIncidentEdges(Statement node)
void	removeEdge(Statement src, Statement dst)
void	removeEdge(Statement src, Statement dst, Dependency label)
void	removeIncomingEdges(Statement node)
void	removeNode(Statement n)	remove a node from this graph
void	removeNodeAndEdges(Statement N)	remove a node and all its incident edges
void	removeOutgoingEdges(Statement node)
static Statement	ssaInstruction2Statement(CGNode node, SSAInstruction s, Map<SSAInstruction,Integer> instructionIndices, IR ir)
Stream<Statement>	stream()
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

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

public static Map<SSAInstruction,Integer> computeInstructionIndices(IR ir)

Returns:

for each SSAInstruction, its instruction index in the ir instruction array

toString

public String toString()

Overrides:

toString in class Object

getParamCalleeStatements

public Statement[] getParamCalleeStatements()

getReturnStatements

public Statement[] getReturnStatements()

getCallGraphNode

public CGNode getCallGraphNode()

equals

public boolean equals(Object obj)

Overrides:

equals in class Object

hashCode

public int hashCode()

Overrides:

hashCode in class Object

getPredNodeCount

public int getPredNodeCount(Statement N)
                     throws UnimplementedError

Description copied from interface: EdgeManager

Return the number of immediate predecessor nodes of n

Specified by:

getPredNodeCount in interface EdgeManager<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 an Iterator over the immediate predecessor nodes of n

This method never returns null.

Specified by:

getPredNodes in interface EdgeManager<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 of immediate successor nodes of this Node in the Graph

Specified by:

getSuccNodeCount in interface EdgeManager<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 n

This method never returns null.

Specified by:

getSuccNodes in interface EdgeManager<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 interface EdgeManager<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 interface Graph<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 interface NodeManager<T extends InstanceKey>

containsNode

public boolean containsNode(Statement N)

Specified by:

containsNode in interface NodeManager<T extends InstanceKey>

Returns:

true iff the graph contains the specified node

getNumberOfNodes

public int getNumberOfNodes()

Specified by:

getNumberOfNodes in interface NodeManager<T extends InstanceKey>

Returns:

the number of nodes in this graph

iterator

public Iterator<Statement> iterator()

Specified by:

iterator in interface Iterable<T extends InstanceKey>

Specified by:

iterator in interface NodeManager<T extends InstanceKey>

Returns:

an Iterator of the nodes in this graph

stream

public Stream<Statement> stream()

Specified by:

stream in interface NodeManager<T extends InstanceKey>

Returns:

a Stream 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 interface NodeManager<T extends InstanceKey>

addEdge

public void addEdge(Statement src,
 Statement dst)

Specified by:

addEdge in interface EdgeManager<T extends InstanceKey>

removeAllIncidentEdges

public void removeAllIncidentEdges(Statement node)
                            throws UnsupportedOperationException

Specified by:

removeAllIncidentEdges in interface EdgeManager<T extends InstanceKey>

Throws:

UnsupportedOperationException

removeEdge

public void removeEdge(Statement src,
 Statement dst)
                throws UnsupportedOperationException

Specified by:

removeEdge in interface EdgeManager<T extends InstanceKey>

Throws:

UnsupportedOperationException

removeIncomingEdges

public void removeIncomingEdges(Statement node)
                         throws UnsupportedOperationException

Specified by:

removeIncomingEdges in interface EdgeManager<T extends InstanceKey>

Throws:

UnsupportedOperationException

removeOutgoingEdges

public void removeOutgoingEdges(Statement node)
                         throws UnsupportedOperationException

Specified by:

removeOutgoingEdges in interface EdgeManager<T extends InstanceKey>

Throws:

UnsupportedOperationException

getMaxNumber

public int getMaxNumber()

Specified by:

getMaxNumber in interface NumberedNodeManager<T extends InstanceKey>

getNode

public Statement getNode(int number)

Specified by:

getNode in interface NumberedNodeManager<T extends InstanceKey>

getNumber

public int getNumber(Statement N)

Specified by:

getNumber in interface NumberedNodeManager<T extends InstanceKey>

iterateNodes

public Iterator<Statement> iterateNodes(IntSet s)

Specified by:

iterateNodes in interface NumberedNodeManager<T extends InstanceKey>

Returns:

iterator of nodes with the numbers in set s

getPredNodeNumbers

public IntSet getPredNodeNumbers(Statement node)

Specified by:

getPredNodeNumbers in interface NumberedEdgeManager<T extends InstanceKey>

Returns:

the numbers identifying the immediate predecessors of node

getSuccNodeNumbers

public IntSet getSuccNodeNumbers(Statement node)

Specified by:

getSuccNodeNumbers in interface NumberedEdgeManager<T extends InstanceKey>

Returns:

the numbers identifying the immediate successors of node

getPredNodeNumbers

public IntSet getPredNodeNumbers(Statement node,
 Dependency label)
                          throws IllegalArgumentException

Specified by:

getPredNodeNumbers in interface NumberedLabeledEdgeManager<Statement,Dependency>

Throws:

IllegalArgumentException

getSuccNodeNumbers

public IntSet getSuccNodeNumbers(Statement node,
 Dependency label)
                          throws IllegalArgumentException

Specified by:

getSuccNodeNumbers in interface NumberedLabeledEdgeManager<Statement,Dependency>

Throws:

IllegalArgumentException

getDefaultLabel

public Dependency 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 interface LabeledEdgeManager<Statement,Dependency>

getPredNodes

public Iterator<Statement> getPredNodes(Statement N,
 Dependency label)

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 interface LabeledEdgeManager<Statement,Dependency>

Returns:

an Iterator over the immediate predecessor nodes of this Node.

getPredLabels

public Iterator<? extends Dependency> getPredLabels(Statement N)

Specified by:

getPredLabels in interface LabeledEdgeManager<Statement,Dependency>

Returns:

the labels on edges whose destination is N

getPredNodeCount

public int getPredNodeCount(Statement N,
 Dependency label)

Description copied from interface: LabeledEdgeManager

Return the number of immediate predecessor nodes of this Node in the Graph on edges with some label.

Specified by:

getPredNodeCount in interface LabeledEdgeManager<Statement,Dependency>

Returns:

the number of immediate predecessor Nodes of this Node in the Graph.

getSuccNodes

public Iterator<? extends Statement> getSuccNodes(Statement N,
 Dependency label)

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 interface LabeledEdgeManager<Statement,Dependency>

Returns:

an Iterator over the immediate successor Nodes of this Node.

getSuccLabels

public Iterator<? extends Dependency> getSuccLabels(Statement N)

Specified by:

getSuccLabels in interface LabeledEdgeManager<Statement,Dependency>

Returns:

the labels on edges whose source is N

getSuccNodeCount

public int getSuccNodeCount(Statement N,
 Dependency label)

Description copied from interface: LabeledEdgeManager

Return the number of immediate successor nodes of this Node in the Graph

Specified by:

getSuccNodeCount in interface LabeledEdgeManager<Statement,Dependency>

Returns:

the number of immediate successor Nodes of this Node in the Graph.

addEdge

public void addEdge(Statement src,
 Statement dst,
 Dependency label)

Description copied from interface: LabeledEdgeManager

adds an edge with some label

Specified by:

addEdge in interface LabeledEdgeManager<Statement,Dependency>

removeEdge

public void removeEdge(Statement src,
 Statement dst,
 Dependency label)
                throws UnsupportedOperationException

Specified by:

removeEdge in interface LabeledEdgeManager<Statement,Dependency>

Throws:

UnsupportedOperationException

hasEdge

public boolean hasEdge(Statement src,
 Statement dst,
 Dependency label)

Specified by:

hasEdge in interface LabeledEdgeManager<Statement,Dependency>

getEdgeLabels

public Set<? extends Dependency> getEdgeLabels(Statement src,
 Statement dst)

Description copied from interface: LabeledEdgeManager

Returns a set of all labeled edges between node src and node dst

Specified by:

getEdgeLabels in interface LabeledEdgeManager<Statement,Dependency>

Parameters:

src - source node of the edge

dst - target node of the edge

Returns:

Set of edge labels