Class AbstractFlowGraph

java.lang.Object

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

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

com.ibm.wala.util.graph.labeled.AbstractNumberedLabeledGraph<Object, IFlowLabel>

com.ibm.wala.util.graph.labeled.SlowSparseNumberedLabeledGraph<Object, IFlowLabel>

com.ibm.wala.demandpa.flowgraph.AbstractFlowGraph

All Implemented Interfaces:

IFlowGraph, EdgeManager<Object>, Graph<Object>, LabeledEdgeManager<Object, IFlowLabel>, LabeledGraph<Object, IFlowLabel>, NumberedLabeledEdgeManager<Object, IFlowLabel>, NumberedLabeledGraph<Object, IFlowLabel>, NodeManager<Object>, NumberedEdgeManager<Object>, NumberedGraph<Object>, NumberedNodeManager<Object>, Serializable, Iterable<Object>

Direct Known Subclasses:

AbstractDemandFlowGraph

public abstract class AbstractFlowGraph
extends SlowSparseNumberedLabeledGraph<Object, IFlowLabel>
implements IFlowGraph

A graph whose edges are labeled with IFlowLabels.

Author:

Manu Sridharan

See Also:

• Serialized Form

Field Summary

Fields

Modifier and Type	Field	Description
protected final Map<PointerKey, SSAAbstractInvokeInstruction>	callDefs	Map: LocalPointerKey -> SSAInvokeInstruction.
protected final Map<PointerKey, Set<SSAAbstractInvokeInstruction>>	callParams	Map: LocalPointerKey -> Set<SSAInvokeInstruction>.
protected final CallGraph	cg
protected final IClassHierarchy	cha
protected final HeapModel	heapModel
protected final MemoryAccessMap	mam
protected final Map<PointerKey, CGNode>	params	Map: LocalPointerKey -> CGNode.
protected final Map<PointerKey, CGNode>	returns	Map: LocalPointerKey -> CGNode.

Constructor Summary

Constructors

Constructor	Description
AbstractFlowGraph(MemoryAccessMap mam, HeapModel heapModel, IClassHierarchy cha, CallGraph cg)

Method Summary

Modifier and Type	Method	Description
protected void	addExceptionDefConstraints(IR ir, CGNode node, List<ProgramCounter> peis, PointerKey exceptionVar, Set<IClass> catchClasses)	Generate constraints which assign exception values into an exception pointer
protected void	addNodeConstantConstraints(CGNode node, IR ir)	add constraints for reference constants assigned to vars
protected void	addNodePassthruExceptionConstraints(CGNode node, IR ir)	Add constraints to represent the flow of exceptions to the exceptional return value for this node
protected void	addNodesForInvocations(CGNode node, IR ir)	For each invocation in the method, add nodes for actual parameters and return values
static PointerKey	convertPointerKeyToHeapModel(PointerKey pk, HeapModel h)	convert a pointer key to one in the memory access map's heap model
protected Iterator<PointerKey>	getArrayReads(PointerKey arrayRef)
SSAAbstractInvokeInstruction	getInstrReturningTo(LocalPointerKey pk)	get the SSAInvokeInstruction whose return value is assigned to a pointer key.
Iterator<SSAAbstractInvokeInstruction>	getInstrsPassingParam(LocalPointerKey pk)
Iterator<PointerKey>	getReadsOfInstanceField(PointerKey pk, IField f)
Iterator<?>	getReadsOfStaticField(StaticFieldKey sfk)
Iterator<PointerKey>	getWritesToInstanceField(PointerKey pk, IField f)
Iterator<?>	getWritesToStaticField(StaticFieldKey sfk)
boolean	isParam(LocalPointerKey pk)
void	visitPreds(Object node, IFlowLabel.IFlowLabelVisitor v)	Apply a visitor to the predecessors of some node.
void	visitSuccs(Object node, IFlowLabel.IFlowLabelVisitor v)	Apply a visitor to the successors of some node.

Methods inherited from class SlowSparseNumberedLabeledGraph

copyInto, duplicate, getEdgeManager, getNodeManager

Modifier and Type	Method	Description
static <T,U> void	copyInto(LabeledGraph<T,U> g, LabeledGraph<T,U> into)
static <T,U> SlowSparseNumberedLabeledGraph<T,U>	duplicate(LabeledGraph<T,U> g)
protected NumberedLabeledEdgeManager<Object, IFlowLabel>	getEdgeManager()
protected NumberedNodeManager<Object>	getNodeManager()

Methods inherited from class AbstractNumberedLabeledGraph

