Package com.ibm.wala.demandpa.flowgraph

Class SimpleDemandPointerFlowGraph

java.lang.Object

com.ibm.wala.util.graph.AbstractGraph<T>

com.ibm.wala.util.graph.AbstractNumberedGraph<T>

com.ibm.wala.util.graph.impl.SlowSparseNumberedGraph<Object>

com.ibm.wala.demandpa.flowgraph.SimpleDemandPointerFlowGraph

All Implemented Interfaces:

EdgeManager<Object>, Graph<Object>, NodeManager<Object>, NumberedEdgeManager<Object>, NumberedGraph<Object>, NumberedNodeManager<Object>, Serializable, Iterable<Object>

public class SimpleDemandPointerFlowGraph
extends SlowSparseNumberedGraph<Object>

The nodes in this graph are PointerKeys corresponding to local variables and static fields, InstanceKeys, and FieldRefs (see below).

This graph is constructed on-demand during a traversal.

The edges represent

• flow from local -> local representing assignment (i.e. phi,pi)
• flow from instancekey -> local for news
• flow from formal -> actual parameter
• flow from return value -> local
• match edges
• local -> local edges representing loads/stores (e.g. x = y.f will have a edge x->y, labelled with f) for a getstatic x = Y.f, we have an edge from x -> Y.f.

N.B: Edges go OPPOSITE the flow of values.

Edges carry labels if they arise from loads/stores, or calls

See Also:

• Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected class	SimpleDemandPointerFlowGraph.StatementVisitor	A visitor that generates graph nodes and edges for an IR.

Constructor Summary

Constructors

Constructor	Description
SimpleDemandPointerFlowGraph(CallGraph cg, HeapModel heapModel, MemoryAccessMap fam, IClassHierarchy cha)

Method Summary

Modifier and Type	Method	Description
protected void	addBlockInstructionConstraints(CGNode node, ControlFlowGraph<SSAInstruction,ISSABasicBlock> cfg, ISSABasicBlock b, SimpleDemandPointerFlowGraph.StatementVisitor v)	Add constraints for a particular basic block.
protected void	addNodeInstructionConstraints(CGNode node, IR ir, DefUse du)	Add pointer flow constraints based on instructions in a given node
protected void	addNodePassthruExceptionConstraints(CGNode node, IR ir)	Add constraints to represent the flow of exceptions to the exceptional return value for this node
void	addSubgraphForNode(CGNode node)
protected HeapModel	getHeapModel()
int	getPredNodeCount(Object N)	Return the number of immediate predecessor nodes of n
IntSet	getPredNodeNumbers(Object node)
Iterator<Object>	getPredNodes(Object N)	Return an Iterator over the immediate predecessor nodes of n
int	getSuccNodeCount(Object N)	Return the number of immediate successor nodes of this Node in the Graph
IntSet	getSuccNodeNumbers(Object node)
Iterator<Object>	getSuccNodes(Object N)	Return an Iterator over the immediate successor nodes of n
boolean	hasEdge(PointerKey src, PointerKey dst)
protected SimpleDemandPointerFlowGraph.StatementVisitor	makeVisitor(ExplicitCallGraph.ExplicitNode node, IR ir, DefUse du)
protected void	unconditionallyAddConstraintsFromNode(CGNode node)

Methods inherited from class com.ibm.wala.util.graph.impl.SlowSparseNumberedGraph

copyInto, duplicate, getEdgeManager, getNodeManager, make

Methods inherited from class com.ibm.wala.util.graph.AbstractNumberedGraph

getMaxNumber, getNode, getNumber, iterateNodes

Methods inherited from class com.ibm.wala.util.graph.AbstractGraph

addEdge, addNode, containsNode, edgeString, getNumberOfNodes, hasEdge, iterator, nodeString, removeAllIncidentEdges, removeEdge, removeIncomingEdges, removeNode, removeNodeAndEdges, removeOutgoingEdges, stream, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface com.ibm.wala.util.graph.EdgeManager

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

Constructor Details

SimpleDemandPointerFlowGraph

public SimpleDemandPointerFlowGraph(CallGraph cg,
 HeapModel heapModel,
 MemoryAccessMap fam,
 IClassHierarchy cha)

Method Details

addSubgraphForNode

public void addSubgraphForNode(CGNode node)

getHeapModel

protected HeapModel getHeapModel()

Returns:

Returns the heapModel.

getPredNodeNumbers

public IntSet getPredNodeNumbers(Object node)
                          throws UnimplementedError

Specified by:

getPredNodeNumbers in interface NumberedEdgeManager<Object>

Overrides:

getPredNodeNumbers in class AbstractNumberedGraph<Object>

Returns:

the numbers identifying the immediate predecessors of node

Throws:

UnimplementedError

See Also:

• AbstractNumberedGraph.getPredNodeNumbers(java.lang.Object)

getSuccNodeNumbers

public IntSet getSuccNodeNumbers(Object node)
                          throws IllegalArgumentException

Specified by:

getSuccNodeNumbers in interface NumberedEdgeManager<Object>

Overrides:

getSuccNodeNumbers in class AbstractNumberedGraph<Object>

Returns:

the numbers identifying the immediate successors of node

Throws:

IllegalArgumentException

See Also:

• AbstractNumberedGraph.getSuccNodeNumbers(java.lang.Object)

getPredNodeCount

public int getPredNodeCount(Object N)
                     throws UnimplementedError

Description copied from interface: EdgeManager

Return the number of immediate predecessor nodes of n

Specified by:

getPredNodeCount in interface EdgeManager<Object>

Overrides:

getPredNodeCount in class AbstractGraph<Object>

Returns:

the number of immediate predecessors of n.

Throws:

UnimplementedError

See Also:

• AbstractGraph.getPredNodeCount(java.lang.Object)

getPredNodes

public Iterator<Object> getPredNodes(Object N)
                              throws IllegalArgumentException

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

Overrides:

getPredNodes in class AbstractGraph<Object>

Returns:

an Iterator over the immediate predecessor nodes of this Node.

Throws:

IllegalArgumentException

See Also:

• AbstractGraph.getPredNodes(java.lang.Object)

getSuccNodeCount

public int getSuccNodeCount(Object 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<Object>

Overrides:

getSuccNodeCount in class AbstractGraph<Object>

Returns:

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

Throws:

UnimplementedError

See Also:

• AbstractGraph.getSuccNodeCount(java.lang.Object)

getSuccNodes

public Iterator<Object> getSuccNodes(Object 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<Object>

Overrides:

getSuccNodes in class AbstractGraph<Object>

Returns:

an Iterator over the immediate successor nodes of n

See Also:

• AbstractGraph.getSuccNodes(java.lang.Object)

hasEdge

public boolean hasEdge(PointerKey src,
 PointerKey dst)

unconditionallyAddConstraintsFromNode

protected void unconditionallyAddConstraintsFromNode(CGNode node)

addNodePassthruExceptionConstraints

protected void addNodePassthruExceptionConstraints(CGNode node,
 IR ir)

Add constraints to represent the flow of exceptions to the exceptional return value for this node

addNodeInstructionConstraints

protected void addNodeInstructionConstraints(CGNode node,
 IR ir,
 DefUse du)

Add pointer flow constraints based on instructions in a given node

addBlockInstructionConstraints

protected void addBlockInstructionConstraints(CGNode node,
 ControlFlowGraph<SSAInstruction,ISSABasicBlock> cfg,
 ISSABasicBlock b,
 SimpleDemandPointerFlowGraph.StatementVisitor v)

Add constraints for a particular basic block.

makeVisitor

protected SimpleDemandPointerFlowGraph.StatementVisitor makeVisitor(ExplicitCallGraph.ExplicitNode node,
 IR ir,
 DefUse du)