addEdge, edgeString, getDefaultLabel, getEdgeLabels, getPredLabels, getPredNodeCount, getPredNodeNumbers, getPredNodes, getSuccLabels, getSuccNodeCount, getSuccNodeNumbers, getSuccNodes, hasEdge, removeEdge

Modifier and Type	Method	Description
void	addEdge(Object src, Object dst, IFlowLabel label)	adds an edge with some label
protected String	edgeString(Object from, Object to)
IFlowLabel	getDefaultLabel()	Sets the default object used as label for operations where no specific edge label is provided.
Set<? extends IFlowLabel>	getEdgeLabels(Object src, Object dst)	Returns a set of all labeled edges between node src and node dst
Iterator<? extends IFlowLabel>	getPredLabels(Object N)
int	getPredNodeCount(Object N, IFlowLabel label)	Return the number of immediate predecessor nodes of this Node in the Graph on edges with some label.
IntSet	getPredNodeNumbers(Object node, IFlowLabel label)
Iterator<Object>	getPredNodes(Object N, IFlowLabel label)	Return an Iterator over the immediate predecessor nodes of this Node in the Graph on edges with some label.
Iterator<? extends IFlowLabel>	getSuccLabels(Object N)
int	getSuccNodeCount(Object N, IFlowLabel label)	Return the number of immediate successor nodes of this Node in the Graph
IntSet	getSuccNodeNumbers(Object node, IFlowLabel label)
Iterator<? extends Object>	getSuccNodes(Object N, IFlowLabel label)	Return an Iterator over the immediate successor nodes of this Node in the Graph on edges with some label.
boolean	hasEdge(Object src, Object dst, IFlowLabel label)
void	removeEdge(Object src, Object dst, IFlowLabel label)

Methods inherited from class AbstractNumberedGraph

getMaxNumber, getNode, getNumber, getPredNodeNumbers, getSuccNodeNumbers, iterateNodes

Modifier and Type	Method	Description
int	getMaxNumber()
Object	getNode(int number)
int	getNumber(Object N)
IntSet	getPredNodeNumbers(Object node)
IntSet	getSuccNodeNumbers(Object node)
Iterator<Object>	iterateNodes(IntSet s)

Methods inherited from class AbstractGraph

addEdge, addNode, containsNode, getNumberOfNodes, getPredNodeCount, getPredNodes, getSuccNodeCount, getSuccNodes, hasEdge, iterator, nodeString, removeAllIncidentEdges, removeEdge, removeIncomingEdges, removeNode, removeNodeAndEdges, removeOutgoingEdges, stream, toString

Modifier and Type	Method	Description
void	addEdge(Object src, Object dst)
void	addNode(Object n)	add a node to this graph
boolean	containsNode(Object n)
int	getNumberOfNodes()
int	getPredNodeCount(Object n)	Return the number of immediate predecessor nodes of n
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
Iterator<Object>	getSuccNodes(Object n)	Return an Iterator over the immediate successor nodes of n
boolean	hasEdge(Object src, Object dst)
Iterator<Object>	iterator()
protected String	nodeString(Object n, boolean forEdge)
void	removeAllIncidentEdges(Object node)
void	removeEdge(Object src, Object dst)
void	removeIncomingEdges(Object node)
void	removeNode(Object n)	remove a node from this graph
void	removeNodeAndEdges(Object N)	remove a node and all its incident edges
void	removeOutgoingEdges(Object node)
Stream<Object>	stream()
String	toString()

Methods inherited from class Object

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

Methods inherited from interface IFlowGraph

addSubgraphForNode, getPossibleTargets, getPotentialCallers, hasSubgraphForNode

Modifier and Type	Method	Description
void	addSubgraphForNode(CGNode node)	add representation of flow for a node, if not already present
Set<CGNode>	getPossibleTargets(CGNode caller, CallSiteReference site, LocalPointerKey actualPk)	get the callees that should be considered at a particular call site
Set<CallerSiteContext>	getPotentialCallers(PointerKey formalPk)
boolean	hasSubgraphForNode(CGNode node)

Methods inherited from interface Iterable

forEach, spliterator

Methods inherited from interface LabeledEdgeManager

getPredNodes

Modifier and Type	Method	Description
default Iterator<Object>	getPredNodes(Object N, Predicate<IFlowLabel> pred)

Field Details

callDefs

protected final Map<PointerKey, SSAAbstractInvokeInstruction> callDefs

Map: LocalPointerKey -> SSAInvokeInstruction. If we have (x, foo()), that means that x was def'fed by the return value from the call to foo()

callParams

protected final Map<PointerKey, Set<SSAAbstractInvokeInstruction>> callParams

Map: LocalPointerKey -> Set<SSAInvokeInstruction>. If we have (x, foo()), that means x was passed as a parameter to the call to foo(). The parameter position is not represented and must be recovered.

params

protected final Map<PointerKey, CGNode> params

Map: LocalPointerKey -> CGNode. If we have (x, foo), then x is a parameter of method foo. For now, we have to re-discover the parameter position. TODO this should just be a set; we can get the CGNode from the LocalPointerKey

returns

protected final Map<PointerKey, CGNode> returns

Map: LocalPointerKey -> CGNode. If we have (x, foo), then x is a return value of method foo. Must re-discover if x is normal or exceptional return value.

mam

protected final MemoryAccessMap mam

heapModel

protected final HeapModel heapModel

cha

protected final IClassHierarchy cha

cg

protected final CallGraph cg

Constructor Details

AbstractFlowGraph

public AbstractFlowGraph(MemoryAccessMap mam,
 HeapModel heapModel,
 IClassHierarchy cha,
 CallGraph cg)

Method Details

visitSuccs

public void visitSuccs(Object node,
 IFlowLabel.IFlowLabelVisitor v)

Description copied from interface: IFlowGraph

Apply a visitor to the successors of some node.

Specified by:

visitSuccs in interface IFlowGraph

visitPreds

public void visitPreds(Object node,
 IFlowLabel.IFlowLabelVisitor v)

Description copied from interface: IFlowGraph

Apply a visitor to the predecessors of some node.

Specified by:

visitPreds in interface IFlowGraph

addNodesForInvocations

protected void addNodesForInvocations(CGNode node,
 IR ir)

For each invocation in the method, add nodes for actual parameters and return values

isParam

public boolean isParam(LocalPointerKey pk)

Specified by:

isParam in interface IFlowGraph

Returns:

true iff pk is a formal parameter

getInstrsPassingParam

public Iterator<SSAAbstractInvokeInstruction> getInstrsPassingParam(LocalPointerKey pk)

Specified by:

getInstrsPassingParam in interface IFlowGraph

Returns:

the SSAInvokeInstructions passing some pointer as a parameter

getInstrReturningTo

public SSAAbstractInvokeInstruction getInstrReturningTo(LocalPointerKey pk)

Description copied from interface: IFlowGraph

get the SSAInvokeInstruction whose return value is assigned to a pointer key.

Specified by:

getInstrReturningTo in interface IFlowGraph

Returns:

the instruction, or null if no return value is assigned to pk

getWritesToStaticField

public Iterator<?> getWritesToStaticField(StaticFieldKey sfk)
                                   throws IllegalArgumentException

Specified by:

getWritesToStaticField in interface IFlowGraph

Parameters:

sfk - the static field

Returns:

all the variables whose values are written to sfk

Throws:

IllegalArgumentException - if sfk == null

getReadsOfStaticField

public Iterator<?> getReadsOfStaticField(StaticFieldKey sfk)
                                  throws IllegalArgumentException

Specified by:

getReadsOfStaticField in interface IFlowGraph

Parameters:

sfk - the static field

Returns:

all the variables that get the value of sfk

Throws:

IllegalArgumentException - if sfk == null

getWritesToInstanceField

public Iterator<PointerKey> getWritesToInstanceField(PointerKey pk,
 IField f)

Specified by:

getWritesToInstanceField in interface IFlowGraph

convertPointerKeyToHeapModel

public static PointerKey convertPointerKeyToHeapModel(PointerKey pk,
 HeapModel h)

convert a pointer key to one in the memory access map's heap model

TODO move this somewhere more appropriate

Throws:

UnsupportedOperationException - if it doesn't know how to handle a PointerKey

getReadsOfInstanceField

public Iterator<PointerKey> getReadsOfInstanceField(PointerKey pk,
 IField f)

Specified by:

getReadsOfInstanceField in interface IFlowGraph

getArrayReads

protected Iterator<PointerKey> getArrayReads(PointerKey arrayRef)

addNodePassthruExceptionConstraints

protected void addNodePassthruExceptionConstraints(CGNode node,
 IR ir)

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

addExceptionDefConstraints

protected void addExceptionDefConstraints(IR ir,
 CGNode node,
 List<ProgramCounter> peis,
 PointerKey exceptionVar,
 Set<IClass> catchClasses)

Generate constraints which assign exception values into an exception pointer

Parameters:

node - governing node

peis - list of PEI instructions

exceptionVar - PointerKey representing a pointer to an exception value

catchClasses - the types "caught" by the exceptionVar

addNodeConstantConstraints

protected void addNodeConstantConstraints(CGNode node,
 IR ir)

add constraints for reference constants assigned to vars